地牢房间迷宫走廊生成（二），Python实现洪水法、完美迷宫

• 前言
• 1 随机房间和房门
• 2 生成走廊
• • 2.1生成迷宫
  • 2.4 使用循环改进
  • 2.3 走廊缩减
  • 2.3 走廊再简化
• 总结

  前面通过随机房间、房门，对房门寻路生成走廊。由于使用A星算法，寻到的是最短路径，这样生成的走廊过直和简单。如果需要生成弯曲的走廊（这样的走廊能增加探险的乐趣和战斗拉扯），需要做些什么呢？
  如果我们要在原基础上修改，可以随机选取几个走廊的点，将其扩大复杂化，那么有没有其他方法呢？通过在一块地图上生成一个弯曲的迷宫可以实现这个需求。在这里，无论这个地图上有无房间。

  首先考虑到数据结构的问题，使用什么样的数据表示地图数据？包括房间、墙壁、房门、走廊、空白点。在这里，我使用一个三维数组表示整个图，前两维的点是坐标，第三维一共有6个数据，前4个依次表示为左上右下是否连通，第5个表示为该点是否存在物体或被遍历，第6个表示物体的类别id，数据表示为map[rows,cols,6]，当然第三维不一定全是数字，也可以使用二维的链表。

  在地图上随机寻找一定大小的房间，如果合适则放入房间。在这里需要限制循环的次数，避免无法放置房间时无限循环下去。随机房门时，在房间最外围随机寻找一个点当做房门（当然也可以使用另一个随机数来设定房门的数量）。为了简化代码，假定从房间的左上角出发，随机产生x和y方向的偏移量，使用预定义好的四个权重对x和y加权，将x和y映射到四个边上。此外，将数据可视化，使用matplotlib将地图画到图像上，在此需要一个数组表示图像。
如下所示

import random
import numpy as np
from matplotlib import pyplot as plt

def randomRoom(M):
    height, width, d = M.shape
    min_size = 5
    max_size = 10
    room_num = 20
    count = 0
    try_count = 0
    room = []
    while count < room_num:
        if try_count > 1000:
            break
        r = random.randint(min_size, max_size)
        c = random.randint(min_size, max_size)
        left = random.randint(3, width - 4)
        top = random.randint(3, height - 4)
        f = True
        for i in range(top-1,top+r+2):
            for j in range(left-1,left+c+2):
                if i >= height-3 or j >= width-3:
                    f = False
                    break
                if M[i,j,5] == 1:
                    f = False
                    break
        if f:
            room.append([left,top,c,r])
            for i in range(top, top + r + 1):
                for j in range(left, left + c + 1):
                    if i >= height-3 or j >= width-3:
                        continue
                    M[i, j, :] = 1
            count += 1
        try_count += 1
    return room

def randomDoor(map,room_list):
    for it in room_list:
        door_x,door_y = randomWall(it)
        for i in range(it[3]+1):
            map[it[1]+i, it[0], 5] = 3
            map[it[1]+i, it[0]+it[2], 5] = 3
        for i in range(it[2]+1):
            map[it[1], it[0]+i, 5] = 3
            map[it[1]+it[3], it[0]+i, 5] = 3
        map[door_x,door_y,5] = 2

def randomWall(room):
    direction = random.randint(0,3)
    dir = [[0,1,-1,0],[1,0,0,-1],[1,0,0,room[3]],[0,1,room[2],0]]
    x_off = random.randint(1,room[2]-2)
    y_off = random.randint(1,room[3]-2)
    x = room[0] + x_off*dir[direction][0] #+ dir[direction][2]
    y = room[1] + y_off*dir[direction][1] #+ dir[direction][3]
    return y,x

