В прошлой статье мы рассмотрели алгоритм поиска пути 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 (на теории, на картинках, на практике), недопонимания и вопросов не осталось ни у кого. Теперь мы легко можем найти кратчайший путь из одной точки в другу.
4 коммент.:
разве через клетку под номером 15 путь был бы не короче?
от 9 до 16 - 14 единиц
от 16 до 22 - 10 единиц
итого 24
от 9 до 15 - 10 единиц
от 15 до 22 - 14 единиц
итого 24
значит одинаково
складывается мнение что автор не до конца понимает как этот алгоритм работает. Либо просто плохой из него оратор. Скомкано и размыто, так где нужно подробно и доходчиво.
Наверно плохой оратор, если есть вопросы, задавайте, попробую ответить :)
Отправить комментарий