СПОСОБ РАСЧЕТА СКОРОСТИ БЕЗ СТОЛКНОВЕНИЙ ДЛЯ АГЕНТА В СРЕДЕ ИМИТАЦИИ ТОЛПЫ

Область техники, к которой относится изобретение

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

Уровень техники

Приложения виртуального мира (например. Вторая жизнь), становятся важным компонентом парадигмы объединенных визуальных вычислений (CVC). Одна из важных задач, которые должны быть выполнены, представляет собой AI (искусственный интеллект), в котором персонажи виртуального мира выполняют конкретные назначенные задачи и перемещаются в этом мире. Навигация персонажа, также называемая имитацией толпы, представляет собой задачу, требующую большого объема вычислений, и существующие алгоритмы могут имитировать только несколько тысяч агентов в режиме реального времени. Этот порядок представляет собой величину, отличную от требуемой поддержки от десятков до сотни тысяч агентов, которая могла бы потребоваться для генерирования реального сценария виртуального мира.

Краткое описание чертежей

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

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

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

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

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

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

Термины "первый", "второй", "третий", "четвертый" и т.д. в описании и в формуле изобретения, если они присутствуют, используются для отличия, между различными аналогичными элементами и необязательно предназначены для описания определенного последовательного или хронологического порядка. Следует понимать, что термины, используемые таким образом, являются взаимозаменяемыми в определенных обстоятельствах, таким образом, что варианты выполнения изобретения, описанные здесь, могут, например, работать в других последовательностях, чем представлены или по-другому описаны здесь. Аналогично, если способ описан здесь, как содержащий последовательности этапов, порядок таких этапов, как представлен здесь, необязательно является единственным порядком, в котором такие этапы могут быть выполнены, и определенные указанные этапы могут быть исключены, и/или некоторые другие этапы, не описанные здесь, могут быть добавлены к способу. Кроме того, термины "содержать", "включать в себя", "иметь", и любые их варианты, предназначены для охвата неисключающего включения, таким образом, что процесс, способ, изделие, или устройство, которое содержит список элементов, не обязательно ограничены этими элементами, но могут включать в себя другие элементы, не выраженные явно в списке, или неотъемлемые от такого процесса, способа, изделия или устройства.

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

Подробное описание изобретения

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

Имитация толпы в виртуальных мирах становится все более важной, учитывая наступление сайтов трехмерных социальных сетей, аналогично, имитация толпы представляет собой все более растущий компонент AI участка контура визуальной имитации. Расчет скоростей без столкновений агентов представляет собой часть, занимающую наибольшее время алгоритма имитации толпы. Способ, наиболее часто используемый в настоящее время, называется RVO (препятствие для встречной скорости), при котором формируют конусы препятствий для агента в пространстве скорости и рассчитывают скорость, которая максимизирует время до столкновения в этих конусах. В алгоритме используется способ на основе выбора, где выбирают набор из 200-300 выборок среди однородно распределенных точек, и выборку, которая максимизирует время до столкновения, выбирают как скорость для следующего временного этапа агента. Этот способ даже не гарантирует нахождение скорости без столкновений и фактически часто приводит к столкновениям между агентами.

В отличие от этого в вариантах осуществления изобретения формулируют задачу поиска скорости без столкновений, как задачу квадратичной оптимизации, и решают ее, точно используя геометрический подход, как будет дополнительно описано ниже (задача квадратичной оптимизации выполняет поиск оптимального значения, где функция оптимизации является квадратичной, и функции ограничения являются линейными). Варианты осуществления изобретения позволяют рассчитывать локальную скорость исключения столкновений агентов существенно быстрее, чем в используемых в настоящее время способах, и позволяет генерировать реалистичную модель трехмерной толпы, получая новые сценарии использования, и обеспечивая более богатое впечатление пользователя. Раскрытые способы также применимы в современных 3D играх, поскольку они представляют собой конкретный случай виртуальных миров.

Рассмотрим теперь чертежи, на фиг.1 представлено пространство скоростей простого сценария 100 имитации толпы, включающее в себя трех агентов, в соответствии с вариантом осуществления изобретения. Как показано на фиг.1, эти три агента включают в себя агента 110 вместе с агентами 120 и 130, которых агент 110 должен избежать. Стрелки 115 (по одной для каждого агента 110, 120 и 130) представляют предпочтительную скорость (например, найденную, используя расчеты, в соответствии с вариантами осуществления изобретения) для каждого агента в следующем кадре. Конусы 125 и 135 препятствий представляют препятствия для скорости агента 110, соответствующие, соответственно, агентам 120 и 130. Такие препятствия для скорости составляют области скоростей, которые приводят к столкновениям с другими агентами. Другими словами, каждая точка внутри конуса соответствует скорости, которая, в конечном итоге, приводит к столкновению, между агентом 110 и одним или обоими агентами 120 и 130 (если только эти агенты поддерживают постоянную скорость), в то время как каждая точка за пределами обоих конусов соответствует скорости без столкновений. Конечно, агенты 120 и 130 могут очень хорошо управлять изменением скорости от одного момента к следующему, делая принятие постоянной скорости малостоящим, но поскольку конусы препятствия обновляют на каждом временном этапе или в кадре обновления, такая потенциальная проблема уменьшается.

