Python实战：迷宫生成与A*寻路算法可视化详解

各位关注算法实战与 Python 小项目的朋友，大家好。

之前在做路径规划相关的技术调研时，经常需要在不同地图上验证寻路效果，但网上现成的迷宫生成与 A* 寻路教程大多只讲算法片段，很难直接跑起来。今天整理了一份完整的项目实战笔记，代号叫“P31：漫漫归途”。这个项目用 Python 从零实现一个可交互的迷宫地图生成器，并在迷宫上完成 A* 最短路径搜索，最终通过可视化窗口把“从起点到终点”的完整路程展示出来。文章会从原理、环境、代码、运行、排错一直讲到可扩展方向，适合想系统掌握寻路算法和迷宫生成的读者，也适合作为毕业设计、课程作业或算法练手的参考项目。

1. P31 项目概览：这个项目到底在做什么

1.1 “漫漫归途”解决什么问题

在很多实际场景中，我们都会遇到“从 A 点到 B 点找一条可行路径”的需求，例如游戏中的 NPC 自动寻路、仓库机器人路径调度、地图导航中的路线规划等。“漫漫归途”这个项目以迷宫为载体，完整复现了一条路径从无到有的全过程：

1. 程序自动生成一个随机迷宫，迷宫中存在墙壁和可通行道路。
2. 在迷宫上指定起点与终点。
3. 通过 A* 搜索算法找到一条从起点到终点的最短可行路径。
4. 用可视化窗口展示迷宫和路径，让算法过程肉眼可见。

这个项目本质上是一个“迷宫生成 + 寻路算法”的综合演练。它不像力扣题那样只写一个函数，而是把算法放在一个完整的、可运行的程序中，处理好数据结构、坐标体系、可视化渲染和交互逻辑。

“P31”可以看作是本次项目的版本代号，表示这是第 31 个实践作品；“漫漫归途”则对应 A* 算法从起点一步步走向终点的过程，也对应递归回溯生成迷宫时不断“向前探索再回头”的路径状态。

1.2 项目技术栈与核心收益

技术选型上，本项目尽量做到轻量易懂：

• Python 3 作为开发语言，使用标准库random、heapq、math实现核心逻辑。
• pygame作为可视化渲染库，用来绘制迷宫和寻路过程。
• 迷宫生成采用递归回溯算法（Recursive Backtracker），也就是深度优先搜索的随机化版本。
• 路径搜索采用 A* 算法，利用启发式函数引导搜索方向。

通过这个项目，可以掌握以下能力：

1.3 适合什么基础的人学习

如果你已经掌握了 Python 基础语法，了解列表、字典、元组和基本的函数定义，那么本项目可以直接上手。

如果你刚接触算法，建议先把第 3 节中的 A* 原理读一遍，再对照代码逐步理解。本项目不是竞赛题，代码会给得很完整，核心逻辑都加了注释，照着敲一遍就能看到运行效果。

2. 环境准备与项目结构

2.1 开发环境说明

本文示例的开发环境如下，具体版本需要根据你的实际环境灵活调整，重点是演示整体思路：

• 操作系统：Windows 10 / 11，macOS 或 Ubuntu 均可
• Python 版本：3.8 及以上（建议 3.10 或更高）
• 第三方库：pygame 2.x
• 开发工具：VS Code 或 PyCharm 均可

在开始之前，先确认 Python 已正确安装。打开命令行终端，执行：

python --version

如果提示找不到命令，可以尝试python3 --version。确认版本后，安装 pygame：

pip install pygame

如果你使用的是国内网络环境，可以指定清华大学镜像，速度更快：

pip install pygame -i https://pypi.tuna.tsinghua.edu.cn/simple

安装完成后，可以执行以下命令验证：

python -c "import pygame; print(pygame.__version__)"

如果能正常输出版本号，说明环境已经就绪。

2.2 项目目录结构

为了避免把所有代码堆在一个文件里，方便后续阅读和维护，我们把项目拆成三个模块：

