Какой самый быстрый алгоритм поиска пути?

Question

[dollar]

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

Comments

[Roman]

не прошло и 20 лет с
Toward More Realistic Pathfinding

[xmoonlight]

Быстрый!=Оптимальный
Речь, наверное не о скорости алгоритма, а о кратчайшем пути.
Поэтому предложу оптимизировать заголовок вопроса.

[dollar]

Путь может быть и не самым кратчайшим. Лишь бы поиск пути был самым быстрым.

В случае с пустым полем без препятствий в общем случае "кратчайший" = "самый быстрый". Хотя, судя по тестам, A* ведёт себя не самым быстрым образом.

Answer 1

[pi314]

https://qiao.github.io/PathFinding.js/visual/

Comments

[dollar]

Судя по тестам самый быстрый Best-First-Search.

Answer 2

[xmoonlight]

Lazy Theta*
Ещё линк по тому же алгоритму.

Comments

[dollar]

Гениально.
Это тот же A*, только красивый.

[xmoonlight]

dollar, это совсем не тот же A*. Он и короче делает путь.

Answer 3

[Даниил Басманов]

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

Answer 4

[Олег]

Моя статья про A*

Answer 5

[GavriKos]

Какой самый быстрый алгоритм поиска пути?

его не существует. Все зависит от входных данных, среди которых: размер сетки, размер и плотность препятствий, необходимость сглаживания пути, статичность/динамичность препятствий, размеры самого объекта (важны/неважны), туман войны (в целом аналогично динамичности препятствий, но не всегда), и еще куча факторов.

Начните с a-star, если под первичные данные он подходит.

Answer 6

[vilasha]

Мне кажется этот алгоритм самый быстрый (не знаю точно название алгоритма, но суть в следующем):
1. Пишем уравнение прямой между текущей координатой объекта и пунктом назначения (www.math.by/geometry/eqline.html).
2. Движемся вдоль этой прямой до первого препятствия
3. Если наткнулись на препятствие, начинаем обход его, скажем, справа. При каждом шаге проверяем, а не на нашей ли прямой находимся
4. Если оказались снова на прямой, и это не та точка, с которой начали обход, то продолжаем идти дальше вдоль прямой до пункта назначения или следующего препятствия.
5. Если оказались снова в той точке, с которой начали обход, или в одной из точек на прямой, которая дальше от пункта назначения, что точка, откуда начали обход (т.е. вернулись назад), то пытаемся обойти препятствие уже слева.
6. Если и здесь вернулись в точку, с которой начали обход, то желаемая точка назначения недостижима.

Comments

[longclaps]

А я знаю название.