One By One Design

Flocking (Steering Behaviour) in 3D

So I just got my grubby little paws on Keith Peters’ latest book, “Advanced Actionscript 3.0 Animation”. I couldn’t even get past chapter 2 before I had to try out some stuff on my own. Chapter 2 is all about steering behaviours for AI animated movement. If you’re not familiar with the concept of steering behaviours, you’ve most likely seen it illustrated in a flocking example at some time or other. That is several little “characters” are moving about doing their own thing, but when they come close to each other they start to tend to group up until they’re all moving around together. Boids they call these things. I’ve seen several examples of this done in Flash in my time and was impressed every time. This is the first I’ve taken the time to examine the script behind the concept though, and my first thought was “why not do that in 3d?” So I did. Mostly. There are still many glitches that can be hammered out. The wander() method is shaky at best. And avoid() doesn’t much work at all, yet. Basically, it’s calculating random 3d angles that’s giving me fits. The flocking, fleeing, and pursuing behaviours are working all right though. And pretty damn fun.

To use the things, you just create a new SteeredVehicle3D instance (which inherits from the papervision3d DisplayObject3D object) and update it on each frame. The actual 3d object you’re moving has its properties (position and rotation) set to that of the SV3D instance. Basically it’s like parenting a layer to a null object in After Effects.

Check out the examples below (double click on them to activate/deactivate). Incidentally, the stars seen in the first two examples come from Slavomír Durej. Nice little quick and easy class to give your PV3D projects a spacy look.

Flocking example. 10 “ships” (well, cones) fly about slowly grouping into a flock. You may have to rotate the camera around to follow them – or go for a wild ride by pressing ‘v’ to get the point of view of one of the cones. Pressing ‘b’ will show or hide the bounding box if, for some reason, you want to see it.

