Как A* ищет короткий путь по игровой карте

Для алгоритма карта выглядит как граф: узлы обозначают положения, рёбра задают допустимые переходы. Поиск в ширину обходит граф равномерно, алгоритм Дейкстры учитывает стоимость перемещения, а A* использует оценку расстояния до цели и направляет поиск преимущественно к ней.

В примере проход по воде стоит в десять раз дороже прохода по траве. Представление карты тоже влияет на производительность: A* быстрее работает с меньшим числом узлов, хотя сетку проще использовать.

Интерактивный разбор Red Blob Games содержит анимации и код на Python: от очереди и восстановления пути до приоритетов и эвристики. Откройте его, если настраиваете навигацию персонажей и хотите увидеть, как граф и стоимость переходов меняют поиск.