p31_road_home/ ├── main.py # 程序入口，负责整体流程 ├── maze.py # 迷宫生成模块 ├── astar.py # A* 路径搜索模块 └── requirements.txt # 依赖清单

文件职责：

• maze.py：定义迷宫网格、生成算法，提供获取当前迷宫数据的方法。
• astar.py：定义 A* 搜索逻辑，输入迷宫、起点、终点，输出路径点列表。
• main.py：初始化 pygame，生成迷宫，调用 A* 寻路，渲染窗口并显示最终路径。

2.3 核心常量约定

在编写代码之前，先约定一些常量。这里我们把坐标统一为“列 x、行 y”的形式，用(x, y)表示迷宫中的一个格子。

# main.py 顶部统一配置 SCREEN_WIDTH = 800 SCREEN_HEIGHT = 600 GRID_SIZE = 20 # 每个格子的像素尺寸 COLS = 25 # 迷宫列数 ROWS = 20 # 迷宫行数 WALL_COLOR = (40, 40, 40) ROAD_COLOR = (240, 240, 240) START_COLOR = (0, 200, 0) END_COLOR = (200, 0, 0) PATH_COLOR = (30, 120, 255)

这些常量在生成迷宫和绘制窗口时都会用到。读者可以根据自己的屏幕大小调整COLS和ROWS，不建议设置过大，否则窗口会超出屏幕边界。

3. 核心原理解析：迷宫生成与 A* 寻路

3.1 迷宫数据模型：如何用二维数组表示迷宫

迷宫本质上是一个二维网格，每个格子有两种状态：墙或路。我们可以用一个二维列表来表示迷宫，例如：

maze = [ [0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0], ]

其中1表示墙，0表示路。在递归回溯算法中，我们通常把所有格子初始化为墙，然后通过“挖路”的方式把通路打通。

本项目采用另一种常见的处理方式：用奇数行列作为路的候选点。假设迷宫尺寸为COLS x ROWS，我们只对行列下标为奇数的格子执行“打通”操作，保证迷宫必然有一圈墙壁，并且墙体厚薄均匀。

3.2 递归回溯生成迷宫的过程

递归回溯算法，也叫随机深度优先搜索，是生成迷宫最简单直观的算法之一。整体流程如下：

1. 从某个起始单元格开始，把当前单元格标记为“已访问”。
2. 随机选择当前单元格的一个未访问相邻单元格。
3. 打通两个单元格之间的墙壁，移动到新的单元格。
4. 如果当前单元格没有未访问的相邻单元格，则回退到上一个单元格。
5. 重复步骤 2~4，直到所有单元格都被访问。

从路径规划的角度看，递归回溯生成出来的迷宫拥有一条唯一的、能连接任意两个格子的路径走廊，非常适合测试寻路算法。

为了让迷宫不越界，我们通常把“可访问单元格”限定在奇数坐标上。例如(1, 1)、(3, 1)、(1, 3)等。这样可以保证墙体厚度统一，迷宫视觉上更加规整。

3.3 A* 寻路算法为什么适合这个场景

迷宫生成之后，就需要从起点找到终点。常用的算法有 BFS、Dijkstra 和 A*。A* 在网格地图中表现高效，因为它引入了一个启发式函数，引导搜索优先朝终点方向扩展。

A* 的核心公式：

f(n) = g(n) + h(n)

• g(n)：从起点到当前节点n的实际移动代价。
• h(n)：从当前节点n到终点的估计代价。
• f(n)：节点的总估计代价。

在网格迷宫中，我们通常使用曼哈顿距离作为启发式函数。因为迷宫中的移动方向是上下左右四个方向，不走斜线，所以曼哈顿距离是对剩余路程的“乐观估计”，不会高估真实代价，从而保证 A* 找到最优路径。

曼哈顿距离公式：

h(n) = abs(x - end_x) + abs(y - end_y)

3.4 循环与优先级队列的配合

A* 算法在实现时需要维护两个集合：

