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 — речь идёт о космических кораблях): 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)
    Share post

    Similar posts

    Comments 23

      +4
      Эй! Нечестно, видео закончилось на самом интересном месте, а мне так хочется знать — отвоевали красные ту большую синюю планету?
      А вообще на 1:25 корабли жестко ступили, нужно увеличить размер Collider у планет, что бы звездолеты их облетали по более высокой орбите.
        +1
        Пробовал — но тогда они начинают застревать в пространствах между двумя планетами, в случае если ближайший курс лежит между ними. Мне кажется что лучшим решением здесь будет воспользоваться тем-же A* для расчёта кратчайшего пути.
          +9
          Играйте на здоровье :)
            +3
            Зараза еще та… ) Оторваться невозможно)
              0
              Ни разу не проиграл, есть с ботами поумнее?
                0
                Да, не очень сложная. Я её тут привёл как пример с похожим алгоритмом движения частиц. Сам на неё напал, когда искал игры с программированием. На том ресурсе нашёл Light Bot, потому просканировал весь ресурс, и Микробики мне запомнились как хорошая казуалка.
                  0
                  www.galcon.com/flash/play.php — я делал клона этой штуки — там есть сетевой режим игры (и даже не пустые сервера).
                    0
                    Мультиплеер не работает, а вот играть действительно интересно уровня с 7го:) Хотя есть подозрение, что после того, как перестает показываться кол-во кораблей на планете, игра читит и у неё ресурсов изначально раза в два больше!
                • UFO just landed and posted this here
                    +1
                    Еще неплохая вариация на тему Eufloria
                  +1
                  Я думаю, отправка кораблей от планеты к ней же самой есть ошибка.
                    +1
                    Так и есть — игрушка ещё сырая.
                    0
                    Когда занимался сервером Lineage, то для перемещения больших групп практиковал очень простой алгоритм — в каждой маршрутной точке на пути группы ставил для участников группы квадрат размером ­±RAND()*разброс и посылал каждого участника по соответствующему пути уже на общих основаниях, включая отработку коллизий. Получается весьма реалистичное поведение. Участники идут немного вразнобой, с чуть разными скоростям при относительно коротких плечах перехода, изредка, подойдя близко друг к другу, меняют строй.

                    Разве что, сейчас только подумал, начало движения было у всех одинаковое. Можно было давать команду на движение не одновременно, а с небольшой задержкой на уровне типичной задержки реакции человека в 0,2..0,4 сек :) Приход же в конечную точку за счёт рандомизации итак было чуть-чуть не одновременным.
                      0
                      Верле не достаточно? Полно готовых реализаций для него. Смотрится живописно.
                        0
                        Метод интегрирования можно применять любой. Сложность заключается в модели (т. е. уравнениях движения).
                          +1
                          В Верле можно задавать ограничения, это отчасти уже описание движения. Отвлекаясь от темы, я ищу для себя математику описывающую поведение аморфного тела(капли масла на на наклонной плоскости) в отличии от повсеместной динамики твердого тела(шаров на столе). Посоветуете что нибудь? И спасибо за статью.
                            0
                            Интересно, надо будет попробовать. Посоветовать вряд ли что-то смогу — к сожалению не знаком с моделированием жидкостей.
                              0
                              Интересно, что вы такое делаете? Я выдумываю: если нужно примерно смоделировать положение центра тяжести капли — почему бы просто не взять тот же Верле и не добавить туда силу трения о поверхность, пропорциональную скорости? Или вам нужна форма капли?
                          +2
                          А помните гениальную русскую модель стадности коров?

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

                          Россияне придумали следующий алгоритм стадности. Если одна корова видела
                          бегущую корову своего вида — она начинала бежать в том же направлении.
                          Любопытно, что никто, кроме россиян, не додумался до такой идеи. По словам
                          организаторов игры, именно эта не рассуждающая массовость принесла
                          россиянам победу.
                            0
                            А что за игра?
                              0
                              Да конкурс был. Надо было AI животных моделировать.
                                0
                                Microsoft Terrarium, если не ошибаюсь.
                              0
                              На хабре есть хорошая статья, подробно описывающая алгоритм боидов — habrahabr.ru/post/182382/
                              И продолжение об оптимизации — habrahabr.ru/post/182690/

                              Only users with full accounts can post comments. Log in, please.