生成数字矩阵表示的迷宫

2023-10-09 01:21| 来源: 网络整理| 查看: 265

目标是生成数字矩阵表示的迷宫，数字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

【本文地址】

生成数字矩阵表示的迷宫

生成数字矩阵表示的迷宫

今日新闻

推荐新闻