простейший алгоритм нахождения пути

бакуард · 07.05.2015, 19:42

Всем доброго времени суток.

Создаю упрощенную версию алгоритма нахождения пути по аналогии того, что описан в http://xitri.com с применением метода hitTest (в моем случае - hitTestPoint).
Возникают проблемы: при столкновении объекта с препятствием он начинает двигаться очень медленно с постоянным подёргиванием. Иногда просто берет и "обрезает" препятствие.

Вот код:

Код AS3:

var speedX:Number;//скорость перемещения объекта по оси X
var speedY:Number;//скорость перемещения объекта по оси Y
var objX:Number;//координата точки на оси X находящейся впереди объекта на расстоянии равного значению скорости
var objY:Number;//координата точки на оси Y находящейся впереди объекта на расстоянии равного значению скорости
var exitX:Number;//координата точки по оси X коректирующей движение объекта в случае столкновения с препятствиями
var exitY:Number;//координата точки по оси Y коректирующей движение объекта в случае столкновения с препятствиями
var angle:Number
var speedObj:Number = 1;
objGo.addEventListener(Event.ENTER_FRAME, fGo);
function fGo (e:Event) {
	var distanceX:Number = point.x - objGo.x;
	var distanceY:Number = point.y - objGo.y;
	angle = Math.atan2(distanceY, distanceX);
	var distanceXY:Number = Math.sqrt(distanceX * distanceX + distanceY * distanceY);
	    if(distanceXY >= 15){
		   objX = objGo.x + speedObj * Math.cos(angle);
		   objY = objGo.y + speedObj * Math.sin(angle);
		   objGo.rotation = Math.atan2(distanceY, distanceX) * 180/Math.PI;
		}
	    if(block.hitTestPoint(objX, objY, true)){
 
		    speedX = objX;
		    speedY = objY;
	    }else{
			fRotation();
		}
	objGo.x = speedX;
	objGo.y = speedY;
}
 
function fRotation(){
	    for(var i:Number = 0; i < 360; i += 10){
			exitX = objGo.x + speedObj * Math.cos(angle + i);
			exitY = objGo.y + speedObj * Math.sin(angle + i);
			if(!block.hitTestPoint(exitX, exitY, true)){
				speedX = exitX;
			    speedY = exitY; 
			}
		}
}

GBee · 07.05.2015, 20:45

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

бакуард · 08.05.2015, 07:49

Шаг - меньше размеров препятствий. При столкновении объект стоит не в притык к препятствию.

GBee · 08.05.2015, 13:56

Цитата:

При столкновении объект стоит не в притык к препятствию.

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

Код AS3:

speedX = objX;
speedY = objY;

caseyryan · 08.05.2015, 21:09

Это не алгоритм нахождения пути, это скорее алгоритм обхода препятствия. Ведь путь в целом этот алгоритм не находит, и не должен находить. Да и еще постоянные расчеты косинуса и синуса не есть гуд. Их надо рассчитывать только при изменении угла и хранить в переменных. Но, не суть. Как уже выше заметили, погрешности здесь адские. Лучше подобные вещи делать на векторах.
У Кита Питерса

Код AS3:

package
{
	import com.foed.Circle;
	import com.foed.SteeredVehicle;
	import com.foed.Vector2D;
	import com.foed.Vehicle;
 
	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 = 10;
 
		public function AvoidTest()
		{
			stage.align = StageAlign.TOP_LEFT;
			stage.scaleMode = StageScaleMode.NO_SCALE;
 
			_vehicle = new SteeredVehicle();
			_vehicle.edgeBehavior = Vehicle.WRAP;
			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();
		}
	}
}

Код AS3:

