A star в картинках

В прошлой статье мы рассмотрели алгоритм поиска пути A star, как на теории, так и на практике. Но было бы не плохо ещё разобраться наглядно не используя ни формулы ни код.

Представим, что у нас есть карта 6 на 5 клеток, итого 30, и нам надо попасть из клетки с номером 6 в 22.

Зеленым квадратиком, я буду обозначать, что эта клетка находится в открытом списке.

Синим - в закрытом.

Я выбрал именно это расположение стартовой, конечной точек и преград, потому что мне показался этот случай интересным. Как мы видим мы сразу добавили нашу стартовую клетку в открытый список. Напомню, открытый список служит для хранения клеток, которые нужно проверить, закрытый хранит уже проверенные ячейки.
Давайте взглянем на то, как я буду записывать данные ячейки:
Напомню обозначения из прошлого урока:

• ID - номер ячейки в сетке;
  
• mID - её родитель;
  
• G - стоимость передвижения из стартовой клетки к данной. В моем примере каждое передвижение по горизонтали и вертикале будет стоить 10 единиц, а по диагонали 14. Так вот G это сумма единиц пройденного расстояния от начала до конкретно рассматриваемой точки;
  
• H - стоимость передвижения от данной клетки до конечной по методу Манхеттена (Manhattan method). Этот метод состоит в том что мы рассчитываем расстояние только по горизонтали и вертикали, игнорируя препятствия и диагональные перемещения.
  
• F - сумма G и H;

Так как в открытом списке у нас лишь одна клетка 6, то мы берем её для анализа.

Мы добавили её проходимых соседей в открытый список, оценили их путь и нашу клетку отправили в закрытый список. Теперь нам надо выбрать клетку с наименьшим значением F (цифра верхнего левого уголка) для анализа. Так как мы начинали искать соседей слева направо, то первая клетка с наименьшим F у нас будет 12.

Опять у нас спорный момент между клетками 7 и 18, но 7 была добавлена раньше. Значит, ищем её соседей.

Клетка под номером 18 была добавлена раньше.

Уже видно два пути, которых наш алгоритм пытается сравнить и выявить наименьший. Хоть нам и ясно какой из них будет верным, продолжим наше наглядное исследование. Ищем соседей для клетки 8.

Следующая клетка, соседей которой мы будем оценивать, это клетка 19. И она будет последним анализируемым звеном в не самом коротком пути (но я вам этого не говорил).

В порядке очереди выбираем клетку 9.

На данном этапе, у нас появилась одна единственная клетка с наименьшим F, и она под номером 16.

Добавляя соседей для клетки 16, мы так же добавили нашу конечную точку, а значит, пора останавливать нашу рутинную процедуру :) Теперь нам надо найти по клеткам, находящимся в закрытом списке наш путь. Так как мы храним их номера родителей (master ID, правая верхняя цифра в квадратике), то двигаясь с конца по родительским клеткам дойдем до стартовой, это и будет наш путь.

Ну и вот так выглядит наш путь найденный алгоритмом A*.

Думаю теперь, когда мы "разжевали" алгоритм поиска пути A star (на теории, на картинках, на практике), недопонимания и вопросов не осталось ни у кого. Теперь мы легко можем найти кратчайший путь из одной точки в другу.

<< Назад | Оглавление | Вперед >>