Python——迷宫生成和迷宫破解算法

迷宫绘制函数

def draw(num_rows, num_cols, m):image = np.zeros((num_rows * 10, num_cols * 10), dtype=np.uint8)for row in range(0, num_rows):for col in range(0, num_cols):cell_data = m[row, col]for i in range(10 * row + 2, 10 * row + 8):image[i, range(10 * col + 2, 10 * col + 8)] = 255if cell_data[0] == 1:image[range(10 * row + 2, 10 * row + 8), 10 * col] = 255image[range(10 * row + 2, 10 * row + 8), 10 * col + 1] = 255if cell_data[1] == 1:image[10 * row, range(10 * col + 2, 10 * col + 8)] = 255image[10 * row + 1, range(10 * col + 2, 10 * col + 8)] = 255if cell_data[2] == 1:image[range(10 * row + 2, 10 * row + 8), 10 * col + 9] = 255image[range(10 * row + 2, 10 * row + 8), 10 * col + 8] = 255if cell_data[3] == 1:image[10 * row + 9, range(10 * col + 2, 10 * col + 8)] = 255image[10 * row + 8, range(10 * col + 2, 10 * col + 8)] = 255return imagedef draw_path(image, move_list):row, col = (0, 0)image[range(10 * row + 2, 10 * row + 8), 10 * col] = 127image[range(10 * row + 2, 10 * row + 8), 10 * col + 1] = 127for i in range(len(move_list) + 1):for x in range(10 * row + 2, 10 * row + 8):image[x, range(10 * col + 2, 10 * col + 8)] = 127if i > 0:go = move_list[i - 1]if go == 'L':image[range(10 * row + 2, 10 * row + 8), 10 * col + 9] = 127image[range(10 * row + 2, 10 * row + 8), 10 * col + 8] = 127elif go == 'U':image[10 * row + 9, range(10 * col + 2, 10 * col + 8)] = 127image[10 * row + 8, range(10 * col + 2, 10 * col + 8)] = 127elif go == 'R':image[range(10 * row + 2, 10 * row + 8), 10 * col] = 127image[range(10 * row + 2, 10 * row + 8), 10 * col + 1] = 127elif go == 'D':image[10 * row, range(10 * col + 2, 10 * col + 8)] = 127image[10 * row + 1, range(10 * col + 2, 10 * col + 8)] = 127if i >= len(move_list):breakgo = move_list[i]if go == 'L':image[range(10 * row + 2, 10 * row + 8), 10 * col] = 127image[range(10 * row + 2, 10 * row + 8), 10 * col + 1] = 127elif go == 'U':image[10 * row, range(10 * col + 2, 10 * col + 8)] = 127image[10 * row + 1, range(10 * col + 2, 10 * col + 8)] = 127elif go == 'R':image[range(10 * row + 2, 10 * row + 8), 10 * col + 9] = 127image[range(10 * row + 2, 10 * row + 8), 10 * col + 8] = 127elif go == 'D':image[10 * row + 9, range(10 * col + 2, 10 * col + 8)] = 127image[10 * row + 8, range(10 * col + 2, 10 * col + 8)] = 127if go == 'L':col = col - 1elif go == 'U':row = row - 1elif go == 'R':col = col + 1elif go == 'D':row = row + 1image[range(10 * row + 2, 10 * row + 8), 10 * col + 9] = 127image[range(10 * row + 2, 10 * row + 8), 10 * col + 8] = 127return image

迷宫生成

1.随机PRIM

思路：先让迷宫中全都是墙，不断从列表（最初只含有一个启始单元格）中选取一个单元格标记为通路，将其周围（上下左右）未访问过的单元格放入列表并标记为已访问，再随机选取该单元格与周围通路单元格（若有的话）之间的一面墙打通。重复以上步骤直到列表为空，迷宫生成完毕。这种方式生成的迷宫难度高，岔口多。

效果：

代码：

