Как сделать smart толпу в игре и почему лидер толпы это важно.

Введение

Если вы не читали первую часть, советую начать с неё (Часть 1 — архитектура). В этой части я расскажу более подробно о таком классе NPC как толпа.

Толпу возможно спроектировать разными способами, проще всего это сделать при помощи простого behavior tree, однако в этой статье я начну проектировать толпу по GOAP методике, которую описал в предыдущей статье.

Примеры будут написаны на языке C# и движке Unity 3d, т.к. он очень хорошо справляется с быстрым прототипированием подобных сцен и легко протестировать гипотезы и новую архитектуру. Я буду скрывать подробные реализации, а сами исходники приложу в качестве GitHub проекта.

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

Приятного чтения!

Сложности вычислений ИИ

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

Представим простую сцену, где у нас одновременно находится N персонажей (от 100). И обычный метод расчета вероятности вызова для цели ReactOnCharacter, которое должно стриггерить NPC на разговор с другим персонажем в случае их столкновения или преграждения пути.

Самый банальный пример алгоритма столкновения - каст области вокруг. В большинстве движков используется spatial search. Если стоит задача реализовать NPC на сервере (например .Net Core или С++ сервер), то она усложняется отсутствием подобных утилит и такой способ придется реализовывать с нуля. С этим вытекают дополнительные архитектурные требования: система контроля позиций всех динамических юнитов игры (игровых и неигровых персонажей, транспорта и т.д), movement prediction и latency/lag compensation, а также системы контроля изменений мира (особенно актуально для игр песочниц).

После всего этого каждые N миллисекунд необходимо проверять каждого персонажа на расстояние к ближайшим найденным NPC. Это все увеличивает нагрузку на CPU, поэтому потребует также коррекции внутри целей и поведений.

Толпа

Толпа (crowd), часто применяется в играх в качестве типа NPC для создания ощущения насыщенности игрового пространства, а также в качестве спасения CPU от постоянных вычислений. Толпа не является индивидуальным типом NPC и скорее всего не будет представлять высококачественное поведение каждой сущности по отдельности (кроме локальных взаимодействий и IK/анимаций).

Для работы с толпой нам понадобится сущность лидера. Лидер представляет собой основного юнита, внутри которого и будет происходить обработка всех расчетов вероятности.

С точки зрения GOAP и схожих механик, даже если вы пишете самопальную архитектуру ИИ, особой разницы не будет, концепция остается одной. Вкратце заключается она в следующем: в наличии есть сущность участника группы (скажем, crowd member) и лидер группы (crowd leader). Лидер группы из основной своей выборки строит план действий, участники группы в свою очередь повторяют его действия и могут дополнять мелкой вариативностью.

Базовая архитектура

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

1. Подготовка

Итак. Нам нужна сцена, нам нужны капсулы, плоскость, навмеш и спавнер.

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

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

1. Архитектура GOAP

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

Вкратце по скриптам и что у нас есть:
• AtomicGoals - простейшие задачи, состоящие зачастую из одного действия и контролирующие статус выполненности цели.
• CompositeGoals - составные задачи, которые либо собирают несколько CompositeGoals, либо несколько AtomicGoals.
• Core - абстракции архитектуры.
• Evaluators - оценщики, смотрят на целесообразность выполнения действия глядя на условия мира.
• Features - утилиты для целей, например поиск героев вокруг.
• Movement - корневой функционал по передвижению. За основу взята логика steering movement из книги "Programming Game AI by Example".
• NPCOfflineManager и OfflineNPC - заглушки, касающиеся спавна NPC и обработки ThinkGoal.

2. Дизайн интеллекта

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

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

Технически лидер это каждый отдельный NPC, для создания участника группы есть два варианта:

1. Повторяем цели лидера без их оценки. Эвалюаторы всех задач NPC не будут использованы, а значит нагрузка на каждые N мс "мозга" не нужна;

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

Так как я описываю GOAP, давайте его придерживаться до конца, плюс немного вариативности логике не помешает.

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

Реализация логики толпы

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

Обозначу основные правила, которые нужно учесть в такой схеме:

• Голосование происходит пока не истечет время на него, каждое голосование определяется уникальным ID по которому персонажи продолжают голосовать, пока не выберется лидер;

• Участники могут голосовать только один раз;

• Если лидер уничтожен, то голосование начинается заново;

• Лидером становится тот NPC, за которого проголосовало большинство;

  

public class NPCSpawner : MonoBehaviour
{
		// Лидер, доступ к которому имеют все NPC группы
    public NPC GroupLeader {get; set;}
    
    // Участники размещают свои голоса в книгу голосований
    public Dictionary<NPC, int> VoteBook = new Dictionary<NPC, int>();
    public GroupTypeEnum GroupType;

