autonomous agent study

/**
 * Copyright wrotenodoc ( http://wonderfl.net/user/wrotenodoc )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/adzw
 */

package {
    
    import flash.text.TextField;
    import flash.display.Sprite;
    import flash.geom.Point
    
    import com.actionscriptbible.Example
    
    // Autonomous Agent Study
    // Programming Game AI by Example - Mat Buckland
    [SWF(width=420, height=420, frameRate=60)]
    public class FlashTest extends Example {
        
        private var world:GameWorld
        private var A:Vehicle, B:Vehicle, C:Vehicle
        
        public function FlashTest() {
            // write as3 code here..
            debug = new TextField
            debug.autoSize = "left"
            debug.y = 410
            addChild(debug)
            
            world = new GameWorld(400, 400)
            world.x = world.y = 10
            addChild(world)
            
            /*A = new Vehicle
            A.x = 50 ; A.y = 50
            world.addVehicle(A)
            
            B = new Vehicle
            B.x = 350 ; B.y = 200
            B.steering.obstacleAvoidanceOn = true
            B.steering.pursuitOn = true
            B.steering.target = A
            world.addVehicle(B)
            
            C = new Vehicle
            C.x = 100 ; C.y = 300
            world.addVehicle(C)*/
            
            for(var i:int=0; i<200; i++){
                var v:Vehicle = new Vehicle
                v.x = Math.random() * world.width
                v.y = Math.random() * world.height
                v.steering.wanderOn = true
                v.steering.obstacleAvoidanceOn = true
                //if(Math.random() < 0.1) v.steering.separationOn = true
                //else v.steering.cohesionOn = true
                //v.steering.alignmentOn = true
                //v.enforceNonPenetration = true
                world.addVehicle(v)
            }
            
            world.addObstacle(new Obstacle(100, 100, 50))
            world.addObstacle(new Obstacle(200, 300, 20))
            world.addObstacle(new Obstacle(300, 50, 30))
            
            // var w1:Wall = new Wall(100, 200, 300, 200)
            /*for(i=0; i<5; i++){
                var w1:Wall = new Wall(Math.random() * 400, Math.random() * 400, Math.random() * 400, Math.random() * 400)
                world.addWall(w1)
            }*/
            
            /*A.steering.target = B
            //A.steering.target2 = C
            A.steering.hideOn = true
            
            B.steering.wanderOn = true
            //B.steering.setPath([new Point(200, 300), new Point(300, 100), new Point(200, 200)], true)
            //B.steering.followPathOn = true
            
            C.steering.target = B
            C.steering.offset = new Point(-30, 0)
            C.steering.offsetPursuitOn = true
            //C.steering.wanderOn = true
            //C.steering.obstacleAvoidanceOn = true*/
            
            addEventListener("enterFrame", loop)
        }
        
        private function loop(e:Object):void {
            world.update(0.05)
        }
        
    }
    
}

import flash.text.TextField
var debug:TextField

import flash.display.Sprite
import flash.geom.Point

class Entity extends Sprite {
    
    protected var _radius:Number = 8
    
    public function Entity() {
        render()
    }
    
    public function update(timeElapsed:Number):void {}
    public function render():void {
        graphics.clear()
        graphics.lineStyle(0, 0x0)
        graphics.drawCircle(0, 0, radius)
    }
    
    public function get position():Point { return new Point(x, y) }
    public function get radius():Number { return _radius }
    
}

class MovingEntity extends Entity {
    
    protected var _velocity:Point = new Point
    protected var _heading:Point = new Point
    protected var side:Point = new Point
    protected var mass:Number = 1
    protected var _maxSpeed:Number = 20
    protected var _maxForce:Number = 200
    protected var maxTurnRate:Number = Infinity
    
    public override function render():void {
        graphics.clear()
        graphics.lineStyle(0, 0x0)
        graphics.moveTo(radius, 0)
        graphics.lineTo(-Math.sqrt(3)/2*radius, .5*radius)
        graphics.lineTo(-Math.sqrt(3)/2*radius, -.5*radius)
        graphics.lineTo(radius, 0)
    }
    
    public function get velocity():Point { return _velocity.clone() }
    public function get speed():Number { return _velocity.length }
    public function get heading():Point { return _heading.clone() }
    public function get maxSpeed():Number { return _maxSpeed }
    public function get maxForce():Number { return _maxForce }

}

