Python迷宫生成和迷宫破解算法实例 |
您所在的位置：网站首页 › python迷宫地图代码 › Python迷宫生成和迷宫破解算法实例 |
|
迷宫生成 1.随机PRIM 思路：先让迷宫中全都是墙，不断从列表（最初只含有一个启始单元格）中选取一个单元格标记为通路，将其周围（上下左右）未访问过的单元格放入列表并标记为已访问，再随机选取该单元格与周围通路单元格（若有的话）之间的一面墙打通。重复以上步骤直到列表为空，迷宫生成完毕。这种方式生成的迷宫难度高，岔口多。 效果： 代码： import random import numpy as np from matplotlib import pyplot as plt def build_twist(num_rows, num_cols): # 扭曲迷宫 # (行坐标，列坐标，四面墙的有无&访问标记) m = np.zeros((num_rows, num_cols, 5), dtype=np.uint8) r, c = 0, 0 trace = [(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] = 2 if 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] = 2 if 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] = 2 if len(check): direction = random.choice(check) if direction == 'L': # 打通一面墙 m[r, c, 0] = 1 c = c - 1 m[r, c, 2] = 1 if direction == 'U': m[r, c, 1] = 1 r = r - 1 m[r, c, 3] = 1 if direction == 'R': m[r, c, 2] = 1 c = c + 1 m[r, c, 0] = 1 if direction == 'D': m[r, c, 3] = 1 r = r + 1 m[r, c, 1] = 1 m[0, 0, 0] = 1 m[num_rows - 1, num_cols - 1, 2] = 1 return m2.深度优先 思路：从起点开始随机游走并在前进方向两侧建立墙壁，标记走过的单元格，当无路可走（周围无未访问过的单元格）时重复返回上一个格子直到有新的未访问单元格可走。最终所有单元格都被访问过后迷宫生成完毕。这种方式生成的迷宫较为简单，由一条明显但是曲折的主路径和不多的分支路径组成。 效果： 代码： def build_tortuous(num_rows, num_cols): # 曲折迷宫 m = np.zeros((num_rows, num_cols, 5), dtype=np.uint8) r = 0 c = 0 trace = [(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] = 1 c = c - 1 m[r, c, 2] = 1 if direction == 'U': m[r, c, 1] = 1 r = r - 1 m[r, c, 3] = 1 if direction == 'R': m[r, c, 2] = 1 c = c + 1 m[r, c, 0] = 1 if direction == 'D': m[r, c, 3] = 1 r = r + 1 m[r, c, 1] = 1 else: r, c = trace.pop() m[0, 0, 0] = 1 m[num_rows - 1, num_cols - 1, 2] = 1 return m迷宫破解 效果： 1.填坑法 思路：从起点开始，不断随机选择没墙的方向前进，当处于一个坑（除了来时的方向外三面都是墙）中时，退一步并建造一堵墙将坑封上。不断重复以上步骤，最终就能抵达终点。 优缺点：可以处理含有环路的迷宫，但是处理时间较长还需要更多的储存空间。 代码： def solve_fill(num_rows, num_cols, m): # 填坑法 map_arr = m.copy() # 拷贝一份迷宫来填坑 map_arr[0, 0, 0] = 0 map_arr[num_rows-1, num_cols-1, 2] = 0 move_list = [] xy_list = [] r, c = (0, 0) while True: if (r == num_rows-1) and (c == num_cols-1): break xy_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 False elif len(way) == 1: # 在坑中 go = way[0] move_list.append(go) if go == 'L': # 填坑 map_arr[r, c, 0] = 0 c = c - 1 map_arr[r, c, 2] = 0 elif go == 'U': map_arr[r, c, 1] = 0 r = r - 1 map_arr[r, c, 3] = 0 elif go == 'R': map_arr[r, c, 2] = 0 c = c + 1 map_arr[r, c, 0] = 0 elif go == 'D': map_arr[r, c, 3] = 0 r = r + 1 map_arr[r, c, 1] = 0 else: 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 - 1 elif go == 'U': r = r - 1 elif go == 'R': c = c + 1 elif go == 'D': r = r + 1 r_list = xy_list.copy() r_list.reverse() # 行动坐标记录的反转 i = 0 while 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 + 1 return move_list2.回溯法 思路：遇到岔口则将岔口坐标和所有可行方向压入栈，从栈中弹出一个坐标和方向，前进。不断重复以上步骤，最终就能抵达终点。 优缺点：计算速度快，需要空间小，但无法处理含有环路的迷宫。 代码： 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): break 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') 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 False m = m + 1 move_list.append(go) if go == 'L': c = c - 1 elif go == 'U': r = r - 1 elif go == 'R': c = c + 1 elif go == 'D': r = r + 1 del 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)以上这篇Python迷宫生成和迷宫破解算法实例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持脚本之家。 您可能感兴趣的文章:如何用 Python 制作一个迷宫游戏Python 实现递归法解决迷宫问题的示例代码10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径Python解决走迷宫问题算法示例一道python走迷宫算法题Python深度优先算法生成迷宫Python使用Tkinter实现机器人走迷宫Python基于分水岭算法解决走迷宫游戏示例Python使用回溯法子集树模板解决迷宫问题示例Python基于递归算法实现的走迷宫问题用Python代码来解图片迷宫的方法整理python实现的生成随机迷宫算法核心代码分享（含游戏完整代码）教你怎么用Python实现多路径迷宫 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |