Python 中的 A* 算法在制定最终路径时遇到问题

问题描述 投票：0回答：1

我尝试编写 A* 寻路算法的代码，并使用 g 和 h 成本以正确的方式扩展它。

它看起来真的很酷，但是当我尝试使用从结束节点开始的递归找到最终路径时，在大多数情况下都是错误的。

我想知道这是 A* 还是我的代码的问题，因为当我发现其他人的算法代码时，它也有同样的问题。

我在 python 中使用 pygame 做了这个。

这是我的代码的相关部分（不包括大部分 pygame 交互）：

BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
PURPLE = (238, 130, 238)
pygame.init()
width = 1200
hight = 900
startNode = None
endNode = None
SCREEN = pygame.display.set_mode((width, hight), pygame.DOUBLEBUF)

class node:

   def __init__(self, pos, h_cost, g_cost, f_cost, Color):
       self.x = pos[0]
       self.y = pos[1]
       self.parent = None
       self.f_cost = f_cost
       self.g_cost = g_cost
       self.h_cost = h_cost
       self.pos = pos
       self.Color = Color

   def TraceBack(self):
       if self.parent != None:
           self.parent.Color = "BLUE"
           self.parent.TraceBack()

   def calG_cost(self, startNode):
       self.g_cost = math.sqrt((self.x - startNode.x) ** 2 + abs(self.y - startNode.y) ** 2)

   def calH_cost(self,endNode):
       self.h_cost = math.sqrt((self.x - endNode.x) ** 2 + abs(self.y - endNode.y) ** 2)

   def calF_cost(self,endNode,startNode):
       self.calG_cost(startNode)
       self.calH_cost(endNode)
       self.f_cost = self.g_cost + self.h_cost

grid = []

def checkIfDone(endNode):
   x = endNode.x
   y = endNode.y
   if grid[x + 1][y].Color == "PURPLE":
       return True

   if grid[x + 1][y + 1].Color == "PURPLE":
       return True
   if grid[x + 1][y - 1].Color == "PURPLE":
       return True
   if  grid[x - 1][y - 1].Color == "PURPLE":
       return True

   if grid[x - 1][y].Color == "PURPLE":
       return True

   if grid[x - 1][y + 1].Color == "PURPLE":
       return True

   if grid[x][y + 1].Color == "PURPLE":
       return True

   if grid[x][y - 1].Color == "PURPLE":
       return True
   return False



def findLowestFCost():
   lowest = math.inf
   lowestNode = None
   for row in grid:
       for node in row:
           if node.Color == "GREEN" and node.f_cost < lowest:
               lowest = node.f_cost
               lowestNode = node

   return lowestNode

def GenerateGrid():
   for x in range(100):
       grid.append([])
       for y in range(100):
           grid[x].append("")

   for y in range(len(grid[0]) ):
       for x in range(len(grid) ):
           grid[x][y] = node((x, y), 0, 0, 0, "")


def checkFound(parent):
   x = parent.x
   y = parent.y
   try:
       if grid[x + 1][y].Color == "RED": return True

       if grid[x + 1][y + 1].Color == "RED": return True

       if grid[x + 1][y - 1].Color == "RED": return True

       if grid[x - 1][y - 1].Color == "RED": return True

       if grid[x - 1][y].Color == "RED": return True

       if grid[x - 1][y + 1].Color == "RED": return True

       if grid[x][y + 1].Color == "RED": return True

       if grid[x][y - 1].Color == "RED": return True

   except:
       pass


