() translation by (you can also view the original English article)
В живой природе организмы подчиняются определенному поведению, когда перемещаются группами. Это явление, которое также называется флокированием, встречается как на микроскопическом уровне (бактерии), так и на макроскопическом (рыбы). Такие паттерны поведения могут быть симулированы на компьютере через создание и комбинирование простых правил. Так называемое эмерджентное поведение может быть использовано в играх для симуляции хаотичного и близкого к реальному группового движения.
Важно: Хотя это руководство было написано на Flash и AS3, вы можете использовать приведенные техники и концепции практически в любой среде разработки.
Введение
В этом руководстве я затрону три главных правила, которые используются для симуляции флокирования, и объясню, как использовать каждое из них. Прежде, чем мы начнем, приведу используемые термины:
Агент: отдельный персонаж.
Вектор скорости: Текущая скорость агента.
Соседство: определенная область вокруг агента, используемая для поиска других агентов.
Результирующий вектор: вектор, полученный в результате обсчета правил поведения.
Это демо показывает эффект наложения трех правил флокирования, о которых я расскажу в руководстве: упорядочение, сцепление и разделение.
Полный исходный код может быть скачан здесь, а в статье только подчеркиваются отдельные важные аспекты реализации. Вы можете свободно скачивать исходники, если у вас есть желание поглубже разобраться в проблеме.
Упорядочение
Упорядочение – это тип поведения, который позволяет отдельному агенту двугаться в одну сторону с другими агентами.
Для начала определим функцию, которая берет агента и возвращает вектор скорости.
1 |
|
2 |
public function computeAlignment(myAgent:Agent):Point |
3 |
{
|
4 |
}
|
Нам нужны две переменные: одна для хранения вычисляемого вектора, а вторая для хранения количества соседей агента.
1 |
|
2 |
var v:Point = new Point(); |
3 |
var neighborCount = 0; |
После инициализации переменных мы итерируем всех агентов и находим тех, что входят в радиус соседства (расстояния, внутри которого двух агентов можно считать соседями). Если внутри радиуса обнаружен агент, его скорость добавляется к вычисляемому вектору, а число соседей инкрементируется.
1 |
|
2 |
|
3 |
for each (var agent:Agent in agentArray) |
4 |
{
|
5 |
if (agent != myAgent) |
6 |
{
|
7 |
if (myAgent.distanceFrom(agent) < 300) |
8 |
{
|
9 |
v.x += agent.velocity.x; |
10 |
v.y += agent.velocity.y; |
11 |
neighborCount++; |
12 |
}
|
13 |
}
|
14 |
}
|
Если соседей не обнаружено, мы просто возвращаемся к нулевому вектору (значение по умолчанию для вычисляемого вектора).
1 |
|
2 |
|
3 |
if (neighborCount == 0) |
4 |
return v; |
5 |
}
|
Наконец, мы делим вычисляемый вектор на число соседей и нормализуем его (делим на его длину, чтобы получить вектор длиной 1), получая результирующий вектор:
1 |
|
2 |
|
3 |
v.x /= neighborCount; |
4 |
v.y /= neighborCount; |
5 |
v.normalize(1); |
6 |
return v; |
Сцепление
Сцепление – это тип поведения, которое позволяет агентам поворачивать в сторону центра масс (среднюю позицию агентов внутри определенного радиуса), и двигаться вместе.
Реализация этого типа поведения практически идентична реализации упорядочения, но есть и ключевые различия. Во-первых, вместо добавления скорости к вычисляемому вектору, добавляется положение:
1 |
|
2 |
v.x += agent.x; |
3 |
v.y += agent.y; |
Как и прежде, вычисляемый вектор делится на количество соседей, что приводит к вычислению центра масс. Однако, нам не нужен центр масс сам по себе, мы хотим знать направление на него, поэтому мы пересчитываем вектор как расстояние от агента до центра масс. Наконец, это значение нормализуется и возвращается.
1 |
|
2 |
v.x /= neighborCount; |
3 |
v.y /= neighborCount; |
4 |
v = new Point(v.x - myAgent.x, v.y - myAgent.y); |
5 |
v.normalize(1); |
6 |
return v; |
Разделение
Разделение – это тип поведения, который позволяет агенту поворачивать в сторону от своих соседей во избежание столкновений. Реализация разделения очень похожа на реализацию упорядочения и сцепления, поэтому я просто приведу различия. Когда найден сосед, расстояние от агента до соседа добавляется к вычисляемому вектору:
1 |
|
2 |
v.x += agent.x - myAgent.x; |
3 |
v.y += agent.y - myAgent.y; |
Вычисляемый вектор делится на соответствующее количество соседей, но до нормализации включается еще один важный шаг. Вычисляемый вектор должен быть вычтен для того, чтобы агент правильно поворачивал в сторону от соседей.
1 |
|
2 |
|
3 |
v.x *= -1; |
4 |
v.y *= -1; |
Соединяем все вместе
После того, как все три правила были реализованы, их нужно совместить. Простейший способ сделать это:
1 |
|
2 |
var alignment = computeAlignment(agent); |
3 |
var cohesion = computeCohesion(agent); |
4 |
var separation = computeSeparation(agent); |
5 |
|
6 |
agent.velocity.x += alignment.x + cohesion.x + separation.x; |
7 |
agent.velocity.y += alignment.y + cohesion.y + separation.y; |
8 |
|
9 |
agent.velocity.normalize(AGENT_SPEED); |
Здесь я просто вычисляю три правила для каждого агента и добавляю их к скорости. Затем я нормализую скорость и умножаю ее на некоторую константу, определяющую скорость агента по умолчанию. Можно развить этот подход, добавив разным типам поведения свои веса.
1 |
|
2 |
agent.velocity.x += alignment.x * alignmentWeight + cohesion.x * cohesionWeight + separatio |
3 |
separationWeight; |
4 |
agent.velocity.y += alignment.y * alignmentWeight + cohesion.y * cohesionWeight + separatio |
5 |
separationWeight; |
Меняя веса, можно управлять характером флокирования агентов. Экспериментируйте, пока получите то, что вам нравится. Вот снова демо, чтобы вы попробовали
Выводы
Флокирование легко реализовать, при этом результаты получаются довольно впечатляющими. Если вы разрабатываете игру с ИИ, особенно с большими группами, которые взаимодействуют друг с другом, флокирование может быть полезным. Используйте на здоровье.
