始终获得与 A* 实现相同的路径

Question

我正在尝试从来自维基百科的伪代码实现A*，但是我得到了一些奇怪的结果。

该实现找到了乍一看看起来不错的路径，但进一步观察它总是产生相同的路径！

有人能发现什么问题吗？该代码是用 python 3.1 编写的，并使用 pygame。

import pygame
import sys, traceback
import random
import math

TILE_WIDTH =  30
TILE_HEIGHT = 30
NUM_TILES_X = 30
NUM_TILES_Y = 30
NUM_TILES = NUM_TILES_X * NUM_TILES_Y
GRID_WIDTH = TILE_WIDTH * NUM_TILES_X
GRID_HEIGHT = TILE_HEIGHT * NUM_TILES_Y



# h(x,y)
def heuristic_dist(source,dest):
    return int(( (source.x - dest.x)**2 + (source.y - dest.y)**2 ) **0.5)

def a_star(nodes,start,goal):

     # Set up data structures
     closedset = []
     openset = [start]
     came_from={}
     g_score = {}
     g_score[start.index] = 0
     h_score = {}
     h_score[start.index] = heuristic_dist(start,goal)
     f_score = {}
     f_score[start.index] = h_score[start.index]


     while len(openset) > 0:

        # Find node with least f_score in openset
        x = min(openset,key=lambda el:f_score[el.index])


        # We have reached our goal!
        if x.index == goal.index:

            path = reconstruct_path(came_from,goal.index)

            # Mark the path with green color
            for node in path:
                nodes[node].color=(0,255,0)
            print( "Yihaaa!" )
            return True

        # Filter out x from openset and add it to closedset
        openset = list(filter(lambda y:y.index!=x.index,openset))
        closedset.append(x)
        # Go through all neighbours
        for y in x.get_neighbours():

            # If this neighbour has been closed, skip it
            if y in closedset: continue

            # Not sure that this is correct.
            tentative_g_score = g_score[x.index] + heuristic_dist(x,y)

            if y not in openset:
                openset.append(y)
                tentative_is_better = True
            elif tentative_g_score < g_score[y.index]:
                 tentative_is_better = True
            else:
                tentative_is_better = False
            if tentative_is_better:
                if y.index in came_from:
                    if f_score[x.index] < f_score[came_from[y].index]:
                        came_from[y.index] = x
                else:
                    came_from[y.index] = x
                g_score[y.index] = tentative_g_score
                h_score[y.index] = heuristic_dist(y, goal)
                f_score[y.index] = g_score[y.index] + h_score[y.index]
     print("Couldn't find a path!")
     return False





# Traverse the path backwards
def reconstruct_path(came_from,current_node,depth=0):
    if current_node in came_from:
        p = reconstruct_path(came_from,came_from[current_node].index)
        return p + [current_node]
    else:
        return [current_node]



def draw_string(surface,string,x,y):
    s = font.render(string,True,(0,0,0))
    surface.blit(s,(x,y))

# Tile or Node that has a cuple of attributes: color, cost and x,y
class Tile:
    def __init__(self,x,y,cost,index):
        self.x=x
        self.y=y
        self.cost=cost
        self.index=index
        self.color = (255,255,255)
    def draw(self,surface):
        surface.fill(self.color,pygame.Rect(self.x*TILE_WIDTH,self.y*TILE_HEIGHT,TILE_WIDTH,TILE_HEIGHT))
        pygame.draw.rect(surface,(255, 180, 180),pygame.Rect(self.x*TILE_WIDTH,self.y*TILE_HEIGHT,TILE_WIDTH,TILE_HEIGHT),2)
        draw_string(surface,str(self.cost),self.x*TILE_WIDTH+TILE_WIDTH//3,self.y*TILE_HEIGHT+TILE_HEIGHT//3)
    def get_neighbours(self):
        nbs = []
        # Where are our neighbours?
        offsets = [(0,-1),(-1,0),(1,0),(0,1)]
        for offset in offsets:
            x = self.x + offset[0]
            y = self.y + offset[1]
            try: # coord_to_tile throws exception if no such neighbour exists (out of bounds for example)
                nbs.append(coord_to_tile(x,y))
            except Exception as e:
                pass
        return nbs
    def __eq__(self,other):
        return self.x == other.x and self.y==other.y




# Small helper function to convert x,y coords to a tile instance
nodes_lookup={}
def coord_to_tile(x,y):
    return nodes_lookup[(x,y)]

def main():
    global nodes_lookup

    screen = pygame.display.set_mode((GRID_WIDTH, GRID_HEIGHT))


    tiles = []
    for x in range(NUM_TILES_X):
        for y in range(NUM_TILES_Y):
            # Create a random distribution where max grows
            cost = random.randint(1,min(x*y,98)+1)

            # Let the bottom line cost 1 as well
            if y == NUM_TILES_Y-1: cost = 1

            t = Tile(x,y,cost,len(tiles))
            nodes_lookup[(x,y)] = t
            tiles.append(t)


    # Do a*
    a_star(tiles,tiles[0],tiles[len(tiles)-1])



    while True:
        event = pygame.event.wait()
        if event.type == pygame.QUIT:
            break

        for tile in tiles:
            tile.draw(screen)

        pygame.display.flip()


pygame.init()
font = pygame.font.SysFont("Times New Roman",18)
try:
    main()
except Exception as e:
    tb = sys.exc_info()[2]
    traceback.print_exception(e.__class__, e, tb)
pygame.quit()

我真的不知道，因为我认为我已经基本上逐条语句地实现了伪代码。

这也是一个屏幕截图： http://andhen.mine.nu/uploads/astar.dib

谢谢！

Answer 1

您可以使用 y 按时访问 came_from，并使用 y.index 访问

     if tentative_is_better:
            if y.index in came_from:
                if f_score[x.index] < f_score[came_from[y].index]: // index by y
                    came_from[y.index] = x // index by y.index
            else:

您可能

if f_score[x.index] < f_score[came_from[y.index].index]:

在第一行中提到的内容。

除此之外，代码看起来还不错。

不管怎样，总是产生相同的路径是什么意思？该算法应该返回应该始终相同的最佳路径...（或者您的意思是，它总是独立于 start 和 goal 产生相同的路径？ )`

编辑：

您不会在算法中的任何地方使用随机成本。该算法使用的“成本”始终是两个相邻节点之间的距离：它们在 heuristic_distance 中定义并在行中使用

tentative_g_score = g_score[x.index] + heuristic_dist(x,y)

如果要定义随机成本，则必须首先意识到该算法分配边的成本，而不是顶点的成本。您必须定义一些函数 real_costs(x,y) 来计算从节点 x 到节点 y 的成本并使用它成本函数而不是上面一行中的 heuristic_dist 。