所以我正在尝试编写 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)
“检查”功能将检查的图块添加到关闭列表中，并将其可行的邻居添加到打开列表中，并且似乎工作正常。该算法似乎允许 H 分数为 X 的所有图块（其中 X 取决于设置目标的迷宫的复杂性）。
将其放慢到逐个节点的可视化基本上表明它正在填充大小为 X 的区域，并在迷宫入口被填充物击中时找到路径。我真的不知道我做错了什么，而且我已经试图解决这个问题两天了。
编辑：为了解决问题，这里是更完整的代码摘录。这是检查（）函数：
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 常量会得到这个同样低效的搜索区域：
在我看来，它不应该搜索所有额外的区域——只搜索障碍物周围的区域。