class Obstacle extends Entity {
    
    public function Obstacle(x0:Number, y0:Number, radius:Number=10) {
        x = x0
        y = y0
        _radius = radius
        render()
    }
    
    public override function render():void {
        graphics.clear()
        graphics.lineStyle(0, 0xff0000)
        graphics.drawCircle(0, 0, radius)
    }
    
}

class Vehicle extends MovingEntity {
    
    public var world:GameWorld
    public var enforceNonPenetration:Boolean = false
    private var _steering:SteeringBehaviors
    
    private var _smoothing:Boolean = false
    private var _smoothingNumSamples:uint = 5
    private var _smoothingAccum:Array = []
    
    public function Vehicle() {
        _steering = new SteeringBehaviors(this)
    }
    
    public override function update(timeElapsed:Number):void {
        var accel:Point = steering.calculate()
        accel.x /= mass ; accel.y /= mass
        
        _velocity.x += accel.x * timeElapsed
        _velocity.y += accel.y * timeElapsed
        
        var speed:Number = _velocity.length
        if(speed > maxSpeed) _velocity.normalize(maxSpeed)
        x += _velocity.x * timeElapsed
        y += _velocity.y * timeElapsed
        
        var currHead:Point = _velocity.clone()
        currHead.normalize(1)
        //if(speed*speed > 0.000000001){
            side.x = -currHead.y
            side.y = currHead.x
        //}
        
        if(_smoothing){
            _smoothingAccum.push(currHead)
            if(_smoothingAccum.length == _smoothingNumSamples){
                _smoothingAccum.shift()
            }
            var xAccum:Number = 0, yAccum:Number = 0
            for each(var accum:Point in _smoothingAccum){
                xAccum += accum.x ; yAccum += accum.y
            }
            xAccum /= _smoothingAccum.length
            yAccum /= _smoothingAccum.length
            currHead.x = xAccum
            currHead.y = yAccum
        }
        
        if(x < 0) x = world.width
        else if(x > world.width) x = 0
        if(y < 0) y = world.height
        else if(y > world.height) y = 0
        rotation = Math.atan2(currHead.y, currHead.x) * 180/Math.PI
    }
    
    public function noPenetration(agents:Array):void {
        for each(var v:Entity in agents){
            if(v == this) continue
            var toEntity:Point = v.position.subtract(position)
            var dist:Number = toEntity.length
            var overlap:Number = radius + v.radius - dist
            if(overlap > 0){
                v.x += toEntity.x * overlap/dist
                v.y += toEntity.y * overlap/dist
            }
        }
    }
    
    public function get steering():SteeringBehaviors { return _steering }
    public function set smoothing(value:Boolean):void {
        _smoothing = value
        if(value) _smoothingAccum.length = 0
     }
    
}

class Wall extends Sprite {
    
    private var _from:Point
    private var _to:Point
    private var _unit:Point
    private var _normal:Point
    
    public function Wall(x0:Number,y0:Number, x1:Number,y1:Number) {
        _from = new Point(x0, y0)
        _to = new Point(x1, y1)
        _unit = _to.subtract(_from)
        _unit.normalize(1)
        _normal = new Point(-_unit.y, _unit.x)
        
        x = x0 ; y = y0
        graphics.lineStyle(2, 0x0)
        graphics.lineTo(x1-x0, y1-y0)
    }
    
    public function lineIntersection(p0:Point, p1:Point):Point {
        var from_p0:Point = p0.subtract(_from)
        var from_p1:Point = p1.subtract(_from)
        if(dotProduct(from_p0, _normal) * dotProduct(from_p1, _normal) > 0) return null
        var IP:Point = _from.add(scalarMult(_unit, dotProduct(from_p0, _unit)))
        if((_from.x <= IP.x && IP.x <= _to.x) || (_to.x <= IP.x && IP.x <= _from.x)){
            return IP
        }
        return null
    }
    
    public function get normal():Point { return _normal.clone() }
    
}

class GameWorld extends Sprite {
    
    //private var _entities:Array = []
    private var _vehicles:Array = []
    private var _walls:Array = []
    private var _obstacles:Array = []
    private var _partitions:Vector.<WorldPartition> // row-major
    private var _width:Number, _height:Number
    private var _partitionX:uint, _partitionY:uint
    private var _partitionWidth:Number, _partitionHeight:Number
    
