Boids — простой алгоритм перемещения групп юнитов

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

Под катом описание алгоритма с примерами кода.

Описание

Алгоритм Boids был создан Крейгом Райнольдсом (Craig Reynolds) в 1986-м году как модель перемещения стаи птиц. В его основе лежат три следующих правила:

• Сплоченность — юниты стараются держаться как можно ближе друг к другу


• Разделение — юниты стремятся разойтись с целью держаться друг от друга на некотором расстоянии


• Выравнивание скоростей — юниты из одной группы стремятся двигаться с одинаковой скоростью

В качестве дополнения к ним я воспользовался ещё двумя:

• Движение к цели — юниты стараются двигаться к заданной цели


• Избегание препятствий — юниты стремятся в противоположную сторону от препятствий

Об имплементации

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

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

v1 = Rule1();
v2 = Rule2();
v3 = Rule3();
unit.v = v1 + v2 + v3 + unit.v;
unit.pos = unit.pos + unit.v;

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

Правила реализуются так:

1. Сплоченность — необходимо найти центр масс (среднее арифметическое координат всех юнитов) и определить вектор, направленный от текущего юнита в центра масс.


2. Разделение — нужно определить среднее направление от всех ближайших юнитов.


3. Выравнивание скоростей — необходимо найти среднюю скорость всех юнитов.


4. Движение к цели — вектор, направленный от юнита в сторону цели.


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

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

Код

А теперь немного кода. Основной код, занимающийся перемещением всех юнитов (Ships — речь идёт о космических кораблях): http://ift.tt/1jIpptO Кроме вышеописанного тут ещё проверяется столкновение юнитов с планетами и вылет за пределы мира. Ограничение скорости — нормированный вектор (представляющий собой направление), умноженный на органичивающий коэффициент: http://ift.tt/1jr87xY

Реализация правил: http://ift.tt/1jIpptS Особенности реализации — часть правил пременяются только к юнитам из текущей группы (принадлежащих одному игроку и имеющими одну и ту-же цель). Distance — расстояние в геометрическом смысле.

Спавнинг кораблей реализован следующим образом. У каждой планеты имеется очередь кораблей, ожидающих спавнинга. Когда игрок отдаёт команду — создаётся несколько кораблей (от 1-го до ~20, в зависимости от количества энергии) и заносятся в очередь планеты: http://ift.tt/1jIpptU А затем, каждые 50 миллисекунд спавнится по одному кораблю: http://ift.tt/1jr87y0

Плюсы и минусы

Алгоритм больше подходит для симмуляции «живых» юнитов. Его хорошо применять в тех случаях, когда допустимо «роевое» поведение группы. В случае, если необходимо организовать более строгое движение юнитов, скорее всего придётся воспользовать другим алгоритмом (или какой-то из модификаций). Так же мне не удалось организовать проход одной группы юнитов через другую при их перпендикулярном движении — либо одна группа начинала сталкивать другую с траектории (и в итоге обходила её сбоку) — либо юниты одной группы начинали проходить сквозь юнитов из второй (почти не огибая их). На встречных курсах ситуация лучше — иногда одна группа разделяла вторую на две и проходила по центру, а иногда проходила рядом с ней. В целом, путём многократного эксперементирования с параметрами, Boids позволят добиться хорошо выглядящих результатов, подходящих для разных ситуаций.

Ссылки

http://ift.tt/1kTMJ5z — описание алгоритма в википедии

http://ift.tt/1jr85pZ — псевдокод boids — с описанием некоторых эвристик

http://ift.tt/1jIps93 — описание boids и его различных вариаций (более теоретическое)

http://ift.tt/1jIppK8 — исходники (реализация boids в server/world.cpp)

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.