Во время разработки клона одной игрушки мне понадобилось перемещать группы юнитов от одной планеты к другой. Первое что пришло в голову — заспавнить юниты один за другим и двигать их по прямой. Но это выглядело не очень весело, кроме того — нужно было как-то обходить планеты. После беглого ознакомления с алгоритмами группового перемещения я решали попробовать 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;
Чтобы юнит сильно не разгонялся — скорость рекомендуется ограничивать. Спавнить юниты, вылетающие из одной точки лучше всего по очереди, через короткие промежутки времени.
Правила реализуются так:
- Сплоченность — необходимо найти центр масс (среднее арифметическое координат всех юнитов) и определить вектор, направленный от текущего юнита в центра масс.
- Разделение — нужно определить среднее направление от всех ближайших юнитов.
- Выравнивание скоростей — необходимо найти среднюю скорость всех юнитов.
- Движение к цели — вектор, направленный от юнита в сторону цели.
- Избегание препятствий — совпадает со вторым, за исключеним того что направление нужно искать в сторону от ближайших препятствий.
На практике скорости, выданные каждым из правил необходимо уменьшать (путём деления на какой-то коэффициент) или ограничивать. Ограничения и коэффициенты подбираются экспериментальным путём для достижения наилучшего результата.
Код
А теперь немного кода. Основной код, занимающийся перемещением всех юнитов (Ships — речь идёт о космических кораблях): pastebin.com/jeHCWr8u Кроме вышеописанного тут ещё проверяется столкновение юнитов с планетами и вылет за пределы мира. Ограничение скорости — нормированный вектор (представляющий собой направление), умноженный на органичивающий коэффициент: pastebin.com/a57hh76V
Реализация правил: pastebin.com/YDSTDh3t Особенности реализации — часть правил пременяются только к юнитам из текущей группы (принадлежащих одному игроку и имеющими одну и ту-же цель). Distance — расстояние в геометрическом смысле.
Спавнинг кораблей реализован следующим образом. У каждой планеты имеется очередь кораблей, ожидающих спавнинга. Когда игрок отдаёт команду — создаётся несколько кораблей (от 1-го до ~20, в зависимости от количества энергии) и заносятся в очередь планеты: pastebin.com/FprtwTy4 А затем, каждые 50 миллисекунд спавнится по одному кораблю: pastebin.com/Tq4cvNbB
Плюсы и минусы
Алгоритм больше подходит для симмуляции «живых» юнитов. Его хорошо применять в тех случаях, когда допустимо «роевое» поведение группы. В случае, если необходимо организовать более строгое движение юнитов, скорее всего придётся воспользовать другим алгоритмом (или какой-то из модификаций). Так же мне не удалось организовать проход одной группы юнитов через другую при их перпендикулярном движении — либо одна группа начинала сталкивать другую с траектории (и в итоге обходила её сбоку) — либо юниты одной группы начинали проходить сквозь юнитов из второй (почти не огибая их). На встречных курсах ситуация лучше — иногда одна группа разделяла вторую на две и проходила по центру, а иногда проходила рядом с ней. В целом, путём многократного эксперементирования с параметрами, Boids позволят добиться хорошо выглядящих результатов, подходящих для разных ситуаций.
Ссылки
en.wikipedia.org/wiki/Boids — описание алгоритма в википедии
www.kfish.org/boids/pseudocode.html — псевдокод boids — с описанием некоторых эвристик
habrahabr.ru/post/105639/ — описание boids и его различных вариаций (более теоретическое)
github.com/bakwc/ozifi/tree/master/projects/space_capture — исходники (реализация boids в server/world.cpp)
Автор: bak
