Поиск пути и предотвращение столкновений на мобильном телефоне

В настоящее время я разрабатываю игру, похожую на Diablo, для мобильной платформы (iphone5 +).

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

Одновременно будет активно около 50 монстров, поэтому производительность очень важна.

Я нашел несколько методов, которые могли бы работать.

1. НавМеш + РВО

   Библиотека recast / detour хорошо работает на pathfindingчасти, но ее симуляция толпы быстро достигает предела (более 5 мс для 30 агентов).

   Другая библиотека RVO2 выглядит нормально (менее 2 мс для 50 агентов), но у библиотеки есть некоторые проблемы с лицензией.

2. Flow Fields + физический движок

   Многие игры RTS используют этот метод, но кажется, что для разрешения столкновений требуется физический движок. Если многие агенты не имеют общей цели, этот метод может стоить дороже, чем традиционный поиск пути A *.

3. Поведение рулевого управления + физический двигатель

   Поведение рулевого управления включает в себя множество концепций, я думаю, что это simple avoidance behaviorможет сработать (просто поверните налево / направо, если что-то впереди), но метод все еще требует физического механизма для совместной работы.

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

PS Halo:Spartan Strikeиспользует Havok AI (основанный на RVO?), Но я не видел много врагов в этой игре, поэтому мне интересно, будет ли первый метод (NavMesh + RVO) хорошо работать на мобильной платформе.

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

Во-первых, я думаю, что вы должны четко определить границы игры, которую вы пытаетесь создать, и определить эти вопросы (на некоторые из них, возможно, уже дан ответ).

• Как далеко находится монстр аггро?
• Сколько монстров одновременно ваша цель?
• Как организована ваша местность? Это выложено плиткой?
• Как много вы хотите избежать столкновения?

Чтобы процитировать ответ отсюда о том, как поиск пути делается в Starcraft 2:

Starcraft II использует ограниченную триангуляцию Делоне для карты местности и зданий для создания навигационной сетки; A * с воронкообразным фильтром используется для прохождения вдоль этой сетки с учетом радиусов единиц измерения; затем поверх этого добавляются слои локального рулевого управления и предотвращения столкновений, в том числе совместная функция «выталкивать незанятые блоки из пути», где в определенных случаях можно перемещать блок вместо обхода вокруг него. Кроме того, блоки, движущиеся параллельно, игнорируются в целях предотвращения столкновений, поскольку они могут гарантированно не влиять друг на друга; [...] SC2 использует шесть рулевых сил: следование, флокирование, группировка, разделение, уклонение и прибытие.

Итак, возвращаясь к вашим 3 предложениям:

1. NavMesh + RVO -> Если есть проблемы с лицензией, то это не вариант. Это может быть самая простая реализация, хотя.
2. Flow Fields + Physics Engine -> Если честно, это зависит, но кажется, что в полудинамической среде действительно требуется много вычислительных ресурсов, как вам нужно
3. Поведение рулевого управления + физический движок -> Поведение рулевого управления мне кажется правильным. Таким образом, вы можете определить некоторые довольно хорошие поведения стада для вашей игры, в зависимости, например, от типа монстра. И это хорошо масштабируется с номером моба. Тем не менее, я бы держался подальше от физики для обнаружения столкновений. Достаточно простого поведения избегания, снижения скорости или увеличения, поворота и т. Д.

Некоторые замечания о поведении рулевого управления, вы можете определить столько сил рулевого управления, сколько вам нужно, с областями, которые вы хотите. Вам нужно по крайней мере 3, для стека / притяжения / отталкивания, но больше, вероятно, интересно.

Затем попытайтесь найти библиотеку , которая делает рулевые поведения , чтобы увидеть , если она соответствует вашим потребностям (как это ? Я не знаю , есть, но она существует).

Если библиотека не соответствует вашим потребностям, тогда вы готовы повеселиться! Но ресурсов и алгоритмов достаточно для того, чтобы самостоятельно реализовать поведение флокирования. Пример 1 Пример 2

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

Ну, это насколько я знаю, я все равно не уверен

Если вражеские пути не очень динамичны (динамические - каждая пара агентов атакует разные цели, и пути к этим целям должны обновляться каждые пару кадров)

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

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

Я бы избегал физики, независимо от вашего окончательного варианта, так как он может стать тяжелым.

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