• open_set：待探索的节点集合，每次从集合中取出f值最小的节点。
• closed_set：已经探索过的节点集合，避免重复处理。

在 Python 中，从集合中取出最小值的最优方式是使用堆（heapq）。堆结构可以保证每次取节点的时间复杂度为 O(log n)。这里需要把(f, g, x, y)放入堆中，Python 会自动按照元组第一个元素比较大小。

同时，我们需要用两个字典记录路径：

• g_score：记录起点到每个节点的实际代价。
• came_from：记录每个节点的父节点，用于最终反向还原路径。

3.5 路径还原：从终点回溯到起点

当 A* 搜索找到终点时，我们从终点出发，沿着came_from不断回退，直到回到起点。这个过程得到的是从终点到起点的倒序列表，最后反转一下，就得到了从起点到终点的顺序路径。

当前节点是终点 while 当前节点 != 起点: 把当前节点加入路径 当前节点 = came_from[当前节点] 把起点加入路径 反转路径

4. 完整代码实现

下面进入代码环节。请按照目录结构创建文件，并把代码完整复制到对应文件中。

4.1 安装依赖清单

在项目根目录下创建requirements.txt：

pygame>=2.0.0

4.2 迷宫生成模块 maze.py

maze.py负责生成迷宫，对外提供Maze类。

# 文件路径：p31_road_home/maze.py import random class Maze: """迷宫数据模型。 内部使用二维列表 maze[row][col] 表示迷宫： 1 表示墙，0 表示路。 """ def __init__(self, rows: int, cols: int): self.rows = rows self.cols = cols # 初始化全部为墙 self.grid = [[1 for _ in range(cols)] for _ in range(rows)] def is_valid_cell(self, x: int, y: int) -> bool: """判断 (x, y) 是否在迷宫范围内，并且是奇数坐标。 奇数坐标是递归回溯算法中可访问的“路候选点”。 """ return 1 <= x < self.cols - 1 and 1 <= y < self.rows - 1 and x % 2 == 1 and y % 2 == 1 def get_neighbors(self, x: int, y: int): """返回当前单元格上下左右距离 2 格的邻居坐标。 只有尚未访问并且为奇数坐标的邻居才会被选中。 """ directions = [(0, 2), (0, -2), (2, 0), (-2, 0)] neighbors = [] for dx, dy in directions: nx, ny = x + dx, y + dy if self.is_valid_cell(nx, ny) and self.grid[ny][nx] == 1: neighbors.append((nx, ny)) return neighbors def remove_wall(self, x1: int, y1: int, x2: int, y2: int): """打通两个单元格之间的墙。 两个单元格距离为 2，中间隔 1 个墙格。 所以打通中间墙的坐标是两者的中点。 """ wall_x = (x1 + x2) // 2 wall_y = (y1 + y2) // 2 self.grid[y1][x1] = 0 self.grid[y2][x2] = 0 self.grid[wall_y][wall_x] = 0 def generate(self, start_x: int = 1, start_y: int = 1): """递归回溯生成迷宫。 使用显式栈的方式实现深度优先遍历，避免递归过深。 """ # 先把起点格子设为路 self.grid[start_y][start_x] = 0 # 栈中保存路径轨迹，用于回溯 stack = [(start_x, start_y)] visited = set() visited.add((start_x, start_y)) while stack: x, y = stack[-1] neighbors = self.get_neighbors(x, y) # 过滤出没有访问过的邻居 unvisited = [n for n in neighbors if n not in visited] if unvisited: nx, ny = random.choice(unvisited) visited.add((nx, ny)) self.remove_wall(x, y, nx, ny) stack.append((nx, ny)) else: # 没有可探索的邻居，回退 stack.pop() def get_path_grid(self): """返回迷宫网格的副本，避免外部直接修改内部数据。""" return [row[:] for row in self.grid]

注意，get_neighbors方法中，我们通过self.grid[ny][nx] == 1判断该候选点是否还未成为路。因为生成过程中已经打通的路会被置为 0，所以只有墙位置才会被考虑为“未访问”。

