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

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

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

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


Шаг 12. Избегание препятствий (object avoidance)

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/04/27/steering_behaviors/AvoidTest .swf, 550, 400[/SWF]

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

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

Конечно, как только столкновение предсказано, мы должны предпринять какие-то меры, чтобы в будущем его не произошло. Самое простое – остановиться и развернуться назад, а если это игра и за вами гонится хищник? Тогда остановка и разворот будет не самым умным решением. В идеале, вы должны каким-либо образом обогнуть препятствие и продолжить убегать от хищника, а он соответственно должен продолжить вас догонять.

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

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

package
{
import flash.display.Sprite;

public class Circle extends Sprite
{
private var _radius:Number;
private var _color:uint;

public function Circle(radius:Number, color:uint = 0x000000)
{
_radius = radius;
_color = color;
graphics.lineStyle(0, _color);
graphics.drawCircle(0, 0, _radius);
}

public function get radius():Number
{
return _radius;
}

public function get position():Vector2D
{
return new Vector2D(x, y);
}
}
}


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

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

Код метода avoid():

public function avoid(circles:Array):void
{
for(var i:int = 0; i < circles.length; i++)
{
var circle:Circle = circles[i] as Circle;
var heading:Vector2D = _velocity.clone().normalize();

// вектор, представляющий разность между вектором позиции окружности
// и вектором позиции персонажа:
var difference:Vector2D = circle.position.subtract(_position);
var dotProd:Number = difference.dotProd(heading);

// если окружность перед персонажем...
if(dotProd > 0)
{
// вектор, представляющий собой датчик
var feeler:Vector2D = heading.multiply(_avoidDistance);
// проекция вектора difference на вектор feeler
var projection:Vector2D = heading.multiply(dotProd);
// расстояние от окружности до датчика
var dist:Number = projection.subtract(difference).length;

// если вектор датчика пересекает окружность радиусом равным
//радиус circle + размер буфера
// и длина вектора projection меньше длины вектора датчика
// мы столкнулись и нам необходимо управляющее воздействие
if(dist < circle.radius + _avoidBuffer &&
projection.length < feeler.length)
{
// разворачиваем нашего персонажа на +/- 90 градусов
var force:Vector2D = heading.multiply(_maxSpeed);
force.angle += difference.sign(_velocity) * Math.PI / 2;

// масштабируем степень воздействия в зависимости от расстояния до препятствия
force = force.multiply(1.0 - projection.length / feeler.length);

// добавляем управляющее воздействие
_steeringForce = _steeringForce.add(force);

// тормозим персонаж
_velocity = _velocity.multiply(projection.length / feeler.length);
}
}
}
}


Заметим, что добавилось еще несколько переменных:

private var _avoidDistance:Number = 300;
private var _avoidBuffer:Number = 20;


Переменная _avoidDistance определяет расстояние, на котором персонаж будет искать препятствия. Переменная _avoidBuffer определяет минимальное расстояние между персонажем и препятствием, которое соблюдает персонаж, когда проходит мимо препятствия.
Этот код не совершенен, но позволяет обходить препятствия и не слишком нагружает процессор. Не стесняйтесь его улучшать. Вот пример использования данного поведения:

