python - 我的 A* 寻路算法并不总是能得到最短路径

Question

提前感谢您的帮助。

我正在 pygame 中使用 python 制作探路者可视化工具。我尝试过制作A*算法，但有时它找不到最短路径。我一直在浏览之前的几个关于同一问题的问题，这使我相信这可能是启发式的问题。如果我将 Hueristic 值设置为 0，则该算法将变为 dijkstra 算法并始终获得最短路径。

该算法使用网格，x 是数字行，y 是数字列(我相信可能是相反的方式，但这并不重要)

网格上的每个方 block 都是一个对象，具有 x 和 y 值，以及 gScore、hScore 和 fScore。初始化时，这些都设置为“无”。

我在底层还有一些函数来做计算，比如从数组中找到最低的fScore节点，找到gScore，找到hScore，fScore并获取两个网格方 block 之间的距离。

我认为问题出在色调函数上，并尝试了多种不同的修复方法，但均无济于事。通过查看下面的代码，任何人都能够看到问题，或者指出我正确的方向吗？非常感谢任何帮助。

为了简单起见，我只包含了 A* 函数，没有任何 pygame 的东西，但如果需要的话我可以添加整个程序，包括 gridsquare 对象。

def a_star():

    for row in grid:
        for square in row:
            if square.state == "start_pos":
                start_pos = square

            elif square.state == "end_pos":
                end_pos = square


    start_pos.gScore = find_g(start_pos, start_pos)
    start_pos.hScore = find_h(start_pos, end_pos)
    start_pos.fScore = find_f(start_pos.gScore, start_pos.hScore)


    openList = [start_pos]
    closedList = []


    while len(openList) > 0:

        current_node = get_lowest_f_node(openList)

        if current_node.state == "end_pos":
            print("found")

            path = [end_pos]
            node = current_node
            while node.parent != None:
                time.sleep(SHORTEST_PATH_DELAY)
                node = node.parent
                path.append(node)
            return

        openList.remove(current_node)
        closedList.append(current_node)


        x = current_node.x
        y = current_node.y

        # get nodes around current node
        node1 = grid[x][y - 1]
        node2 = grid[x][y + 1]
        node3 = grid[x - 1][y]
        node4 = grid[x + 1][y]

        successor_nodes = [node1, node2, node3, node4]

        for node in successor_nodes:

            # check if walkable
            if (node.state == "wall") or (node in closedList):
                continue


            if node.gScore == None:
                node.gScore = current_node.gScore

            tentative_g_score = current_node.gScore + get_distance(node, current_node)

            if (node in closedList) and (tentative_g_score >= node.gScore):
                continue

            if (node not in openList) or (tentative_g_score < node.gScore):
                node.parent = current_node
                node.gScore = tentative_g_score
                node.fScore = node.gScore + find_h(node, end_pos)
                if node not in openList:
                    openList.append(node)






def get_lowest_f_node(array):
    min_f = min(array, key = attrgetter("fScore"))
    return min_f


# distance from current node and start node
def find_g(current, start_pos):
    g = get_distance(current, start_pos)
    return g


# distance from current node and target / destination / finish node
def find_h(current, end_pos):
    h = get_distance(current, end_pos)
    return h


# hscore and gscore added together
def find_f(score1, score2):
    return score1 + score2


# distance from 2 points
def get_distance(start, end):
    x1 = start.x
    y1 = start.y
    x2 = end.x
    y2 = end.y
    distancex = sqr(x2 - x1)
    distancey = sqr(y2 - y1)
    #distance = sqrt(distancex + distancey)
    distance = distancex + distancey
    return distance

def sqr(number):
    return number * number

下面是路径查找结果的一些图像，具有不同的模式。起始节点始终是底部的红色方 block 。

^^^ 这是 A* 算法找到正确的最短路径的地方。一切都好。

^^^这是A*找到一条路径的地方，但它不是最短路径。这就是我正在尝试解决的问题，非常感谢任何帮助。

^^^ 这是迪杰斯特拉在面对相同的墙壁排列时找到正确的路径。

我非常感谢您的帮助。

Answer 1

