生成数字矩阵表示的迷宫
目标是生成数字矩阵表示的迷宫,数字1表示不可通行的墙体,数字0表示可通行的道路,如下图:
11111111111111111
10100000000010001
10101111111010101
10001010001010101
11111010101010101
10000010100010101
10111110111111101
10000000100000001
10111111101111101
10001010000010001
11101010111011111
10001000001010001
10111111111010101
10001000001000101
11101011101111101
10000010000000001
11111111111111111
为了方便逻辑处理,我们不直接生成方块的墙或者方块的路,而是标记可走的路的最小单元cell的上下左右四个边的状态,这个状态是可通行或者不可通行。这里不关注墙,请直接忽略,后面通过路的最小单元的四个边的状态来生成墙。
注意,这里的cell表示道路的最小单元,它有四个状态,分别表示上下左右四条边的状态。和墙没有关系。
从某一个cell开始遍历,从当前cell的相邻的未访问的cell集合中随机选一个作为下一时间状态的cell,并将这两个cell相邻的两条边的状态置为可通行,并将每个时间状态的cell存入一个后进先出栈stack。当当前的cell周围没有未访问的cell时,从stack中出栈一个cell作为新的时间状态的cell。
初始cell入栈stack
当前cell置为初始cell
循环,终止条件:栈stack为空
将当前cell的访问状态置为已访问
如果,当前cell有相邻的未访问cell
随机选择相邻的未访问cell中的一个cell
当前cell与随机选择的cell之间的相邻的两个状态置为可通行
随机选择的cell入栈stack
当前cell置为随机选择的cell
否则
从stack中出栈一个cell作为当前cell
由于上面的cell不涉及墙体,所以需要通过cell的四个状态在其周围生成墙体,即状态为不可通行时,则应该在这个cell的不可通行状态位置填充墙体。
完整代码如下:
import random
row, col = 8, 8
i, j = 0, 0
status = [[[False for _ in range(4)] for _ in range(col)]
for _ in range(row)]
visited = [[False for _ in range(col)] for _ in range(row)]
stack = [(i, j)]
while stack:
visited[i][j] = True
choosable = []
if j > 0 and not visited[i][j-1]:
choosable.append('L')
if i > 0 and not visited[i-1][j]:
choosable.append('U')
if j < col-1 and not visited[i][j+1]:
choosable.append('R')
if i < row-1 and not visited[i+1][j]:
choosable.append('D')
if choosable:
direct = random.choice(choosable)
if direct == 'L':
status[i][j][0] = True
j -= 1
status[i][j][2] = True
elif direct == 'U':
status[i][j][1] = True
i -= 1
status[i][j][3] = True
elif direct == 'R':
status[i][j][2] = True
j += 1
status[i][j][0] = True
elif direct == 'D':
status[i][j][3] = True
i += 1
status[i][j][1] = True
stack.append((i, j))
else:
i, j = stack.pop()
maze = [[1 for _ in range(col*2+1)] for _ in range(row*2+1)]
for r in range(row):
for c in range(col):
cell = status[r][c]
maze[r*2+1][c*2+1] = 0
if cell[0]:
maze[r*2+1][c*2] = 0
if cell[1]:
maze[r*2][c*2+1] = 0
if cell[2]:
maze[r*2+1][c*2+2] = 0
if cell[3]:
maze[r*2+2][c*2+1] = 0
for r in range(row*2+1):
for c in range(col*2+1):
print(maze[r][c], end=' ')
print()
下面列举几个不同大小的数字矩阵表示的迷宫的可视化图: