Какие алгоритмы поиска пути существуют? [закрыто]

49

Я хотел бы прочитать о алгоритмах поиска пути. Есть ли в Интернете учебник для начинающих или какие-либо материалы или учебные пособия, которые могли бы послужить хорошим началом для меня?

Spoike
источник
Связанный: cstheory.stackexchange.com/questions/11855
BlueRaja - Дэнни Пфлугхофт

Ответы:

34

Если вы хотите изучить и узнать о поиске путей в целом, я бы определенно предложил изучить больше, чем один алгоритм. Вы захотите понять общие концепции, но сможете применить их к тому, над чем вы работаете. Большинство разработчиков игр, которым необходимо найти какой-либо серьезный способ поиска пути, заканчивают тем, что пишут свои собственные алгоритмы, хотя основанные на известных решениях, каждая игра отличается и будет иметь разные требования.

Я бы начал с изучения некоторых наиболее известных методов, таких как A *, алгоритм Дейкстры, поиск по глубине и по ширине. В интернете есть много полезной информации по каждому из них. ( http://en.wikipedia.org/wiki/Pathfinding )

Читая их, обратите внимание на достоинства и недостатки каждого подхода, а также тип данных, с которыми может работать алгоритм. Может ли оно быть применено к трехмерным путям? Можно ли изменить его, чтобы учесть наш человеческий ИИ, который хочет избежать наземных мин на карте?

Когда дело доходит до поиска пути, A * - в значительной степени золотой билет, который все используют. Вы должны определенно знать, как это работает. ( http://en.wikipedia.org/wiki/A*_search_algorithm )

Вот хороший пример использования A * в игре RTS, в которой необходимо учитывать объекты разного размера: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

Удачи!

dcarrigg
источник
2
+1 за немного о программистах, которые должны научиться адаптировать известные решения. Это то, что многие потенциальные разработчики игр не понимают.
инженер
22

Алгоритмы поиска пути - это в основном алгоритмы решения задач поиска графа.

http://en.wikipedia.org/wiki/Pathfinding#Algorithms

Наиболее известным из них является алгоритм Джикстры: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

и его вариант A * алгоритм поиска: http://en.wikipedia.org/wiki/A*

ключевой кадр
источник
2
Последняя ссылка не работает, потому что * не рассматривается как ее часть: en.wikipedia.org/wiki/A%2A
Хендрик Бруммерман
fixx0r3d обе ссылки
tenpn
Простые алгоритмы поиска в графе - это только основы для поиска пути.
Мартинкунев,
13

Это отличный начальный ресурс, который рассматривает все аспекты поиска пути в очень простом для понимания подходе.

Заметки Амит о поиске пути

... Поиск пути решает проблему поиска хорошего пути от начальной точки до цели ― избегая препятствий, избегая врагов и минимизируя затраты (топливо, время, расстояние, оборудование, деньги и т. Д.). Движение решает проблему выбора пути и движения по нему. Можно потратить свои усилия только на один из них. С одной стороны, сложный следопыт в сочетании с тривиальным алгоритмом движения ...

Дэвид Янг
источник
1
+1 за Амит. Я узнал A * на его сайте более 10 лет назад.
10
Великолепные иллюстрации тоже. Высокого качества.
Обезьяна
5

Поиск пути - довольно решенная проблема ... как уже упоминалось почти в каждом ответе, некоторые варианты A * будут тем, что вы используете.

Более сложная задача для меня - как вы хотите представить свой путь . Использование сетки, путей, навигационных сеток, иерархических сеток или других сложных структур и т. Д.

Я не имею в виду никаких конкретных ссылок, но изучение AIGameDev даст вам всевозможные идеи относительно того, что там происходит.

Просто помните, что у каждого представительства есть свои плюсы и минусы; Речь идет не о поиске «лучшего», а о том, который лучше всего подходит для вашего игрового процесса .

Ipsquiggle
источник
5

В Википедии есть хороший список: Pathfinding

Насколько я знаю, A * и D * оба довольно популярны.

Крейг Мартек
источник
+1 за упоминание динамического A *, лучше известного как D *
Дэвид Янг
4

Существует несколько алгоритмов поиска путей.

Один из самых популярных из них, вероятно, A * ( A-Star ). Это очень полезный алгоритм, если у вас есть эвристическая функция, которая может дать вам приблизительные затраты для достижения цели (например, расстояние до цели до линии прямой видимости). * Очень полезен, чтобы найти кратчайший путь от начала до конца.

Кроме этого есть также алгоритм Дейкстры, который очень полезен для поиска ближайшего предмета из нескольких предметов. Например. если вы хотите узнать, какое включение (или подобное) ближе всего к вашему игровому персонажу.

Есть несколько других алгоритмов, но я думаю, что A * является самым популярным. Mat Buckland имеет отличную главу о поиске пути в своей книге AI Programming Game by Example . Я настоятельно рекомендую вам получить его копию. В противном случае вы найдете много информации в Интернете, выполнив поиск "A Star search".

bummzack
источник
Боже мой Пока я это печатал, один и тот же ответ давался около миллиарда раз. Извините :)
bummzack
Просто заметил, что упомянутая книга тоже есть в Google-Книгах (хотя и не полная). Прочитайте это здесь: books.google.com/books?id=gDLpyWtFacYC
bummzack
2

Это не большой пример, но мы подробно обсуждали алгоритмы графов в нашем классе алгоритмов прошлой осенью 2009 года. Мы использовали эту книгу,

Введение в алгоритмы, третье издание Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л. Ривеста и Клиффорда Стейна

http://mitpress.mit.edu/algorithms/

и это также сопровождает лекции на YouTube из класса MIT.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Главы 17, 18 и 19 посвящены кратчайшим путям.

bluedes
источник
2

Смотрите [График и древовидные алгоритмы поиска] в Википедии 1 . Это всего лишь разновидности State Space Search, вам просто нужно пройтись по всем этим и найти, чем они отличаются.

Существует также Collaborative Diffusion , который является одним из ранее упомянутых алгоритмов, выполненных интересным способом.

user712092
источник
+1 Этот документ о совместном распространении довольно интересен.
инженер
1
Я думаю, что ссылка не работает. Может быть , это правильный один: scalablegamedesign.cs.colorado.edu/gamewiki/index.php/...
пекин
-2

Это выглядит интересно:

http://www.codeproject.com/Articles/455 Интересно, это лучше, чем A *?

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