Python迷宫构建打印实现优化及寻路适配数据结构咨询

一、现有实现的优化方案 #

你的现有代码可正常运行，但存在几个提升效率与可维护性的优化点：

1. 修正类属性与实例属性混淆问题 #

原代码中board、max_x、max_y为类属性，会被所有Maze实例共享，多实例场景下会互相干扰。需改为实例属性，在__init__中初始化：

class Maze:
    def __init__(self):
        self.board = []
        self.max_x = 2
        self.max_y = 2
        # 原代码中未使用的list属性可删除

2. 优化动态扩容逻辑 #

原代码每次扩容都需创建新二维列表并复制旧数据，频繁扩容时效率低下。可改用字典存储非默认坐标（默认墙体为1，仅记录通路0的坐标），打印时再生成完整网格：

class Maze:
    def __init__(self):
        self.open_coords = set()  # 存储所有通路坐标(x,y)
        self.max_x = 2
        self.max_y = 2

    def addCoordinate(self, x, y, blockType):
        if x > self.max_x:
            self.max_x = x
        if y > self.max_y:
            self.max_y = y
        if blockType == 0:
            self.open_coords.add((x, y))
        else:
            self.open_coords.discard((x, y))  # 若之前为通路则移除

3. 修正printMaze的坐标遍历错误 #

原代码存储逻辑为board[y][x]，但打印时循环顺序错位，导致迷宫显示异常。同时适配Python3的print语法：

def printMaze(self):
    # 遍历y轴（行）
    for y in range(self.max_y + 1):
        row = []
        # 遍历x轴（列）
        for x in range(self.max_x + 1):
            row.append(" " if (x, y) in self.open_coords else "*")
        print(" ".join(row))

4. 其他小优化 #

• 移除未使用的冗余属性；
• 可在addCoordinate中加入坐标合法性检查（如x、y不能为负数）；
• 若提前知晓迷宫最大尺寸，初始化时直接创建固定大小的board，避免动态扩容。

二、寻路算法适配的数据结构 #

除二维列表外，以下数据结构更适配寻路场景：

1. 集合（set） #

• 用途：存储墙体或通路坐标，判断(x,y)是否可通行的时间复杂度为O(1)，远快于二维列表的遍历查询；
• 示例：wall_coords = {(0,0), (0,1)}，寻路时只需判断(x,y) not in wall_coords即可快速确认通行状态。

2. 字典（dict） #

• 用途：在BFS/DFS/A*算法中记录节点的父节点、累计代价、启发式值等信息，用于路径回溯或代价计算；
• 示例：parent = {(1,0): None, (1,1): (1,0)}（记录父节点用于回溯路径），g_score = {(1,0): 0, (1,1): 1}（记录起点到节点的实际代价）。

3. 优先队列（heapq） #

• 用途：A*算法中需按f_score = 实际代价 + 启发式代价的优先级取出节点，Python的heapq模块实现的最小堆可完美适配；
• 示例：

import heapq
open_heap = []
heapq.heappush(open_heap, (f_score, x, y))

4. 邻接表 #

• 用途：若迷宫为稀疏结构（通路占比低），邻接表仅存储每个通路节点的相邻可通行节点，节省空间且遍历邻居更高效；
• 示例：adjacency = {(1,0): [(1,1)], (1,1): [(1,0), (1,2)]}，键为通路节点，值为其上下左右的可通行节点列表。

内容的提问来源于stack exchange，提问作者dev_neil