Взаимные локальные уклонения и навигация для видеоигр

Jamie Snape, Stephen J. Guy, Deepak Vembar, Adam Lake, Ming C. Lin, and Dinesh Manocha

Введение

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

Простые сценарии локального уклонения, такие как стая (Reynolds, 1987), были реализованы с использованием моделей основанных на векторах сил во многих недавних видеоиграх и коммерческих игровых движках. Эти методы моделируют группы виртуальных агентов, как системы частиц, где каждая частица влияет на близлежащие частицы. Законы физики используются для вычисления движение частиц, наряду с набором поведений, предусмотренных разработчиками игр, которые влияют на свойства системы, такие как разделение, выравнивание и сплоченность частиц. Примеры видеоигр с помощью этого метода включают Dead Rising * (Capcom, 2006) и Assassin's Creed * (Ubisoft, 2007).

Совсем недавно, методы основанные на векторах скорости (Fiorini & Shiller, 1998; van den Berg, Lin, & Manocha, 2008) показали значительные улучшения результатов в локальном уклонении и поведении виртуальных агентов, а также улучшения в скорости вычислений, по сравнению с методами, основанными на векторах силы. Вместо того чтобы использовать виртуальные силы, чтобы предотвратить столкновения виртуальных агентов, методы основанные на скорости используют текущую скорость каждого виртуального агента в группе, а затем предсказывают положение каждого виртуального агента в течение некоторого короткого интервала времени, предполагая, что виртуальный агент будет поддерживать практически постоянную скорость на протяжении этого времени. На основе прогнозирования будущей позиции других виртуальных агентов, каждый виртуальный агент стремится выбрать новую скорость, такую, что бы столкновение не произошло. Недавняя видео игра Warhammer 40000: Space Marine * (THQ, 2011) использует метод основанный на векторах скорости.

Взаимное предупреждение столкновения (van den Berg, Lin, & Manocha, 2008) является расширением методов основанных на векторах скорости. Основное отличие от известных методов, заключается в том, взаимное предупреждение столкновений рассматривает обратную взаимность между парами виртуальных агентов. Предполагается, что каждый виртуальный агент, пытается избежать столкновения с другим агентом, а нес движущимся препятствием. Включение взаимности в методы основанные на векторе скорости, как правило, обеспечивает более плавное движение для виртуальных агентов, но также может привести к возникновению различных проблем, таких как заклинивание и блокировка van den Berg, Patil, Sewall, Manocha, & Lin, 2008; Guy, Chhugani, Curtis, Dubey, Lin, & Manocha, 2010; van den Berg, Lin, & Manocha, 2008).

2. Локальные уклонения

A. Velocity Obstacles (VO) and Reciprocal Velocity Obstacles (RVO)

Скоростное препятствие (Fiorini & Shiller, 1998) для виртуального агента, созданное движущимся препятствием – это все векторы скоростей при движении по которым, через небольшой промежуток времени, произойдет коллизия между агентом и движущимся препятствием, при условии что препятствие будет двигаться с постоянной скоростью. Это означает, что если агент выберет себе вектор скорости, который находится в области скоростного препятствия, то, в будущем, между агентом и препятствием произойдет коллизия. Если скорость будет выбрана за пределами скоростного препятствия – коллизия не произойдет. Геометрическое представление скоростного препятствия VOab для агента А по отношению к агенту B, соответствующее конусу, показано на рисунке 1.

Рисунок 1

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

Взаимное скоростное препятствие (van den Berg, Lin, & Manocha, 2008; de Berg, Cheong, van Kreveld, & Overmars, 2008) направлено на решение проблемы колебаний, возникаемой при использовании скоростного препятствия, путем разрешения агентам реагировать на изменение вектора скорости другими агентами. Вместо того, что бы один из агентов брал на себя всю ответственность за совершение маневра уклонения, взаимное скоростное препятствие, позволяет агенту совершить лишь половину, допуская что вторую половину совершит другой агент. Геометрическое представление взаимного скоростного препятствия RVOab для виртуального агента А по отношению к агенту B, соответствующее скоростному препятствию с перемещенной вершиной, показано на рисунке 2.

