Python A* 算法搜索不当

Question

所以我正在尝试编写 A* 算法的 Python 实现。我的算法可以毫不费力地找到通往目标的路径，但是当我让程序可视化封闭和开放列表时，我注意到封闭列表，只要障碍物有点复杂，就会膨胀成一个大而完美的菱形。换句话说，我的算法将节点添加到封闭列表中，这些节点与目标的距离比“预期”封闭列表的任何邻居都应该远得多。

为了说明，当封闭列表中的一个点距离目标 (2, 1) 远，但一堵墙挡住了去路时，算法将同时添加距离目标 (2, 2) 处的节点 (尝试越过墙)和 (3, 1) 处的算法远离目标...没有充分的理由，因为它显然更远。

我不确定我做错了什么。此距离计算旨在使用“曼哈顿方法”(对我的目的而言不完美，但它不应该导致此类问题)，但其他方法继续提供相同的问题(或实际上更糟糕的问题)。

def distance(self, tile1, tile2):
    self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE)
    self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE)
    self.totalDist = self.straightCost * (self.xDist + self.yDist)
    return self.totalDist

填充关闭列表的代码如下所示。在这里，.score 2是 H 值，使用上面显示的距离方法计算。

    while self.endTile not in self.openList:
        self.smallestScore = MAX_DIST * 50
        self.bestTile = None
        for tile in self.openList:
            if tile.score[2] <= self.smallestScore:
                self.bestTile = tile
                self.smallestScore = tile.score[2]
        self.examine(self.bestTile)

“检查”功能将检查过的图 block 添加到关闭列表并将其可行的邻居添加到打开列表，并且似乎工作正常。该算法似乎承认所有 H 分数为 X 的图 block (其中 X 根据目标所在迷宫的复杂性而变化)。

将其放慢到逐个节点的可视化基本上表明它正在填充一个大小为 X 的区域，并在迷宫的入口被填充击中时找到路径。我真的不知道我做错了什么，两天来我一直在努力解决这个问题。

编辑:为了解决问题，这里是更完整的代码摘录。这是 examine() 函数:

def examine(self, tile):
    #Add the tile to the closed list, color it in, remove it from open list.
    self.closedList.append(tile)
    tile.color = CLOSED
    pygame.draw.rect(windowSurface, tile.color, tile.rect)
    pygame.display.update(tile.rect)
    self.openList.remove(tile)
    #Search all neighbors.
    for a, b in ((tile.col + 1, tile.row), (tile.col - 1, tile.row),
                 (tile.col + 1, tile.row + 1), (tile.col + 1, tile.row - 1),
                 (tile.col - 1, tile.row + 1), (tile.col - 1, tile.row - 1),
                 (tile.col, tile.row + 1), (tile.col, tile.row - 1)):
        #Ignore if out of range.
        if a not in range(GRID_WIDTH) or b not in range(GRID_HEIGHT):
            pass
        #If the neighbor is pathable, add it to the open list.
        elif self.tileMap[b][a].pathable and self.tileMap[b][a] not in self.openList and self.tileMap[b][a] not in self.closedList:
            self.where = abs((a - tile.col)) + abs((b - tile.row))
            if self.where == 0 or self.where == 2:
                self.G = tile.score[1] + self.diagCost
                self.H = self.distance(self.endTile, self.tileMap[b][a])
                self.F = self.G + self.H
            elif self.where == 1:
                self.G = tile.score[1] + self.straightCost
                self.H = self.distance(self.endTile, self.tileMap[b][a])
                self.F = self.G + self.H

            #Append to list and modify variables.
            self.tileMap[b][a].score = (self.F, self.G, self.H)
            self.tileMap[b][a].parent = tile
            self.tileMap[b][a].color = OPEN
            pygame.draw.rect(windowSurface, self.tileMap[b][a].color, self.tileMap[b][a].rect)
            pygame.display.update(self.tileMap[b][a].rect)
            self.openList.append(self.tileMap[b][a])
        #If it's already in one of the lists, check to see if this isn't a better way to get to it.
        elif self.tileMap[b][a] in self.openList or self.tileMap[b][a] in self.closedList:
            self.where = abs((a - tile.col)) + abs((b - tile.row))
            if self.where == 0 or self.where == 2:
                if tile.score[1] + self.diagCost < self.tileMap[b][a].score[1]:
                    self.tileMap[b][a].score = (self.tileMap[b][a].score[0], tile.score[1] + self.diagCost, self.tileMap[b][a].score[2])
                    self.tileMap[b][a].parent = tile
                    print "parent changed!"
            elif self.where == 1:
                if tile.score[1] + self.straightCost < self.tileMap[b][a].score[1]:
                    self.tileMap[b][a].score = (self.tileMap[b][a].score[0], tile.score[1] + self.straightCost, self.tileMap[b][a].score[2])
                    self.tileMap[b][a].parent = tile
                    print "parent changed!"

这是一个较新版本的迭代，它放慢了速度，因此我可以看到它的进展。意思是找到得分最低的节点[0](得分是F，G，H得分的元组)。

def path(self):
    self.openList.append(self.startTile)
    self.startTile.score = (self.distance(self.startTile, self.endTile), 0, self.distance(self.startTile, self.endTile))
    self.examine(self.openList[0])
    self.countDown = 0
    while self.endTile not in self.openList:
        if self.countDown <= 0:
            self.countDown = 5000
            self.smallestScore = MAX_DIST * 50
            self.bestTile = self.startTile
            for tile in self.openList:
                if tile.score[0] <= self.smallestScore:
                    self.bestTile = tile
                    self.smallestScore = tile.score[0]
            self.examine(self.bestTile)
        else:
            self.countDown -= timePassed

下图是使用 self.totalDist = self.diagCost * math.sqrt(pow(self.xDist, 2) + pow(self.yDist, 2))

或者，从等式中删除 TILE_SIZE 常量得到这个看起来同样低效的搜索区域:

在我看来，它不应该搜索所有额外区域 - 只搜索紧邻障碍物的区域。

Answer 1

我的理论:这是因为曼哈顿距离不是 admissible在这种情况下，因为您也可以沿对角线移动。

试试这个:

def distance(self, tile1, tile2):
    self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE)
    self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE)
    self.totalDist = self.diagCost * math.sqrt(self.xDist*self.xDist + self.yDist*self.yDist)
                     # or it might be self.straightCost, depending on their values.
                     # self.diagCost is probably right, though.
    return self.totalDist