def drawMap(M, image):
    rows, cols, deep = M.shape
    block = [[2,8,0,2],[0,2,2,8],[2,8,8,10],[8,10,2,8]]
    color = [0,0,230,140]
    for row in range(0, rows):
        for col in range(0, cols):
            unit = M[row, col]
            if unit[5] == 1:
                image[10 * row : 10 * row + 10, 10 * col:10 * col + 10] = 255
            else:
                image[10 * row + 2: 10 * row + 8, 10 * col + 2:10 * col + 8] = 255 - color[unit[5]]
                for i in range(4):
                    if unit[i] == 1:
                        x1 = 10 * row + block[i][0]
                        x2 = 10 * row + block[i][1]
                        y1 = 10 * col + block[i][2]
                        y2 = 10 * col + block[i][3]
                        image[x1:x2,y1:y2] = 255 - color[unit[5]]

    plt.imshow(image, interpolation='none', cmap ='gray')
    plt.show()

if __name__ == '__main__':
    rows = int(input('输入房间行数：'))
    cols = int(input('输入房间列数：'))
    map = np.zeros((rows,cols,6),np.int16)
    image = np.zeros((rows * 10, cols * 10), dtype=np.uint8)

    room = randomRoom(map)
    randomDoor(map,room.copy())
    drawMap(map,image)

这样就生成了房间和房门，画出所示图

  现在有一个地图，地图上有带有房门的房间，接下来要做的是是未定区域产生走廊。在这里使用一个新的方法：洪水法(flood fill)，随机选取一点，从这点出发将附近可到达的点填充。在迷宫中有一点不同的是前往下一个点时，需要将两点间的墙壁打通。同时，在迭代中，当发现走入死胡同时，回到上一次拐弯的地方选取另外一个方向。

  可以想到，通过递归来解决这个问题。在选取方向时，让电脑随机选取一个方向。当打通两个点间的墙壁时，显然，一个点向左必然是另一个点的向右，它们是对称的。假设用0123来表示三个方向，它们之间的关系很明显是在4的有限域内，将该点方向加上2模4就是另一点的方向。

def floodFill(M):
    h, w, d = M.shape

    def findFree():
        x = random.randint(1,h-2)
        y = random.randint(1,w-2)
        for i1 in range(x,h-1):
            for j1 in range(y,w-1):
                if M[i1,j1,5] == 0:
                    return [i1,j1]
        for i1 in range(1,h-1):
            for j1 in range(1,w-1):
                if M[i1,j1,5] == 0:
                    return [i1,j1]
        return None

    direction = [[0,-1],[-1,0],[0,1],[1,0]]

    def fill(point,dir=0):
        if point[0] < 1 or point[0] >= h-1 or point[1] < 1 or point[1] >= w-1:
            return
        if M[point[0], point[1], 4] == 1:
            return
        M[point[0], point[1], 4] = 1
        M[point[0], point[1], 5] = 4
        M[point[0], point[1], (dir+2)%4] = 1
        M[point[0]-direction[dir][0], point[1]-direction[dir][1], dir] = 1

        ind = random.randint(0,3)
        for i2 in range(4):
            index = (ind + i2) % 4
            fill([point[0]+direction[index][0],point[1]+direction[index][1]], index)


    while True:
        point = findFree()
        if point == None:
            break
        fill(point)

if __name__ == '__main__':
    rows = int(input('输入房间行数：'))
    cols = int(input('输入房间列数：'))
    map = np.zeros((rows,cols,6),np.int16)
    image = np.zeros((rows * 10, cols * 10), dtype=np.uint8)

    room = randomRoom(map)
    randomDoor(map,room.copy())
    floodFill(map)
    drawMap(map,image)

生成迷宫如下

  这样很简单地就生成了房间外的迷宫，由于洪水法的特点和所使用的数据结构，这样保证了房间是被迷宫的通道包围的，从房门打开，就进入了迷宫。

  此外，该迷宫是一个完美的迷宫。完美的迷宫是指：在迷宫任意两点间有且只有一条路径。如果不想让迷宫完美（也即有多种方法可以到达另一点，这往往是我们想要的），可以令房间产生多个房门，通过房间产生额外的路径，或者，可以在死胡同（周围三面是墙）上打洞。

