Итак, я пытаюсь написать реализацию алгоритма 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, и находит путь, когда вход в лабиринт попадает под заливку. Я действительно понятия не имею, что я делаю неправильно, и я пытаюсь разобраться в этом уже два дня.
РЕДАКТИРОВАТЬ: в интересах решения проблемы, здесь более полный фрагмент кода. Это функция 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))
Кроме того, удаление константы TILE_SIZE из уравнения дает мне такую же неэффективно выглядящую область поиска:
Мне кажется, что он не должен искать всю эту дополнительную область - только область, непосредственно окружающую препятствия.