import randomimport numpy as npfrom matplotlib import pyplot as pltdef build_twist(num_rows, num_cols): # 扭曲迷宫# (行坐标，列坐标，四面墙的有无&访问标记)m = np.zeros((num_rows, num_cols, 5), dtype=np.uint8)r, c = 0, 0trace = [(r, c)]while trace:r, c = random.choice(trace)m[r, c, 4] = 1# 标记为通路trace.remove((r, c))check = []if c > 0:if m[r, c - 1, 4] == 1:check.append('L')elif m[r, c - 1, 4] == 0:trace.append((r, c - 1))m[r, c - 1, 4] = 2# 标记为已访问if r > 0:if m[r - 1, c, 4] == 1:check.append('U')elif m[r - 1, c, 4] == 0:trace.append((r - 1, c))m[r - 1, c, 4] = 2if c < num_cols - 1:if m[r, c + 1, 4] == 1:check.append('R')elif m[r, c + 1, 4] == 0:trace.append((r, c + 1))m[r, c + 1, 4] = 2if r < num_rows - 1:if m[r + 1, c, 4] == 1:check.append('D')elif m[r + 1, c, 4] == 0:trace.append((r + 1, c))m[r + 1, c, 4] = 2if len(check):direction = random.choice(check)if direction == 'L':# 打通一面墙m[r, c, 0] = 1c = c - 1m[r, c, 2] = 1if direction == 'U':m[r, c, 1] = 1r = r - 1m[r, c, 3] = 1if direction == 'R':m[r, c, 2] = 1c = c + 1m[r, c, 0] = 1if direction == 'D':m[r, c, 3] = 1r = r + 1m[r, c, 1] = 1m[0, 0, 0] = 1m[num_rows - 1, num_cols - 1, 2] = 1return m

2.深度优先

思路：从起点开始随机游走并在前进方向两侧建立墙壁，标记走过的单元格，当无路可走（周围无未访问过的单元格）时重复返回上一个格子直到有新的未访问单元格可走。最终所有单元格都被访问过后迷宫生成完毕。这种方式生成的迷宫较为简单，由一条明显但是曲折的主路径和不多的分支路径组成。

效果：代码：

def build_tortuous(num_rows, num_cols): # 曲折迷宫m = np.zeros((num_rows, num_cols, 5), dtype=np.uint8)r = 0c = 0trace = [(r, c)]while trace:m[r, c, 4] = 1# 标记为已访问check = []if c > 0 and m[r, c - 1, 4] == 0:check.append('L')if r > 0 and m[r - 1, c, 4] == 0:check.append('U')if c < num_cols - 1 and m[r, c + 1, 4] == 0:check.append('R')if r < num_rows - 1 and m[r + 1, c, 4] == 0:check.append('D')if len(check):trace.append([r, c])direction = random.choice(check)if direction == 'L':m[r, c, 0] = 1c = c - 1m[r, c, 2] = 1if direction == 'U':m[r, c, 1] = 1r = r - 1m[r, c, 3] = 1if direction == 'R':m[r, c, 2] = 1c = c + 1m[r, c, 0] = 1if direction == 'D':m[r, c, 3] = 1r = r + 1m[r, c, 1] = 1else:r, c = trace.pop()m[0, 0, 0] = 1m[num_rows - 1, num_cols - 1, 2] = 1return m

迷宫破解

效果：

1.填坑法

思路：从起点开始，不断随机选择没墙的方向前进，当处于一个坑（除了来时的方向外三面都是墙）中时，退一步并建造一堵墙将坑封上。不断重复以上步骤，最终就能抵达终点。

优缺点：可以处理含有环路的迷宫，但是处理时间较长还需要更多的储存空间。

代码：

