Первая часть статьи здесь.

Часть 6. Избегание коллизий

Для правильной навигации NPC часто требуется способность избегать препятствий. В этой части мы рассмотрим steering behavior collision avoidance (избегание коллизий), позволяющее персонажам благополучно уворачиваться от препятствий в окружении.

---

Введение

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

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


Анализируются препятствия перед персонажем и выбирается ближайшее (наиболее угрожающее).

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

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

---

Смотрим вперёд

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

Как объяснялось в предыдущей статье, направление движения персонажа описывает вектор скорости. Мы используем его для создания нового вектора с названием ahead, который будет являться копией вектора скорости, но с другой длиной:


Вектор ahead — это линия видимости персонажа.

Этот вектор вычисляется следующим образом:

ahead = position + normalize(velocity) * MAX_SEE_AHEAD

Длина вектора ahead (изменяемая с помощью MAX_SEE_AHEAD) определяет расстояние, на которое персонаж может «видеть».

Чем больше MAX_SEE_AHEAD, тем раньше персонаж будет начинать уклоняться от препятствия, потому что оно будет восприниматься как угроза, даже находясь далеко:


Чем больше длина ahead, тем раньше персонаж будет предпринимать меры по уклонению от препятствия.

---

Проверка коллизии

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

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

Вектор ahead будет использоваться для создания ещё одного вектора в половину его длины:


То же направление, половинная длина.

Вектор ahead2 вычисляется точно так же, как ahead, но его длина укорочена вдвое:

ahead = position + normalize(velocity) * MAX_SEE_AHEAD
ahead2 = position + normalize(velocity) * MAX_SEE_AHEAD * 0.5

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

Если расстояние меньше или равно радиусу сферы, то вектор находится внутри сферы и коллизия обнаружена:


Вектор ahead пересекается с препятствием, если d < r. Чтобы было понятнее, вектор ahead2 убран.

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

private function distance(a :Object, b :Object) :Number {
	return Math.sqrt((a.x - b.x) * (a.x - b.x)  + (a.y - b.y) * (a.y - b.y));
}

private function lineIntersectsCircle(ahead :Vector3D, ahead2 :Vector3D, obstacle :Circle) :Boolean {
	// свойство "center" препятствия - это Vector3D.
	return distance(obstacle.center, ahead) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius;
}

Если блокирует путь персонажа несколько препятствий, то для вычислений выбирается ближайшее (наиболее угрожающее):


Для вычислений выбирается ближайшее препятствие (наиболее угрожающее).

---

Вычисление силы избегания

Сила избегания должна отталкивать персонажа от препятствия, позволяя ему уклониться от сферы. Это можно реализовать с помощью вектора, сформированного с помощью центра сферы (вектора позиции) и вектора ahead. Мы вычисляем эту силу избегания следующим образом:

avoidance_force = ahead - obstacle_center
avoidance_force = normalize(avoidance_force) * MAX_AVOID_FORCE

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


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

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

---

Избегание препятствия

Готовая реализация метода collisionAvoidance(), возвращающего силу избегания, будет иметь такой вид:

private function collisionAvoidance() :Vector3D {
	ahead = ...; // вычисление вектора ahead
	ahead2 = ...; // вычисление вектора ahead2

	var mostThreatening :Obstacle = findMostThreateningObstacle();
	var avoidance :Vector3D = new Vector3D(0, 0, 0);

	if (mostThreatening != null) {
		avoidance.x = ahead.x - mostThreatening.center.x;
		avoidance.y = ahead.y - mostThreatening.center.y;

		avoidance.normalize();
		avoidance.scaleBy(MAX_AVOID_FORCE);
	} else {
		avoidance.scaleBy(0); // обнуление силы избегания
	}

	return avoidance;
}

private function findMostThreateningObstacle() :Obstacle {
	var mostThreatening :Obstacle = null;

	for (var i:int = 0; i < Game.instance.obstacles.length; i++) {
		var obstacle :Obstacle = Game.instance.obstacles[i];
		var collision :Boolean = lineIntersecsCircle(ahead, ahead2, obstacle);

		// "position" - это текущая позиция персонажа
		if (collision && (mostThreatening == null || distance(position, obstacle) < distance(position, mostThreatening))) {
			mostThreatening = obstacle;
		}
	}
	return mostThreatening;
}

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

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

steering = nothing(); // нулевой вектор, обозначающий "нулевую величину силы"
steering = steering + seek(); // предполагаем, что персонаж к чему-то стремится
steering = steering + collisionAvoidance();

