Динамическое нахождение пути в реальном времени?

19

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

Я попробовал алгоритм A * и некоторые его варианты, и они отлично работают. Однако теперь меня больше интересует «динамическое» нахождение путей. Например, при поиске пути из точки A в точку B, если неожиданно появляется новое препятствие, я хочу, чтобы мой алгоритм сразу же смог перепланировать путь и не начинать поиск с нуля снова.

Я немного почитал алгоритм D * и подумал, будет ли это подходящим для того, что мне нужно, или это будет излишним.

Поэтому мои вопросы в основном таковы: какой алгоритм лучше всего подходит для динамического поиска путей в реальном времени? ИЛИ какую комбинацию техник я мог бы использовать вместо этого?

Андрей
источник
Я не уверен, какой алгоритм они используют, так что это не ответ, но я думаю, что это то, что вы пытаетесь подражать: видео на YouTube
MichaelHouse
Как насчет расширения A *? Расширение того, что хранится в узлах его открытых / закрытых множеств, на то, что Вы хотите, и расширение A * для его рассмотрения.
user712092
Я искал ответ такой же, как и вы, и я нашел статью о HPA *, и она связана с видеоиграми. Я все еще ищу статью и, вероятно, собираюсь ее реализовать. Пока что для меня имеет смысл улучшить производительность, и его можно использовать как в статической, так и в динамической среде. Вот статья
NelsonPunch

Ответы:

19

D * весьма вовлечен - я не рекомендую пытаться реализовать это. Даже когда проекты хорошо финансируются и разрабатываются умными / опытными людьми, D * lite используется, потому что D * - такая боль, чтобы получить право.

Вас может заинтересовать эта презентация, которая включает в себя обсуждение поиска пути Left 4 Dead:

http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Один из подходов состоит в том, чтобы использовать грубый поиск уровня A *, чтобы получить общий путь для агента, а затем выполнить точный поиск уровня A * для локальной среды агента. Таким образом, вы можете быстро пересчитать детали курса A * поиска, если местность меняется, и затем быстро пересчитать детализацию A * поиска для небольшого сегмента среды. Это не идеально. Он работает до тех пор, пока ваши препятствия не могут блокировать несколько узлов графа с деталями курса, что хорошо для большинства игр. Этот метод я рекомендую, если у вас менее 100 агентов.

Если вы хотите поддерживать сотни или тысячи агентов, вы можете реализовать что-то вроде непрерывного скопления людей. Смотрите это исследование: http://grail.cs.washington.edu/projects/crowd-flows/ В нем обсуждается метод, основанный исключительно на процессоре, который может поддерживать тысячи участников в динамической среде.

Если вы хотите поддерживать десятки тысяч или сотни тысяч агентов, вы можете реализовать что-то вроде непрерывных скоплений с помощью графического процессора. См. Здесь для соответствующего исследования: https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf

Вот видео, демонстрирующее толпы людей в действии: http://www.youtube.com/watch?v=lGOvYyJ6r1c (перейдите к 4:10, чтобы увидеть большие динамические препятствия, такие как автомобили и светофоры, затрагивающие сотни людей, идущих по городу.)

Ольховский
источник
Спасибо за ссылки. D * Lite кажется правильным из того, что я читал
Андрей
9

Вы смотрели на простое поведение руля?

http://www.red3d.com/cwr/steer/

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

Также довольно легко комбинировать несколько видов поведения.

BigSandwich
источник
+1. Я не уверен, почему за это проголосовали. Хотя это просто и, возможно, не тот ответ, который искал аскер, я думаю, что это по теме, и я нашел это полезным :)
Ольховский
1
Я прочитал и реализовал это поведение руля в нашей последней игре. Теперь мы собираемся заменить его снова другими методами. Я думаю, что это не работает хорошо вместе с предварительно рассчитанными оптимальными путями. «Сочетание» нескольких типов поведения обычно приводит к плохим результатам. Если вы все еще планируете использовать его, не пытайтесь одновременно управлять и следовать своему пути. Вместо этого переключитесь на 100% рулевое управление и переключитесь на 100% назад, когда вы преодолеете препятствие.
Imi
4

Поскольку ваш пост находится в разделе «Разработка игр» обмена стеками, вот что ответит вам большинство программистов игр: Речь идет не о динамическом поиске путей в реальном времени, а о динамическом пути в реальном времени * после *!

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

Итак, мой совет - начать с реализации Поведения рулевого управления (http://red3d.com/cwr/steer/), обработать случаи, когда путь становится невозможным, а затем добавить слой поверх него для обработки крайних случаев, которые не ' т обрабатываются двумя предыдущими решениями.

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

emartel
источник
Нет «Путь следования» аналогичен поиску пути. Существует множество подходов, которые позволяют в реальном времени отслеживать тысячи агентов при смене препятствий на настольном ПК. Конечно, не так уж и дорого найти путь для отдельного агента, когда вокруг проходят препятствия. Вот один из многих таких подходов: grail.cs.washington.edu/projects/crowd-flows. Ускоренные версии графических процессоров для непрерывного скопления людей существуют.
Ольховский
Я бы не согласился с этим. Любой механизм будет рассматривать поиск пути и следование по пути как две различные проблемы, где первая - это поиск в графике судоходной области, а другая предназначена для поиска оптимального вектора движения в локальном пространстве. Я работал над такой симуляцией толпы, производя промежуточное программное обеспечение, используемое играми ААА, не полагаясь на графический процессор. Большинство реализаций будет использовать поле потока (указатель пути) и рулевое управление, чтобы следить за потоком и избегать других агентов (последователь пути). Как говорилось в моем ответе, это ответ "программиста игры", а не академический ответ.
Эмартел
Я знаю, что вам не нужен графический процессор для массового скопления людей, поэтому я связал версию на базе процессора. Ваше описание пути следования по-прежнему является поиском поиска пути, это просто поиск пути на другом уровне детализации в другом наборе данных. Так что у вас действительно есть проход поиска пути детализации курса и проход поиска пути детализации. В конечном итоге вы пытаетесь найти путь, по которому должен идти актер. Придумывание новых терминов для этого просто сбивает с толку.
Ольховский
1
Извините, но «путь следования» - это не выдуманный термин. Прочитайте документы промышленного производства, и вы увидите, что они используются снова и снова: ссылка или ссылка просто для ссылки. К сожалению, я не могу связать вас с защищенной NDA документацией о механизмах / промежуточном программном обеспечении, широко используемых в отрасли.
Эмартел
1
Ваша первая ссылка - это ссылка, которую я дал в своем ответе. Хорошо, честно, было бы справедливо описать этот тип поиска пути следующим образом. В конечном итоге они оба пытаются найти путь, по которому следует идти, но я думаю, что в этом случае я ошибаюсь, и мы должны назвать то, что мы видим в вашей второй ссылке, следующим образом. Например, акт связывания точек грубой траектории вместе с кубическими сплайсами / кривыми Бизера / insert-your-method-here. Тем не менее, я все еще категорически не согласен с тем, что не представляется возможным осуществить поиск пути вокруг динамических препятствий, как, по-видимому, предлагает ваш ответ.
Ольховский