def expandParent(parent):
   x = parent.x
   y = parent.y
   if grid[x + 1][y].Color == "" or grid[x + 1][y].Color == "GREEN":
       grid[x + 1][y].Color = "GREEN"

       if grid[x + 1][y].parent == None:
           grid[x + 1][y].parent = parent

       elif parent.f_cost < grid[x + 1][y].parent.f_cost:
           grid[x + 1][y].parent = parent

   if grid[x + 1][y + 1].Color == "" or grid[x + 1][y + 1].Color == "GREEN":
       grid[x + 1][y + 1].Color = "GREEN"

       if grid[x + 1][y + 1].parent == None:
           grid[x + 1][y + 1].parent = parent

       elif parent.f_cost < grid[x + 1][y + 1].parent.f_cost:
           grid[x + 1][y + 1].parent = parent

   if grid[x + 1][y - 1].Color == "" or grid[x + 1][y - 1].Color == "GREEN":
       grid[x + 1][y - 1].Color = "GREEN"

       if grid[x + 1][y - 1].parent == None:
           grid[x + 1][y - 1].parent = parent

       elif parent.f_cost < grid[x + 1][y - 1].parent.f_cost:
           grid[x + 1][y - 1].parent = parent

   if grid[x - 1][y - 1].Color == "" or grid[x - 1][y - 1].Color == "GREEN":
       grid[x - 1][y - 1].Color = "GREEN"

       if grid[x - 1][y - 1].parent == None:
           grid[x - 1][y - 1].parent = parent

       elif parent.f_cost < grid[x - 1][y - 1].parent.f_cost:
           grid[x - 1][y - 1].parent = parent

   if grid[x - 1][y].Color == "" or grid[x - 1][y].Color == "GREEN":
       grid[x - 1][y].Color = "GREEN"

       if grid[x - 1][y].parent == None:
           grid[x - 1][y].parent = parent

       elif parent.f_cost < grid[x - 1][y].parent.f_cost:
           grid[x - 1][y].parent = parent

   if grid[x - 1][y + 1].Color == "" or grid[x - 1][y + 1].Color == "GREEN":
       grid[x - 1][y + 1].Color = "GREEN"

       if grid[x - 1][y + 1].parent == None:
           grid[x - 1][y + 1].parent = parent

       elif parent.f_cost < grid[x - 1][y + 1].parent.f_cost:
           grid[x - 1][y + 1].parent = parent

   if grid[x][y + 1].Color == "" or grid[x][y + 1].Color == "GREEN":
       grid[x][y + 1].Color = "GREEN"

       if grid[x][y + 1].parent == None:
           grid[x][y + 1].parent = parent

       elif parent.f_cost < grid[x][y + 1].parent.f_cost:
           grid[x][y + 1].parent = parent

   if grid[x][y - 1].Color == "" or grid[x][y - 1].Color == "GREEN":
       grid[x][y - 1].Color = "GREEN"

       if grid[x][y - 1].parent == None:
           grid[x][y - 1].parent = parent

       elif parent.f_cost < grid[x][y - 1].parent.f_cost:
           grid[x][y - 1].parent = parent

   parent.Color = "PURPLE"

红色为结束节点，蓝色为最终路径，紫色为父节点。我看不到起始节点，因为它被覆盖了。我会在某个时候解决这个问题：

image of maze

在这里工作得更好：

image of better maze

python algorithm path-finding
1个回答
0
投票

主要问题之一是如何计算𝑔-成本：

   def calG_cost(self, startNode):
       self.g_cost = math.sqrt((self.x - startNode.x) ** 2 + abs(self.y - startNode.y) ** 2)

这计算了从起始节点到当前节点的距离“如乌鸦飞翔”，但是𝑔应该反映actual遍历的路径。我们通常不能仅从起始节点和当前节点知道这一点。这需要随着节点的扩大而递增累加，下一步加入𝑔成本。

另一个问题是

findLowestFCost
效率不高：它需要访问网格中的每个单元格。为此，A* 算法专为与优先级队列一起使用而设计。

expandParent
有非常相似的代码，重复了好几次。这可以用更好的方式完成。由于您已经在使用 
Node
类，为什么不在 
neighbors
属性中注册每个节点的邻居。这样你就可以在一个循环中迭代那个 
neighbors
集合。

这就是我在以下解决方案中所做的。请注意，它是基于文本的，没有与 pygame 集成。

from heapq import heappop, heappush

DIAGDIST = 2**0.5
# Define meaning of letters
WALL = "#"
START = "y"
END = "r"
NEW = "."
QUEUED = "?"
VISITED = ","
ONPATH = "B"

class Node:
    def __init__(self, pos, *neighbors):
        self.x, self.y = pos
        self.pos = pos
        self.color = NEW
        self.parent = None
        self.f_cost = self.g_cost = float("inf")
        # Define neighbor bi-directional relations 
        self.neighbors = set()
        for neighbor in neighbors:
            if neighbor:
                self.neighbors.add(neighbor)
                neighbor.neighbors.add(self)

    def minDistance(self, other):
        # minimum distance with legal steps when there would be no walls
        dx = abs(self.x - other.x)
        dy = abs(self.y - other.y)
        diag = min(dx, dy)
        straight = max(dx, dy) - diag
        return diag * DIAGDIST + straight

    # Make Node instances comparable; for use by a heap
    def __lt__(self, other):
        return (self.f_cost - other.f_cost or self.x - other.x or self.y - other.y) < 0
    
    def traceBack(self):
        node = self
        while node:
            node.color = ONPATH
            node = node.parent