Рисунок 2

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

Если каждый агент выберет новую скорость ближайшую к его текущей скорости, то агенты автоматически обойдут друг друга по одной стороне. Но вместо этого для достижения конечной цели, агентам обычно необходимо выбрать скорость ближайшую к их предпочитаемой скорости, вектор которой указывает от каждого агента к их конечной цели. Если агенту необходимо двигаться в обратную сторону от его точки назначения, чтобы избежать коллизии, то предпочитаемая скорость будет сильно отличаться от текущей. Присутствие третьего агента, тоже может заставить одного из агентов выбрать скорость, которая будет еще больше отличается от текущей. Это означает, что агенты не обязательно выберут одинаковую сторону для манёвра уклонения, что приведет к появлению непредсказуемых колебаний, которые называются «взаимные танцы». Они могут не решиться быстро, и агент останется заблокированным надолго.

B. Hybrid Reciprocal Velocity Obstacles (HRVO)

Гибридное взаимное скоростное препятствие призвано решить проблему взаимных танцев, путем комбинирования скоростного препятствия и взаимного скоростного препятствия. Гибридное взаимное скоростное препятствие берет одну строну из двух предыдущих методов и формирует новое скоростное препятствие, у которого одна из сторон увеличена. Это позволяет заставить агентов выбрать для манёвра уклонения одинаковую сторону. Например, если вектор скорости агента находится с правой стороны от центральной линии скоростного препятствия созданного другим агентом, то этот агент должен выбрать новую скорость тоже с правой стороны от центральной линии. Такое поведение достигается путем увеличения той стороны, которую агенту нельзя выбирать. Геометрическое представление гибридного взаимного скоростного препятствия HRVOab для агента А по отношению к агенту B, включая центральную линию и увеличенную часть, показано на рисунке 3.

Рисунок 3

Оптимальные взаимные локальные уклонения

Оптимальные взаимные локальные уклонения (van den Berg, Guy, Lin, & Manocha, 2011) решают проблему взаимных танцев путем соединения взаимных скоростных препятствий, немного подругому. Такой подход аргуметирует скростное препятствие с полуплоскостью которая представляет собой набор векторов скоростей, движение по которым будет без коллизий и дополнительно гарантирует что движение агентов будет плавным и без танцев.

Полуплоскость оптимального взаимного локального уклонения ORCA a|b для виртуального агента А по отношению к агенту В определяется, так как показано на рисунке 3. Пусть u – вектор указывающий от относительной скорости Va – Vb виртуальных агентов А и В к ближайшей точке на границе усеченного скоростного препятствия для виртуального агента В порожденного агентом В. Пусть n – внешняя нормаль границы скоростного препятствия к Va – Vb + u. Из этого следует, что u – наименьшее изменение которое необходимо применить к относительной скорости виртуальных агентов А и В чтобы избежать столкновения. Включая взаимность, каждый агент должен регулировать скорость как минимум на 1/2u чтобы избежать столкновения. Таким образом скорости разрешенные оптимальным взаимным локальным уклонением, лежат в полуплоскости в направлении n и начинаются в точке Va+1/2u

Рисунок 3: Два виртуальных агента А и В (слева). Уменьшенная препятствием скорость В.О. для виртуального агента А индуцируется виртуальным агентом B (в центре). Оптимальные обратная предупреждения столкновений полуплоскости разрешенного скоростей ORCA для виртуальных агентов А и В. (Справа).

Реализация

А. Библиотеки HRVO и RVO2

Гибридные взаимные скоростные препятствия и оптимальные взаимные локальные уклонения были реализованы как С++ библиотеки HRVO и RVO2 соответственно.