上述方法固然简单，也是常常想到的方法。但是随着地图增大，进行深递归时，往往会发生爆栈。一个不是解决方法的方法是使用循环去代替递归，改进如下

def floodFill2(M):
    h,w,d = M.shape
    ls = []

    x = y = 0
    ls.append([x,y])
    dir = []
    direction = [[0,-1],[-1,0],[0,1],[1,0]]
    while ls:
        M[x, y, 4] = 1
        dir.clear()
        ind = 0
        for it in direction:
            if x+it[0] >= 0 and y+it[1] >= 0 and x+it[0] < h and y+it[1] < w:
                if M[x+it[0],y+it[1],4] == 0:
                    dir.append(ind)
            ind += 1

        if len(dir) > 0:
            ls.append([x, y])
            next = random.choice(dir)
            M[x,y,5] = 4
            M[x,y,next] = 1
            x = x+direction[next][0]
            y = y+direction[next][1]
            M[x,y,(next+2)%4] = 1
        else:
            M[x, y, 5] = 4
            x, y = ls.pop()
            
if __name__ == '__main__':
    rows = int(input('输入房间行数：'))
    cols = int(input('输入房间列数：'))
    map = np.zeros((rows,cols,6),np.int16)
    image = np.zeros((rows * 10, cols * 10), dtype=np.uint8)

    room = randomRoom(map)
    randomDoor(map,room.copy())
    floodFill2(map)
    drawMap(map,image)

这样即使地图增大，也能计算迷宫了，放下效果图

  当主要的关注点是在房间，而不是迷宫上时，往往不需要迷宫占满整个地图，这很浪费时间。

  那么需要将迷宫缩减一下，入手点是死胡同。我希望这个走廊没有那么多死胡同，不至于走到浪费大量的时间在走迷宫上。寻找死胡同也很简单，周围三面是墙该点就是死胡同。

  首先遍历搜索当前所有的死胡同点加入链表，对链表内容循环直至循环超过一定次数/剩余走廊少于一定数量/没有死胡同。这个条件可以自行设置。代码如下

def deleteCorner(M,left_floor=500):
    direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]
    try_num = 1000
    count = 0
    r, c, d = M.shape
    total = (r-1) * (c-1)
    corner = []
    for i in range(r):
        for j in range(c):
            if sum(M[i,j,:4]) == 1:
                corner.append([i,j])
    while len(corner):
        if count > try_num or len(corner) == 0 or total < left_floor:
            break
        cor = random.choice(corner)
        if sum(M[cor[0],cor[1],:4]) != 1:
            corner.remove(cor)
            continue
        is_door = False
        for it in direction:
            if M[cor[0]+it[0],cor[1]+it[1],5] == 2:
                corner.remove(cor)
                is_door = True
        if is_door:
            continue
        temp = np.where(M[cor[0], cor[1], :4] == 1)
        front = int(temp[0])
        M[cor[0], cor[1], :] = 0
        M[cor[0] + direction[front][0], cor[1] + direction[front][1], (front + 2) % 4] = 0
        total -= 1
        corner.remove(cor)
        corner.append([cor[0] + direction[front][0], cor[1] + direction[front][1]])
        count += 1
    print(count)

if __name__ == '__main__':
    rows = int(input('输入房间行数：'))
    cols = int(input('输入房间列数：'))
    map = np.zeros((rows,cols,6),np.int16)
    image = np.zeros((rows * 10, cols * 10), dtype=np.uint8)

    room = randomRoom(map)
    randomDoor(map,room.copy())
    floodFill2(map)
    deleteCorner(map)
    drawMap(map,image)