4.3 A* 寻路模块 astar.py

astar.py负责在迷宫网格上搜索路径。

# 文件路径：p31_road_home/astar.py import heapq import math def heuristic(x1: int, y1: int, x2: int, y2: int) -> int: """曼哈顿距离启发函数。""" return abs(x1 - x2) + abs(y1 - y2) def astar(grid, start, end): """在二维迷宫网格中搜索从 start 到 end 的最短路径。 grid: 二维列表，0 表示路，1 表示墙。 start: 起点坐标 (x, y) end: 终点坐标 (x, y) 返回值：路径点列表 [(x, y), ...]，包含起点和终点；如果不存在路径，返回 None。 """ rows = len(grid) cols = len(grid[0]) start_x, start_y = start end_x, end_y = end # 边界条件检查 if not (0 <= start_x < cols and 0 <= start_y < rows): return None if not (0 <= end_x < cols and 0 <= end_y < rows): return None if grid[start_y][start_x] == 1 or grid[end_y][end_x] == 1: return None # open_set 使用堆结构，元素为 (f, g, x, y) # 元组比较时先比较 f，再比较 g，因此可以实现按 f 值排序 open_set = [] heapq.heappush(open_set, (0, 0, start_x, start_y)) # g_score 记录从起点到当前节点的实际代价 g_score = {} g_score[(start_x, start_y)] = 0 # came_from 记录路径父节点 came_from = {} # closed_set 记录已搜索节点 closed_set = set() directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while open_set: f_current, g_current, x, y = heapq.heappop(open_set) current = (x, y) if current in closed_set: continue closed_set.add(current) if current == (end_x, end_y): # 回溯路径 path = [] node = current while node is not None: path.append(node) node = came_from.get(node) path.reverse() return path # 遍历四个方向的邻居 for dx, dy in directions: nx, ny = x + dx, y + dy neighbor = (nx, ny) # 越界检查 if not (0 <= nx < cols and 0 <= ny < rows): continue # 墙壁检查 if grid[ny][nx] == 1: continue # 已搜索节点跳过 if neighbor in closed_set: continue tentative_g = g_current + 1 if neighbor not in g_score or tentative_g < g_score[neighbor]: g_score[neighbor] = tentative_g h = heuristic(nx, ny, end_x, end_y) f = tentative_g + h heapq.heappush(open_set, (f, tentative_g, nx, ny)) came_from[neighbor] = current return None

这段代码中，一个比较容易误解的地方是open_set中可能同时存在同一个节点的多个历史记录。我们使用closed_set来避免重复处理，保证算法正确性。

4.4 主程序 main.py

main.py负责把所有模块串起来：初始化迷宫、调用 A*、用 pygame 渲染窗口。