steering = truncate (steering, max_force)
steering = steering / mass

velocity = truncate (velocity + steering, max_speed)
position = position + velocity

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

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

---

Усовершенствование распознаваний коллизий

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

Если такое случится, то персонаж коснётся (или войдёт) в препятствие, пропуская процесс избегания, потому что коллизия не обнаружена:


Иногда векторы ahead находятся снаружи препятствия, но персонаж внутри.

Эту проблему можно устранить, добавив к проверке коллизий третий вектор: вектор позиции персонажа. Использование трёх векторов значительно улучшает распознавание коллизий.

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


Маневрирование может привести к коллизии, даже если персонаж всего лишь поворачивается.

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

dynamic_length = length(velocity) / MAX_VELOCITY
ahead = position + normalize(velocity) * dynamic_length

Переменная dynamic_length изменяется в интервале от 0 до 1. Когда персонаж движется на полной скорости, dynamic_length равна 1; когда персонаж замедляется или ускоряется, dynamic_length равна 0 или больше (например, 0.5).

Следовательно, если персонаж просто маневрирует без движения, dynamic_length стремится к нулю, создавая нулевой вектор ahead, не имеющий коллизий.

---

Демо: время зомби!

Чтобы продемонстрировать поведение избегания препятствий в действии, лучше всего подойдёт орда зомби. Ниже показано демо с несколькими зомби (у всех них разная скорость), стремящимися (seek) к курсору мыши.


Интерактивное демо на Flash находится здесь.

---

Заключение

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

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

Часть 7. Следование по пути

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

---

Введение

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

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

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

---

Задание пути

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

Если вам нужно использовать кривые, то их можно свести к множеству соединённых точек:


Кривые и отрезки.

Для описания маршрута будет использоваться класс Path. По сути, у класса есть вектор точек и несколько методов для обработки этого списка:

public class Path
{
	private var nodes :Vector.<Vector3D>;

	public function Path() {
		this.nodes = new Vector.<Vector3D>();
	}

	public function addNode(node :Vector3D) :void {
		nodes.push(node);
	}

	public function getNodes() :Vector.<Vector3D> {
		return nodes;
	}
}

Каждая точка пути — это Vector3D, представляющий собой позицию в пространстве, аналогично тому, как работает свойство position персонажа.

---

Движение от узла к узлу

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

Каждую точку на пути можно рассматривать как цель, поэтому мы можем использовать поведение Seek:


Выполнение Seek от одной точки к другой.

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

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

public class Boid
{
	public var path	:Path;
	public var currentNode	:int;
	(...)

	private function pathFollowing() :Vector3D {
		var target :Vector3D = null;

		if (path != null) {
			var nodes :Vector.<Vector3D> = path.getNodes();

			target = nodes[currentNode];

			if (distance(position, target) <= 10) {
				currentNode += 1;

				if (currentNode >= nodes.length) {
					currentNode = nodes.length - 1;
 				}
 			}
 		}

		return null;
 	}

 	private function distance(a :Object, b :Object) :Number {
		return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
 	}
 	(...)
}

Метод pathFollowing() отвечает за генерирование силы следования по пути. Пока он не создаёт силы, но правильно выбирает цели.

Тест path != null проверяет, следует ли персонаж по какому-нибудь пути. Если это так, то используется свойство currentNode для поиска текущей цели (той, к которой должен стремиться персонаж) в списке точек.

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

---

Вычисление и прибавление сил

Сила, используемая для подталкивания персонажа к каждому узлу пути — эта сила поведения seek. В методе pathFollowing() уже выбран соответствующий код, поэтому теперь он должен возвращать силу, которая подталкивает персонажа к этому узлу:

private function pathFollowing() :Vector3D {
  var target :Vector3D = null;

  if (path != null) {
    var nodes :Vector.<Vector3D> = path.getNodes();

    target = nodes[currentNode];

    if (distance(position, target) <= 10) {
        currentNode += 1;

        if (currentNode >= nodes.length) {
            currentNode = nodes.length - 1;
        }
    }
  }

  return target != null ? seek(target) : new Vector3D();
}

После вычисления силы следования по пути, её, как обычно, необходимо прибавить к вектору скорости персонажа:

steering = nothing(); // нулевой вектор, обозначающий "нулевую величину силы"
steering = steering + pathFollowing();

steering = truncate (steering, max_force)
steering = steering / mass

velocity = truncate (velocity + steering, max_speed)
position = position + velocity

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

