МОДЕЛЬ НАПРАВЛЕННОГО ДВИЖЕНИЯ ГРУПП ОБЪЕКТОВ В ПРОСТРАНСТВЕ С ПРЕПЯТСТВИЯМИ

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

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

В качестве основного алгоритма выбора и обхода пути был выбран алгоритм стиринга (Steering behavior) [2]. Идеи, лежащие в основе стиринга, были предложены Крейгом Рейнольдсом. В них не используются сложные стратегии, связанные с планированием пути или огромные вычисления, вместо этого используется доступная информация, например, силы, действующие на соседних персонажей (юнитов). Это делает их простыми для понимания и реализации, при этом, позволяя очень сложные паттерны перемещения.

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

Рисунок 1 Передвижение юнита по кривой, например при огибании препятствия

Для реализации поворотов объектов в пространстве были использованы кватернионы.

Кватернион — это четверка чисел, которые ввел в обращение Уильям Гамильтон в виде гиперкомплексного числа [1]. Мы будем рассматривать кватернион как четыре действительных числа, например, как 4d вектор или 3d вектор и скаляр.

,                                                                      (1)

где – вектор, а  – скалярная величина.

Первые три компонента представляют вектор, лежащий на оси вращения, причем длина вектора зависит от угла поворота. Четвертый компонент зависит только от величины угла поворота. Зависимость довольно простая — если взять единичный вектор  за ось вращения и угол  за вращение вокруг этой оси, тогда кватернион, представляющий это вращение можно записать как:

,                                                              (2)

где  – единичный вектор.

Рисунок 2 Кватернион и его представление в виде матрицы вращения

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

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

Метод k-средних - наиболее популярный метод кластеризации. Был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров:

                                                                   (3)

где  — число кластеров,  — полученные кластеры,  и  — центры масс векторов .

Идея алгоритма k-средних:

1. Задается число кластеров k.

2. Случайным образом выбираются k объектов, их параметры будут начальными центрами k кластеров.

3. Для каждого объекта исходного множества I определяется ближайший к нему центр кластера.

4. Вычисляется центр тяжести каждого кластера, как усреднение параметров по всем объектам, попавшим в кластер. Они становятся новыми центрами кластеров для следующих итераций алгоритма. Шаги 3,4 повторяются до тех пор, пока границы кластеров и расположение центров изменяются.

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

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

Рисунок 3 Общий вид сцены

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

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

Рисунок 4. Пример работы программы: обход препятствия

Список литературы:

1. Норель М. Вращение и кватернионы. Сборник рецептов // Разработка игр. — 2004. [электронный ресурс] — Режим доступа. — URL: http://www.gamedev.ru/code/articles/?id=4215 (дата обращения 11.05.2016)
2. Reynolds C. W.  Steering Behaviors For Autonomous Characters / C.W. Reynolds// Game Developers Conference 1999 held in San Jose, California. - 1999. P. 763-782.