Алгоритм поиска пути А* на JavaScript

Существует много реализаций волнового алгоритма для поиска кратчайшего пути. Обычно, подобные алгоритмы нужны при работе с графами, а также часто используются при разработке игр, когда некоторому объекту на игровой карте нужно попасть из точки А в точку Б, учитывая различные препятствия на пути. Для моих целей подошел алгоритм под названием "А-звездочка", который работает следующим образом:

Начало Поиска

Начинаем поиск пути выполняя следующее: Начинаем со стартовой точки A и добавляем ее в "открытый список" клеток, которые нужно обработать. Открытый список это что-то наподобие списка покупок. В данный момент есть только один элемент в списке, но позже мы добавим еще. Список содержит клетки, которые может быть находятся вдоль пути, который вы выберете, а может и нет. Проще говоря, это список клеток, которые нужно проверить. Ищем доступные или проходимые клетки, граничащие со стартовой точкой, игнорируя клетки со стенами, водой или другой непроходимой областью. И также добавляем их в открытый список. Для каждой из этих клеток сохраняем точку A, как "родительскую клетку". Эта родительская клетка важна, когда мы будем прослеживать наш путь. Удаляем стартовую точку A с вашего открытого списка и добавляем ее в "закрытый список" клеток, которые вам больше не нужно проверять.

Оценка пути

Дальше мы выберем одну из соседних клеток в открытом списке и практически повторим вышеописанный процесс . Но какую клетку мы выберем? Ту, у которой меньше стоимость F. Способом определения того, какую же клетку использовать, является следующие выражение:

F = G + H, где

G = стоимость передвижения из стартовой точки A к данной клетке, следуя найденному пути к этой клетке.
H = примерная стоимость передвижения от данной клетки до целевой, то есть точки B. Она обычно является эвристической функцией. Причина по которой она так называется в том, что это предположение. Мы действительно не узнаем длину пути, пока не найдем сам путь, потому что в процессе поиска нам может встретиться множество непроходимых препятствий.

Итоги метода A*

1) Добавляем стартовую клетку в открытый список.
2) Повторяем следующее:

a) Ищем в открытом списке клетку с наименьшей стоимостью F. Делаем ее текущей клеткой;
b) Помещаем ее в закрытый список. (и удаляем с открытого);
c) Для каждой из соседних 8-ми клеток:

Если клетка непроходимая или она находится в закрытом списке, игнорируем ее. В противном случае делаем следующее.
Если клетка еще не в открытом списке, то добавляем ее туда. Делаем текущую клетку родительской для это клетки. Расчитываем стоимости F, G и H клетки.
Если клетка уже в открытом списке, то проверяем, не дешевле ли будет путь через эту клетку. Для сравнения используем стоимость G. Более низкая стоимость G указывает на то, что путь будет дешевле. Эсли это так, то меняем родителя клетки на текущую клетку и пересчитываем для нее стоимости G и F. Если вы сортируете открытый список по стоимости F, то вам надо отсортировать свесь список в соответствии с изменениями.

d) Останавливаемся если:

Добавили целевую клетку в открытый список, в этом случае путь найден.
Или открытый список пуст и мы не дошли до целевой клетки. В этом случае путь отсутствует.

3) Сохраняем путь. Двигаясь назад от целевой точки, проходя от каждой точки к ее родителю до тех пор, пока не дойдем до стартовой точки. Это и будет наш путь.

Статья основана на http://www.policyalmanac.org/games/aStarTutorial_rus.htm, где более подробно по шагам расписан алгоритм. Новичкам рекомендуется к прочтению.
Пример реализации алгоритма А* на Javascript с подробными комментариями в коде. Понажимайте F5 на странице скрипта, "карта" генерится каждый раз заново.