По сути, алгоритм в РВО2 рассчитывает полуплоскости оптимальных взаимных локальных уклонений для виртуального агента, порожденные другим виртуальным агентом и потом пересекает эти полуплоскости для создания региона разрешенных скоростей для виртуального агента. Затем алгоритм вычисляет предпочтительную скорость (см. раздел 3.B ниже) виртуального агента и вычисляет новую скорость, используя двумерное линейное программирование (см. раздел 3.C ниже), которая находится в пределах области допустимых скоростей и как можно ближе к предпочтительной скорости. При наличии большого количества виртуальных агентов поблизости и отсутствии скорости в регионе разрешенных скоростей, некоторые ограничения ослабляются, и новая скорость находится с использованием трехмерной линейного программирования (см. 3.e ниже). Общий алгоритм RVO2 в библиотеке показан на рисунке 4.

Алгоритм, используемый в библиотеке HRVO во многом аналогичен, за исключением того, что он использует геометрический алгоритм ClearPath (Гай, и др., 2009;. Рейнольдс, 1987; Снейп, ван ден Берг, Гай, и Маноча 2011; ван ден Берг, Гай, Лин , и Маноча, 2011) для вычисления новых скоростей.

Рисунок 4: Алгоритм, используемый в библиотеке RVO2.

Б. Привилегированные скорости.

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

С. Линейное программирование

Библиотека RVO2 использует эффективный рандомизированный линейный алгоритм программирования (де Берг, Cheong, ван Kreveld, и Overmars, 2008; ван ден Берг, Гай, Лин, и Маноча, 2011), который добавляет ограничения один за одним в случайном порядке, сохраняя при этом текущее оптимальное значение новой скорости для виртуального агента в группе. Линейное программирование - метод оптимизации, обычно используемый в операционном исследовании, для нахождения одного определенного решения ряда линейных ограничений равенства и неравенства, который оптимизирует данную линейную функцию переменных. Геометрически, линейный программный алгоритм вычисляет пункт в многоугольнике, где у функции есть свое максимальное или минимальное значение, если такой пункт существует. Рандомизированный линейный программный алгоритм добавляет линейные ограничения в случайном порядке, чтобы вычислить оптимальное решение.

Д. Вычисление ближайших соседей

Эффективность и масштабируемость вычисления новых скоростей для действительного агента могут быть увеличены, если не включать ограничения для всех виртуальных агентов, а только тех виртуальных агентов, которые находятся рядом. У отдаленных виртуальных агентов существует мало шансов взаимодействия с текущим виртуальным агентом в кратковременном интервале, таким образом, возможность столкновения существенно не увеличивается. Библиотека RVO2 использует k d-дерево для вычисления ближайших соседей. Дерево строится в начале каждого временного шага и затем уточняется во время новых вычислений скорости для каждого виртуального агента во время текущего временного шага.

Е. Плотные сценарии

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

Ф. Параллелизм задач

Intel® VTune™ Amplifier XE был использован для анализа существующих узких мест библиотеки RVO2 и ее оптимизации, с целью использования многоядерных процессоров. Шаги вычисления, включенные в нахождение ближайших соседей, вычисление новых скоростей и обновление положения (рисунок 5), выполнены многократно для каждого виртуального агента и независимы друг от друга в моделировании. Библиотека RVO2 использует современные многоядерные процессоры, разделяя шаги алгоритма для каждого виртуального агента, используя или OpenMP* или Intel® Threading Building Blocks (Intel® TBB).

Рисунок 5: Intel® VTune™ Amplifier XE скриншот Benchmark применения анализа параллелизма на процессоре Intel® Core™ i7-980X (6C/12T). Приложение показывает хороший параллелизм (нижние зеленые полосы) с общей хорошей производительностью для каждой функции, представленной Intel® Threading Building Blocks (Intel® TBB).

The application shows good concurrency (bottom green bars) with overall good per-function threading provided by Intel® Threading Building Blocks (Intel® TBB). ==== Я не до конца осилил смысл

