一文看懂Python迷宫生成和迷宫破解算法python爬虫程序学习教程-

@本文来源于公众号：csdn2299，喜欢可以关注公众号 程序员学府
今天小编就为大家一今天小编就为大家一篇Python迷宫生成和迷宫破解算法实例，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧

1迷宫生成

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 m 

2.深度优先

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

效果：
代码：

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 

2.迷宫破解

效果：

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_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):    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核心知识，深入的研习计算机基础知识，整理好了，如果你也不甘平庸，那就与我一起在编码之外，不断成长吧！
其实这里不仅有技术，更有那些技术之外的东西，比如，如何做一个精致的程序员，而不是“屌丝”，程序员本身就是高贵的一种存在啊，难道不是吗？[点击加入]想做你自己想成为高尚人，加油！