[kml_flashembed fversion=”9.0.0″ movie=”http://blog.onebyonedesign.com/wp-content/uploads/2009/06/flock.swf” targetclass=”flashmovie” publishmethod=”static” width=”500″ height=”400″]

Get Adobe Flash player

[/kml_flashembed]

Pursue/Flee example. Here the green cone is fleeing from red cone which is pursuing the green cone. It’s a thrilling cat-and-mouse chase in the third dimension. Keep the mouse down to control the camera yourself, or just follow the fleeing green cone.

[kml_flashembed fversion=”9.0.0″ movie=”http://blog.onebyonedesign.com/wp-content/uploads/2009/06/chase.swf” targetclass=”flashmovie” publishmethod=”static” width=”500″ height=”400″]

Get Adobe Flash player

[/kml_flashembed]

And some flocking 3d ribbons.

[kml_flashembed fversion=”9.0.0″ movie=”http://blog.onebyonedesign.com/wp-content/uploads/2009/06/ribbons.swf” targetclass=”flashmovie” publishmethod=”static” width=”500″ height=”400″]

Get Adobe Flash player

[/kml_flashembed]

If you’d like to play to play around, all the pertinent code is below. Again, 90% of it was written by Keith Peters (you can download the original at the Friends of ED website, if you don’t have the book). I just added a dimension and used some references to the Papervision3D library.

Bounds3D.as – use this for the bounding areas of the vehicles. Also use it for obstacles to avoid (if you get the avoid method working properly before me, let me know).

package com.onebyonedesign.td.pv3d.steering {
	
	import org.papervision3d.core.math.Number3D;
	
	public class Bounds3D {
		
		private var _xmin:Number;
		private var _xmax:Number;
		private var _ymin:Number;
		private var _ymax:Number;
		private var _zmin:Number;
		private var _zmax:Number;
		private var _width:Number;
		private var _height:Number;
		private var _depth:Number;
		private var _x:Number;
		private var _y:Number;
		private var _z:Number;
		
		public function Bounds3D(width:Number = 2000, height:Number = 2000, depth:Number = 2000) {
			_width = width;
			_height = height;
			_depth = depth;
			_x = 0;
			_y = 0;
			_z = 0;
			
			setProps();
		}
		
		private function setProps():void {
			_xmin = _x - _width * .5;
			_xmax = _x + _width * .5;
			_ymin = _y - _height * .5;
			_ymax = _y + _height * .5;
			_zmin = _z - _depth * .5;
			_zmax = _z + _depth * .5;
		}
		
		public function get xmin():Number { return _xmin; }
		
		public function get xmax():Number { return _xmax; }
		
		public function get ymin():Number { return _ymin; }
		
		public function get ymax():Number { return _ymax; }
		
		public function get zmin():Number { return _zmin; }
		
		public function get zmax():Number { return _zmax; }
		
		public function get width():Number { return _width; }
		
		public function set width(value:Number):void {
			_width = value;
			setProps();
		}
		
		public function get height():Number { return _height; }
		
		public function set height(value:Number):void {
			_height = value;
			setProps();
		}
		
		public function get depth():Number { return _depth; }
		
		public function set depth(value:Number):void {
			_depth = value;
			setProps();
		}
		
		public function get x():Number { return _x; }
		
		public function set x(value:Number):void {
			_x = value;
			setProps();
		}
		
		public function get y():Number { return _y; }
		
		public function set y(value:Number):void {
			_y = value;
			setProps();
		}
		
		public function get z():Number { return _z; }
		
		public function set z(value:Number):void {
			_z = value;
			setProps();
		}
		
		public function get position():Number3D {
			return new Number3D(x, y, z);
		}
		
		public function set position(value:Number3D):void {
			x = value.x;
			y = value.y;
			z = value.z;
			setProps();
		}
	}
}

Vehicle3D.as – the base class for the steered vehicles.

package com.onebyonedesign.td.pv3d.steering {
	
	import org.papervision3d.core.math.Number3D;
	import org.papervision3d.objects.DisplayObject3D;
	
	/**
	 * Base class for moving 3d characters.
	 * 
	 * Script based on Keith Peters script from Ch. 2 of 
	 * "Advanced Actionscript 3.0 Animation"
	 */
	public class Vehicle3D extends DisplayObject3D {
		
		protected var _edgeBehavior:String = BOUNCE;
		protected var _mass:Number = 1.0;
		protected var _maxSpeed:Number = 10;
		protected var _velocity:Number3D;
		
		private var _bounds:Bounds3D = new Bounds3D();
		
		// potential edge behaviors
		public static const WRAP:String = "wrap";
		public static const BOUNCE:String = "bounce";
		
		public function Vehicle3D() {
			_velocity = new Number3D();
		}
		
		public function update():void {
			if (_velocity.isModuloGreaterThan(_maxSpeed)) {
				var mult:Number = _maxSpeed / _velocity.modulo;
				_velocity.reset(_velocity.x * mult, _velocity.y * mult, _velocity.z * mult);
			}
			
			position = Number3D.add(position, _velocity);
			
			if(_edgeBehavior == WRAP) {
				wrap();
			} else if(_edgeBehavior == BOUNCE) {
				bounce();
			}
			
			/**
			 * TODO Make this good
			 * 
			 * very low tech way of determining 3d rotation that
			 * I'm not 100% satisfied with, but it does all right
			 */
			var rotObj:Number3D = _velocity.clone();
			rotObj.normalize();
			rotObj.multiplyEq(90);
			rotationX = rotObj.z;
			rotationZ = -rotObj.x;
			rotationY = rotObj.y;
		}

		private function bounce():void {

			if(x > _bounds.xmax) {
				x = _bounds.xmax;
				velocity.x *= -1;
			} else if (x < _bounds.xmin) {
				x = _bounds.xmin;
				velocity.x *= -1;
			}
				
			if(y > _bounds.ymax) {
				y = _bounds.ymax;
				velocity.y *= -1;
			} else if (y < _bounds.ymin) {
				y = _bounds.ymin;
				velocity.y *= -1;
			}
			
			if (z > _bounds.zmax) {
				z = _bounds.zmax;
				velocity.z *= -1;
			} else if (z < _bounds.zmin) {
				z = _bounds.zmin;
				velocity.z *= -1;
			}
		}
		
		private function wrap():void {
			if (x > _bounds.xmax) x = _bounds.xmin;
			if (x < _bounds.xmin) x = _bounds.xmax;
			if (y > _bounds.ymax) y = _bounds.ymin;
			if (y < _bounds.ymin) y = _bounds.ymax;
			if (z > _bounds.zmax) z = _bounds.zmin;
			if (z < _bounds.zmin) z = _bounds.zmax;
		}
		
		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; }
		
		public function set velocity(value:Number3D):void {
			_velocity = value;
		}
		public function get velocity():Number3D { return _velocity; }
		
		public function get bounds():Bounds3D { return _bounds; }
		
		public function set bounds(value:Bounds3D):void {
			_bounds = value;
		}
	}
}

SteeredVehicle3D.as - the thing you'll want to actually use in a project.

package com.onebyonedesign.td.pv3d.steering {
	
	import flash.display.Sprite;
	import org.papervision3d.core.math.Number3D;
	import org.papervision3d.Papervision3D;
	
	/**
	 * Based on SteeredVehicle class by Keith Peters in Ch. 2 of
	 * "Advanced Actionscript 3.0 Animation"
	 */
	public class SteeredVehicle3D extends Vehicle3D {
		
		private var _maxForce:Number = 1;
		private var _steeringForce:Number3D;
		private var _arrivalThreshold:Number = 100;
		private var _wanderAngleX:Number = 0;
		private var _wanderAngleY:Number = 0;
		private var _wanderAngleZ:Number = 0;
		private var _wanderDistance:Number = 50;
		private var _wanderRadius:Number = 20;
		private var _wanderRange:Number = 1;
		private var _pathIndex:int = 0;
		private var _pathThreshold:Number = 20;
		private var _avoidDistance:Number = 200;
		private var _avoidBuffer:Number = 20;
		private var _inSightDist:Number = 200;
		private var _tooCloseDist:Number = 60;
		
		public function SteeredVehicle3D() {
			Papervision3D.useDEGREES = true;
			_steeringForce = new Number3D();
			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 {
			if (_steeringForce.modulo > _maxForce) {
				var mult:Number = _maxForce / _steeringForce.modulo;
				_steeringForce.reset(_steeringForce.x * mult, _steeringForce.y * mult, _steeringForce.z * mult);
			}
			_steeringForce.reset(_steeringForce.x / _mass, _steeringForce.y / _mass, _steeringForce.z / _mass);
			_velocity = Number3D.add(_velocity, _steeringForce);
			_steeringForce = new Number3D();
			super.update();
		}
		
		public function seek(target:Number3D):void {
			var desiredVelocity:Number3D = Number3D.sub(target, position);
			desiredVelocity.normalize();
			desiredVelocity.multiplyEq(_maxSpeed);
			var force:Number3D = Number3D.sub(desiredVelocity, _velocity);
			_steeringForce = Number3D.add(_steeringForce, force);
		}
		
		public function flee(target:Number3D):void {
			var desiredVelocity:Number3D = Number3D.sub(target, position);
			desiredVelocity.normalize();
			desiredVelocity.multiplyEq(_maxSpeed);
			var force:Number3D = Number3D.sub(desiredVelocity, _velocity);
			_steeringForce = Number3D.sub(_steeringForce, force);
		}
		
		public function arrive(target:Number3D):void {
			var desiredVelocity:Number3D = Number3D.sub(target, position);
			var dist:Number = desiredVelocity.modulo;
			desiredVelocity.normalize();
			
			if(dist > _arrivalThreshold) {
				desiredVelocity.multiplyEq(_maxSpeed);
			} else {
				desiredVelocity.multiplyEq(_maxSpeed * dist / _arrivalThreshold);
			}
			
			var force:Number3D = Number3D.sub(desiredVelocity, _velocity);
			_steeringForce = Number3D.add(_steeringForce, force);
		}
		
		
		public function pursue(target:Vehicle3D):void {
			var lookAhead:Number3D = Number3D.sub(target.position, position);
			var lookAheadTime:Number = lookAhead.modulo / _maxSpeed;
			var targetVelocity:Number3D = target.velocity.clone();
			targetVelocity.multiplyEq(lookAheadTime);
			var predictedTarget:Number3D = Number3D.add(target.position, targetVelocity);
			seek(predictedTarget);
		}
		
		public function evade(target:Vehicle3D):void {
			var lookAhead:Number3D = Number3D.sub(target.position, position);
			var lookAheadTime:Number = lookAhead.modulo / _maxSpeed;
			var targetVelocity:Number3D = target.velocity.clone();
			targetVelocity.multiplyEq(lookAheadTime);
			var predictedTarget:Number3D = Number3D.add(target.position, targetVelocity);
			flee(predictedTarget);
		}
		
		public function wander():void {
			
			/**
			 * TODO Fix this method. Wandering around is not very good at all.
			 */
			
			var center:Number3D = velocity.clone();
			center.normalize();
			center.multiplyEq(_wanderDistance);
			var offset:Number3D = new Number3D(_wanderRadius, _wanderRadius, _wanderRadius);
			
			offset.rotateX(_wanderAngleX);
			offset.rotateY(_wanderAngleY);
			offset.rotateZ(_wanderAngleZ);
			
			_wanderAngleX += Math.random() * _wanderRange - _wanderRange * .5 * 180 / Math.PI;
			_wanderAngleY += Math.random() * _wanderRange - _wanderRange * .5 * 180 / Math.PI;
			_wanderAngleZ += Math.random() * _wanderRange - _wanderRange * .5 * 180 / Math.PI;
			
			var force:Number3D = Number3D.add(center, offset);
			_steeringForce = Number3D.add(_steeringForce, force);
		}
		
		public function avoid(obstacles:Array):void {
		    for(var i:int = 0; i < obstacles.length; i++) {
		        var bound:Bounds3D = obstacles[i] as Bounds3D;
		        var heading:Number3D = _velocity.clone();
				heading.normalize();
		        
				var difference:Number3D = Number3D.sub(bound.position, position);
				var dotProd:Number = Number3D.dot(difference, heading);

		        if(dotProd > 0) {
		            var feeler:Number3D = heading.clone();
					feeler.multiplyEq(_avoidDistance);
		            var projection:Number3D = heading.clone();
					projection.multiplyEq(dotProd);
					var dif:Number3D = Number3D.sub(projection, difference);
		            var dist:Number = dif.modulo;
		            
		            if(dist < bound.width * .5 + _avoidBuffer && projection.modulo < feeler.modulo) {
		                // calculate a force +/- 90 degrees from vector to circle
		                var force:Number3D = heading.clone();
						force.multiplyEq(_maxSpeed);
						
						/**
						 * TODO calculate deflection angle
						 * as is, this method is FUBAR
						 */
						
						// original line of code
		                //force.angle += difference.sign(_velocity) * Math.PI / 2;
		                
		                force.multiplyEq(1.0 - projection.modulo / feeler.modulo);
		                
		                _steeringForce = Number3D.add(_steeringForce, force);
		                
						_velocity.multiplyEq(projection.modulo / feeler.modulo);
		            }
		        }
		    }
		}
		
		public function followPath(path:Array, loop:Boolean = false):void {
			var wayPoint:Number3D = path[_pathIndex];
			if (wayPoint == null) return;
			var distPoint:Number3D = Number3D.sub(position, wayPoint);
			var dist:Number = distPoint.modulo;
			if(dist < _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:Number3D = _velocity.clone();
			var averagePosition:Number3D = new Number3D();
			var inSightCount:int = 0;
			for(var i:int = 0; i < vehicles.length; i++) {
				var vehicle:Vehicle3D = vehicles[i] as Vehicle3D;
				if (vehicle != this && inSight(vehicle)) {
					averageVelocity = Number3D.add(averageVelocity, vehicle.velocity);
					averagePosition = Number3D.add(averagePosition, vehicle.position);
					if(tooClose(vehicle)) flee(vehicle.position);
					inSightCount++;
				}
			}
			if (inSightCount > 0) {
				averageVelocity.reset(averageVelocity.x / inSightCount, averageVelocity.y / inSightCount, averageVelocity.z / inSightCount);
				averagePosition.reset(averagePosition.x / inSightCount, averagePosition.y / inSightCount, averagePosition.z / inSightCount);
				seek(averagePosition);
				_steeringForce = Number3D.add(_steeringForce, Number3D.sub(averageVelocity, _velocity));
			}
		}
		
		public function inSight(vehicle:Vehicle3D):Boolean {
			if(dist(this.position, vehicle.position) > _inSightDist) return false;
			var heading:Number3D = _velocity.clone();
			heading.normalize();
			var difference:Number3D = Number3D.sub(vehicle.position, this.position);
			var dotProd:Number = Number3D.dot(difference, heading);
			
			if(dotProd < 0) return false;
			return true;
		}
		
		public function tooClose(vehicle:Vehicle3D):Boolean {
			var dist:Number = dist(this.position, vehicle.position);
			return dist < _tooCloseDist;
		}
		
		private function dist(pos1:Number3D, pos2:Number3D):Number {
			var dx:Number = pos1.x - pos2.x;
			var dy:Number = pos1.y - pos2.y;
			var dz:Number = pos1.z - pos2.z;
			return Math.sqrt(dx * dx + dy * dy + dz * dz);
		}
	}
}

In any case, I highly recommend Keith Peters' book - very inspirational...

Posted by

Post a comment

Your email address will not be published. Required fields are marked *