package com.foed
{
	import flash.display.Sprite;
 
	public class SteeredVehicle extends Vehicle
	{
		private var _maxForce:Number = 1;
		private var _steeringForce:Vector2D;
		private var _arrivalThreshold:Number = 100;
		private var _wanderAngle:Number = 0;
		private var _wanderDistance:Number = 10;
		private var _wanderRadius:Number = 5;
		private var _wanderRange:Number = 1;
		private var _pathIndex:int = 0;
		private var _pathThreshold:Number = 20;
		private var _avoidDistance:Number = 300;
		private var _avoidBuffer:Number = 20;
		private var _inSightDist:Number = 200;
		private var _tooCloseDist:Number = 60;
 
		public function SteeredVehicle()
		{
			_steeringForce = new Vector2D();
			super();
		}
 
		public function set maxForce(value:Number):void
		{
			_maxForce = value;
		}
		public function get maxForce():Number
		{
			return _maxForce;
		}
 
		public function set arriveThreshold(value:Number):void
		{
			_arrivalThreshold = value;
		}
		public function get arriveThreshold():Number
		{
			return _arrivalThreshold;
		}
 
		public function set wanderDistance(value:Number):void
		{
			_wanderDistance = value;
		}
		public function get wanderDistance():Number
		{
			return _wanderDistance;
		}
 
		public function set wanderRadius(value:Number):void
		{
			_wanderRadius = value;
		}
		public function get wanderRadius():Number
		{
			return _wanderRadius;
		}
 
		public function set wanderRange(value:Number):void
		{
			_wanderRange = value;
		}
		public function get wanderRange():Number
		{
			return _wanderRange;
		}
 
		public function set pathIndex(value:int):void
		{
			_pathIndex = value;
		}
		public function get pathIndex():int
		{
			return _pathIndex;
		}
 
		public function set pathThreshold(value:Number):void
		{
			_pathThreshold = value;
		}
		public function get pathThreshold():Number
		{
			return _pathThreshold;
		}
 
		public function set avoidDistance(value:Number):void
		{
			_avoidDistance = value;
		}
		public function get avoidDistance():Number
		{
			return _avoidDistance;
		}
 
		public function set avoidBuffer(value:Number):void
		{
			_avoidBuffer = value;
		}
		public function get avoidBuffer():Number
		{
			return _avoidBuffer;
		}
 
		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;
		}
 
		override public function update():void
		{
			_steeringForce.truncate(_maxForce);
			_steeringForce = _steeringForce.divide(_mass);
			_velocity = _velocity.add(_steeringForce);
			_steeringForce = new Vector2D();
			super.update();
		}
 
		public function seek(target:Vector2D):void
		{
			var desiredVelocity:Vector2D = target.subtract(_position);
			desiredVelocity.normalize();
			desiredVelocity = desiredVelocity.multiply(_maxSpeed);
			var force:Vector2D = desiredVelocity.subtract(_velocity);
			_steeringForce = _steeringForce.add(force);
		}
 
		public function flee(target:Vector2D):void
		{
			var desiredVelocity:Vector2D = target.subtract(_position);
			desiredVelocity.normalize();
			desiredVelocity = desiredVelocity.multiply(_maxSpeed);
			var force:Vector2D = desiredVelocity.subtract(_velocity);
			_steeringForce = _steeringForce.subtract(force);
		}
 
		public function arrive(target:Vector2D):void
		{
			var desiredVelocity:Vector2D = target.subtract(_position);
			desiredVelocity.normalize();
 
			var dist:Number = _position.dist(target);
			if(dist > _arrivalThreshold)
			{
				desiredVelocity = desiredVelocity.multiply(_maxSpeed);
			}
			else
			{
				desiredVelocity = desiredVelocity.multiply(_maxSpeed * dist / _arrivalThreshold);
			}
 
			var force:Vector2D = desiredVelocity.subtract(_velocity);
			_steeringForce = _steeringForce.add(force);
		}
 
		public function pursue(target:Vehicle):void
		{
			var lookAheadTime:Number = position.dist(target.position) / _maxSpeed;
			var predictedTarget:Vector2D = target.position.add(target.velocity.multiply(lookAheadTime));
			seek(predictedTarget);
		}
 
		public function evade(target:Vehicle):void
		{
			var lookAheadTime:Number = position.dist(target.position) / _maxSpeed;
			var predictedTarget:Vector2D = target.position.subtract(target.velocity.multiply(lookAheadTime));
			flee(predictedTarget);
		}
 
		public function wander():void
		{
			var center:Vector2D = velocity.clone().normalize().multiply(_wanderDistance);
			var offset:Vector2D = new Vector2D(0);
			offset.length = _wanderRadius;
			offset.angle = _wanderAngle;
			_wanderAngle += Math.random() * _wanderRange - _wanderRange * .5;
			var force:Vector2D = center.add(offset);
			_steeringForce = _steeringForce.add(force);
		}
 
		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();
 
		        // vector between circle and vehicle:
		        var difference:Vector2D = circle.position.subtract(_position);
		        var dotProd:Number = difference.dotProd(heading);
 
		        // if circle is in front of vehicle...
		        if(dotProd > 0)
		        {
		            // vector to represent "feeler" arm
		            var feeler:Vector2D = heading.multiply(_avoidDistance);
		            // project difference vector onto feeler
		            var projection:Vector2D = heading.multiply(dotProd);
		            // distance from circle to feeler
		            var dist:Number = projection.subtract(difference).length;
 
		            // if feeler intersects circle (plus buffer),
		            //and projection is less than feeler length,
		            // we will collide, so need to steer
		            if(dist < circle.radius + _avoidBuffer &&
		               projection.length < feeler.length)
		            {
		                // calculate a force +/- 90 degrees from vector to circle
		                var force:Vector2D = heading.multiply(_maxSpeed);
		                force.angle += difference.sign(_velocity) * Math.PI / 2;
 
		                // scale this force by distance to circle.
		                // the further away, the smaller the force
		                force = force.multiply(1.0 - projection.length /
		                                             feeler.length);
 
		                // add to steering force
		                _steeringForce = _steeringForce.add(force);
 
		                // braking force
		                _velocity = _velocity.multiply(projection.length / feeler.length);
		            }
		        }
		    }
		}
 
		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);
			}
		}
 
		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));
			}
		}
 
		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;
		}
	}
}