    public function GameWorld(w:Number, h:Number, partitionX:uint=10, partitionY:uint=10) {
        _width = w ; _height = h
        _partitionX = partitionX ; _partitionY = partitionY
        _partitionWidth = w/partitionX ; _partitionHeight = h/partitionY
        
        _partitions = new Vector.<WorldPartition>(partitionX * partitionY, true)
        for(var i:int=0; i<partitionX * partitionY; i++){
            var px:Number = (i%partitionX) * _partitionWidth
            var py:Number = uint(i/partitionY) * _partitionHeight
            _partitions[i] = new WorldPartition(this, i, px, py, _partitionWidth, _partitionHeight)
        }
        for(i=0; i<_partitions.length; i++) _partitions[i].findNeighbors()
        
        graphics.lineStyle(0, 0x0)
        var p:WorldPartition
        for(i=0; i<_partitions.length; i++){
            p = _partitions[i]
            graphics.drawRect(p.x, p.y, p.width, p.height)
        }
        graphics.lineStyle(2, 0x0000ff)
        graphics.drawRect(0, 0, w, h)
        
        //addEventListener("enterFrame", debug)
    }
    
    private function debug(e:Object):void {
        var tx:Number = mouseX, ty:Number = mouseY
        var part:WorldPartition = getPartition(tx, ty)
        for(var i:int=0; i<_vehicles.length; i++) _vehicles[i].alpha = 1
        if(part != null){
            for(var j:int=0; j<part.neighbors.length; j++)
            for(i=0; i<part.neighbors[j].vehicles.length; i++) part.neighbors[j].vehicles[i].alpha = .5
        }
        /*graphics.clear()
        for each(var p:WorldPartition in part.neighbors){
            graphics.beginFill(0xff0000, .5)
            graphics.drawRect(p.x, p.y, p.width, p.height)
            graphics.endFill()
        }*/
    }
    
    public function getPartition(x:Number, y:Number):WorldPartition {
        if(x < 0 || x >= _width || y < 0 || y >= _height) return null
        var unitX:uint = uint(x/_partitionWidth)
        var unitY:uint = uint(y/_partitionHeight)
        var idx:uint = unitY*_partitionY + unitX
        //if(idx >= _partitions.length) return null
        return _partitions[idx]
    }
    
    /*public function addEntity(entity:Entity):void {
        _entities.push(entity)
        addChild(entity)
    }*/
    
    public function addVehicle(v:Vehicle):void {
        _vehicles.push(v)
        addChild(v)
        getPartition(v.x, v.y).add(v)
        v.world = this
    }
    
    public function addWall(w:Wall):void {
        _walls.push(w)
        addChild(w)
    }
    
    public function addObstacle(o:Obstacle):void {
        _obstacles.push(o)
        addChild(o)
    }
    
    public function update(timeElapsed:Number):void {
        var part:WorldPartition, part2:WorldPartition
        var v:Vehicle
        for(var i:int=0; i<_vehicles.length; i++){
            v = _vehicles[i]
            part = getPartition(v.x, v.y)
            v.update(timeElapsed)
            part2 = getPartition(v.x, v.y)
            if(part != part2){
                part.remove(v)
                part2.add(v)
            }
        }
        // ensure zero overlap
        for(i=0; i<_vehicles.length; i++){
            v = _vehicles[i]
            v.enforceNonPenetration && v.noPenetration(_vehicles)
        }
    }
    
    /*public function render():void {
        for(var i:int=0; i<_vehicles.length; i++){
            _vehicles[i].render()
        }
    }*/
    
    public function getNeighbors(vehicle:Vehicle):Array {
        var ary:Array = []
        var part:WorldPartition = getPartition(vehicle.x, vehicle.y)
        if(part == null) return ary
        for each(var p:WorldPartition in part.neighbors){
            for each(var v:Vehicle in part.vehicles){
                if(v == vehicle) continue
                if(v.position.subtract(vehicle.position).length <= vehicle.steering.neighborRadius){
                    ary.push(v)
                }
            }            
        }
        return ary
    }
    
    public override function get width():Number { return _width }
    public override function get height():Number { return _height }
    public function get vehicles():Array { return _vehicles }
    public function get obstacles():Array { return _obstacles }
    public function get walls():Array { return _walls }
    public function get partitions():Vector.<WorldPartition> { return _partitions }
    
}

class WorldPartition {
    