Результат будет следующим:


Интерактивное демо на Flash находится здесь.

---

Сглаживание движения

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

В природе все движения стремятся следовать принципу наименьших усилий. Например, человек не идёт постоянно посередине коридора; если впереди поворот, то он приближается к стене, чтобы сократить расстояние.

Этот паттерн можно воссоздать добавлением к пути радиуса. Радиус применяется к точкам и может рассматриваться как «ширина» маршрута. Он будет управлять тем, насколько может удаляться персонаж от точек, двигаясь по пути:


Влияние радиуса на следование по пути.

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


Интерактивное демо на Flash находится здесь.
Чем больше радиус, тем шире маршрут и тем больше расстояние до точек, которое персонажи будут сохранять при поворотах. Значение радиуса можно изменять, чтобы создавать различные паттерны следования.

---

Вперёд и назад

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

Этого можно достичь, добавив в класс персонажа свойство pathDir; это целое значение, управляющее направлением, в котором персонаж движется по пути. Если pathDir равно 1, то персонаж движется к концу пути; -1 обозначает движение к началу.

Метод pathFollowing() можно изменить следующим образом:

private function pathFollowing() :Vector3D {
    var target :Vector3D = null;

    if (path != null) {
        var nodes :Vector.<Vector3D> = path.getNodes();

        target = nodes[currentNode];

        if (distance(position, target) <= path.radius) {
            currentNode += pathDir;

            if (currentNode >= nodes.length || currentNode < 0) {
                pathDir *= -1;
                currentNode += pathDir;
            }
        }
    }

    return target != null ? seek(target) : new Vector3D();
}

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

После этого тест проверяет, достиг ли персонаж конца маршрута. Если это так, то pathDir умножается на -1, что обращает значение, заставляя персонаж обратить своё направление движения.

В результате мы получим паттерн движения вперёд и назад.

---

Заключение

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

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

Часть 8. Следование за лидером

В дополнение к способности следовать по пути, персонаж (или группа персонажей) также должна уметь следовать за каким-то персонажем (например командиром отряда). Эту задачу можно решить с помощью поведения leader following (следование за лидером).

---

Введение

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

При поведении seek персонаж подталкивается к цели, рано или поздно занимая то же самое место, что и цель. Поведение pursuit, с другой стороны, подталкивает персонажа к другому персонажу, но с целью поймать его (на основании прогнозов), а не просто следовать за ним.

При поведении следования за лидером задача заключается в том, чтобы оставаться достаточно близко к лидеру, но слегка позади него. Кроме того, когда персонаж находится далеко, то он должен двигаться к лидеру быстрее, но замедляться при сокращении расстояния. Этого можно достичь сочетанием трёх steering behaviors:

• Arrive: движение к лидеру с постепенным замедлением и остановкой движения.
• Evade: если персонаж находится на пути лидера, то должен быстро отодвинуться.
• Separation (разделение): избежание скученности, когда за лидером следует несколько персонажей.

Ниже я объясню, как каждое из этих поведений можно скомбинировать для создания паттерна следования за лидером.

---

Нахождение нужной точки для следования

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

tv = leader.velocity * -1;
tv = normalize(tv) * LEADER_BEHIND_DIST;
behind = leader.position + tv;

Если вектор скорости умножается на -1, то результат будет обратным вектору скорости. Этот результирующий вектор (называемый tv) затем можно нормализировать, отмасштабировать и прибавить к текущей позиции персонажа.

Вот визуальное отображение процесса:


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

Чем больше LEADER_BEHIND_DIST, тем больше расстояние между лидером и точкой позади него. Так как персонажи будут следовать за этой точкой, то чем дальше она от лидера, тем дальше от него будут персонажи.

---

Следование и прибытие

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

private function followLeader(leader :Boid) :Vector3D {
	var tv 		:Vector3D = leader.velocity.clone();
	var force 	:Vector3D = new Vector3D();

	// Вычисление точки behind
	tv.scaleBy(-1);
	tv.normalize();
	tv.scaleBy(LEADER_BEHIND_DIST);
	behind = leader.position.clone().add(tv);

	// Создание силы для прибытия в точку behind
	force = force.add(arrive(behind));

	return force;
}

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

steering = nothing(); // нулевой вектор, обозначающий "нулевую величину силы"
steering = steering + followLeader();

steering = truncate (steering, max_force)
steering = steering / mass

velocity = truncate (velocity + steering, max_speed)
position = position + velocity

