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

填充关闭列表的代码如下所示。这里，.score2 是 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)

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

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

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

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)) img src="https://i.sstatic.net/T6lfU.jpg" alt="多余搜索区域">

或者，从方程中删除 TILE_SIZE 常量会得到这个看起来同样低效的搜索区域：

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

Answer 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.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