Как вдохнуть хотя бы подобие жизни в персонажей компьютерной игры? Стайное поведение (steering behavior) — термин, обозначающий широкий класс вариантов поведения нескольких объектов живой или неживой природы, когда объекты начинают вести себя как часть некой системы — стаи или роя. В качестве примеров таких систем можно привести поток автомобилей, модель «хищник-жертва», столкновение армий воюющих сторон...

Общая суть в том, что объекты в каждой такой системе действуют не сами по себе, а в зависимости от состояния соседних объектов.

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

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

Простые правила

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

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

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

Поиск и избегание цели

Seek and flee steering behaviors

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

В итоге можно сказать, что шаблон «Поиск» заставляет особь двигаться по направлению к цели. Эта сила отличается от «Центральной силы» (гравитационного притяжения), которая в итоге заставляет тела притягиваться и двигаться по орбите — менее массивного вокруг более массивного.

Шаблоны «Поиск» и «Избегание» применяют к особи управляющую силу, направленную по вектору разности между текущим направлением движения особи и желательным направлением (по направлению к цели — для «Поиска», в противоположном направлении — для «Избегания»).

Преследование и уклонение от объекта

Pursuit and evasion steering behaviors

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

В основе шаблонов «Преследования» и «Ускользания» лежат уже знакомые нам «Поиск» и «Избегание». В процессе работы шаблона оценивается возможное положение преследуемой серой особи в следующий момент времени на основе ее текущего местоположения, скорости, направления движения и расстояния от преследователя (или беглеца).

Эта оценка будущего положения цели обозначена как прицел (круг с крестиком). Зеленая особь применяет «Поиск» для достижения оцененной будущей позиции серой жертвы, а красная применяет «Избегание» для уклонения от серой. Когда зеленый преследователь настигнет серую жертву, цель будет достигнута.

Блуждание

Wander steering behavior

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

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

Такая модель блуждания зависит от следующих параметров:

величины поворота траектории движения, которая меняется от 0 (направление не изменяется) до 1. Эти изменения можно видеть по движению красной прерывистой линии по белой линии. скорости изменения направления движения, меняющейся от 0 (без изменений) до 1 (быстрые неустойчивые изменения). Эта величина показана как радиус белого круга.

Прибытие к месту назначения

Arrival steering behavior

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

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

Обход препятствий

Obstacle avoidance steering behavior

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

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

Движение в ограниченной области

Containment steering behavior

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

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

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

Есть несколько стратегий зондирования. Зеленая особь использует три ложноножки — одна направлена всегда вперед по ходу движения, а две другие — слегка в стороны. Голубая особь применяет одну-единственную, но ее направление меняется случайно, двигаясь по эллиптической орбите.

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

Особи ничего не знают друг о друге.

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

Следование вдоль стены

Wall following steering behavior

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

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

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

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

Следование по маршруту

Path following steering behavior

Зеленая особь движется по заданному маршруту. Ее задача — следовать пути в заданном направлении (вход слева — выход справа), придерживаясь центра серой области. Путь задан серией взаимосвязанных участков (отрезков) и размером. Этот шаблон похож на «Следование вдоль стены» и «Движение в ограниченной области», отличаясь от них лишь наличием направленного движения.

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

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

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

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

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

Взаимодействие особи и пути проходит по следующему протоколу: случайная точка отображается в точку на пути, преобразуется в отрезок пути и т.д. Знаний о форме пути не требуется.

Движение в поле течения

Flow field following steering behavior

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

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

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

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

Рассредоточение

Separation

Рассредоточение объектов в неком локальном объеме. Объекты выдерживают определенную дистанцию друг относительно друга.

Регулировка движения

Alignment

Движение объектов в неком усредненном направлении. В итоге система имеет единый вектор движения.

Сплоченность

Cohesion

Объекты стремятся не разбегаться, а сохранять определенную дистанцию друг относительно друга.

Комбинации правил

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

Гонка за лидером

Leader following steering behavior

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

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

Гонка за лидером сочетает рассредоточение (чтобы избежать столпотворения) и прибытие к месту назначения (стремление двигаться к лидеру, замедляя движение, если лидер находится близко). Применение прибытия объясняет движение преследователей на некотором почтительном расстоянии от лидера. К тому же преследователь изменяет свое направление движения, если его будущая позиция будет находиться слишком близко от будущей позиции лидера.

Если произошло столкновение особей, они вспыхивают красным цветом.

Следование в потоке

Crowd path following steering behavior

Толпа из тридцати особей создает поток движения. Каждая особь использует следование по маршруту; также применяется рассредоточение, чтобы особи не лезли друг другу «на голову» и не сбивались в стаи. Два шаблона комбинируются по средневзвешенной схеме, причем следование по маршруту получает вес в три раза больший, чем рассредоточение.

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

Очередь

Queuing steering behavior (at a doorway)

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

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

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

Хаотическое движение с обходом препятствий

Unaligned collision avoidance steering behavior

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

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

Если столкновение все же произошло, оно помечается вспышкой красного цвета.

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

Моделирование стадного инстинкта

Flocking

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

Инструмент для построения демонстраций

Для создания примеров применялся движок LKI Creator, расширенный для эмуляции стайного поведения автономных персонажей. Персонажами могут быть люди, животные, машины, самолеты и иные подвижные объекты.

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

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