python 迷宫地图可视化（迷宫生成算法、pygame 地图可视化可扩展详细注释）-best365彩票-microsoft365破解版-best365彩票-365bet注册指南

前言：

实现：

研究思路

思路：

算法：

应用：

扩展（可玩性角度）：

总结

题外话：

前言：

该领域确实没什么新东西，我那天突发奇想学了迷宫生成算法，看的那些效果，哇塞哇塞，copy下来代码后一跑一个报错，然后自己实现了一遍，我觉得本文除了记录以外，当属迷宫绘制类最有意义了。（高端的东西写不来，低端的东西节省一下大家时间还是蛮不错的）

效果是下面的样子，自娱自乐了。

实现：

复制下述代码即可，注意todo，代码含义见注释。

补充解释：MazeMap用于处理迷宫数据，其中迷宫的生成有两种生成方式，分别为深搜的solved_map和prim算法的solved_map1，在初始化里面更新就行，自己改改也行。

然后是两种迷宫可视化方式，MazeShow和MazeGazeShow，对应上面的左右两种效果。

我只是给个可能行的应用，自己用最好修修，还有就是我的代码（一言难尽），有点小毒

import pygame

import sys

import random as r

from typing import List

# todo:

# 1. maze_size处修改迷宫尺寸

# 2. 迷宫可视化类与迷宫计算类

# 3. main函数思路

# 设定全局界面参数

SCREEN_WIDTH = 800

SCREEN_HIGHT = 600

maze_size = (10, 10) # 迷宫的宽和高

class MazeMap(object):

"""处理地图相关数据"""

def __init__(self, size=(5, 5)):

"""初始化"""

self.width, self.high = (0, 0) # 地图有效格子

self.map = [[]] # 地图数据

self.point = [] # 地图有效格子的坐标

self.set_map(size) # 生成初始化地图

self.solve_map1() # 地图迷宫化

def set_map(self, size=(5, 5)):

"""生成路径与围墙地图"""

self.width, self.high = size # 读取地图尺寸

# 将有效格子周围的墙壁特化为格子，因此地图尺寸变为（x * 2 + 1, y * 2 + 1）

self.map = [[1 for _ in range(self.width * 2 + 1)] for _ in range(self.high * 2 + 1)]

self.point = []

for i in range(self.high): # 处理有效格子

for j in range(self.width):

self.map[i * 2 + 1][j * 2 + 1] = 0

self.point.append((i * 2 + 1, j * 2 + 1))

def solve_map(self):

"""所有点遍历一次 dfs算法"""

"""

数据结构：

遍历节点列表：储存已经遍历过的节点

遍历栈：储存遍历节点的循序

周围节点列表：储存当前节点周围的节点（符合一定条件）

思路：

初始化：将起点设为当前点

当有节点没有被遍历时：

对于当前点

更新周围节点列表为空

查询当前点周围所有点（四个方向），若有不在遍历节点列表的，将其加入周围节点列表

若周围节点列表不为空

将当前点压入遍历栈

从中随机选取一点，将其与当前点之间的墙壁打通，并将其设定为当前点

若周围节点列表为空

从遍历栈弹出顶点，将其设为当前点

"""

length = len(self.point)

pass_point = []

path_list = []

swap_point = [] # 本来不该在这写的，方便理解吧

current_point = self.point[0] # 初始化起点为当前点

while length != len(pass_point): # 有节点未遍历

if current_point not in pass_point: # 更新当前点的遍历状态

pass_point.append(current_point)

# 寻找当前点周围的所有点，并筛选合法的且没有遍历过的那些

possible_point = self.possible_point(current_point)

swap_point = []

for _point in possible_point:

if _point in self.point and _point not in pass_point: # 点有效且未经过

swap_point.append(_point)

if swap_point: # 周围节点列表有点

path_list.append(current_point) # 入栈

swap_point = self.choose_point(swap_point) # 随机选取一点

self.break_wall(current_point, swap_point) # 打破墙壁