# 文件路径：p31_road_home/main.py import sys import pygame from maze import Maze from astar import astar # 窗口与网格配置 SCREEN_WIDTH = 800 SCREEN_HEIGHT = 600 GRID_SIZE = 20 COLS = 25 ROWS = 20 # 颜色定义 WALL_COLOR = (40, 40, 40) ROAD_COLOR = (240, 240, 240) START_COLOR = (0, 200, 0) END_COLOR = (200, 0, 0) PATH_COLOR = (30, 120, 255) LINE_COLOR = (200, 200, 200) def draw_maze(screen, maze): """绘制迷宫网格。""" for row in range(maze.rows): for col in range(maze.cols): rect = pygame.Rect( col * GRID_SIZE, row * GRID_SIZE, GRID_SIZE, GRID_SIZE ) if maze.grid[row][col] == 1: pygame.draw.rect(screen, WALL_COLOR, rect) else: pygame.draw.rect(screen, ROAD_COLOR, rect) def draw_path(screen, path): """绘制找到的路径，使用 PATH_COLOR 标记。""" for x, y in path: rect = pygame.Rect( x * GRID_SIZE + 3, y * GRID_SIZE + 3, GRID_SIZE - 6, GRID_SIZE - 6 ) pygame.draw.rect(screen, PATH_COLOR, rect) def draw_start_end(screen, start, end): """绘制起点和终点标记。""" x, y = start rect = pygame.Rect( x * GRID_SIZE + 3, y * GRID_SIZE + 3, GRID_SIZE - 6, GRID_SIZE - 6 ) pygame.draw.rect(screen, START_COLOR, rect) x, y = end rect = pygame.Rect( x * GRID_SIZE + 3, y * GRID_SIZE + 3, GRID_SIZE - 6, GRID_SIZE - 6 ) pygame.draw.rect(screen, END_COLOR, rect) def main(): pygame.init() screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT)) pygame.display.set_caption("P31：漫漫归途 - 迷宫生成与 A* 寻路") clock = pygame.time.Clock() # 生成迷宫 maze = Maze(ROWS, COLS) maze.generate(1, 1) # 设置起点和终点 start = (1, 1) end = (COLS - 2, ROWS - 2) # 校验终点是路 if maze.grid[end[1]][end[0]] == 1: print("终点位置是墙，尝试修改终点坐标。") pygame.quit() sys.exit(1) # 调用 A* 寻路 path = astar(maze.grid, start, end) if path is None: print("未找到可行路径，请检查迷宫生成逻辑。") else: print(f"找到路径，路径长度：{len(path)} 个格子") print(f"起点：{start}") print(f"终点：{end}") print(f"前 10 个路径点：{path[:10]}") running = True while running: for event in pygame.event.get(): if event.type == pygame.QUIT: running = False elif event.type == pygame.KEYDOWN: if event.key == pygame.K_SPACE: # 按空格键重新生成迷宫并重新寻路 maze = Maze(ROWS, COLS) maze.generate(1, 1) path = astar(maze.grid, start, end) if path is None: print("未找到可行路径，请检查迷宫生成逻辑。") else: print(f"找到路径，路径长度：{len(path)} 个格子") screen.fill((255, 255, 255)) # 绘制迷宫 draw_maze(screen, maze) # 绘制路径 if path is not None: draw_path(screen, path) # 绘制起点终点 draw_start_end(screen, start, end) pygame.display.flip() clock.tick(30) pygame.quit() if __name__ == "__main__": main()

4.5 代码运行与预期结果

在项目根目录执行：

python main.py

如果一切正常，会弹出一个 800x600 的窗口，窗口中显示一个随机生成的迷宫，蓝色路径从左上角起点延伸到右下角终点。控制台输出类似下面的信息：