    private var _x:Number, _y:Number, _width:Number, _height:Number
    private var _world:GameWorld
    private var _vehicles:Vector.<Vehicle>
    private var _index:uint
    private var _neighbors:Vector.<WorldPartition> // * includes this partition!! *
    
    public function WorldPartition(world:GameWorld, idx:uint, x:Number,y:Number, w:Number,h:Number) {
        _world = world
        _x = x; _y = y; _width=w; _height=h
        _vehicles = new Vector.<Vehicle>
        _index = idx
    }
    
    public function add(v:Vehicle):void {
        _vehicles.push(v)
    }
    public function remove(v:Vehicle):void {
        var idx:int = _vehicles.indexOf(v)
        if(idx != -1) _vehicles.splice(idx, 1)
    }
    
    public function findNeighbors():void {
        _neighbors = new Vector.<WorldPartition>
        var cx:Number = _x + _width/2, cy:Number = _y + _height/2
        
        append(cx - _width, cy - _height)
        append(cx, cy - _height)
        append(cx + _width, cy - _height)
        
        append(cx - _width, cy)
        append(cx, cy)
        append(cx + _width, cy)
        
        append(cx - _width, cy + _height)
        append(cx, cy + _height)
        append(cx + _width, cy + _height)
        
        function append(px:Number, py:Number):void {
            var p:WorldPartition = _world.getPartition(px, py)
            if(p != null) _neighbors.push(p)
        }
    }
    
    public function get x():Number { return _x }
    public function get y():Number { return _y }
    public function get width():Number { return _width }
    public function get height():Number { return _height }
    public function get vehicles():Vector.<Vehicle> { return _vehicles }
    public function get neighbors():Vector.<WorldPartition> { return _neighbors }
    
}

class SteeringBehaviorsSummingMethod {
    public static const WEIGHTED_AVERAGE:String = "weightedAverage"
    public static const PRIORITIZED:String = "prioritized"
    public static const DITHERED:String = "dithered"
    public static function checkValid(option:String):void {
        if([WEIGHTED_AVERAGE, PRIORITIZED, DITHERED].indexOf(option) == -1){
            throw new Error("Not a valid summing method: " + option)
        }
    }
}


class SteeringBehaviors {
    
    private var _summingMethod:String = SteeringBehaviorsSummingMethod.PRIORITIZED
    
    private var _target:Vehicle
    private var _target2:Vehicle
    private var _vehicle:Vehicle // owner
    
    private var _path:Array
    private var _pathIdx:int
    private var _pathClosed:Boolean
    
    private var _offset:Point // used in offsetPursuit()
    
    // sole behaviors
    public var seekOn:Boolean = false
    public var fleeOn:Boolean = false
    public var arriveOn:Boolean = false
    public var pursuitOn:Boolean = false
    public var evadeOn:Boolean = false
    public var wanderOn:Boolean = false
    public var obstacleAvoidanceOn:Boolean = false
    public var wallAvoidanceOn:Boolean = false
    public var interposeOn:Boolean = false
    public var hideOn:Boolean = false
    public var followPathOn:Boolean = false
    public var offsetPursuitOn:Boolean = false
    
    // group behaviors
    public var neighborRadius:Number = 150
    public var separationOn:Boolean = false
    public var alignmentOn:Boolean = false
    public var cohesionOn:Boolean = false
    
    public function SteeringBehaviors(v:Vehicle) {
        _vehicle = v
    }
    
    public function get target():Vehicle { return _target }
    public function set target(v:Vehicle):void { _target = v }
    public function get target2():Vehicle { return _target2 }
    public function set target2(v:Vehicle):void { _target2 = v }
    public function set offset(o:Point):void { _offset = o }
    
    public function set summingMethod(sm:String):void {
        SteeringBehaviorsSummingMethod.checkValid(sm)
        _summingMethod = sm
    }
    
    public function setPath(path:Array, closed:Boolean=false):void {
        _path = path
        _pathClosed = closed
        _pathIdx = 0
    }
    
    public function calculate():Point {
        if(_summingMethod == SteeringBehaviorsSummingMethod.WEIGHTED_AVERAGE){
            return calculateWeightedSum()
        }else if(_summingMethod == SteeringBehaviorsSummingMethod.PRIORITIZED){
            return calculatePrioritized()
        }else if(_summingMethod == SteeringBehaviorsSummingMethod.DITHERED){
            return calculateDithered()
        }
        return new Point
    }
    