current_point = swap_point # 更新当前点

else: # 周围节点列表无点

current_point = path_list[-1] # 等效出栈，更新当前点

path_list.remove(current_point)

def solve_map1(self):

"""prim算法实现"""

start = self.point[0] # 迷宫起点

visited = [start] # 已访问节点

frontier = [] # 边界节点（待处理的未访问节点）

# 初始化边界列表：添加起点的所有有效邻居

for neighbor in self.possible_point(start):

if neighbor in self.point and neighbor not in visited:

frontier.append(neighbor)

while frontier:

# 从边界列表中随机选择当前节点

current = self.choose_point(frontier)

# 获取当前节点的所有邻居

neighbors = self.possible_point(current)

# 找出已访问的邻居（用于打通墙壁）

linked = [n for n in neighbors if n in visited]

if linked:

# 随机选择一个已访问邻居，打通墙壁

target = self.choose_point(linked)

wx = (current[0] + target[0]) // 2

wy = (current[1] + target[1]) // 2

self.map[wx][wy] = 0 # 移除墙壁

# 标记当前节点为已访问

visited.append(current)

frontier.remove(current)

# 将当前节点的新邻居加入边界列表

for neighbor in neighbors:

if neighbor in self.point and neighbor not in visited and neighbor not in frontier:

frontier.append(neighbor)

def possible_point(self, current_point):

"""找一个节点周围的节点"""

x, y = current_point

path = [[0, 2], [2, 0], [-2, 0], [0, -2]] # 四个方向，后续可扩展

possible = []

for enum in path:

_x, _y = enum

possible.append((x + _x, y + _y))

return possible

def choose_point(self, next_point):

"""在一个点的列表中随机抽取一点"""

return next_point[r.randint(0, len(next_point) - 1)]

def break_wall(self, pos1, pos2):

"""打通两个格子之间的墙壁"""

self.map[int((pos1[0] + pos2[0]) / 2)][int((pos1[1] + pos2[1]) / 2)] = 0

def get_map(self):

"""获得地图数据"""

return self.map

def get_point(self):

"""获得有效点信息"""

return self.point

# 用于可视化迷宫

# 要求二维列表,例如下

# [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

# [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]

# [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]

# [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]

# [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]

# [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]

# [1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1]

# [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1]

# [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1]

# [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]

# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

class MazeShow(object):

"""迷宫可视化工具1"""

def __init__(self, size=(SCREEN_WIDTH, SCREEN_HIGHT)):

"""初始化"""

self.high = size[1] - 100 # 最大显示范围

self.wide = size[0] - 100

self.high_size = 0 # 单个格子的显示参数

self.width_size = 0

self.high_num = 0 # 格子的数目

self.width_num = 0

self.data = [[]] # 数据

def set_data(self, inf: List[List[int]]) -> None:

"""设定地图数据"""

self.data = inf

self.high_num = len(inf)

self.width_num = len(inf[0])

self.high_size = int(self.high / self.high_num)

self.width_size = int(self.wide / self.width_num)

self.high_size, self.width_size = min(self.high_size, self.width_size), min(self.high_size, self.width_size)

def display(self, screen, pos=(50, 50)):

"""绘制图像"""

x, y = pos # 绘制的左上角

for i in range(self.high_num):

for j in range(self.width_num):

# 对于每个点，根据地图中的不同数值，绘制不同效果，留作后续接口

# 此处应当还有一个函数的，不写了

if self.data[i][j] == 1: # 绘制一个填充的方块