def solve_fill(num_rows, num_cols, m): # 填坑法map_arr = m.copy()# 拷贝一份迷宫来填坑map_arr[0, 0, 0] = 0map_arr[num_rows-1, num_cols-1, 2] = 0move_list = []xy_list = []r, c = (0, 0)while True:if (r == num_rows-1) and (c == num_cols-1):breakxy_list.append((r, c))wall = map_arr[r, c]way = []if wall[0] == 1:way.append('L')if wall[1] == 1:way.append('U')if wall[2] == 1:way.append('R')if wall[3] == 1:way.append('D')if len(way) == 0:return Falseelif len(way) == 1:# 在坑中go = way[0]move_list.append(go)if go == 'L':# 填坑map_arr[r, c, 0] = 0c = c - 1map_arr[r, c, 2] = 0elif go == 'U':map_arr[r, c, 1] = 0r = r - 1map_arr[r, c, 3] = 0elif go == 'R':map_arr[r, c, 2] = 0c = c + 1map_arr[r, c, 0] = 0elif go == 'D':map_arr[r, c, 3] = 0r = r + 1map_arr[r, c, 1] = 0else:if len(move_list) != 0:# 不在坑中come = move_list[len(move_list)-1]if come == 'L':if 'R' in way:way.remove('R')elif come == 'U':if 'D' in way:way.remove('D')elif come == 'R':if 'L' in way:way.remove('L')elif come == 'D':if 'U' in way:way.remove('U')go = random.choice(way)# 随机选一个方向走move_list.append(go)if go == 'L':c = c - 1elif go == 'U':r = r - 1elif go == 'R':c = c + 1elif go == 'D':r = r + 1r_list = xy_list.copy()r_list.reverse()# 行动坐标记录的反转i = 0while i < len(xy_list)-1:# 去掉重复的移动步骤j = (len(xy_list)-1) - r_list.index(xy_list[i])if i != j:# 说明这两个坐标之间的行动步骤都是多余的，因为一顿移动回到了原坐标del xy_list[i:j]del move_list[i:j]r_list = xy_list.copy()r_list.reverse()i = i + 1return move_list

2.回溯法

思路：遇到岔口则将岔口坐标和所有可行方向压入栈，从栈中弹出一个坐标和方向，前进。不断重复以上步骤，最终就能抵达终点。

优缺点：计算速度快，需要空间小，但无法处理含有环路的迷宫。

代码：

def solve_backtrack(num_rows, num_cols, map_arr): # 回溯法move_list = ['R']m = 1# 回溯点组号mark = []r, c = (0, 0)while True:if (r == num_rows-1) and (c == num_cols-1):breakwall = map_arr[r, c]way = []if wall[0] == 1:way.append('L')if wall[1] == 1:way.append('U')if wall[2] == 1:way.append('R')if wall[3] == 1:way.append('D')come = move_list[len(move_list) - 1]if come == 'L':way.remove('R')elif come == 'U':way.remove('D')elif come == 'R':way.remove('L')elif come == 'D':way.remove('U')while way:mark.append((r, c, m, way.pop()))# 记录当前坐标和可行移动方向if mark:r, c, m, go = mark.pop()del move_list[m:]# 删除回溯点之后的移动else:return Falsem = m + 1move_list.append(go)if go == 'L':c = c - 1elif go == 'U':r = r - 1elif go == 'R':c = c + 1elif go == 'D':r = r + 1del move_list[0]return move_list

测试

rows = int(input("Rows: "))cols = int(input("Columns: "))Map = build_twist(rows, cols)plt.imshow(draw(rows, cols, Map), cmap='gray')fig = plt.gcf()fig.set_size_inches(cols/10/3, rows/10/3)plt.gca().xaxis.set_major_locator(plt.NullLocator())plt.gca().yaxis.set_major_locator(plt.NullLocator())plt.subplots_adjust(top=1, bottom=0, right=1, left=0, hspace=0, wspace=0)plt.margins(0, 0)fig.savefig('aaa.png', format='png', transparent=True, dpi=300, pad_inches=0)move = solve_backtrack(rows, cols, Map)plt.imshow(draw_path(draw(rows, cols, Map), move), cmap='hot')fig = plt.gcf()fig.set_size_inches(cols/10/3, rows/10/3)plt.gca().xaxis.set_major_locator(plt.NullLocator())plt.gca().yaxis.set_major_locator(plt.NullLocator())plt.subplots_adjust(top=1, bottom=0, right=1, left=0, hspace=0, wspace=0)plt.margins(0, 0)fig.savefig('bbb.png', format='png', transparent=True, dpi=300, pad_inches=0)