Результатом такой реализации станет то, что группа персонажей сможет прибыть в точку behind лидера (интерактивное демо на Flash).

---

Избегание скученности

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

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

private function separation() :Vector3D {
	var force :Vector3D = new Vector3D();
	var neighborCount :int = 0;

	for (var i:int = 0; i < Game.instance.boids.length; i++) {
		var b :Boid = Game.instance.boids[i];

		if (b != this && distance(b, this) <= SEPARATION_RADIUS) {
			force.x += b.position.x - this.position.x;
			force.y += b.position.y - this.position.y;
			neighborCount++;
		}
	}

	if (neighborCount != 0) {
		force.x /= neighborCount;
		force.y /= neighborCount;

		force.scaleBy( -1);
	}

	force.normalize();
	force.scaleBy(MAX_SEPARATION);

	return force;
}

Затем силу разделения можно прибавить к силе followLeader, позволяя ей расталкивать персонажей друг от друга в то же самое время, когда они стремятся к лидеру:

private function followLeader(leader :Boid) :Vector3D {
	var tv 		:Vector3D = leader.velocity.clone();
	var force 	:Vector3D = new Vector3D();

	// Вычисление точки behind
	tv.scaleBy(-1);
	tv.normalize();
	tv.scaleBy(LEADER_BEHIND_DIST);
	behind = leader.position.clone().add(tv);

	// Создание силы для прибытия в точку behind
	force = force.add(arrive(behind));

	// Прибавление силы разделения
	force = force.add(separation());

	return force;
}

В результате мы получаем гораздо естественнее выглядящий паттерн (демо на Flash).

---

Уходим с пути

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

Если какой-то персонаж встаёт на пути лидера, то он немедленно должен отойти, чтобы освободить путь. Этого можно достичь поведением evade:


Избегание пути лидера

Чтобы проверять, находится ли персонаж в области видимости лидера, мы воспользуемся концепцией, схожей с тем, как мы распознавали препятствия в поведении collision avoidance: на основании текущих скорости и направления лидера мы проецируем перед ним точку (называемую ahead); если расстояние между точкой лидера ahead и персонажем меньше, например, 30, то персонаж находится в области видимости лидера и должен сдвинуться.

Точка ahead вычисляется точно так же, как точка behind point; разница в том, что вектор скорости не инвертируется:

tv = leader.velocity;
tv = normalize(tv) * LEADER_BEHIND_DIST;
ahead = leader.position + tv;

Нам нужно изменить метод followLeader(), чтобы проверять, находится ли персонаж в области видимости. Если это происходит, то к переменной force (представляющей силу следования) прибавляется значение, возвращаемое evade(leader) значение, то есть сила избегания местоположения лидера:

private function followLeader(leader :Boid) :Vector3D {
	var tv 		:Vector3D = leader.velocity.clone();
	var force 	:Vector3D = new Vector3D();

	// Вычисление точки ahead
	tv.normalize();
	tv.scaleBy(LEADER_BEHIND_DIST);
	ahead = leader.position.clone().add(tv);

	// Вычисление точки behind
	tv.scaleBy(-1);
	behind = leader.position.clone().add(tv);

	// Если персонаж находится в области видимости лидера, то прибавляем силу
	// для мгновенного избегания его маршрута.
	if (isOnLeaderSight(leader, ahead)) {
		force = force.add(evade(leader));
	}

	// Создание силы прибытия в точку behind
	force = force.add(arrive(behind, 50)); // 50 - радиус прибытия

	// Прибавление силы разделения
	force = force.add(separation());

	return force;
}

private function isOnLeaderSight(leader :Boid, leaderAhead :Vector3D) :Boolean {
	return distance(leaderAhead, this) <= LEADER_SIGHT_RADIUS || distance(leader.position, this) <= LEADER_SIGHT_RADIUS;
}

private function distance(a :Object, b :Object) :Number {
	return Math.sqrt((a.x - b.x) * (a.x - b.x)  + (a.y - b.y) * (a.y - b.y));
}

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

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

---

Демо

Ниже представлено демо, показывающее поведение следования за лидером. Синий солдат (лидер) выполняет поведение arrive относительно курсора мыши, а зелёные солдаты следуют за лидером.

Когда игрок щёлкает мышью на экране, все солдаты поворачиваются в направлении курсора и стреляют. Монстры каждые несколько секунд применяют поведение arrive в случайные точки.


Интерактивное демо на Flash находится здесь.

---

Заключение