Как показано, стрелка 115 скорости для агента 110 пересекает конус 125 препятствий, что означает неизбежное столкновение с агентом 120. Поэтому для агента 110 должна быть рассчитана новая скорость для того, чтобы избежать столкновения; эта новая скорость должна находиться за пределами обоих конусов препятствий. Рассматривая все еще фиг.1, одна из таких новых скоростей представлена стрелкой 117. Поскольку такая новая скорость расположена за пределами конусов 125 и 135 препятствий, она (на основе информации, известной в момент времени, представленный на чертеже) позволяет агенту 110 избежать столкновения с агентами 120 и 130. Конечно, стрелка 117 представляет только одну из множества возможных скоростей без столкновений. Такая конкретная скорость была выбрана, поскольку она находится за пределами всех конусов препятствий и находится ближе всего к исходной скорости, сводя, таким образом, к минимуму резкое изменение скорости для агентов 110 и обеспечивая возможность плавного и естественного движения. Способ, с помощью которого выбирают такую ближайшую скорость, будет подробно описан ниже.

Как упомянуто выше, варианты осуществления изобретения рассчитывают новую (без столкновений) скорость (которая, как следует напомнить, представляет собой точку в двумерном пространстве скоростей), которая находится за пределами всех конусов препятствий и отклоняет последние от точки исходной скорости. Это может быть выполнено в результате минимизации евклидового расстояния новой скорости от исходной скорости для получения следующей квадратичной задачи оптимизации (в которой (х₀, y₀) представляет исходную скорость и (x, y) представляет новую скорость соответствующего агента):

Минимизировать (x-x₀)²+(y-y₀)², таким образом, чтобы A_ix+B_iy<C_i для всех сегментов конуса. (1)

Для N конусов существует 2N таких (линейных) ограничений.

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

На фиг.2 представлен конус 225 препятствия и конус 235 препятствия, оба из которых возникают для соответствующего агента (не показан), как результат присутствия других, находящихся рядом, агентов (также не показаны). Исходная скорость для данного агента представлена в точке 215. Варианты осуществления изобретения направлены на разделение конусов 225 и 235 препятствий на "сегменты", которые имеют длину, обусловленную линиями границ конуса, заканчивающимися концом линий или пересечениями с другим сегментом линий (в качестве иллюстрации, на фиг.2, например, показан сегмент 237 линий внутри конуса 235 препятствий, и дополнительно показаны сегменты 227 и 228 линий, внутри конуса 225 препятствия). Далее, сегменты конуса разделяют на "внутренние" и "внешние" области, в зависимости от их мест расположения, либо внутри, или снаружи других конусов, как представлено (где "внешние" области включают в себя области границ конуса, при условии, что они не находятся внутри любых других конусов). Тестирование внешних/внутренних сегментов конуса обычно представляют собой проверку линейного ограничения, и может быть представлено выражением в форме Ax+Bx<С. Следуя разделению на внутренние и внешние сегменты минимальное расстояние каждого сегмента от исходной точки рассчитывают для поиска ближайшей точки скорости каждого сегмента (то есть точки на каждом сегменте, которая ближе всего к исходной точке скорости), и затем, из этих ближайших точек, выбирают общую ближайшую точку скорости, как новую скорость. Эта точка представлена на фиг.2 точкой 217.

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

Варианты осуществления изобретения обеспечивают возможность моделирования толпы за время выполнения (для количества агентов, изменяющегося в диапазоне от 100 до 250000 и больше), которое на порядок выше по магнитуде и быстрее, чем наилучшее время исполнения, представленное в литературе. Кроме того, варианты осуществления изобретения масштабируются приблизительно линейно в пределах большого количества ядер (32 и больше), и также позволяют эксплуатировать параллелизм уровня данных для достижения еще большего ускорения обработки. В восьмиядерной системе Intel Penryn всего наблюдались 7Х параллельных масштабов. При моделировании с использованием многоядерных имитаторов достигали масштабирования 29Х на 32 ядрах. Все вместе, на 8 ядерной системе 3,2 Гц Penryn, варианты осуществления изобретения позволяют имитировать 15000 агентов при 58 FPS (кадров в секунду) и 5000 агентов в сложных окружающих средах при 121 FPS.

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

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

Четыре потока: 2000 агентов организуют в четыре потока, которые движутся вдоль диагонали квадрата. Наблюдали плавное движение, формирование тропинок и некоторые вращения.

Впереди и назад: от 10 до 100 агентов движутся вперед и назад вдоль линии. Этот тест был запущен параллельно с OpenSteer (библиотека C++, которая помогает построить управляемое поведение для автономных персонажей в играх и в анимации) для сравнения количества столкновений не модифицированного OpenSteer, по сравнению со столкновениями OpenSteer, в комбинации с вариантами осуществления изобретения.

