вторник, 27 апреля 2010 г.

Управление поведениями (Steering behaviors). Часть 1.

Представляю вашему вниманию очередной вольный перевод одной из глав книги AdvancED ActionScript 3.0 Animation, автор Keith Peters.

Речь пойдет об управлении поведениями объектов (steering behaviors).

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

поведение поиск (seek) - перемещайте указатель мыши над роликом, чтобы объект начал его поиск
[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/04/27/steering_behaviors/SeekTest.swf, 550, 400[/SWF]

поведение следование по маршруту (path following) - щелкайте по ролику, чтобы задать точки маршрута
[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/04/27/steering_behaviors/PathTest.swf, 550, 400[/SWF]

поведение скапливание (flocking)
[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/04/27/steering_behaviors/FlockTest.swf, 550, 400[/SWF]




Шаг 1. Предисловие

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

Термин управление поведениями был предложен Крейгом Рейнольдсом в докладе «Управление поведениями отдельных персонажей», сделанном для конференции разработчиков игр (Craig Reynolds, “Steering Behaviors For Autonomous Characters” 1999 HTML, PDF). В этом докладе описывается ряд алгоритмов, которые создают систему воздействий, прикладывающихся к персонажам, которые используются в играх и симуляциях. Эти воздействия используются, чтобы привести персонажи в движение или изменить направление движения персонажа по мере его перемещения. Они также могут использоваться для симуляции различных поведений групп объектов, например, таких как скапливание (flockling).

Шаг 2. Типы поведений

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

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

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

- прибытие (arrive): почти тоже, что и поиск, но персонаж по мере приближения к цели замедляет свое движение и полностью останавливается в точке назначения.

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

- уклонение (evade): полная противоположность преследования. Персонаж определяет точку, где будет находиться его преследователь, и будет стараться покинуть эту точку или отдалиться от нее.

- блуждание (wander): случайное, но гладкое и реалистичное движение персонажа.

- избегание препятствий (object avoidance): персонаж видит препятствия на своем пути и огибает их.

- следование по маршруту (path following): персонаж прилагает все усилия, чтобы остаться на данном пути, но делает это реалистично (в соответствии с законами физики).

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

- разделение (separation): каждый символ в скоплении пытается поддержать приемлемое расстояние от соседей (т.е. следит за тем, чтобы расстояние между ним и соседом не было меньше, чем минимально установленное).

- сцепление (cohesion): каждый символ в скоплении предпринимает действия, чтобы не отдалиться от скопления слишком далеко.

- выравнивание (alignment): каждый персонаж пытается держаться в том же самом направлении, что и его соседи.

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

Шаг 3. Класс Vector2D

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

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

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

Все эти векторные свойства очень полезны для управления поведениями, т.к. поведения активно используют такие понятия как скорость, направление силы, приложенной к персонажу, расстояние между объектами и направление движения объекта. Класс вектора был бы для нас очень полезен для создания управления поведениями. И, будучи хорошим парнем, я создал такой класс для вас. Конечно, позже я узнал, что в Flash CS4 появился внутренний класс Vector3D, и возможно вы будете использовать его. Но я думаю, что дополнительно измерение принесет дополнительные сложности, и поэтому в этой главе мы будем придерживаться собственного класса Vector2D. Я не буду объяснять его здесь очень подробно, но по мере использования методов этого класса при создании поведений мы остановимся на них более подробно. Итак:

package
{
import flash.display.Graphics;

public class Vector2D
{
private var _x:Number;
private var _y:Number;

public function Vector2D(x:Number = 0, y:Number = 0)
{
_x = x;
_y = y;
}

/**
* Метод может быть использован для визуализации вектора. Используется в основном при
* отладке.
* @param graphics экземпляр класса Graphics для рисования вектора.
* @param color цвет вектора.
*/
public function draw(graphics:Graphics, color:uint = 0):void
{
graphics.lineStyle(0, color);
graphics.moveTo(0, 0);
graphics.lineTo(_x, _y);
}

/**
* Создает копию данного вектора.
* @return Vector2D копия данного вектора.
*/
public function clone():Vector2D
{
return new Vector2D(x, y);
}

/**
* Устанавливает значения х и у, а следовательно и длину
* вектора равным нулю и возвращает этот вектор.
* @return Vector2D .
*/
public function zero():Vector2D
{
_x = 0;
_y = 0;
return this;
}

/**
* Проверяет является ли данный вектор нулевым, т.е. равны ли его х, у и длина нулю
* @return Boolean True если вектор нулевой, false иначе.
*/
public function isZero():Boolean
{
return _x == 0 && _y == 0;
}

/**
* Сеттер/геттер для записи/чтения длины вектора. Изменение длины изменит x и y, но не угол этого вектора.
*/
public function set length(value:Number):void
{
var a:Number = angle;
_x = Math.cos(a) * value;
_y = Math.sin(a) * value;
}
public function get length():Number
{
return Math.sqrt(lengthSQ);
}

/**
* Возвращает квадрат длины вектора
*/
public function get lengthSQ():Number
{
return _x * _x + _y * _y;
}

/**
* Геттер/сеттер угла этого вектора. Изменение угла изменяет x и y, но сохраняет ту же самую длину.
*/
public function set angle(value:Number):void
{
var len:Number = length;
_x = Math.cos(value) * len;
_y = Math.sin(value) * len;
}
public function get angle():Number
{
return Math.atan2(_y, _x);
}

/**
* Нормализует вектор (делает его длину равной единице) и возвращает его.
* @return Vector2D.
*/
public function normalize():Vector2D
{
if(length == 0)
{
_x = 1;
return this;
}
var len:Number = length;
_x /= len;
_y /= len;
return this;
}

/**
* Ограничивает длину вектора, значением которое задается параметром max
* @param max.
* @return Vector2D.
*/
public function truncate(max:Number):Vector2D
{
length = Math.min(max, length);
return this;
}

/**
* Изменяет направление вектора на противоположное.
* @return Vector2D.
*/
public function reverse():Vector2D
{
_x = -_x;
_y = -_y;
return this;
}

/**
* Проверяет, является ли вектора нормализованным
* @return Boolean True - вектор нормализован, false - нет.
*/
public function isNormalized():Boolean
{
return length == 1.0;
}

/**
* Если угол между векторами меньше 180 градусов, метод возвращает положительное число,
* если нет - отрицательное.
* @param v2.
* @return Number.
*/
public function dotProd(v2:Vector2D):Number
{
return _x * v2.x + _y * v2.y;
}

/**
* Calculates the cross product of this vector and another given vector.
* @param v2 Another Vector2D instance.
* @return Number The cross product of this vector and the one passed in as a parameter.
*/
public function crossProd(v2:Vector2D):Number
{
return _x * v2.y - _y * v2.x;
}

/**
* Определяет угол между двумя векторами.
* @param v1 первый вектор.
* @param v2 второй вектор.
* @return Number угол между двумя векторами.
*/
public static function angleBetween(v1:Vector2D, v2:Vector2D):Number
{
if(!v1.isNormalized()) v1 = v1.clone().normalize();
if(!v2.isNormalized()) v2 = v2.clone().normalize();
return Math.acos(v1.dotProd(v2));
}

/**
* Определяет направление вектора перпендикулярного данному.
* @return int
*/
public function sign(v2:Vector2D):int
{
return perp.dotProd(v2) < 0 ? -1 : 1;
}

/**
* Возвращает вектор, перпендикулярный данному
* @return Vector2D.
*/
public function get perp():Vector2D
{
return new Vector2D(-y, x);
}

/**
* Определяет расстояние между данным вектором и любым другим.
* @param v2.
* @return Number.
*/
public function dist(v2:Vector2D):Number
{
return Math.sqrt(distSQ(v2));
}

/**
* Определяет квадрат расстояния между данным вектором и любым другим.
* @param v2.
* @return Number.
*/
public function distSQ(v2:Vector2D):Number
{
var dx:Number = v2.x - x;
var dy:Number = v2.y - y;
return dx * dx + dy * dy;
}

/**
* Складывает вектор v2 с заданным вектором, возвращает результирующий вектор.
* @param v2 A Vector2D.
* @return Vector2D новый вектор - результат сложения двух векторов.
*/
public function add(v2:Vector2D):Vector2D
{
return new Vector2D(_x + v2.x, _y + v2.y);
}

/**
* Вычитает вектор v2 из заданного вектора, возвращает результирующий вектор.
* @param v2 Vector2D.
* @return Vector2D новый вектор - результат вычитания двух векторов.
*/
public function subtract(v2:Vector2D):Vector2D
{
return new Vector2D(_x - v2.x, _y - v2.y);
}

/**
* Умножает заданный вектор на число, возвращает результирующий вектор.
* @param v2 Vector2D.
* @return Vector2D вектор, полученный умножением заданного вектора на число.
*/
public function multiply(value:Number):Vector2D
{
return new Vector2D(_x * value, _y * value);
}

/**
* Делит заданный вектор на число, возвращает результирующий вектор.
* @param v2 Vector2D.
* @return Vector2D вектор, полученный делением заданного вектора на число.
*/
public function divide(value:Number):Vector2D
{
return new Vector2D(_x / value, _y / value);
}

/**
* Проверяет равенство двух векторов.
* @param v2 Vector2D.
* @return Boolean True - если векторы равны, false - если не равны.
*/
public function equals(v2:Vector2D):Boolean
{
return _x == v2.x && _y == v2.y;
}

/**
* Сеттер/геттер свойства х вектора.
*/
public function set x(value:Number):void
{
_x = value;
}
public function get x():Number
{
return _x;
}

/**
* Сеттер/геттер свойства у вектора.
*/
public function set y(value:Number):void
{
_y = value;
}
public function get y():Number
{
return _y;
}

/**
* Генерирует строковое представление вектора.
* @return String строковое представление вектора.
*/
public function toString():String
{
return "[Vector2D (x:" + _x + ", y:" + _y + ")]";
}
}
}


Шаг 4. Класс Vehicle

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

До сих пор, мы именовали персонажами все, что может передвигаться и имеет поведение. Теперь мы будем использовать термины персонаж (character) и носитель (vehicle) как взаимозаменяемые. Если это поможет, то думайте о персонаже, как о вещи, которая перемещается в носителе, а носитель это «тело» персонажа.

Итак, класс Vehicle:

package
{
import flash.display.Sprite;

/**
* Базовый класс для перемещаемого носителя.
*/
public class Vehicle extends Sprite
{
protected var _edgeBehavior:String = BOUNCE;
protected var _mass:Number = 1.0;
protected var _maxSpeed:Number = 10;
protected var _position:Vector2D;
protected var _velocity:Vector2D;

// Константы, определяющие возможные поведения носителя
// при столкновении с краями сцены
public static const WRAP:String = "wrap";
public static const BOUNCE:String = "bounce";

public function Vehicle()
{
_position = new Vector2D();
_velocity = new Vector2D();
draw();
}

/**
* Изображение нашего носителя, может быть переопределено в подклассе
*/
protected function draw():void
{
graphics.clear();
graphics.lineStyle(0);
graphics.moveTo(10, 0);
graphics.lineTo(-10, 5);
graphics.lineTo(-10, -5);
graphics.lineTo(10, 0);
}

/**
* Метод, который перемещает носитель. Может вызываться в каждом кадре или временном интервале.
*/
public function update():void
{
// убеждаемся, что скорость не больше максимально допустимой величины.
_velocity.truncate(_maxSpeed);

// добавляем скорость в позицию
_position = _position.add(_velocity);

// в зависимости от выбранного варианта поведения при столкновенни с краем
// сцены, вызываем соответствующий метод
if(_edgeBehavior == WRAP)
{
wrap();
}
else if(_edgeBehavior == BOUNCE)
{
bounce();
}

// обновляем позицию
x = position.x;
y = position.y;

// поворачиваем носитель, чтобы он был ориентирован также, как и вектор скорости
rotation = _velocity.angle * 180 / Math.PI;
}

/**
* Если носитель достигает края сцены,
* то отталкивается от него и возвращается на сцену
*/
private function bounce():void
{
if(stage != null)
{
if(position.x > stage.stageWidth)
{
position.x = stage.stageWidth;
velocity.x *= -1;
}
else if(position.x < 0)
{
position.x = 0;
velocity.x *= -1;
}

if(position.y > stage.stageHeight)
{
position.y = stage.stageHeight;
velocity.y *= -1;
}
else if(position.y < 0)
{
position.y = 0;
velocity.y *= -1;
}
}
}

/**
* Если носитель сталкивается с краем сцены, то появляется с противоположного края сцены.
*/
private function wrap():void
{
if(stage != null)
{
if(position.x > stage.stageWidth) position.x = 0;
if(position.x < 0) position.x = stage.stageWidth;
if(position.y > stage.stageHeight) position.y = 0;
if(position.y < 0) position.y = stage.stageHeight;
}
}

/**
* Сеттер/геттер для определения поведения носителя при столкновении с краем сцены.
*/
public function set edgeBehavior(value:String):void
{
_edgeBehavior = value;
}
public function get edgeBehavior():String
{
return _edgeBehavior;
}

/**
* Сеттер/геттер массы носителя.
*/
public function set mass(value:Number):void
{
_mass = value;
}
public function get mass():Number
{
return _mass;
}

/**
* Сеттер/геттер максимальной скорости носителя.
*/
public function set maxSpeed(value:Number):void
{
_maxSpeed = value;
}
public function get maxSpeed():Number
{
return _maxSpeed;
}

/**
* Сеттер/геттер позиции носителя (определяется как вектор Vector2D).
*/
public function set position(value:Vector2D):void
{
_position = value;
x = _position.x;
y = _position.y;
}
public function get position():Vector2D
{
return _position;
}

/**
* Сеттер/геттер скорости носителя (определяется как вектор Vector2D).
*/
public function set velocity(value:Vector2D):void
{
_velocity = value;
}
public function get velocity():Vector2D
{
return _velocity;
}

/**
* Сеттер координаты х носителя. Overrides Sprite.x to set internal Vector2D position as well.
*/
override public function set x(value:Number):void
{
super.x = value;
_position.x = x;
}

/**
* Сеттер координаты у носителя. Overrides Sprite.y to set internal Vector2D position as well.
*/
override public function set y(value:Number):void
{
super.y = value;
_position.y = y;
}

}
}


Здесь позиция и скорость задаются не значениями x, y, vx, vy, а простыми векторами Vector2D: _position и _velocity.

Основная часть работы в этом классе происходит в методе update(). Во-первых, мы ограничиваем значение скорости максимально допустимым значением, которое мы определили в свойстве _maxSpeed, затем складываем векторы скорости и позиции. Раньше мы бы это сделали так:

x += _vx;
y +=_vy;


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

_position = _position.add(_velocity);


Также этот метод проверяет края сцены и носитель на столкновения и вызывает метод wrap() или bounce() . Наконец, обновляется позиция носителя, т.е. значения свойств x и y вектора позиции _position присваиваются свойствам x и y спрайта, и носитель поворачивается в направлении вектора скорости.

// обновляем позицию
x = position.x;
y = position.y;

// поворачиваем носитель, чтобы он был ориентирован так же, как и вектор скорости
rotation = _velocity.angle * 180 / Math.PI;


Большая часть остального кода содержит сеттеры и геттеры для записи/чтения закрытых свойств класса. Я также включил метод draw(), который вызывается когда создается экземпляр класса. Этот метод может быть переопределен в подклассе для создания надлежащей графики для вашего персонажа, а пока этой графики нет, мы будем довольствоваться этим методом.
Для того чтобы быстро протестировать класс Vehicle, создадим новый документ, зададим следующий класс, в качестве класса документа:

package
{
import Vector2D;
import Vehicle;

import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;

public class VehicleTest extends Sprite
{
private var _vehicle:Vehicle;

public function VehicleTest()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;

_vehicle = new Vehicle();
addChild(_vehicle);

_vehicle.position = new Vector2D(100, 100);

_vehicle.velocity.length = 5;
_vehicle.velocity.angle = Math.PI / 4;

addEventListener(Event.ENTER_FRAME, onEnterFrame);
}

private function onEnterFrame(event:Event):void
{
_vehicle.update();
}
}
}


Здесь мы создаем новый экземпляр класса Vehicle и добавляем его в список отображения. Устанавливаем его позицию с помощью экземпляра класса Vector2D:

_vehicle.position = new Vector2D(100, 100);


Другими словами мы сделали то же самое:

_vehicle.position.x = 100;
_vehicle.position.y = 100;


Или с переопределенными сеттерами x и y вы могли бы даже установить свойства x и y непосредственно, а вектор position все равно получит значения:

_vehicle.x = 100;
_vehicle.y = 100;


Класс использует другой способ для записи значения скорости: задаем значение длины и угла в свойства вектора скорости:

_vehicle.velocity.length = 5;
_vehicle.velocity.angle = Math.PI / 4;


Здесь длина будет величиной вектора скорости, а угол – его направлением. Не забывайте, что угол необходимо брать в радианах, таким образом, наш угол равен Math.PI / 4 или 45 градусам.

Наконец, устанавливаем слушатель onEnterFrame для события ENTER_FRAME и вызываем метод _vehicle.update() в каждом кадре. Этот метод заставляет двигаться носитель в заданном направлении. Когда он достигает края сцены, то отталкивается от него и движется в другом направлении.

Теперь мы можем протестировать класс Vehicle и перейти непосредственно к управлению поведениями.

Шаг 5. Класс SteeredVehicle

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

Например, если мы хотим создать носитель с поведением блуждания, то мы сначала вызываем метод wander() и только потом метод update():

public function onEnterFrame(e:Event):void 
{
_vehicli.wander();
_vehicle.update();
}


Как работают управляющие методы: когда управляющий метод вызывают, он рассчитывает управляющее воздействие, которое заставит поворачиваться носитель по часовой или против часовой стрелки. Например, метод seek() рассчитывает воздействие, поворачивающее носитель в сторону объекта, который этот носитель ищет. К носителю может быть применено более одного управляющего воздействия – он может одновременно искать один объект и убегать от другого объекта. Для этого необходимо сложить управляющие воздействия. Когда вызывается метод update(), к носителю применяется суммарное воздействие для изменения его вектора скорости (а это изменит направление и значение скорости).

Итак, класс SteeredVehicle:

package
{
import flash.display.Sprite;

public class SteeredVehicle extends Vehicle
{
private var _maxForce:Number = 1;
private var _steeringForce:Vector2D;

public function SteeredVehicle()
{
_steeringForce = new Vector2D();
super();
}

public function set maxForce(value:Number):void
{
_maxForce = value;
}
public function get maxForce():Number
{
return _maxForce;
}

override public function update():void
{
_steeringForce.truncate(_maxForce);
_steeringForce = _steeringForce.divide(_mass);
_velocity = _velocity.add(_steeringForce);
_steeringForce = new Vector2D();
super.update();
}
}
}


Как вы видите здесь есть свойство _steeringForce тип которого Vector2D. Это свойство хранит в себе полное управляющее воздействие, которое представляет собой сумму простых управляющих воздействий (заметим, что есть переменная _maxForce, которая ограничивает максимальное значение этого суммарного воздействия). В реальной жизни мы не можем повернуть персонаж в требуемую точку мгновенно, и здесь мы ограничиваем величину управляющего воздействия, которое может быть применено в одном кадре. Делаем мы это с помощью сеттера свойства _maxForce. Изменяя его, мы можем поворачивать носитель быстро или медленно.

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

Продолжение следует

Исходники

4 комментария:

  1. Хорошо переведено, т.е. легко читается, спасибо. Кажется, в предпоследнем предложении опечатка - " тяжелый носитель будет поворачиваться медленно, а легкий повернется Медленно"

    ОтветитьУдалить
  2. Спасибо за отзыв, исправил

    ОтветитьУдалить
  3. Очень интересный и нужный материал, спасибо за перевод. В универе на кафедре очень много людей занимаются искусственным интеллектом, но было так не интересно, сейчас про поведение прочитал и понимаю что тема очень интересная

    ОтветитьУдалить