    private function calculateWeightedSum():Point {
        var vel:Point = new Point
        
        if(separationOn || alignmentOn || cohesionOn){
            var neighbors:Array = _vehicle.world.getNeighbors(_vehicle)
            if(neighbors.length > 0){
                if(separationOn) vel = vel.add(separation(neighbors))
                if(alignmentOn) vel = vel.add(alignment(neighbors))
                if(cohesionOn) vel = vel.add(cohesion(neighbors))
            }
        }
        
        if(wanderOn) vel = vel.add(wander())
        if(obstacleAvoidanceOn) vel = vel.add(obstacleAvoidance(_vehicle.world.obstacles))
        if(wallAvoidanceOn) vel = vel.add(wallAvoidance(_vehicle.world.walls))
        if(followPathOn) vel = vel.add(followPath())
        
        if(!target) return vel
        if(seekOn) vel = vel.add(seek(target.position))
        if(fleeOn) vel = vel.add(flee(target.position))
        if(arriveOn) vel = vel.add(arrive(target.position, 0.3))
        if(pursuitOn) vel = vel.add(pursuit(target))
        if(evadeOn) vel = vel.add(evade(target))
        if(hideOn) vel = vel.add(hide(target, _vehicle.world.vehicles))
        if(offsetPursuitOn && _offset) vel = vel.add(offsetPursuit(target, _offset))
        
        if(!target2) return vel
        if(interposeOn) vel = vel.add(interpose(target, target2))
        
        if(vel.length > _vehicle.maxForce) vel.normalize(_vehicle.maxForce)
        return vel
    }
    
    private function calculatePrioritized():Point {
        var sum:Point = new Point
        
        if(wallAvoidanceOn){
            if(!accumulate(wallAvoidance(_vehicle.world.walls))) return sum
        }
        if(obstacleAvoidanceOn){
            if(!accumulate(obstacleAvoidance(_vehicle.world.obstacles))) return sum
        }
        if(evadeOn){
            if(!accumulate(evade(target))) return sum
        }
        if(fleeOn){
            if(!accumulate(flee(target.position))) return sum
        }
        if(separationOn || alignmentOn || cohesionOn){
            var neighbors:Array = _vehicle.world.getNeighbors(_vehicle)
            if(neighbors.length > 0){
                if(!accumulate(separation(neighbors))) return sum
                if(!accumulate(alignment(neighbors))) return sum
                if(!accumulate(cohesion(neighbors))) return sum
            }
        }
        if(seekOn){
            if(!accumulate(seek(target.position))) return sum
        }
        if(arriveOn){
            if(!accumulate(arrive(target.position, 0.1))) return sum
        }
        if(wanderOn){
            if(!accumulate(wander())) return sum
        }
        if(pursuitOn){
            if(!accumulate(pursuit(target))) return sum
        }
        if(offsetPursuitOn){
            if(!accumulate(offsetPursuit(target, _offset))) return sum
        }
        if(interposeOn){
            if(!accumulate(interpose(target, target2))) return sum
        }
        if(hideOn){
            if(!accumulate(hide(target, _vehicle.world.vehicles))) return sum
        }
        if(followPathOn){
            if(!accumulate(followPath())) return sum
        }
        
        if(sum.length > _vehicle.maxForce) sum.normalize(_vehicle.maxForce)        
        return sum
        
        function accumulate(force:Point, scale:Number=1):Boolean {
            force.x *= scale
            force.y *= scale
            var currMag:Number = sum.length
            var rest:Number = _vehicle.maxForce - currMag
            if(rest <= 0) return false
            var candMag:Number = force.length
            if(candMag > rest) force.normalize(rest)
            sum = sum.add(force)
            return true
        }
    }
    private function calculateDithered():Point {
        return new Point
    }
    
    private function seek(target:Point):Point {
        var desired:Point = target.subtract(_vehicle.position)
        desired.normalize(_vehicle.maxSpeed)
        return desired.subtract(_vehicle.velocity)
    }
    
    private function flee(target:Point):Point {
        var panicDistance:Number = 100
        var desired:Point = _vehicle.position.subtract(target)
        if(desired.length > panicDistance) return new Point
        desired.normalize(_vehicle.maxSpeed)
        return desired.subtract(_vehicle.velocity)
    }
    
