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

В игровом мире нет сложных лабиринтов. Это материки, острова. То есть самое сложное - это пролив, который нужно обойти. Также встречаются отдельные препятствия - камни, деревья, которые легко обойти. Но если цель за речкой, алгоритм не должен искать мост на другом конце континента. Нужен самый быстрый алгоритм.
  • Вопрос задан
  • 1720 просмотров
Решения вопроса 2
pi314
@pi314
Президент Солнечной системы и окрестностей
xmoonlight
@xmoonlight Куратор тега Разработка игр
https://sitecoder.blogspot.com
Lazy Theta*
Ещё линк по тому же алгоритму.
lRKeN.png5b71e590ed581382983263.png
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
BasmanovDaniil
@BasmanovDaniil
Геймдизайнер-телепат
Все поголовно используют A*, изредка JPS. Если скорости не хватает, то оптимизируют граф, по которому происходит поиск, например, равномерную сетку заменяют на ключевые точки.
Ответ написан
GavriKos
@GavriKos Куратор тега Разработка игр
Какой самый быстрый алгоритм поиска пути?

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
2Reallife Москва
от 110 000 до 130 000 ₽
LEVEL Москва
от 130 000 до 200 000 ₽
от 100 000 до 130 000 ₽
25 февр. 2020, в 13:26
500 руб./за проект
25 февр. 2020, в 13:06
2000 руб./за проект
25 февр. 2020, в 12:59
50000 руб./за проект