		// ID для определения участниками текущего голосования
    public Guid VotingId = Guid.NewGuid();

		// Время нужное для определния голосования и таймеры
    private float _votingTime = 5;
    private float _lastVoteTime;
    private bool _voteRuns = true;
    
    private void Update()
    {
    		// Обычная система таймера и выборка из книги голосов
        if (Time.time > _lastVoteTime + _votingTime)
        {
            if (_voteRuns)
            {
                _voteRuns = false;
                var potentialLeader = VoteBook.FirstOrDefault(a => a.Value == VoteBook.Max(b => b.Value));
                GroupLeader = potentialLeader.Key;
                
                var leaderMaterial = GroupLeader.GetComponent<MeshRenderer>().material;
                if (leaderMaterial.GetColor("_Color") != Color.white)
                    leaderMaterial.SetColor("_Color", Color.white);
            }
            
            // Начать голосование при потере лидера
            if (GroupLeader == null && !_voteRuns)
            {
                _lastVoteTime = Time.time;
                _voteRuns = true;
                VoteBook.Clear();
                VotingId = new Guid();
            }

        }
    }
}

...
  	// Эвалюатор дает сигнал цели голосовать при смене айди
    public override double CalculateDesirability(NPC bot)
    {
        if (bot.Home.VotingId == _lastVoted)
            return 0;
        
        _lastVoted = bot.Home.VotingId;
        return 1;
    }
...

...
  
    public override GoalStatus Process()
    {
        if (Status == GoalStatus.Inactive) Activate();

        var npcAround = NPCFeature.GetNearestNPCs(Owner, 10).ToList();
        if (npcAround.Count == 0)
        {
            Status = GoalStatus.Completed;
            return Status;
        }

        // Поиск случайного персонажа вокруг для голоса
  			// Возможно улучшить до эвристик (сила, здоровье, хар-ки)
        var rndNpc = Random.Range(0, npcAround.Count);
        if (Owner.Home.VoteBook.ContainsKey(npcAround[rndNpc]))
            Owner.Home.VoteBook[npcAround[rndNpc]] ++;
        else 
            Owner.Home.VoteBook[npcAround[rndNpc]] = 1;

        return Status;
    }
...

Шаг 2. Следующее, что необходимо сделать, это переработать эвалюаторы для работы только на лидерах.

Набор эвалюаторов выглядит следующим образом:

var evaluators = new List<GoalEvaluator>
{
    new VoteForLeaderGoalEvaluator(1),
    new ExploreGoalEvaluator(1),
    new IdlingGoalEvaluator(1),
    new LookAtPlayerGoalEvaluator(1)
};

После того как лидер был определен, мы переходим в рассчет цели Explore. Технически это поиск пути и выбор направления движения. Затем задачи Idle и LookAt (остановиться для "общения" возле героя, пример взят из боевого проекта, в рамках статьи не рассматривается, но как пример оставлю).

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

...
public override double CalculateDesirability(NPC bot)
{
  return bot.Home.GroupLeader == bot ? 0 : 1;
}
...

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

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

Шаг 3. Добавим немного геймплея - создадим новую цель уничтожения противника при тесном контакте с ним. Небольшой дизайн:

1. Атака противника будет приоритетнее движения за лидером;

2. Атака происходит на небольшом расстоянии и только с группой противника;

3. Шанс убийства будет 1 из 3 в случайном порядке, таким образом мы не сможем предугадать кто уничтожит противника, однако если на него нападет группа - шанс уничтожить одного юнита возрастает;

4. Атаковать может как лидер, так и участник команды, поэтому оставим это как цель для всех (назовем AttackNearestTargetGoal);

5. Для цели движения за лидером понизим приоритет эвалюатора до 0.9, а для атаки до 1, чтобы наверняка не продолжать идти за лидером в случае столкновения.

Проверка толпы

Я не буду останавливаться здесь на подробностях юнит и интеграционных тестов, а также вариантах отладки ИИ в играх, выведу для этого отдельную статью.

А в этой, посмотрите, что в итоге получилось:

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

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

Исходники кода прикладываю в дополнительных материалах.

Вывод

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

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

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

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

Дополнительные материалы

1. https://github.com/StanKryvenko/goap_development - исходники проекта, в будущем будет расширяться новыми демо, по этой статье папка называется Crowd;

2. stannot.es - мой блог о разработке игр, торговых ботов и размышления о будущем;

3. https://www.youtube.com/watch?v=gm7K68663rA - неплохой материал по GOAP техникам на конференции GDC;

4. https://www.youtube.com/watch?v=Wb84Vi7XFRg - разбор игры стратегии Command & Conquer, как еще можно реализовать интеллект в подобных играх.