<====下载此图片

我不是 A* 方面的专家，但有一段时间我为要制作的 YouTube 视频编写了脚本。

如果您想要它，就在这里:https://pastebin.com/WycrpAfZ

您也可以在这里查看:

import math, random, sys
import pygame
from pygame.locals import *

# exit the program
def events():
    for event in pygame.event.get():
        if event.type == QUIT or (event.type == KEYDOWN and event.key == K_ESCAPE):
            pygame.quit()
            sys.exit()

# define display surface            
W, H = 1920, 1080
HW, HH = W / 2, H / 2
AREA = W * H

# initialise display
pygame.init()
pygame.font.init()
CLOCK = pygame.time.Clock()
FONT_SMALL = pygame.font.Font(None, 26)
FONT_LARGE = pygame.font.Font(None, 50)
DS = pygame.display.set_mode((W, H))
pygame.display.set_caption("code.Pylet - Template")
FPS = 1

# define some colors
BLACK = (0, 0, 0, 255)
WHITE = (255, 255, 255, 255)
RED = (255, 0, 0, 255)
GREEN = (0, 128, 0, 255)
BLUE = (0, 0, 255, 255)
PURPLE = (255, 255, 0, 255)

# define node class
class node:
    def __init__(self, x, y, obstacle):
        self.x = x
        self.y = y
        self.pos = (x, y)
        self.h = 0
        self.g = 0
        self.f = 0
        self.obstacle = obstacle
        self.other = None
        self.parent = None

    def neighbourPos(self, offset):
        return (self.x + offset[0], self.y + offset[1])

    def draw(self, size, color = None, id = None, surface = None):
        global text, FONT_SMALL, FONT_LARGE
        if not surface: surface = pygame.display.get_surface()
        pos = (self.x * size[0], self.y * size[1])
        if not color:
            if not self.obstacle:
                if not self.other: pygame.draw.rect(surface, BLACK, pos + size, 0)
                else: pygame.draw.rect(surface, BLUE, pos + size, 0)
            else:
                pygame.draw.rect(surface, WHITE, pos + size, 0)
        else:
            pygame.draw.rect(surface, color, pos + size, 0)
        pygame.draw.rect(surface, WHITE, pos + size, 1)
        if self.f:
            text(FONT_SMALL, "G:{0}".format(self.g), pos[0] + 5, pos[1] + 5, 0, 0, surface)
            text(FONT_SMALL, "H:{0}".format(self.h), pos[0] + size[0] - 5, pos[1] + 5, 1, 0, surface)
            text(FONT_LARGE, "F:{0}".format(self.f),  pos[0] + size[0] / 2, pos[1] + size[1] / 2 , 2, 2, surface)
            if not id == None:
                text(FONT_SMALL, "{0}".format(id), pos[0] + 5, pos[1] + size[1] - 5, 0, 1, surface)


def drawNodes(n, ms, cs):
    for x in range(ms[0]):
        for y in range(ms[1]):
            n[x][y].draw(cs)

def drawNodeList(node_list, cs, color):
    id = 0
    for n in node_list:
        n.draw(cs, color, id)
        id += 1

def heuristics(pos1, pos2):
    return int(math.hypot(pos1[0] - pos2[0], pos1[1] - pos2[1]) * 10)

def text(font, string, x, y, xJustify = None, yJustify = None, surface = None):
    global WHITE
    if not surface: surface = pygame.display.get_surface()
    textSurface = font.render(string, 1, WHITE)
    textRect = textSurface.get_rect()
    if xJustify == 1:
        x -= textRect.width
    elif xJustify == 2:
        x -= textRect.center[0]
    if yJustify == 1:
        y -= textRect.height
    elif yJustify == 2:
        y -= textRect.center[1]
    surface.blit(textSurface, (x, y))

map = pygame.image.load("test.png").convert()
map_size = map_width, map_height = map.get_rect().size
cell_size = (W / map_width, H / map_height)

