[moka]

Ну если понимаешь разницу между алгоритмами, то тут можно понять не затрудняясь.

В Астаре, ты гуляешь по массиву, и вся логика отталкивается от этого.

А вот с вэйпоинтами, ты гуляешь по вп (вэйпоинтам) и от них к подсоединёным (каждый вп имеет 1 или более ссылки на другие вп). И нужно учитывать дистанцию каждой вариации пути, и далее сверять их, т.к. вариаций может быть много. Более детализированный путь может иметь 10 точек, а менее детализированный 5 и быть длиннее. Поэтому нада учитывать общую длину пути и в итоге выбирать по ней.
Это подобно волновому алгоритму, только используются именно точки, а не массив.

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

У вейпоинтов есть один минус, то что это заранее или автоматически проставленные точки. А это значит что уровень должен быть статичен (максимум наличие дверей и т.п. проходов может меняться, и то, заранее учтено).
Плюс, в перемещении будут заметны часто патерны, и для этого нада будет делать разного рода вариации в перемещении для разнообразия. Отклонения от пути и т.п.
Сложные уровни опять будут страдать..

Я предлагаю, совсем другой подход.
Что является главным фактором поиска пути? Препятствия. Тут Астар или Волновой алгоритмы молодцы. Но учитывая детализацию и сам уровень, опять, сильно не замудришь, плюс подходит лишь для узкого круга жанров и т.п.
Если взять уровень, и описать его отрезками. Вот стоит у нас стена - это один отрезок. Чтобы её обойти, нужно провезти отрезок через неё, если пересекаются, провезти два к одному углу стены, и второй к другому от точки старта, при этом снова делать эту же проверку (это уже два пути развивается + возможные ещё перемещение), и так проводить от концов путей до точки назначения пока не достигнет.
Это динамическая генерация пути, основываясь лишь уровню. Не важно где находишься, не важно куда идёшь. Таким образом уровень может быть Очень сложный. Также можно учитывать любую динамику, и делать "локальные" вычисления рассчитанного пути, если на отрезок попадает динамический объект, или где-то изменился уровень, это всё можно пересчитать, т.к. есть путь.

Я делал давно картинку по этому алгоритму, но были и лучше идеи, которые потом пришли. В общем, я считаю при корректной реализации, можно внедрить слои, степень проходимости, области с разными параметрами, учёт изменений уровня, локальный перерасчёт для обхода динамичных объектов, да кучу всего. При этом математически, алгоритм будет весьма и весьма сладкий.
Единственное о чём нужно заботиться, это автоматический расчёт отрезков препятствий, а это может быть и не такая простая задача для тех же FPS игр, хотя и не очень сложная учитывая современные возможности.
Для игр с видом сверху, это вообще сказка имхо..