Поведение leader following (следование за лидером) позволяет группе персонажей следовать за определённой целью, оставаясь слегка позади неё. Кроме того, персонажи избегают текущего местоположения лидера, если оказываются на его пути.

Важно заметить, что поведение следования за лидером — это сочетание нескольких других поведений, таких как arrive, evade и separation. Оно показывает, что простые поведения можно комбинировать для создания чрезвычайно сложных паттернов движения.

Часть 9. Очередь

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

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

---

Введение

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

Для иллюстрации поведения queue и демонстрации его различных реализаций лучше всего подойдёт демо со «сценой с очередью». Хорошим примером будет комната с управляемыми ИИ сущностями, пытающимися покинуть комнату, выйдя через дверь (демо на Flash).

Эта сцена создана с помощью двух ранее описанных поведений: seek и collision avoidance.

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

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

---

Смотрим вперёд

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

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


Проверка соседей с помощью точки ahead.

Перед персонажем проецируется точка с названием ahead. Если расстояние между этой точкой и соседним персонажем меньше или равно MAX_QUEUE_RADIUS, то это значит, что впереди кто-то есть и персонаж должен остановиться.

Точка ahead вычисляется следующим образом (псевдокод):

// И qa, и ahead являются математическими векторами
qa  = normalize(velocity) * MAX_QUEUE_AHEAD;
ahead = qa + position;

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

Всё это можно обернуть в метод getNeighborAhead():

private function getNeighborAhead() :Boid {
	var i:int;
	var ret :Boid = null;
	var qa :Vector3D = velocity.clone();
	
	qa.normalize();
	qa.scaleBy(MAX_QUEUE_AHEAD);
	
	ahead = position.clone().add(qa);
	
	for (i = 0; i < Game.instance.boids.length; i++) {
		var neighbor :Boid = Game.instance.boids[i];
		var d :Number = distance(ahead, neighbor.position);
		
		if (neighbour != this && d <= MAX_QUEUE_RADIUS) {
			ret = neighbor;
			break;
		}
	}
	
	return ret;
}

Метод проверяет расстояние между точкой ahead и всеми остальными персонажами, возвращая первого персонажа, расстояние до которого меньше или равно MAX_QUEUE_AHEAD. Если персонаж не найден, то метод возвращает null.

---

Создание метода Queuing

Как и во всех остальных поведениях, сила выстраивания в очередь вычисляется в методе под названием queue():

private function queue() :Vector3D {
	var neighbor :Boid = getNeighborAhead();

	if (neighbor != null) {
		// TODO: выполнить действие, потому что впереди находится сосед
	}
	
	return new Vector3D(0, 0);
}

Результат getNeighborAhead() хранится в переменной neighbor. Если neighbor != null, то впереди кто-то есть; в противном случае путь свободен.

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

Метод update() для всех персонажей в сцене с дверью пока выглядит так (псевдокод):

