定义
- 我们讨论二维情况
- 可以通行的区域，我们叫做“路”，用1或2表示。具体说，1表示生成迷宫之前就已经存在的路，并且在迭代过程中还没有加入到迷宫体系中。2表示生成过程中加入到迷宫体系中的路。
- 不可通行的区域，我们叫做“墙”，用0或-1表示。其中0是可以被打通变成路的墙，-1是不能被打通的墙（海）
方案1：深度优先搜索
特点
- 有一条特别长的主路
- 路线很扭曲
import matplotlib.pyplot as plt
import numpy as np
# step1：生成一个网点图
length, width = 50, 50 # 定义迷宫大小
maze = np.zeros(shape=(length, width))
maze[::2, ::2] = 1
# 每次只能上下左右试探
step_set = np.array([[1, 0],
[-1, 0],
[0, 1],
[0, -1]])
def find_next_step(maze, point, step_set):
# 用递归实现深度优先搜索
step_set = np.random.permutation(step_set)
for next_step in step_set:
next_point = point + next_step * 2
x, y = next_point
if 0 <= x < length and 0 <= y < width: # 在格子内
if maze[x, y] == 1: # 如果还没打通，就打通
maze[x, y] = 2
maze[(point + next_step)[0], (point + next_step)[1]] = 2
maze, _, _ = find_next_step(maze, next_point, step_set) # 深度优先搜索
# 全部遍历后，还是找不到，就是这个叶节点没有下一步了，返回即可
return maze, point, step_set
# 定义起点
point = np.array([0, 0])
find_next_step(maze, point, step_set)
# 至于终点，道路上的每个点都可以作为终点
plt.imshow(maze)
plt.show()
解释一下思路
step1：生成一个网点格子，下面黄色是道路，紫色是墙
step2：从起点出发，进行下面的深度优先搜索：
对于当前点，递归遍历上下左右4个最近的道路，
如果道路未被加入路径，就加入路径，移动到当前点
直到无法递归为止。
step3：得到迷宫并画图
方案2：广度优先搜索
既然有深度优先搜索，就有广度优先搜索。
实现很简单，就是深度优先搜索方案改一改。
地图特点：
- 不会出现一条特别长的主路的情况
改进：分块生成迷宫
前面我们已经有了生成迷宫的方法，自然能想到分块生成迷宫，这种方法可以实现以下两种迷宫
- 有时候，我们不想让迷宫太复杂，想让某些分支路线限定在某个区域内。
- 有时候，我们不想让路径填充整个迷宫，想留下一片未开垦地。
先看要求2
我们只需要挖掉一些区域即可，例如
maze[4:9, 4:17] = -1
maze[12:39, 20:39] = -1
效果如下：
完整代码
import matplotlib.pyplot as plt
import numpy as np
# step1：生成一个网点图
length, width = 50, 50 # 定义迷宫大小
maze = np.zeros(shape=(length, width))
maze[::2, ::2] = 1
maze[4:9, 4:17] = -1
maze[12:39, 20:39] = -1
# 每次只能上下左右试探
step_set = np.array([[1, 0],
[-1, 0],
[0, 1],
[0, -1]])
def find_next_step(maze, point, step_set):
# 用递归实现深度优先搜索
step_set = np.random.permutation(step_set)
for next_step in step_set:
next_point = point + next_step * 2
x, y = next_point
if 0 <= x < length and 0 <= y < width: # 在格子内
if maze[x, y] == 1: # 如果还没打通，就打通
maze[x, y] = 2
maze[(point + next_step)[0], (point + next_step)[1]] = 2
maze, _, _ = find_next_step(maze, next_point, step_set) # 深度优先搜索
# 全部遍历后，还是找不到，就是这个叶节点没有下一步了，返回即可
return maze, point, step_set
# 定义起点
point = np.array([0, 0])
find_next_step(maze, point, step_set)
# 至于终点，道路上的每个点都可以作为终点
plt.imshow(maze)
plt.show()
看要求1
我们在挖掉的区域内，生成一个小迷宫，然后把两个迷宫连接起来
import matplotlib.pyplot as plt
import numpy as np
def find_next_step(maze, point, step_set):
# 用递归实现深度优先搜索
length, width = maze.shape
step_set = np.random.permutation(step_set)
for next_step in step_set:
next_point = point + next_step * 2
x, y = next_point
if 0 <= x < length and 0 <= y < width: # 在格子内
if maze[x, y] == 1: # 如果还没打通，就打通
maze[x, y] = 2
maze[(point + next_step)[0], (point + next_step)[1]] = 2
maze, _, _ = find_next_step(maze, next_point, step_set) # 深度优先搜索
# 全部遍历后，还是找不到，就是这个叶节点没有下一步了，返回即可
return maze, point, step_set
length, width = 50, 50 # 定义迷宫大小
maze = np.zeros(shape=(length, width))
maze[::2, ::2] = 1
maze[4:9, 4:17] = -1
maze[12:39, 20:39] = -1
# 每次只能上下左右试探
step_set = np.array([[1, 0],
[-1, 0],
[0, 1],
[0, -1]])
point = np.array([0, 0])
find_next_step(maze, point, step_set)
# 在右下的方块里生成一个迷宫
maze1 = np.zeros_like(maze[12:39, 20:39])
maze1[::2, ::2] = 1
find_next_step(maze1, point, step_set)
# 把小迷宫覆盖到大迷宫上
maze[12:39, 20:39] = maze1
maze[11, 20] = 2 # 不要忘记把大迷宫和小迷宫连接起来
plt.imshow(maze)
plt.show()
