dollar
@dollar
Делай добро и бросай его в воду.

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

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

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

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

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

Войти через центр авторизации
Похожие вопросы