package
{

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

public class AvoidTest extends Sprite
{
private var _vehicle:SteeredVehicle;
private var _circles:Array;
private var _numCircles:int = 5;

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

_vehicle = new SteeredVehicle();
_vehicle.edgeBehavior = Vehicle.BOUNCE;
addChild(_vehicle);

_circles = new Array();
for(var i:int = 0; i < _numCircles; i++)
{
var circle:Circle = new Circle(Math.random() * 50 + 50);
circle.x = Math.random() * stage.stageWidth;
circle.y = Math.random() * stage.stageHeight;
addChild(circle);
_circles.push(circle);
}

addEventListener(Event.ENTER_FRAME, onEnterFrame);
}

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


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

Шаг 13. Следование по маршруту (path following)

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/04/27/steering_behaviors/PathTest.swf, 550, 400[/SWF]

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

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


Рисунок 6



Вот новые переменные, которые нужно добавить в класс:

private var _pathIndex:int = 0;
private var _pathThreshold:Number = 20;


И геттеры/сеттеры для них:

public function get pathIndex():int
{
return _pathIndex;
}

public function set pathThreshold(value:Number):void
{
_pathThreshold = value;
}
public function get pathThreshold():Number
{
return _pathThreshold;
}


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

Сама реализация метода:

public function followPath(path:Array, loop:Boolean = false):void
{
var wayPoint:Vector2D = path[_pathIndex];
if(wayPoint == null) return;
if(_position.dist(wayPoint) < _pathThreshold)
{
if(_pathIndex >= path.length - 1)
{
if(loop)
{
_pathIndex = 0;
}
}
else
{
_pathIndex++;
}
}
if(_pathIndex >= path.length - 1 && !loop)
{
arrive(wayPoint);
}
else
{
seek(wayPoint);
}
}


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

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

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

Теперь пример реализации:

package
{

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

public class PathTest extends Sprite
{
private var _vehicle:SteeredVehicle;
private var _path:Array;

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

_vehicle = new SteeredVehicle();
addChild(_vehicle);

_path = new Array();

stage.addEventListener(MouseEvent.CLICK, onClick);
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}

private function onEnterFrame(event:Event):void
{
_vehicle.followPath(_path, true);
_vehicle.update();
}

private function onClick(event:MouseEvent):void
{
graphics.lineStyle(0, 0, .25);
if(_path.length == 0)
{
graphics.moveTo(mouseX, mouseY);
}
graphics.lineTo(mouseX, mouseY);

graphics.drawCircle(mouseX, mouseY, 10);
graphics.moveTo(mouseX, mouseY);
_path.push(new Vector2D(mouseX, mouseY));
}
}
}


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

Как только вы нажмете клавишу мыши, наш персонаж начнет движение в первую, указанную вами, точку. Т.к. параметр loop==true то персонаж будет двигаться по маршруту бесконечно. Чтобы наш персонаж двигался более натурально мы сделали так, чтобы он сглаживал свои повороты и немного пролетал через контрольные точки. Изменяя свойства mass, maxSpeed, maxForce класса SteeredVehicle мы можем существенно изменить характер движения персонажа.

Переходим к последнему поведению – скопление.

Шаг 14. Скопление (flocking)

[SWF]http://coolisee.com/wordpress/wp-content/uploads/2010/04/27/steering_behaviors/FlockTest.swf, 550, 400[/SWF]

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

Когда мы думаем о стае птиц как о скоплении, то на ум приходит три ее поведения:

- во-первых – стая птиц занимает определенную общую площадь, если одна из них отдалиться от стаи, то, скорее всего, она туда снова вернется. Назовем это поведение сцепление. См рис.7.


Рисунок 7



- во-вторых – птицам, не смотря на их сцепление, удается не сталкиваться друг с другом. Они имеют свое место в стае, поэтому не стараются занимать чужое место и не пускают других птиц на свое. Назовем это поведение разделение. См рис. 8.


Рисунок 8



- в-третьих – птицы двигаются в общем направлении. Да, наблюдаются некоторые отклонения отдельных особей, но в целом они придерживаются одного общего направления. Назовем это поведение выравнивание. См рис. 9.


Рисунок 9



Эти три поведения в сумме дают нам поведение скопление.

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

Хотя скапливание технически состоит из трех подповедений, они в нашей реализации практически не разделены, а соединены в один метод. Итак, сам метод:

public function flock(vehicles:Array):void
{
var averageVelocity:Vector2D = _velocity.clone();
var averagePosition:Vector2D = new Vector2D();
var inSightCount:int = 0;
for(var i:int = 0; i < vehicles.length; i++)
{
var vehicle:Vehicle = vehicles[i] as Vehicle;
if(vehicle != this && inSight(vehicle))
{
averageVelocity = averageVelocity.add(vehicle.velocity);
averagePosition = averagePosition.add(vehicle.position);
if(tooClose(vehicle)) flee(vehicle.position);
inSightCount++;
}
}
if(inSightCount > 0)
{
averageVelocity = averageVelocity.divide(inSightCount);
averagePosition = averagePosition.divide(inSightCount);
seek(averagePosition);
_steeringForce.add(averageVelocity.subtract(_velocity));
}
}



