路径寻路算法网格生长耗时久易崩溃，求高效迭代优化方案

我的路径寻路算法中“生长网格”操作耗时极长，有时甚至直接崩溃，想知道怎么实现更高效的迭代。目前还未实现跳过墙体方块、计算（代价*距离）的数值，这也是功能不完善的原因。试过添加break语句，但问题仍未解决。

以下是我的代码：

#add all x and y axis coordinates to arrays
def CreateGridCoordinates():
    x = 0
    for i in range(0, 24):
        gridXCoordinates.append(x)
        gridYCoordinates.append(x)
        x+=20;

CreateGridCoordinates()

#get grid coordinates and create black wall
def GetGridCoordinatesIndexAndCreateWall():
    #get mouse location
    mousex, mousey = pygame.mouse.get_pos()
    for y in range(0, 24):
        for x in range(0, 24):
            #check each square for mouse location
            if mousex >= gridXCoordinates[x] and mousex <= (gridXCoordinates[x] + gridXCoordinates[1]) and mousey >= gridYCoordinates[y] and mousey <= (gridYCoordinates[y] + gridYCoordinates[1]):
                #create wall cell and paint it black
                wallCell = GridCell(black)
                wallCell.rect.x = gridXCoordinates[x]
                wallCell.rect.y = gridXCoordinates[y]
                wallCells.add(wallCell)

    global wallCellsBool
    wallCellsBool = True

#create backdrop grid
def CreateCells():
    cellX = 0
    cellY = 0
    for i in range(0, 24):
        for e in range(0, 24):
            cell = GridCell(grey)
            cell.rect.x = cellX
            cell.rect.y = cellY
            bgCells.add(cell)
            cellX+=20
        cellY+=20
        cellX = 0
        
    return bgCells

pathFinderCellX = 0
pathFinderCellY = 0

#create start cell
startCell = GridCell(pink)
startCell.rect.x = pathFinderCellX
startCell.rect.y = pathFinderCellY
pathFinderCells.add(startCell)

#create end cell
endCell = GridCell(green)
endCell.rect.x = gridXCoordinates[23]
endCell.rect.y = gridYCoordinates[23]
finishCell.add(endCell)

#create path finder cell
def CreatePathFinderCell(x, y):
    global pathFinderCellX, pathFinderCellY
    pathFinderCell = GridCell(pink)
    pathFinderCellX+=x
    pathFinderCellY+=y
    pathFinderCell.rect.x = pathFinderCellX
    pathFinderCell.rect.y = pathFinderCellY
    pathFinderCells.add(pathFinderCell)

#decide where pathfinder should be created
def MovePathFinder(direction):
    if direction == "up":
        print("up")
        CreatePathFinderCell(0, -cellSpace)
    elif direction == "down":
        print("down")
        CreatePathFinderCell(0, cellSpace)
    elif direction == "left":
        print("left")
        CreatePathFinderCell(-cellSpace, 0)
    elif direction == "right":
        print("right")
        CreatePathFinderCell(cellSpace, 0)

#save distance and cost of movement

growthCellX = 0
growthCellY = 0

boolCellGrowth = False

def CheckFinish(x, y):
    for finishcell in finishCell:
        if finishcell.rect.x != x and finishcell.rect.y != y:
            boolCellGrowth = False
            break

def CheckWallAndBounds(x, y):
    if wallCellsBool == True:
        for wallcell in wallCells:
                if wallcell.rect.x != x and wallcell.rect.y != y:
                    return True
                else:
                    return False

def DontReplace(x, y):
    for growthcell in growthCells:
        if growthcell.rect.x == x and growthcell.rect.y == y:
            return True
        else:
            return False

#create growth cells
def CreateNewGrowthCell(x, y): 
    if CheckWallAndBounds(x, y) == True or DontReplace(x, y) == True:
        growthCell = GridCell(lightPink)
        growthCell.rect.x = x
        growthCell.rect.y = y
        growthCells.add(growthCell)
        #calculate distance from growth to finish
        #calculate distance from start to growth
    
complete = True