#create list of nodes
nodes = list([])
for x in range(map_width):
    nodes.append(list([]))
    for y in range(map_height):
        color = map.get_at((x, y))
        if color != WHITE:
            nodes[x].append(node(x, y, False))
            if color == BLUE:
                start = nodes[x][y]
                start.other = True
            elif color == RED:
                end = nodes[x][y]
                end.other = True
        else:
            nodes[x].append(node(x, y, True))


# This list contains relative x & y positions to reference a node's neighbour 
NEIGHBOURS = list([(-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0)])           




# the closed list contains all the nodes that have been considered economical viable.
# By that I mean a node that has been closer to the end node than any other in the open list at one time
closed = list([])

# The open list contains all the closed list's neighbours that haven't been identified as being economically sound node yet
open = list([])
open.append(start) # add the start node so that we can then add it's neighbours



# if the algorithm finds the end node then pathFound will be true otherwise it's false. 
# Once it becomes true there's no more calculations to do so the path finding script will be skipped over
pathFound = False
completedPath = list([]) # 

# main loop
while True:
    DS.fill(BLACK)  
    drawNodes(nodes, map_size, cell_size)
    drawNodeList(open, cell_size, GREEN)
    drawNodeList(closed, cell_size, RED)
    if pathFound: drawNodeList(completedPath, cell_size, PURPLE)
    pygame.display.update()

    # wait for user to press mouse button
    while not pygame.mouse.get_pressed()[0]:
        events()
    while pygame.mouse.get_pressed()[0]:
        events()

    # if we've found the quickest path from start node to end node then just draw, no need continue path finding
    if pathFound: continue
    if not open: continue


    # get lowest f from the open list, the node with the lowest f is the most economical in terms of the path towards the end node
    openNodeWithlowestF = open[0]
    for o in open:
        if  o.f < openNodeWithlowestF.f: openNodeWithlowestF = o

    mostEconomicalNodeSoFar = openNodeWithlowestF # let's make this more readable! Economical means the best path to the end given the choices but not definitive.

    # remove the mostEconomicalNodeSoFar from the open list
    open.remove(mostEconomicalNodeSoFar)
    # add mostEconomicalNodeSoFar to the closed list
    closed.append(mostEconomicalNodeSoFar)

    # if the mostEconomicalNodeSoFar is equal to the end node then we've reach our target
    if mostEconomicalNodeSoFar == end:
        temp = end
        while temp.parent:
            completedPath.append(temp)
            temp = temp.parent
        completedPath.append(start)
        pathFound = True
        # get the path etc

    # iterate through the list of neighbours belonging to the mostEconomicalNodeSoFar. Why?
    for neighbourOffset in NEIGHBOURS:
        nx, ny = mostEconomicalNodeSoFar.neighbourPos(neighbourOffset)

        if nx < 0 or nx >= map_width or ny < 0 or ny >= map_height: continue
        neighbour = nodes[nx][ny] # create a variable to represent the mostEconomicalNodeSoFar's neighbour
        if neighbour.obstacle: continue # if the mostEconomicalNodeSoFar's neighbouring node is an obstacle then we can't ...?
        if neighbour in closed: continue # if the mostEconomicalNodeSoFar's neighbouring node is in the closed list then we can't ...?

        # now we need to see if the mostEconomicalNodeSoFar's neighbour is more economical ...?
        hypotheticalFScore = mostEconomicalNodeSoFar.g + heuristics(neighbour.pos, mostEconomicalNodeSoFar.pos)
        NeighbourIsBetterThanMostEconomicalNodeSoFar = False # Yes it's a long variable name but it describes what it is so all is good!

        # is this neighbour already in open list? if it is then we don't want to be adding it again. to chec
        if not neighbour in open:
            NeighbourIsBetterThanMostEconomicalNodeSoFar = True
            neighbour.h = heuristics(neighbour.pos, end.pos)
            open.append(neighbour)
        elif hypotheticalFScore < neighbour.g:
            NeighbourIsBetterThanMostEconomicalNodeSoFar = True

        if NeighbourIsBetterThanMostEconomicalNodeSoFar:
            neighbour.parent = mostEconomicalNodeSoFar
            neighbour.g = hypotheticalFScore
            neighbour.f = neighbour.g + neighbour.h
    #sys.exit()