找到路径，路径长度：127 个格子 起点：(1, 1) 终点：(23, 18) 前 10 个路径点：[(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (4, 3), (5, 3), (5, 4), (5, 5), (6, 5)]

路径长度每次运行都会变化，因为迷宫是随机生成的。图中的蓝色线条就是 A* 算法计算出来的最短路径，绿色是起点，红色是终点。

按空格键可以重新生成迷宫，并自动重新计算路径，方便观察不同迷宫下的寻路效果。

5. 进阶：显示 A* 搜索过程

如果只想看最终路径，上面代码已经够了。但如果希望更直观地理解 A* 算法是如何一步步扩展搜索范围的，可以在寻路过程中记录“搜索过的节点”，并把这些节点绘制在窗口中。

5.1 修改 astar 函数返回搜索过程

我们可以在astar.py中增加一个可选参数，用于记录搜索过程中访问到的节点。核心思路是把closed_set中的节点复制出来，在每次主循环结束时记录下来。

# 文件路径：p31_road_home/astar.py（增加搜索过程返回） def astar_with_search(grid, start, end): """A* 搜索，同时返回搜索过的节点列表和最终路径。""" rows = len(grid) cols = len(grid[0]) start_x, start_y = start end_x, end_y = end open_set = [] heapq.heappush(open_set, (0, 0, start_x, start_y)) g_score = {} g_score[(start_x, start_y)] = 0 came_from = {} closed_set = set() search_history = [] directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while open_set: f_current, g_current, x, y = heapq.heappop(open_set) current = (x, y) if current in closed_set: continue closed_set.add(current) search_history.append(current) if current == (end_x, end_y): path = [] node = current while node is not None: path.append(node) node = came_from.get(node) path.reverse() return search_history, path for dx, dy in directions: nx, ny = x + dx, y + dy neighbor = (nx, ny) if not (0 <= nx < cols and 0 <= ny < rows): continue if grid[ny][nx] == 1: continue if neighbor in closed_set: continue tentative_g = g_current + 1 if neighbor not in g_score or tentative_g < g_score[neighbor]: g_score[neighbor] = tentative_g h = heuristic(nx, ny, end_x, end_y) f = tentative_g + h heapq.heappush(open_set, (f, tentative_g, nx, ny)) came_from[neighbor] = current return search_history, None

5.2 在主程序中绘制搜索节点

修改main.py，增加一个颜色较浅的搜索图层。在绘制最终路径之前，先用浅色把所有搜索过的节点显示出来。

SEARCH_COLOR = (180, 220, 255) def draw_search_nodes(screen, search_history): """绘制搜索过的节点，方便观察 A* 扩展范围。""" for x, y in search_history: rect = pygame.Rect( x * GRID_SIZE + 6, y * GRID_SIZE + 6, GRID_SIZE - 12, GRID_SIZE - 12 ) pygame.draw.rect(screen, SEARCH_COLOR, rect)

然后在主循环中调用前先获取search_history：

search_history, path = astar_with_search(maze.grid, start, end)

绘制顺序要注意：

1. 先绘制迷宫。
2. 再绘制搜索节点。
3. 再绘制最终路径。
4. 最后绘制起点和终点。

这样可以形成层次感，浅蓝色区域代表算法探索过的范围，深蓝色线条代表最终选择的路径，视觉上非常清晰。

6. 常见问题与排查思路

在实际运行这个项目时，初学者可能会遇到一些问题。下面整理了几类高频问题。

6.1 起点位置是墙怎么处理

递归回溯生成迷宫时，起点(1, 1)已经是代码中固定的生成起始点，理论上一定是路。但如果修改了生成算法或者改变了起点的行列坐标，就必须确保(x, y)满足三个条件：

1. x为奇数。
2. y为奇数。
3. x、y在迷宫边界内部。

如果起点是墙，A* 函数会在入口处直接返回None。

6.2 路径不是最短怎么办

A* 算法的前提是启发函数不高估实际代价。曼哈顿距离在只能上下左右移动的网格中满足这个条件，所以理论上找到的路径是最短的。如果你改成允许斜向移动，就必须把启发函数改成欧几里得距离或切比雪夫距离，否则启发函数可能不再一致，路径质量会下降。

6.3 A* 搜索过慢怎么优化

如果迷宫尺寸很大，例如 200x200，A* 搜索节点数量会明显增加。可以尝试以下优化方式：

• 使用heapq的堆结构，这是目前代码中已经在用的方式。
• 对搜索过的节点做closed_set判断，避免重复入堆。
• 适当调大启发函数权重，例如使用f = g + 1.2 * h，可以加快搜索速度，但是不能保证严格最优。

6.4 迷宫生成不是随机的

递归回溯算法的随机性来自random.choice(unvisited)。如果每次运行结果都一样，可以检查代码开头是否调用了random.seed()。示例代码中未调用 seed，所以每次运行生成结果都不同。

7. 工程化建议：从“能跑”到“好用”

7.1 用配置文件管理参数

随着功能越来越多，把地图尺寸、颜色、帧率直接写在代码里会比较混乱。推荐把参数抽取到config.py中，统一管理。例如：

# 文件路径：p31_road_home/config.py # 窗口设置 SCREEN_WIDTH = 800 SCREEN_HEIGHT = 600 FPS = 30 # 迷宫设置 GRID_SIZE = 20 COLS = 25 ROWS = 20 # 颜色设置 WALL_COLOR = (40, 40, 40) ROAD_COLOR = (240, 240, 240) START_COLOR = (0, 200, 0) END_COLOR = (200, 0, 0) PATH_COLOR = (30, 120, 255) SEARCH_COLOR = (180, 220, 255)

这样后续需要调整地图大小或颜色时，只需要修改config.py，不需要动主逻辑。

7.2 增加日志与调试输出

在算法调试阶段，建议在关键节点输出日志。例如：

• 迷宫生成完毕后，统计路和墙的数量。
• A* 开始搜索前，输出起点、终点、迷宫尺寸。
• 搜索结束后，输出搜索节点数量、路径长度、耗时。

这样即使程序出现问题，也能快速判断是哪一步出了问题。

示例：

import time start_time = time.time() path = astar(maze.grid, start, end) end_time = time.time() print(f"A* 搜索耗时：{(end_time - start_time) * 1000:.2f} ms") print(f"搜索节点数：{len(search_history)}") print(f"路径长度：{len(path)}")

7.3 路径搜索的边界条件处理

在实际工程中，路径搜索的输入不一定总是合法。入口处必须有边界检查，包括：

• 起点和终点是否在边界内。
• 起点和终点是否为可以通行的路。
• 起点和终点是否相同。
• 迷宫数据是否为空或形状不一致。

7.4 性能优化思路

如果要在更大的地图上运行，可以进一步优化：

• 使用array模块或numpy存储迷宫数据，减少内存占用。
• 对closed_set使用二维布尔数组，而不是 Python 集合。
• 对g_score使用二维数组，避免字典哈希开销。
• 把搜索过程放在独立线程中，避免阻塞渲染循环。

不过对于演示项目来说，25x20 的地图已经足够展示算法效果，不需要过度优化。过度优化反而会降低代码可读性，不利于新手学习。

7.5 项目扩展方向

“P31：漫漫归途”是一个很好的算法练手项目，后续可以从以下几个方向继续扩展：

1. 增加用户交互：运行时用鼠标点击设置起点和终点。
2. 双人模式或人机对比：同时用 A* 和 BFS 寻路，对比搜索节点数量。
3. 导出地图：把生成的迷宫保存为图片或文本文件，供其他程序使用。
4. 不同迷宫生成算法：实现 Prim 算法、Kruskal 算法，对比生成效果。
5. 连续寻路：角色沿着路径平滑移动，模拟真实游戏中的 NPC 行走。

8. 总结与后续学习建议

到这里，“P31：漫漫归途”这个项目就完整跑通了。我们从零开始搭建了一个随机迷宫生成器，实现了 A* 最短路径搜索，并且通过 pygame 把整个流程可视化。项目代码虽然不长，但涉及数据结构、算法设计、可视化交互三个层面的内容，是一个比较完整的练手项目。

回顾一下关键收获：

• 理解了如何用二维数组表示迷宫地图。
• 掌握了递归回溯生成迷宫的原理和实现细节。
• 理解了 A* 算法的核心公式 f(n) = g(n) + h(n)。
• 学会了用堆结构维护待探索节点。
• 学会了用 pygame 渲染网格地图并展示搜索过程。

如果后续想继续深入，可以沿着两个方向走：一是研究更多寻路算法，例如 Dijkstra、JPS、双向 BFS，比较不同算法在不同地图上的性能差异；二是研究真实游戏引擎中的导航系统，比如 Unity 的 NavMesh、Godot 的 NavigationServer，找出从“网格寻路”到“任意多边形寻路”的演进逻辑。

最后分享一下我调试项目时的个人经验：写完一个算法模块后，不要急着写可视化代码，先用纯命令行输出验证核心逻辑，再叠加窗口渲染。这样一旦出问题，可以快速定位是算法问题还是渲染问题。强烈建议你也试试这种“先逻辑后界面”的开发习惯。如果本文对你有帮助，可以收藏备用，后续我会继续更新寻路算法相关的实战文章。