    private function arrive(target:Point, deceleration:Number):Point {
        var toTarget:Point = target.subtract(_vehicle.position)
        var dist:Number = toTarget.length
        if(dist > 0){
            var speed:Number = dist / deceleration
            speed = Math.min(speed, _vehicle.maxSpeed)
            var desired:Point = toTarget.clone()
            desired.normalize(desired.length * speed/dist)
            return desired.subtract(_vehicle.velocity)
        }
        return new Point
    }
    
    private function pursuit(evader:Vehicle):Point {
        var toEvader:Point = evader.position.subtract(_vehicle.position)
        var relativeHeading:Number = dotProduct(_vehicle.heading, evader.heading)
        if(dotProduct(toEvader, _vehicle.heading) > 0 && relativeHeading < -0.95){
            return seek(evader.position)
        }
        var lookAheadTime:Number = toEvader.length / (_vehicle.maxSpeed + evader.speed)
        return seek(evader.position.add(scalarMult(evader.velocity, lookAheadTime)))
    }
    
    private function evade(pursuer:Vehicle):Point {
        var toPursuer:Point = pursuer.position.subtract(_vehicle.position)
        var lookAheadTime:Number = toPursuer.length / (_vehicle.maxSpeed + pursuer.speed)
        return flee(pursuer.position.add(scalarMult(pursuer.velocity, lookAheadTime)))
    }
    
    private var _wanderTarget:Point = new Point
    private var _wanderRadius:Number = 50
    private var _wanderDistance:Number = 400
    private var _wanderJitter:Number = 50
    private function wander():Point {
        var rand1:Number = (Math.random() - .5) * 2
        var rand2:Number = (Math.random() - .5) * 2
        _wanderTarget = _wanderTarget.add(new Point(rand1*_wanderJitter, rand2*_wanderJitter))
        _wanderTarget.normalize(_wanderRadius)
        var targetLocal:Point = _wanderTarget.add(new Point(_wanderDistance, 0))
        var targetWorld:Point = _vehicle.localToGlobal(targetLocal)
        return targetWorld.subtract(_vehicle.position)
    }
    
    private var minDetectionBoxLength:Number = 60
    private function obstacleAvoidance(obstacles:Array):Point {
        var boxLength:Number = minDetectionBoxLength * (1 + _vehicle.speed/_vehicle.maxSpeed)
        var closest:Entity, closestDist:Number = Infinity, closestLocal:Point
        var ob:Entity, obLocal:Point
        for(var i:int=0; i<obstacles.length; i++){
            ob = obstacles[i]
            if(ob == _vehicle) continue
            
            var to:Point = ob.position.subtract(_vehicle.position)
            var r:Number = to.length + _vehicle.radius
            if(r > boxLength) continue
            
            obLocal = _vehicle.globalToLocal(ob.position)
            
            if(obLocal.x < 0) continue
            var exRadius:Number = ob.radius + _vehicle.radius
            
            if(Math.abs(obLocal.y) >= exRadius) continue
            
            var cx:Number = obLocal.x, cy:Number = obLocal.y
            var sqrtPart:Number = Math.sqrt(exRadius * exRadius - cy * cy)
            var ip:Number = cx - sqrtPart
            if(ip <= 0) ip = cx + sqrtPart
            if(ip < closestDist){
                closestDist = ip
                closest = ob
                closestLocal = obLocal
            }
        }
        if(!closest) return new Point
        
        var steering:Point = new Point
        var mult:Number = 1 + (boxLength - closestLocal.x) / boxLength
        steering.y = (closest.radius - closestLocal.y) * mult
        
        var brake:Number = .2
        steering.x = (closest.radius - closestLocal.x) * brake
        
        return _vehicle.localToGlobal(steering)
    }
    
    private function wallAvoidance(walls:Array):Point {
        var closest:Point, closestWall:Wall
        var closestDist:Number = Infinity
        var dist:Number, ip:Point
        var w:Wall
        
        var vp:Point = _vehicle.position
        var feeler:Point = scalarMult(_vehicle.velocity, 10), feelerHit:Point
        var feelers:Array = [vp.add(feeler), vp.add(perpVector(feeler)), vp.add(invert(perpVector(feeler)))]
        for(var j:int=0; j<feelers.length; j++){
            feeler = feelers[j]
            for(var i:int=0; i<walls.length; i++){
                w = walls[i]
                ip = w.lineIntersection(vp, feeler)
                if(!ip) continue
                dist = ip.subtract(vp).length
                if(dist < closestDist){
                    closest = ip
                    closestDist = dist
                    closestWall = w
                    feelerHit = feeler
                }
            }
        }
        if(!closest) return new Point
        
        var overshoot:Point = feelerHit.subtract(closest)
        var steering:Point = closestWall.normal.clone()
        steering.normalize(overshoot.length)
        if(dotProduct(overshoot, closestWall.normal) > 0){
            steering.x = -steering.x
            steering.y = -steering.y
        }
        return steering
    }
    