Код AS3:

package com.foed
{
	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);
		}
	}
}

Код AS3:

package com.foed
{
	import flash.display.Sprite;
 
	/**
	 * Base class for moving characters.
	 */
	public class Vehicle extends Sprite
	{
		protected var _edgeBehavior:String = WRAP;
		protected var _mass:Number = 1.0;
		protected var _maxSpeed:Number = 10;
		protected var _position:Vector2D;
		protected var _velocity:Vector2D;
 
		// potential edge behaviors
		public static const WRAP:String = "wrap";
		public static const BOUNCE:String = "bounce";
 
		/**
		 * Constructor.
		 */
		public function Vehicle()
		{
			_position = new Vector2D();
			_velocity = new Vector2D();
			draw();
		}
 
		/**
		 * Default graphics for vehicle. Can be overridden in subclasses.
		 */
		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);
		}
 
		/**
		 * Handles all basic motion. Should be called on each frame / timer interval.
		 */
		public function update():void
		{
			// make sure velocity stays within max speed.
			_velocity.truncate(_maxSpeed);
 
			// add velocity to position
			_position = _position.add(_velocity);
 
			// handle any edge behavior
			if(_edgeBehavior == WRAP)
			{
				wrap();
			}
			else if(_edgeBehavior == BOUNCE)
			{
				bounce();
			}
 
			// update position of sprite
			x = position.x;
			y = position.y;
 
			// rotate heading to match velocity
			rotation = _velocity.angle * 180 / Math.PI;
		}
 
		/**
		 * Causes character to bounce off edge if edge is hit.
		 */
		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;
				}
			}
		}
 
		/**
		 * Causes character to wrap around to opposite edge if edge is hit.
		 */
		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;
			}
		}
 
		/**
		 * Sets / gets what will happen if character hits edge.
		 */
		public function set edgeBehavior(value:String):void
		{
			_edgeBehavior = value;
		}
		public function get edgeBehavior():String
		{
			return _edgeBehavior;
		}
 
		/**
		 * Sets / gets mass of character.
		 */
		public function set mass(value:Number):void
		{
			_mass = value;
		}
		public function get mass():Number
		{
			return _mass;
		}
 
		/**
		 * Sets / gets maximum speed of character.
		 */
		public function set maxSpeed(value:Number):void
		{
			_maxSpeed = value;
		}
		public function get maxSpeed():Number
		{
			return _maxSpeed;
		}
 
		/**
		 * Sets / gets position of character as a Vector2D.
		 */
		public function set position(value:Vector2D):void
		{
			_position = value;
			x = _position.x;
			y = _position.y;
		}
		public function get position():Vector2D
		{
			return _position;
		}
 
		/**
		 * Sets / gets velocity of character as a Vector2D.
		 */
		public function set velocity(value:Vector2D):void
		{
			_velocity = value;
		}
		public function get velocity():Vector2D
		{
			return _velocity;
		}
 
		/**
		 * Sets x position of character. Overrides Sprite.x to set internal Vector2D position as well.
		 */
		override public function set x(value:Number):void
		{
			super.x = value;
			_position.x = x;
		}
 
		/**
		 * Sets y position of character. Overrides Sprite.y to set internal Vector2D position as well.
		 */
		override public function set y(value:Number):void
		{
			super.y = value;
			_position.y = y;
		}
 
	}
}