def CellGrowthByOne():
    global complete
    for e in growthCells:
        #from each cell create 8 surrounding cells
        growthSpaceX = e.rect.x
        growthSpaceY = e.rect.y
        CreateNewGrowthCell(growthSpaceX, (growthSpaceY - 20))
        CreateNewGrowthCell((growthSpaceX - 20), (growthSpaceY - 20))
        CreateNewGrowthCell((growthSpaceX - 20), growthSpaceY)
        CreateNewGrowthCell((growthSpaceX - 20), (growthSpaceY + 20))
        CreateNewGrowthCell(growthSpaceX, (growthSpaceY + 20))
        CreateNewGrowthCell((growthSpaceX + 20), (growthSpaceY + 20))
        CreateNewGrowthCell((growthSpaceX + 20), growthSpaceY)
        CreateNewGrowthCell((growthSpaceX + 20), (growthSpaceY - 20))

优化方案 #

• 用哈希集合替代遍历检查：把growthCells的坐标存入set（比如visited = set()），生成新单元格前直接判断(x,y) in visited，时间复杂度从O(n)降到O(1)；墙体坐标也提前存入wall_coords = set()，检查墙体时直接判断坐标是否在集合里，避免遍历整个wallCells。
• 修复CheckWallAndBounds逻辑错误：当前函数逻辑完全颠倒，正确逻辑是先判断坐标是否在网格边界内，再判断是否是墙体。如果是墙体或超出边界，返回False（不可生成），否则返回True。示例：

  def CheckWallAndBounds(x, y):
      # 先检查边界
      if x < 0 or x > gridXCoordinates[-1] or y <0 or y > gridYCoordinates[-1]:
          return False
      # 检查墙体
      return (x, y) not in wall_coords
  

• 改用BFS队列控制生长：CellGrowthByOne现在每次遍历所有已生成的生长单元格，导致重复处理旧单元格。改用队列存储待扩展的单元格，每次只处理当前队列中的单元格，生成新单元格后加入队列，避免重复操作：

  from collections import deque
  
  growth_queue = deque()
  # 初始化时把起点加入队列
  growth_queue.append((pathFinderCellX, pathFinderCellY))
  visited.add((pathFinderCellX, pathFinderCellY))
  
  def CellGrowthByOne():
      current_level_size = len(growth_queue)
      for _ in range(current_level_size):
          x, y = growth_queue.popleft()
          # 遍历8个方向
          directions = [(0,-20), (-20,-20), (-20,0), (-20,20), (0,20), (20,20), (20,0), (20,-20)]
          for dx, dy in directions:
              new_x = x + dx
              new_y = y + dy
              if CheckWallAndBounds(new_x, new_y) and (new_x, new_y) not in visited:
                  visited.add((new_x, new_y))
                  growthCell = GridCell(lightPink)
                  growthCell.rect.x = new_x
                  growthCell.rect.y = new_y
                  growthCells.add(growthCell)
                  growth_queue.append((new_x, new_y))
                  # 检查是否到达终点
                  if (new_x, new_y) == (endCell.rect.x, endCell.rect.y):
                      # 停止生长逻辑
                      return
  

• 重构网格状态存储：不要依赖Sprite集合判断单元格状态，用二维数组或字典记录网格的每个位置状态（0=空地，1=墙体，2=已访问），比如grid = [[0 for _ in range(24)] for _ in range(24)]，设置墙体时直接修改grid[y_idx][x_idx] = 1，检查时直接访问数组，速度远快于遍历Sprite。
• 实现A*算法的代价计算：如果要计算（代价距离），可以引入A核心逻辑：每个单元格记录g（起点到当前的移动代价，比如横向/纵向移动代价10，斜向14）、h（到终点的曼哈顿距离或欧几里得距离），f = g + h，用优先队列（堆）每次扩展f值最小的单元格，避免盲目生长，大幅提升路径搜索效率。
• 修复CheckFinish函数：当前函数逻辑混乱，应该直接判断坐标是否等于终点坐标，返回布尔值：

  def CheckFinish(x, y):
      return (x == endCell.rect.x) and (y == endCell.rect.y)
  

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