    private function interpose(A:Vehicle, B:Vehicle):Point {
        var mid:Point = A.position.add(B.position)
        mid.x /= 2 ; mid.y /= 2
        
        var dt:Number = _vehicle.position.subtract(mid).length / _vehicle.maxSpeed
        var Apos:Point = A.position.add(scalarMult(A.velocity, dt))
        var Bpos:Point = B.position.add(scalarMult(B.velocity, dt))
        mid = Apos.add(Bpos)
        mid.x /= 2 ; mid.y /= 2
        
        return arrive(mid, 0.1)
    }
    
    private function hidingPosition(obstacle:Point, obstacleRadius:Number, target:Point):Point {
        var distAway:Number = obstacleRadius + 30 // 30 = distance from boundary
        var toOb:Point = obstacle.subtract(target)
        toOb.normalize(1)
        return scalarMult(toOb, distAway).add(obstacle)
    }
    private function hide(target:Vehicle, obstacles:Array):Point {
        var dist:Number, bestDist:Number = Infinity
        var spot:Point, bestSpot:Point
        
        var ob:Entity, targetPos:Point = target.position
        for(var i:int=0; i<obstacles.length; i++){
            ob = obstacles[i]
            if(ob == _vehicle || ob == target) continue
            spot = hidingPosition(ob.position, ob.radius, targetPos)
            dist = spot.subtract(targetPos).length
            if(dist < bestDist){
                bestDist = dist
                bestSpot = spot
            }
        }
        if(!bestSpot) return evade(target)
        return arrive(bestSpot, 0.1)
    }
    
    private function followPath():Point {
        if(!_path) return new Point
        var dist:Number = _path[_pathIdx].subtract(_vehicle.position).length
        if(dist < 0.1){
            _pathIdx ++
            if(_pathIdx == _path.length){
                if(_pathClosed) _pathIdx = 0
                else{
                    _path = null
                    return new Point
                }
            }
        }
        if(_pathIdx == _path.length - 1) return arrive(_path[_pathIdx], 0.5)
        return seek(_path[_pathIdx])
    }
    
    private function offsetPursuit(leader:Vehicle, offset:Point):Point {
        var worldOffset:Point = leader.localToGlobal(offset)
        var toOffset:Point = worldOffset.subtract(_vehicle.position)
        var lookAhead:Number = toOffset.length / (_vehicle.maxSpeed + leader.speed)
        return arrive(worldOffset.add(scalarMult(leader.velocity, lookAhead)), 0.1)
    }
    
    private function separation(neighbors:Array):Point {
        var steering:Point = new Point
        var toAgent:Point
        for each(var n:Vehicle in neighbors){
            toAgent = _vehicle.position.subtract(n.position)
            toAgent.normalize(1 / toAgent.length)
            steering = steering.add(toAgent)
        }
        return steering
    }
    private function alignment(neighbors:Array):Point {
        var avg:Point = new Point
        for each(var n:Vehicle in neighbors){
            avg = avg.add(n.heading)
        }
        avg.x /= neighbors.length
        avg.y /= neighbors.length
        return avg.subtract(_vehicle.heading)
    }
    private function cohesion(neighbors:Array):Point {
        var center:Point = new Point
        for each(var n:Vehicle in neighbors){
            center = center.add(n.position)
        }
        center.x /= neighbors.length
        center.y /= neighbors.length
        return seek(center)
    }
    
}

function dotProduct(a:Point, b:Point):Number {
    return a.x*b.x + a.y*b.y
}
function scalarMult(v:Point, s:Number):Point {
    return new Point(v.x*s, v.y*s)
}
function perpVector(v:Point):Point {
    return new Point(-v.y, v.x)
}
function invert(v:Point):Point {
    return new Point(-v.x, -v.y)
}