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

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

47 голосов | спросил 4 revs, 4 users 67%
Spoike
1 Jam1000000amThu, 01 Jan 1970 03:00:00 +030070 1970, 03:00:00

11 ответов


32

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

Я бы начал с изучения некоторых из наиболее известных методов, таких как A *, Dijkstra's Algorithm, Depth и Breadth-First. На каждом из них есть много хорошей информации в Интернете. ( http://en.wikipedia.org/wiki/Pathfinding )

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

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

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

Удачи!

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
22

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

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

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

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

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
13

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

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

  

... Pathfinding решает проблему нахождения хорошего пути от начальной точки до цели - избегая препятствий, избегая врагов и минимизируя издержки (топливо, время, расстояние, оборудование, деньги и т. д.). Движение решает проблему прохождения пути и перемещения по нему. Itâ € ™ s можно потратить ваши усилия только на один из них. С одной стороны, сложный следопыт, связанный с тривиальным алгоритмом движения ...

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
5

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

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

У меня нет конкретных ссылок, но изучение AIGameDev даст вам все виды идей относительно того, что там есть.

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

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
5

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

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

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
4

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

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

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

Есть несколько других алгоритмов, но я думаю, что A * является самым популярным. У Мата Бакланда есть прекрасная глава о Path-Finding в его книге Программирование игрового AI с помощью примера . Я настоятельно рекомендую вам получить его копию. В противном случае вы найдете множество информации в Интернете, выполнив поиск «Поиск по звездам».

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
3

Вот учебник по использованию Алгоритм Дейкстры для поиска пути .

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
3

Вот хороший пример того, как A * используется в игре с некоторым кодом psuedo: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
2

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

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

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

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

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
2

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

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

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47
-2

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

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

ответил Chimango Chisuwo 19 Jpm1000000pmTue, 19 Jan 2016 17:18:47 +030016 2016, 17:18:47

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132