На рисунке 5 показан запуск Intel® VTune™ Amplifier XE, который использует эталонный тест для анализа сценария, написанного с использованием библиотеки RVO. Эталонный тест состоял из 1000 виртуальных агентов, расположенных по периметру круга известного радиуса и задачей провести к противоположной стороне круга, предотвращая столкновения с другими виртуальными агентами. Тест сценарий был запущен на Intel ® Core ™ i7-980X Processor Extreme Edition с 6 ядрами, каждое с Intel ® Hyper-Threading (6C/12T). Конкурентный анализ и анализ активного участка от Intel® VTune™ Amplifier XE показывает, что приложение обладает хорошим параллелизмом, а анализ основных значимых горячих точек в коде – на оптимальное использование возможностей процессора (зеленая полоса на верхней диаграмме). Мы считаем, что все 12 потоков в процессоре полностью распределены с небольшим количеством неактивных периодов (зеленая полоса на нижней диаграмме).

Чтобы понять влияние различных процессоров на производительность алгоритма, эталонный тест запускался на двух разных платформах с идентичными конфигурациями за исключением процессоров. Данные о производительности были получены для Intel® Core™ i7-980X Processor Extreme Edition (кодовое название Gulftown) и 2-го поколения Intel® Core™ i7-2820QM Processor (кодовое название Sandy Bridge). Количество виртуальных агентов в моделировании варьировалось в пределах 50, 100, 500, 1000 агентов. Среднее время вычисления за такт, а также среднее количество столкновений в такт, были собраны для библиотек RVO2 и HRVO.

Рисунок 6: Пошаговое вычисление с использованием библиотек HRVO (слева) и RVO2 (справа), при запуске эталонного теста на двух разных процессорах Intel®. Количество агентов, обозначено на оси X и времени на оси Y. Увеличение количества ядер процессора, уменьшает время вычисления за такт.

Рисунок 6 показывает производительность библиотек HRVO и RVO2 на двух разных платформах. В целом, время вычислений за такт меньше на процессор Intel® Core™ i7-980X по сравнению с Intel® Core™ i7-2820QM из-за дополнительных ядер, доступных для распределения вычислительной задачи, и становится более выраженным по мере увеличения количества виртуальных агентов в симуляции. Также наблюдается почти линейное увеличение времени вычислений, принятого за такт, при увеличении количества виртуальных агентов в симуляции.

Рисунок 7: Среднее число столкновений за такт для 50, 100, 500 и 1000 агентов для эталонного сценария с использованием библиотек HRVO и RVO2 на Intel® Processor Core™ i7-980X Processor Extreme Edition (6C/12T). В среднем, при использовании библиотеки HRVO, было меньше столкновений по сравнению с библиотекой RVO2.

Рисунок 7 показывает среднее число столкновений на временном шаге при использовании библиотек HRVO и RVO2. Для 50 и 100 агентов, оба алгоритма имеют одинаковую производительность. Тем не менее, число столкновений для библиотеки RVO2 для 500 и 1000 виртуальных агентов почти в два раза превышает аналогичный показатель для библиотеки HRVO.

Г. Интеграция движка в игру

Библиотека RVO2 была интегрирована в несколько игровых движков для того, чтобы или предупредить локальные столкновения при навигации для групп виртуальных агентов или улучшить реализацию по умолчанию, предоставляемую разработчиками игровых движков. Примеры включают мульти-платформенный пакет от стороннего производителя для Unity 3.5 (Unity Technologies, 2010), написанный на C # и DLL от стороннего производителя для Unreal Development Kit* (Epic Games, 2010) , написанной на C++ для Microsoft Windows * привязкой UnrealScript. Скриншот из Unreal Development Kit* показан на рисунке 8. Подход, подобный гибридному взаимному скоростному препятствию, который используется в Библиотеке HRVO, был включен в Detour компонент из комплекта инструментов навигации игры Recast and Detour 8 (Mikko Mononen, 2009), для обеспечения предотвращения местного столкновения в пределах навигационной петли, как показано в рисунке 9.