Код AS3:

package com.foed
{
	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;
		}
		public function draw(graphics:Graphics, color:uint = 0):void
		{
			graphics.lineStyle(0, color);
			graphics.moveTo(0, 0);
			graphics.lineTo(_x, _y);
		}
		public function clone():Vector2D
		{
			return new Vector2D(x, y);
		}
 
		public function zero():Vector2D
		{
			_x = 0;
			_y = 0;
			return this;
		}
		public function isZero():Boolean
		{
			return _x == 0 && _y == 0;
		}
		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;
		}
		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);
		}
		public function normalize():Vector2D
		{
			if(length == 0)
			{
				_x = 1;
				return this;
			}
			var len:Number = length;
			_x /= len;
			_y /= len;
			return this;
		}
		public function truncate(max:Number):Vector2D
		{
			length = Math.min(max, length);
			return this;
		}
		public function reverse():Vector2D
		{
			_x = -_x;
			_y = -_y;
			return this;
		}
		public function isNormalized():Boolean
		{
			return length == 1.0;
		}
		public function dotProd(v2:Vector2D):Number
		{
			return _x * v2.x + _y * v2.y;
		}
		public function crossProd(v2:Vector2D):Number
		{
			return _x * v2.y - _y * v2.x;
		}
		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));
		}
		public function sign(v2:Vector2D):int
		{
			return perp.dotProd(v2) < 0 ? -1 : 1;
		}
		public function get perp():Vector2D
		{
			return new Vector2D(-y, x);
		}
		public function dist(v2:Vector2D):Number
		{
			return Math.sqrt(distSQ(v2));
		}
		public function distSQ(v2:Vector2D):Number
		{
			var dx:Number = v2.x - x;
			var dy:Number = v2.y - y;
			return dx * dx + dy * dy;
		}
		public function add(v2:Vector2D):Vector2D
		{
			return new Vector2D(_x + v2.x, _y + v2.y);
		}
		public function subtract(v2:Vector2D):Vector2D
		{
			return new Vector2D(_x - v2.x, _y - v2.y);
		}
		public function multiply(value:Number):Vector2D
		{
			return new Vector2D(_x * value, _y * value);
		}
		public function divide(value:Number):Vector2D
		{
			return new Vector2D(_x / value, _y / value);
		}
		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;
		}
		public function toString():String
		{
			return "[Vector2D (x:" + _x + ", y:" + _y + ")]";
		}
	}
}

бакуард · 09.05.2015, 10:31

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

caseyryan · 09.05.2015, 10:52

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

бакуард · 10.05.2015, 11:16

Еще один небольшой вопрос - класс vector2D я так понял пользовательский, а не предопределенный?

caseyryan · 10.05.2015, 14:11

Да. Он же тут тоже есть

Опции темы
Версия для печати Отправить по электронной почте
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид