Алгоритм поиска пути A* в воксельной 3d игре на Unity

[LaFut]

на первой гифке не a*

[arandomic]

Ну и как теперь определить какую гифку вы имели ввиду и не поменял ли ее с тех пор автор?
Вот эта:

?
Почему не a*?
Зависит от эвристики ©
Но да, если бы эвристикой было бы простое эвклидово расстояние, он пошел бы вдоль стенки

[arandomic]

Вот так как-то
Хотя зависит от того как подкрутить h (эвристику) и g (вес ребра)

[Igor_Sib]

Это не A star, путь явно не оптимальный. Либо подкручено не правильно.

Для квадратов давно разработаны эвристики, для только вертикаль/горизонталь — Манхэттен, для плюс диагоналей — Чебышев.
https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A*

[arandomic]

Где можно срезать?
Вот здесь?
Так длина пути не изменится.
1 клетка — 1 шаг. Как раз по Чебышеву.

[arandomic]

Если хочется минимизировать количество изломов — то нужно либо напрямую за них штраф добавлять, либо отказаться от чебышева в пользу эвклида. (чтобы шаг по диагонали был не 1, а sqrt(2))

[Igor_Sib]

Да не а-стар это, картинка не такая должна быть. :)

qiao.github.io/PathFinding.js/visual — здесь эмулируете? Если нет — дайте ссылку где именно, мне прямо интересно посмотреть как A* дает такую картинку.

A* будет давать другую, вот такую:


То что на вашем скрине — судя по всему Trace.

[Igor_Sib]

С Weight 5 и более и Octile или Manhattan получилось несколько похожее получить — но это не правильно при диагональных переходах, Manhattan точно нельзя (Octile не знаю как работает эвристика).

Скажите уже параметры, не томите.

[arandomic]

Что значит «неправильно»? Что вам визуально не нравится рисунок?
Путь кратчайший? Кратчайший.
Фронтир на момент достижения пути — минимизирован. (Меньше посетили клеток перед тем как нашли финиш)
Эвклида я взял:

[Igor_Sib]

Да, согласен, был не прав — по клеткам столько же, уже прочитал ваш коммент выше. Если брать длину желтой ломаной — то так больше получается.

[arandomic]

Ну у меня была цель минимизировать количество «синего» — посещенных клеток.
А так, можно в эвристику затолкать много чего. Например направление на север сделать менее желанным, итп

[Igor_Sib]

Да, я знаю — у меня AI для платформера (вернее лабиринта) сча в разработке, своя реализация A*, все бегают/прыгают/лазают, просто у меня идет подсчет переходов между нодами (не клетки, так генерятся), там везде разные длины, я удивился что находит такой путь, но длина по клеткам в общем то это объясняет.

[LaFut]

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

[Igor_Sib]

// закрываем точку
closedPoints.Add(openPoints[0]);
// открываем новые точки и удаляем закрытую
openPoints = ClosePoint(0, openPoints, closedPoints, worldData, pfType, targetPoint);

Это обычно делается в основном цикле, зачем вы вынесли это отдельно для первой точки?

По оптимизации не очень понятно, слишком кратко написали. Можете попонятнее расписать, это самая интересная часть статьи.

Кстате у вас много открытых пространств, Jump Point Search искал бы быстрее.

[slayez]

JPS будет сканировать почти всю карту если нужно обойти гору. А карта большая.

[Kudesunik]

Если не учитывать вопрос особенностей реализации A* алгоритма и, соответственно, его производительность даже при поиске пути одного NPC, что во многих случаях может оказаться минусом алгоритма, то в минусы можно записать еще и игнорирование данным алгоритмом движущихся объектов и любых изменений воксельного мира после нахождения оптимального пути. Проще говоря, достаточно поставить единственный воксель на пути NPC и он застрянет и не узнает об этом, а постоянные перерасчеты A* будут стоить крайне дорого.

[slayez]

На открытых пространствах алгоритм считает быстро.