[pax]

AStar очень простой, и работает быстрее Дейкстры, т.к. имеет направление поиска (функцию эвристики). http://www.policyalmanac.org/games/a...torial_rus.htm

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

2) Повторяем следующее:

a) Ищем в открытом списке клетку с наименьшей стоимостью F. Делаем ее текущей клеткой.

b) Помещаем ее в закрытый список. (И удаляем с открытого)

c) Для каждой из соседних 8-ми клеток ...

Если клетка непроходимая или она находится в закрытом списке, игнорируем ее. В противном случае делаем следующее.

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

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

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

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