Эвакуация из здания: агенты установлены в исходные положения в разных комнатах офисного здания. В сцене присутствуют 218 препятствий, и дорожная карта состоит из 429 узлов и 7200 ребер. Агенты движутся в направлении целевых положений, соответствующих знакам выхода. В этом сценарий использовали три версии с 500, 1000 и 5000 агентами, соответственно.

Сцена стадиона: она имитирует движение 25000 агентов, при их выходе с их мест на стадионе. Сцена имеет приблизительно 1400 препятствий, и дорожная карта состоит из почти 2000 узлов и 3200 ребер. Агенты движутся в направлении коридоров, что приводит к сценарию скопления и плотной упаковки.

Имитация города: использовали модель города со зданиями и улицами, и 1500 препятствиями. Дорожная карта имела 480 узлов и 916 ребер. Имитировали движение разных агентов по мере их перемещения в городе и в местах пересечения. Агенты перемещаются с разными скоростями и догоняют друг друга и избегают столкновений с приближающимися агентами. Использовали три версии этого сценария с 10000, 100000 и 250000 агентами, соответственно.

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

Этап 310 способа 300 предназначен для идентификации квадратичной задачи оптимизации, которая соответствует скорости без столкновений. В качестве примера, квадратичная задача оптимизации может быть аналогична выражению (1), которое показано выше. В качестве другого примера, вычислительное устройство может представлять собой компьютер-клиент, второе вычислительное устройство может представлять собой сервер, и сеть передачи данных может представлять собой Интернет.

Этап 320 из способа 300 направлен на то, чтобы найти точное решение в вычислительном устройстве для квадратичной задачи оптимизации, используя геометрический подход. В некоторых вариантах осуществления геометрический подход включает в себя идентификацию конусов препятствий для агента в пространстве скорости и в поиске точки, которая находится за пределами конусов препятствий (в случае, когда точка представляет собой скорость без столкновений).

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

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

На этапе 410 способа 400 идентифицируют, как внешний сегмент границы, все сегменты границы конусов препятствий, которые находятся за пределами всех других конусов препятствий. В качестве примера, конус препятствия может быть аналогичен конусам 125, 135, 225, и 235 препятствий, которые показаны на фиг.1 и 2, и находятся за пределами сегментов границы так, как определено выше при обсуждении фиг.2. Как отмечено выше, в ситуациях, когда не существуют сегменты внешней границы, способ дополнительно содержит, игнорирует один из конусов препятствия, например, конус препятствия, который маловероятно затронет агента или, более широко, конус препятствия, который в наименьшей степени может повлиять на агента, и в более общем случае, конус препятствия, который в наименьшей степени, чем другой конус препятствия может повлиять на агента. Возможные варианты идентичности таких конусов были описаны выше.

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

На этапе 430 способа 400 выбирают, как скорость без столкновений, скорость, соответствующую наименьшему рассчитанному минимальному расстоянию.

На фиг.5 показана блок-схема последовательности операций, иллюстрирующая способ 500 расчета скорости без столкновений для агента в приложении виртуального мира в соответствии с вариантом осуществления изобретения. В способе 500 используется ситуация, которая аналогична ситуации, в которой применяются способы 300 и 400, но она описана по-другому. Каждый один из этапов 510-550 способа 500 выполняют для каждого кадра обновления изображения или этапа времени контура визуальной имитации приложения виртуального мира.

На этапе 510 способа 500 получают исходную скорость для агента. Следует понимать, что при этом не требуется (хотя это разрешено) фактически выполнять расчет; при этом просто требуется, чтобы исходная скорость была известна перед выполнением следующих этапов. Таким образом, исходная скорость может быть рассчитана, получена из сервера виртуального мира, или получена каким-либо другим способом.

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

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

На этапе 540 способа 500 определяют расстояние от исходной скорости до каждой одной из возможных новых скоростей для поиска определенной одной из возможных новых скоростей, которая находится ближе всего к исходной скорости, в одном варианте осуществления, поиск определенной одной из возможных новых скоростей содержит минимизацию (x-x₀)²+(y-y₀)² таким образом, чтобы A_ix+B_iy<C, для каждого одного из конусов препятствия, где (x₀, y₀) представляет исходную скорость, (x, y) представляет собой скорость без столкновения агента, и A_ix+B_iy<C представляет собой проверку линейного ограничения.

На этапе 550 способа 500 выбирают ближайшую одну из множества новых скоростей, как скорость без столкновений для кадра обновления изображения.

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

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

Кроме того, варианты осуществления и ограничения, описанные здесь, не предназначены для публикации, в соответствии с доктриной, посвященной вариантам осуществления и/или ограничениям: (1) не заявлены в явном виде в формуле изобретения; и (2) является или являются потенциально эквивалентными элементам и/или ограничениям выражения в формуле изобретения, в соответствии с доктриной эквивалентов.