可以看到一些死胡同被删除了，迷宫也不是占满整个地图。

  上述方法可以生成一个完整的迷宫和房间了。那么当然了需求是满足不完的，尽管做了上述工作，还是觉得走廊过于复杂了，我不希望它是一条直线，也不希望它拐来拐去，该怎么办？

  在递归打通填充下一个点时，使用的是随机一个方向，那么要保持稳定，可以初始随机选定一个方向，在填充的过程中有概率拐弯，这样的小设定能保持一段直道走廊。

def floodFill3(M):
    h, w, d = M.shape
    area = 4
    area_list = []

    def findFree():
        for i1 in range(1,h-1):
            for j1 in range(1,w-1):
                if M[i1,j1,5] == 0:
                    return [i1,j1]
        return None

    def outRect(p):
         return p[0] < 1 or p[0] >= h-1 or p[1] < 1 or p[1] >= w-1

    direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]
    corner = []
    while True:
        new_point = point = findFree()
        if point == None:
            break
        dir = random.randint(0, 3)
        while True:
            point = new_point
            M[point[0], point[1], 5] = area
            M[point[0], point[1], 4] = 1

            change = random.random()
            old_dir = dir
            if change > 0.9:
                tran = int((random.randint(-1,0)+0.5)*2)
                old_dir = dir
                dir = (dir + tran) % 4

            new_point = [point[0]+direction[dir][0], point[1]+direction[dir][1]]
            f = False
            if outRect(new_point):
                f = True
            elif M[new_point[0],new_point[1],4] == 1:
                f = True
            if f:
                for i in range(4):
                    ind = (old_dir + i) % 4
                    temp = [point[0]+direction[ind][0], point[1]+direction[ind][1]]
                    if outRect(temp):
                        continue
                    elif M[temp[0],temp[1],4] == 1:
                        continue
                    else:
                        new_point = temp
                        f = False
                        dir = ind
            if old_dir != dir and not f:
                corner.append(point)
            if not f:
                M[point[0],point[1],dir] = 1
                M[new_point[0],new_point[1],(dir+2)%4] = 1
            else:
                if len(corner):
                    new_point = corner.pop()
                else:
                    break
        area_list.append(area)
        area += 1
    return area_list

if __name__ == '__main__':
    rows = int(input('输入房间行数：'))
    cols = int(input('输入房间列数：'))
    map = np.zeros((rows,cols,6),np.int16)
    image = np.zeros((rows * 10, cols * 10), dtype=np.uint8)

    room = randomRoom(map)
    randomDoor(map,room.copy())
    floodFill3(map)
    drawMap(map,image)

  需要注意的是修改后的方法产生的不是完美迷宫了，而是一块一块不连通的迷宫，某些时候需要将两个不连通的迷宫打通，这需要额外的计算。对死胡同进行消除后看看结果。

#打通区域,ls存放area的列表
def breakArea(map,ls):
    h,w,d = map.shape
    known = []
    direction = [[0,-1],[-1,0],[0,1],[1,0]]
    while len(ls) > 1:
        f = False
        for i in range(h):
            for j in range(w):
                if map[i,j,5] in ls and not map[i,j,5] in known:
                    ind = 0
                    for it in direction:
                        if map[i+it[0],j+it[1],5] in ls and map[i+it[0],j+it[1],5] != map[i,j,5]:
                            ls.remove(map[i+it[0],j+it[1],5])
                            map[i, j, ind] = 1
                            map[i+it[0], j+it[1], (ind + 2) % 4] = 1
                            map[map==map[i+it[0],j+it[1],5]] = map[i, j, 5]
                            known.append(map[i,j,5])
                            known.append(map[i+it[0],j+it[1],5])
                            f = True
                            break
                        ind += 1
                if f:
                    break
            if f:
                break

那么这种方法就能生成需求中的迷宫和房间了。

在看着自己随机生成的迷宫不断变化时一件有趣的事情，最后的最后，让我放上两种迷宫来奖赏自己。