A* 寻路算法有时找不到路径，即使有一个 (Python)

Question

我在Python中制作了自定义路径A*寻路算法，但有时即使明明有路径，它也找不到到末端节点的路径。这是我的实现。

# this is my Node class. I am representing the whole maze as a matrix and every cell
# of that matrix is a Node Object

class Node():
    def __init__(self, i, j):
        self.i = i
        self.j = j
        self.isWall = False
        self.isOpen = None
        self.f = 0
        self.g = 0
        self.h = 0
        self.neighbors = []
        self.previous = None

    def __repr__(self):
        return f'< i = {self.i}, j = {self.j}, previous = {self.previous} >'

    def add_neighbors(self, grid, diagonal):
        i = self.i
        j = self.j

        if i > 0:
            self.neighbors.append(grid[i - 1][j])

        if i < len(grid) - 1:
            self.neighbors.append(grid[i + 1][j])


        if j > 0:
            self.neighbors.append(grid[i][j - 1])

        if j < len(grid) - 1:
            self.neighbors.append(grid[i][j + 1])

        if diagonal:
            # for diagonal neighbors

            # down and right
            if i < len(grid) - 1 and j < len(grid) - 1:
                self.neighbors.append(grid[i + 1][j + 1])

            # up and right
            if i > 0 and j < len(grid) - 1:
                self.neighbors.append(grid[i - 1][j + 1])

            #down and left
            if i < len(grid) - 1 and j > 0:
                self.neighbors.append(grid[i + 1][j - 1])

            #up and left
            if i > 0 and j > 0:
                self.neighbors.append(grid[i - 1][j - 1])

遍历并设置节点

def make_grid(length):
    main_grid = []
    for i in range(length):
        lst = []
        
        for j in range(length):
            node = Node(i, j)

            # 30 % chance that the current node will be set as a wall
            if random.randrange(1, 101) > 70 and i != 0 and j != 0: node.isWall = True

            lst.append(node)

        main_grid.append(lst)


    for i in range(length):
        for j in range(length):
            main_grid[i][j].add_neighbors(main_grid, diagonal = True)
 

    return main_grid

# Below is how the above function 'make_grid' is called

# making the grid
grid_len = 25
main_grid = make_grid(grid_len)
path = [] # to reconstruct the optimal path

下面是我正在使用的 HScore 函数

# HScore function

def getHScore(node, endNode):
    return sqrt(abs(node.i - endNode.i)**2 + abs(node.j - endNode.j)**2)

下面是实际的算法实现

# A* PATHFINDING ALGORITHM

def aStar(start_node, end_node):
    # node.f = node.g + node.h
    # node.g = distance of current node from the starting node
    # node.h = distance of current node from the end node

    start_node.g = 0
    start_node.h = getHScore(start_node, end_node)
    start_node.f = start_node.g + start_node.h
    open_set = [start_node]
    closed_set = []

    if start_node.isWall:
        print("The start node is a wall")
        return

    while True:
        
        if len(open_set) < 1:
            print('No Solutions Found')
            break

        current_node = open_set[0]

        for node in open_set:
            if node.f < current_node.f:
                current_node = node
                current_node.isOpen = True

        # print(f'current_node = {current_node.i, current_node.j}', end = " ")

        if current_node == end_node:
            temp = end_node
            path.append(temp)

            while temp.previous is not None:
                path.append(temp.previous)
                temp = temp.previous

            print("DONE")
            colorFinalPath(main_grid)
            break

        # current_node.isPath = True
        current_node.isOpen = False

        open_set.remove(current_node)
        closed_set.append(current_node)

        for neighbor in current_node.neighbors:
            # assuming 1 as the distance btw two neighbouring points that aren't diagonally
            # neighbors

            # need to add 1.14 if neighbor is diagonal. add propery to node class to check if neighbor is diagonal

            if neighbor in closed_set:
                continue

            tempG = current_node.g + getHScore(current_node, neighbor)

            if neighbor not in open_set and not neighbor.isWall:
                neighbor.g = tempG
                open_set.append(neighbor)
                neighbor.isOpen = True
                neighbor.previous = current_node

            if tempG >= neighbor.g:
                continue # there is no better path
            
            # neighbor was found in the open set, so we check if we can get to it in 
            # a better way as tempG is now less than neighbor.g

            neighbor.previous = current_node
            neighbor.g = tempG
            neighbor.h = getHScore(neighbor, end_node)
            neighbor.f = neighbor.g + neighbor.h

        show_steps(main_grid, start_node, end_node)

一些屏幕截图在第三张图中，起始节点（左上）和结束节点（右下）之间显然有一条路径，但没有找到任何解决方案。

请告诉我我的实现有什么问题。感谢任何帮助

Answer 1

我在这段代码中发现了一些问题：

tempG = current_node.g + getHScore(current_node, neighbor)

if neighbor not in open_set and not neighbor.isWall:
    neighbor.g = tempG
    open_set.append(neighbor)
    neighbor.isOpen = True
    neighbor.previous = current_node

if tempG >= neighbor.g:
    continue # there is no better path

当邻居是墙时，你应该立即跳过它。所以在顶部添加：
```
  if neighbor.isWall:
      continue
```
这也意味着您可以从您已经拥有的 if
中删除墙壁检查
检查没有更好路径的条件在您第一次设置 g 组件时也将为真，即在执行中间部分时。这不应该发生。因此，将 if 更改为 elif:
```
  if neighbor not in open_set:
       # ... etc ...
  elif tempG >= neighbor.g:
      continue # there is no better path
```
您的 make_grid 代码可以将结束节点标记为墙。您不拒绝这种情况，然后您的代码将 continue 并跳过它作为邻居以放入开放集中。从您的图像中不清楚是否发生了这种情况，因为您将结束节点涂成了蓝色。

那么问题不大，但有时您会为同一个节点多次调用 getHScore。显然，该函数将为每个调用 return 相同的值。所以你可以对此进行改进。例如，通过在 if 条件下移动该行：

if neighbor.h == 0:
    neighbor.h = getHScore(neighbor, end_node)

我不知道这是否是有意为之，但对角线步的成本为 2 (1²+1²)，并且与步行 2 步到同一个广场相比没有任何优势。这是一个很小的细节，因为您将首先通过对角线步骤访问这些节点，然后忽略具有相同成本的路径。

A* 寻路算法有时找不到路径，即使有一个 (Python)

A* path finding algo sometimes doesn't find path even when there is one (Python)

python

algorithm

path-finding

a-star