Алгоритм поиска маршрута в 8 направлениях

Question

У меня проблемы с поиском правильного алгоритма нахождения пути для некоторого ИИ, над которым я работаю.

У меня есть игроки на поле, свободно передвигающиеся (не привязанные к сетке), но они ограниченычтобы двигаться в 8 направлениях (N NE E и т. д.)

Я работал над использованием A *, и график для этого.Но я понял, что каждый узел на графике одинаково далеко друг от друга, и все ребра имеют одинаковый вес - так как шаг прямоугольный.И количество узлов огромно (будучи большим шагом, с их возможностью перемещаться между 1 пикселем и другим)

Я подумал, что должен быть другой алгоритм, оптимизированный для такого рода вещей?

Answer 1

Я бы разбил шаг на 10x10 пикселей сетки. Ваша маршрутизация не должна быть настолько тонкой, как остальная часть вашей системы, и это заставляет алгоритм занимать гораздо меньше памяти.

Как говорит Крис выше, выбор правильной эвристики - ключ к правильной работе алгоритма.

Answer 2

Если игроки движутся по прямым линиям между точками на вашей сетке, вам действительно не нужно использовать A *. Алгоритм линии Брезенхама очень быстро обеспечит прямой путь.

Answer 3

Я думаю, вам стоит попробовать поиск в Jump Point. Это очень быстрый алгоритм поиска пути по 8-му.

Вот блог , в котором кратко описан поиск точки перехода.

И это академическая статья <<a href="http://grastien.net/ban/articles/hg-aaai11.pdf" rel="nofollow"> Сокращение онлайн-графика для поиска путей на картах сетки >

Кроме того, на Youtube есть несколько интересных видео.

Надеюсь, это поможет.

Answer 4

Вы можете взвесить направление, основываясь на другой эвристике.Таким образом, в отличие от взвешивания путей на основе фактического расстояния, вы можете взвесить или масштабировать, основываясь на другом факторе, таком как «близость к другому игроку», то есть игроки будут предпочитать маршруты, которые не будут сталкиваться с другими игроками.

A* алгоритм должен хорошо работать следующим образом.