Рисунок 8: Скриншот из тестового сценария для интеграции библиотеки RVO2 с Unreal Development Kit*, 200 виртуальных агентов, перемещающихся в режиме реального времени между случайно выбранными местами в четырех углах игрового уровня (Intel® Core™ i5-760 с тактовой частотой 2,8 ГГц).

Рисунок 9: Скриншот сценария Dungeon включая Recast и Detour, 50 виртуальных агентов, перемещающихся в режиме реального времени из одного конца уровня игры к другому на навигационной сетке (Intel® Core™ i5-760 с тактовой частотой 2,8 ГГц).

4. Производительность

Производительность библиотек HRVO и RVO2 были сравнены в трех сценариях, а именно:

Все расчеты проводились на i7-2600 Processor Intel® Core™ (кодовое название Sandy Bridge), работающего на частоте 3.40GHz с 8 Гб оперативной памяти. Операционная система: Microsoft Windows 7 SP1 64-разрядная. Каждая библиотека была скомпилирована с использованием компилятора Microsoft Visual C++, версия 10 SP1.

Рисунок 10: Скриншоты из моделирования Circle-1000, 1000 виртуальных агентов движущиеся одновременно в реальном времени через круг, чтобы достичь диаметрально противоположных позиций (Intel® Core™ i7-2600 Processor на 3,4 ГГц).

Таблица 1: Сроки и столкновения при моделировании сценариев Круга-100, Движущееся препятствие и Блоки.

Таблица 1 выше показывает общее время вычисления и число столкновений за один раз в каждом из трех сценариев. В среднем, для трех сценариев, Библиотека RVO2 оказывается примерно в два-три раза быстрее, чем библиотека HRVO из-за эффективности рандомизированного линейного алгоритма программирования. Однако при подсчете столкновений между виртуальными агентами, их оказывается вполовину меньше при использовании библиотеки HRVO по сравнению с библиотекой RVO2. На практике Библиотека HRVO гораздо менее консервативна с точки зрения количества областей в пространстве скоростей, которые она запрещает, так что это событие менее вероятно, таким образом, уменьшается вероятность, что ее алгоритм станет невыполнимым или что должны быть смягчены некоторые ограничения.

Таблица 2: Время моделирования для большего числа виртуальных агентов, движущихся одновременно по кругу увеличенного радиуса в сценарии Круг-N.

Таблица 2 выше, показывает время вычислений за такт для сценария Круг-N, с N варьирующимся от 100 до 1000. Окружность круга также изменяется пропорционально N. Во всех случаях, время вычисления составляет порядка микросекунд с библиотекой HRVO и медленнее, чем при использовании RVO2 библиотеки.

Таблица 3: Столкновения в моделировании при увеличении числа виртуальных агентов, движущихся одновременно по кругу фиксированной окружности в сценарии Круг-N.

Таблица 3 выше показывает среднее число столкновений за такт для сценария Круг-N. В этом случае длина окружности круга была зафиксирована для того, чтобы создать увеличение плотных сценариев. Как и прежде было меньше столкновений при использовании библиотеки HRVO, по сравнению с библиотекой RVO2. Тем не менее, число столкновений была крайне низкой для обоих методов в этих сценариях.

5. Заключение

Мы представили гибридное взаимное скоростное препятствие и оптимальные взаимные методы предотвращения столкновения для взаимного предотвращения столкновения и навигации в видеоиграх. Произведено сравнение производительности библиотек HRVO и RVO2, которые реализуют эти методы в C++ и показано, что они могут эффективно моделировать группы от 25 до 1000 виртуальных агентов в плотных условиях и вокруг движущихся и статических препятствий. RVO2 Библиотека в среднем, по крайней мере, в два раза быстрее библиотеки HRVO, но положительным результатом библиотеки HRVO является меньшее количество столкновений между виртуальными агентами, чем при использовании библиотеки RVO2 и, следовательно, приводит лучшему локальному взаимодействию между виртуальными агентами.

6. Библиография