public function update():void {
	var doorway :Vector3D = getDoorwayPosition();
	
	steering = seek(doorway); // seek дверного проёма
	steering = steering + collisionAvoidance(); // избегание препятствий
	steering = steering + queue(); // выстраивание в очередь вдоль пути
	
	steering = truncate (steering, MAX_FORCE);
	steering = steering / mass;
 
	velocity = truncate (velocity + steering , MAX_SPEED);
	position = position + velocity;

Так как queue() возвращает нулевую силу, персонажи будут продолжать двигаться, не создавая рядов. Настало время им предпринимать какие-то действия, когда впереди обнаруживается сосед.

---

Несколько слов об остановке движения

Steering behaviors основаны на постоянно изменяющихся силах, поэтому система в целом становится очень динамичной. Чем больше используется сил, тем сложнее становится выявить и отменить вектор определённой силы.

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

Именно это происходит в поведении Arrival, в котором скорость отменяется, чтобы заставить персонаж остановиться. Но что происходит, когда вместе воздействуют несколько сил, например, в поведениях collision avoidance, flee и других?

В разделах ниже представлены две идеи о том, как заставить персонаж остановиться. В первой используется подход с «жёстким остановом», воздействующий непосредственно на вектор скорости и игнорирующий все другие управляющие силы. Во второй используется вектор силы под названием brake, отменяющий все другие управляющие силы, то есть заставляющий персонажа остановиться.

---

Остановка движения: «жёсткий останов»

На векторе скорости персонажа основано несколько управляющих сил. Если этот вектор изменяется, это воздействует на все другие силы, то есть их нужно вычислять заново. Идея «жёсткого останова» довольно проста: если впереди есть персонаж, то мы «урезаем» вектор скорости:

private function queue() :Vector3D {
	var neighbor :Boid = getNeighborAhead();

	if (neighbor != null) {
		velocity.scaleBy(0.3);
	}
	
	return new Vector3D(0, 0);
}

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

Это проще понять, проанализировав, как вычисляется движение при каждом обновлении:

velocity = truncate (velocity + steering , MAX_SPEED);
position = position + velocity;

Если сила velocity продолжает снижаться, то это происходит и с силой steering, потому что она основана на силе velocity. Это создаёт порочный круг, который в результате приводит к чрезвычайно низкому значениюю velocity. И тогда персонаж перестаёт двигаться.

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

Решение с «жёстким остановом» создаёт следующие результаты (демо на Flash).

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

---

Остановка движения: тормозящая сила

Во втором подходе к остановке движения реализуется менее «механистичный» результат благодаря отмене всех активных управляющих сил с помощью силы brake:

private function queue() :Vector3D {
	var v :Vector3D = velocity.clone();
	var brake :Vector3D = new Vector3D();
	
	var neighbor :Boid = getNeighborAhead();

	if (neighbor != null) {
		brake.x = -steering.x * 0.8;
		brake.y = -steering.y * 0.8;
		
		v.scaleBy( -1);
		brake = brake.add(v);
	}
		
	return brake;
}

Вместо создания силы brake пересчётом и инвертированием каждой из активных управляющих сил, brake вычисляется на основе текущего вектора steering, в котором содержатся все управляющие силы, приложенные в данный момент:


Представление тормозящей силы.

Сила brake получает компоненты x и y от силы steering, но обращает их и изменяет их масштаб на 0.8. Это значит, что brake имеет 80% величины steering и указывает в противоположном направлении.

Подсказка: непосредственное применение силы steering опасно. Если queue() является первым поведением, применяемым к персонажу, то сила steering будет «пустой». Следовательно, queue() необходимо вызывать после всех других методов поведений, чтобы он мог получить к полной и окончательной силе steering.

Сила brake также должна отменять скорость персонажа. Это выполняется прибавлением -velocity к силе brake. После этого метод queue() может вернуть окончательную силу brake.

Результат использования силы торможения выглядит так:


Интерактивное демо на Flash находится здесь.

---

Снижение наложения персонажей

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

Чтобы устранить её, решение с торможением можно улучшить немного изменённой версией подхода с «жёстким остановом»:

private function queue() :Vector3D {
	var v :Vector3D = velocity.clone();
	var brake :Vector3D = new Vector3D();
				
	var neighbor :Boid = getNeighborAhead();

	if (neighbor != null) {
		brake.x = -steering.x * 0.8;
		brake.y = -steering.y * 0.8;
		
		v.scaleBy( -1);
		brake = brake.add(v);
		
		if (distance(position, neighbor.position) <= MAX_QUEUE_RADIUS) {
			velocity.scaleBy(0.3);
		}
	}
	
	return brake;
}

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


Проверка ближайших соседей в пределах радиуса MAX_QUEUE_RADIUS, центрированного в позиции, а не в точке ahead.

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

Наложение можно уменьшить, масштабируя при каждом обновлении вектор velocity до 30% от его текущей величины. Как и в подходе с «жёстким остановом», урезание вектора velocity значительно снижает движение.

Результат кажется менее «механистичным», но всё равно неидеален, потому что персонажи по-прежнему пересекаются в дверном проёме (демо на Flash).

---

Добавление разделения

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

Эту проблему можно решить, добавив силу разделения (separation):

private function queue() :Vector3D {
	var v :Vector3D = velocity.clone();
	var brake :Vector3D = new Vector3D();
	
	var neighbor :Boid = getNeighborAhead();

	if (neighbor != null) {
		brake.x = -steering.x * 0.8;
		brake.y = -steering.y * 0.8;
		
		v.scaleBy( -1);
		brake = brake.add(v);
		brake = brake.add(separation());
		
		if (distance(position, neighbor.position) <= MAX_QUEUE_RADIUS) {
			velocity.scaleBy(0.3);
		}
	}
	return brake;
}

Сила разделения, ранее использованная в поведении leader following, прибавляется к силе brake и заставляет персонажей останавливаться, и при этом они пытаются не касаться друг от друга.

В результате мы получаем правдоподобную толпу, пытающуюся выбраться через дверной проём:


Интерактивное демо на Flash находится здесь.

---

Заключение

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

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

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