pygame.draw.rect(screen, (155, 155, 155),

(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),

if self.data[i][j] == 0: # 通过两次绘制，实现方框与填充不同颜色的效果

pygame.draw.rect(screen, "red",

(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),

pygame.draw.rect(screen, (155, 155, 155),

(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),

class MazeGazeShow(object):

def __init__(self, size=(SCREEN_WIDTH, SCREEN_HIGHT)):

self.high = size[1] - 100

self.wide = size[0] - 100

self.high_size = 0

self.width_size = 0

self.high_num = 0

self.width_num = 0

self.player = (0, 0)

self.player_path = []

self.data = [[]]

def set_data(self, inf: List[List[int]]) -> None:

self.data = inf

self.high_num = int(len(inf) / 2) # 有效网格数

self.width_num = int(len(inf[0]) / 2)

self.high_size = int(self.high / self.high_num)

self.width_size = int(self.wide / self.width_num)

self.high_size, self.width_size = min(self.high_size, self.width_size), min(self.high_size, self.width_size)

def display(self, screen, pos=(50, 50)):

x, y = pos

# 为整个界面铺设背景，方便后续添加功能

for i in range(self.high_num):

for j in range(self.width_num):

# if self.data[i * 2 + 1][j * 2 + 1] == 1:

pygame.draw.rect(screen, (155, 155, 155),

(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),

# 水平

for i in range(self.high_num + 1):

for j in range(self.width_num):

if self.data[i * 2][j * 2 + 1] == 1:

pygame.draw.line(screen, (255, 0, 0), (x + j * self.width_size, y + i * self.high_size),

(x + (j + 1) * self.width_size, y + i * self.high_size), 2)

# 竖直

for i in range(self.high_num):

for j in range(self.width_num+1):

if self.data[i * 2 + 1][j * 2] == 1:

pygame.draw.line(screen, (255, 0, 0), (x + j * self.width_size, y + i * self.high_size),

(x + j * self.width_size, y + (i + 1) * self.high_size), 2)

def main():

# 初始化

pygame.init()

screen = pygame.display.set_mode((SCREEN_WIDTH * 2, SCREEN_HIGHT))

pygame.display.set_caption("迷宫可视化")

running = True

clock = pygame.time.Clock()

# 准备数据

maze = MazeShow()

maze1 = MazeGazeShow()

map1 = MazeMap((10, 10))

for line in map1.get_map():

print(line)

maze.set_data(map1.get_map())

maze1.set_data(map1.get_map())

# 绘制一次界面

screen.fill("white")

maze.display(screen)

maze1.display(screen, (SCREEN_WIDTH, 50))

# 刷新，目前不刷新也行

pygame.display.flip()

# 死循环

while running:

for event in pygame.event.get():

if event.type == pygame.QUIT:

pygame.quit()

sys.exit()

# 需刷新请在此更新

clock.tick(10)

if __name__ == "__main__":

main()

————————————分割线——————————————————

代码解释：

我代码可读性还可以吧。。。（细节后面我再补）(已补)

理论部分放在后面了，文章不想重构了。

首先进入main函数，在此我创建了三个对象maze,maze1,map，分别对应我自定义的MazeShow类、MazeGazeShow类和MazeMap类。其中map初始化传入（10,10），该类在初始化时会自动生成有效格子为10*10的迷宫数据。

maze = MazeShow()

maze1 = MazeGazeShow()

map1 = MazeMap((10, 10))

接下来查看生成的迷宫数据，并将数据传入maze,maze1。

for line in map1.get_map():

print(line)

maze.set_data(map1.get_map())

maze1.set_data(map1.get_map())

然后将maze,maze1的数据展示在屏幕上。

# 绘制一次界面

screen.fill("white")

maze.display(screen)

maze1.display(screen, (SCREEN_WIDTH, 50))

# 刷新，目前不刷新也行

pygame.display.flip()

其他部分为标准的pygame中main函数结构，请自学。

然后来看类是怎么实现的（代码不重复贴了）。

MazeMap类，初始化创建数据成员，调用set_map和solve_map方法。前者生成一个二维列表，表中的数据按照prim迷宫的数据结构来，构成一个初始化的迷宫。后者采用生成树的方法将迷宫的墙壁打通，变成一个可以使用的迷宫。其他函数均为辅助。

MazeShow类，初始化创建空数据成员，调用set_data方法接受二维列表构成的迷宫，根据全局变量屏幕大小自适应单个格子的宽度，取整后将长宽取小。display方法在传入的屏幕句柄上绘制图像，已传入的pos作为左上方的坐标，绘制整个地图，根据地图数据中的值不同，绘制不同的效果。绘制方框和方块组合城整个迷宫。在此类中空格与墙壁等价。

MazeGazeShow类，基本同MazeShow类，区别在于set_data方法自适应时，参照的是（m,n）而不是(2m+1, 2n+1)，display方法分三个部分实现：绘制背景，绘制横着的墙壁、竖着的墙壁。

于是整段代码可以概括为：使用pygame创建一个界面，实例化一个MazeMap对象，生成迷宫数据，生成方式为树算法，然后实例化两个MazeShow对象和MazeGazeShow对象，将生成的数据传入，设定自适应的地图数据，然后在界面上绘制，然后界面保持不变直到退出。

研究思路

首先普及一下迷宫生成问题中的数据结构，看这篇文章pygame迷宫生成-CSDN博客，比较难评的是他要收费，没有关系，看看预览部分就懂了（细节后面我再补）(已补)，毕竟我不收费是吧哈哈。

为什么要有这样的数据结构？首先我们知道，迷宫中的元素有两个，或者说可以通过和不可通过两种状态的元素，在此称为格子和墙壁。单独生成格子和墙壁构成一个迷宫是很困难的（可以看我之前写的A*算法，就是解这类迷宫），但是提前将格子和墙壁规规矩矩的设定好，然后将多余的墙壁打破，生成迷宫就变容易了。可以将迷宫抽象成许多个小部分，小部分的四周有墙壁，类似于一个九宫格，中间的部分代表格子，四周代表墙壁，许多个小部分组合成整体，格子与格子之间就会有两个墙壁，为了优化数据结构，直接合并，最终的初始化数据应当是下面的样子。

思路：

在上述数据结构的基础上，迷宫生成表面上看，是找个复杂的网络，把所有格子连接起来。于是大家将其抽象成树，为了确保起点和终点之间有且仅有一条路径，要求树中没有环，于是进一步抽象成最小生成树，所以啊，所有可以实现最小生成树的算法都有对应的迷宫生成算法。我学了prim算法，手搓的时候给搓成了dfs，然后用了ai辅助一下，写出来了prim。

算法：

prim算法，理论部分看看其他文章吧（细节后面我再补）(已补)

准备一个已访问列表，一个候选列表。

1. 初始化一个起始单元格（随机），将其加入已访问列表，并将它的所有相邻单元格加入候选列表。

2. 当候选列表不为空时：

a. 随机选择一个候选单元格，将其从候选列表移除，加入已访问列表。

b. 如果当前候选单元格周围有已访问单元格，随机选取一个，打通两者间的墙壁。

c. 将当前候选单元格周围所有未访问单元格加入候选列表（去重）。

思想：将所有格子分成三部分，已经访问、等待访问、未知。已经访问的部分，所有格子都是想通的，等待访问的部分，所有格子都可以加入已经访问，未知部分，无意义。

因为每个格子至少和两个其他格子相邻，所以按照上面的流程可以将所有格子遍历一遍。

这篇文章理论好prim算法（普里姆算法）详解，图文并茂 - C语言中文网

这篇文章讲了怎么在迷宫问题中应用Python编程：自制迷宫生成器-CSDN博客

(手机端预览可以最后看到思路)

dfs，额，应该都会。

应用：

假设生成迷宫为m行n列（后面写（m, n）了），按照上面的数据结构，初始化（2m+1, 2n+1）的二维列表全为1，然后把格子变成0，然后想办法把格子之间的墙壁打通（改为0）就成功了。最后类返回一个二维列表（数据结构真的很重要，某个文章代码崩了我一脸）。（细节后面我再补）（我的窘迫还是算了吧，不补了）

这样的数据，方便你我他是吧。

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]