class Maze:
    def __init__(self, pattern):
        pattern = pattern.replace(" ", "")  # Remove intermediate spaces
        lines = pattern.strip().splitlines()
        row = [None] * len(lines[0])
        self.startNode = self.endNode = None
        self.grid = []
        for x, line in enumerate(lines):
            left = None
            # Create a row of Nodes that are immediately connected to previously created neighbors
            #   Don't create Nodes for Walls.
            row = [left := Node((x, y), left, *row[max(0, y-1):y+2]) if ch != WALL else None 
                   for y, ch in enumerate(line)]
            self.grid.append(row)
            if not self.startNode:
                self.startNode = next((node for node, ch in zip(row, line) if ch == START), None)
            if not self.endNode:
                self.endNode = next((node for node, ch in zip(row, line) if ch == END), None)
    
    def __str__(self):
        return "\n".join([
            " ".join(node.color if node else WALL for node in row)
            for row in self.grid
        ])


    def aStarSearch(self):
        self.startNode.g_cost = 0
        self.startNode.f_cost = self.startNode.minDistance(self.endNode)
        heap = [self.startNode]
        while heap:
            node = heappop(heap)
            if node == self.endNode:  # found target
                node.traceBack()
                # Restore indications of start/end nodes
                self.startNode.color = "y"
                self.endNode.color = "r"
                return
            if node.color != VISITED:
                node.color = VISITED
                for neighbor in node.neighbors:
                    if neighbor.color != VISITED:
                        g_cost = node.g_cost + node.minDistance(neighbor)
                        if g_cost < neighbor.g_cost:
                            h_cost = neighbor.minDistance(self.endNode)
                            neighbor.g_cost = g_cost
                            neighbor.f_cost = g_cost + h_cost
                            neighbor.parent = node
                            neighbor.color = QUEUED
                            heappush(heap, neighbor)
            
            
# Example run (text-based, no pygame)
maze = Maze("""
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . # . . . . . . . . . . . . . . . . . . . . . . . .
. . . . # . . . . . . . . y . . . . . . . . . . . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # # # # # # # # # # # # # # # # # # # # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . # . . . . . . . . . . . . . . . . . . # . . . . .
. . . . . . . . . . . r . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
""")

maze.aStarSearch()
print(maze)

这输出：

. . ? ? , , , , , , , , , , , , , , , , , , ? ? . . . . .
. ? ? , , , , , , , , , , , , , , , , , , , , ? ? . . . .
? ? , , , , , , , , , , , , , , , , , , , , , , ? ? . . .
? , , , B B , , , , , , , , , , , , , , , , , , , ? ? . .
? , , B # , B , , , , , , , , , , , , , , , , , , , ? ? .
, , , B # , , B B B B B B y , , , , , , , , , , , , , ? .
, , , B # , , , , , , , , , , , , , , , , , , # , , , ? ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , , ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , ? ?
, , , B # , , , , , , , , , , , , , , , , , , # , , , ? .
, , , B # # # # # # # # # # # # # # # # # # # # , , ? ? .
, , , B # . . . . . . . . . . . . . . . . . . # , , ? . .
, , , B # . . . . . . . . . . . . . . . . . . # , , ? . .
? , , B # . . . . . . . . . . . . . . . . . . # , ? ? . .
? , , B # . . . . . . . . . . . . . . . . . . # , ? . . .
? , , B # . . . . . . . . . . . . . . . . . . # ? ? . . .
? ? , B # . . . . . . . . . . . . . . . . . . # . . . . .
. ? , B # . . . . . . . . . . . . . . . . . . # . . . . .
. ? ? B # . . . . . . . . . . . . . . . . . . # . . . . .
. . ? B # . . . . . . . . . . . . . . . . . . # . . . . .
. . ? B # ? ? ? ? ? ? ? . . . . . . . . . . . # . . . . .
. . ? ? B B B B B B B r . . . . . . . . . . . . . . . . .
. . . ? ? ? ? ? ? ? ? ? . . . . . . . . . . . . . . . . .
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.