Во-первых, мы начинаем обход элементов массива, в котором хранятся наши персонажи. Стратегия обхода этого массива в том, чтобы взаимодействовать только с теми персонажами, которые находятся в поле зрения нашего персонажа. Если другой персонаж находится в пределах видимости, то мы добавляем его скорость и позицию в общую скорость и позицию. Мы также следим за тем, сколько персонажей находится в поле зрения нашего, чтобы определить средние значения общей скорости и позиции. Обратите внимание, что если при переборе мы натыкаемся на наш персонаж, то мы с ним ничего не делаем. Если другой персонаж слишком близко к нашему, то мы применяем к нашему персонажу поведение избегание от той точки, где находится другой персонаж. После того, как мы обошли в цикле всех персонажей в массиве, мы вычисляем среднюю скорость и среднюю позицию. Далее мы применяем к нашему персонажу поведение поиск средней позиции и управляющее воздействие для корректировки скорости.
Как вы заметили, появилось несколько новых методов: insight() и tooClose()

public function inSight(vehicle:Vehicle):Boolean		
{
if(_position.dist(vehicle.position) > _inSightDist) return false;
var heading:Vector2D = _velocity.clone().normalize();
var difference:Vector2D = vehicle.position.subtract(_position);
var dotProd:Number = difference.dotProd(heading);

if(dotProd < 0) return false;
return true;
}

public function tooClose(vehicle:Vehicle):Boolean
{
return _position.dist(vehicle.position) < _tooCloseDist;
}



Метод inSight() определяет, может ли персонаж видеть другого персонажа, для этого сравнивается расстояние между этими двумя персонажами с определенным значением. Если это расстояние меньше, то возвращаем false. Теперь применим математику, чтобы определить находиться ли проверяемый персонаж спереди или сзади от нашего. Если он спереди, то наш персонаж его видит, если сзади, то нет. Метод dotProd() класса Vector2D возвращает положительное значение, если угол между проверяемыми векторами меньше 180 градусов, если больше – значение отрицательное.

Следующий метод tooClose(), который возвращает true, если расстояние между персонажами меньше значения переменной _tooCloseDist, и возвращает false – если нет.
Добавились переменные и геттеры/сеттеры этих переменных:

private var _inSightDist:Number = 200;
private var _tooCloseDist:Number = 60;

public function set inSightDist(value:Number):void
{
_inSightDist = value;
}
public function get inSightDist():Number
{
return _inSightDist;
}

public function set tooCloseDist(value:Number):void
{
_tooCloseDist = value;
}
public function get tooCloseDist():Number
{
return _tooCloseDist;
}



И наконец, сам пример реализации:

package
{

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

public class FlockTest extends Sprite
{
private var _vehicles:Array;
private var _numVehicles:int = 30;

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

_vehicles = new Array();
for(var i:int = 0; i < _numVehicles; i++)
{
var vehicle:SteeredVehicle = new SteeredVehicle();
vehicle.position = new Vector2D(Math.random() * stage.stageWidth, Math.random() * stage.stageHeight);
vehicle.velocity = new Vector2D(Math.random() * 20 - 10, Math.random() * 20 - 10);
vehicle.edgeBehavior = Vehicle.BOUNCE;
_vehicles.push(vehicle);
addChild(vehicle);
}
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}

private function onEnterFrame(event:Event):void
{
for(var i:int = 0; i < _numVehicles; i++)
{
_vehicles[i].flock(_vehicles);
_vehicles[i].update();
}
}
}
}


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

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

  1. ух... вроде затолкал 8( )
    осталось разжевать и проглотить %[

    ОтветитьУдалить
  2. хорошо, это полезная штука, пригодится в хозяйстве :)

    ОтветитьУдалить
  3. Благодарю за твои старания! Низкий поклон!

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