(illustrative) automatic navigation generation

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

// forked from wrotenodoc's automatic navigation generation
package {
    
    import flash.events.Event
    import flash.geom.Point
    import flash.geom.Rectangle
    import flash.display.Sprite
    
    public class FlashTest extends Sprite {
        
        private var step:int = 10
        private var cell0:Cell
        private var obstacles:Array = []
        
        public function FlashTest() {
            // write as3 code here..
            cell0 = new Cell(new Rectangle(50, 50, 300, 300))
            render(cell0)
            stage.addEventListener("mouseDown", onMouseDown)
        }
        
        private function onMouseDown(e:Event):void {
            cell0 = new Cell(new Rectangle(50, 50, 300, 300))
            obstacles.push(new Rectangle(50+Math.random()*300, 50+Math.random()*300, 20+Math.random()*50, 20+Math.random()*50))
            for each(var ob:Rectangle in obstacles) cell0.divide(ob)
            
            var leaves:Array = cell0.collectLeaves()
            findNeighbor(leaves)
            
            graphics.clear()
            render(cell0)
            renderLink(leaves)
            
            step --
            if(step < 0){
                stage.removeEventListener("mouseDown", onMouseDown)
            }
        }
        
        private function renderLink(leaves:Array):void {
            for each(var L:Cell in leaves){
                for each(var M:Cell in L.neighbors){
                    graphics.lineStyle(2, int(Math.random() * 0xff) << 16, 1)
                    graphics.moveTo(L.shape.x + L.shape.width/2, L.shape.y + L.shape.height/2)
                    graphics.lineTo(M.shape.x + M.shape.width/2, M.shape.y + M.shape.height/2)
                }
            }
        }
        
        public function render(cell:Cell):void {
            if(cell.isLeaf){
                graphics.lineStyle(1, 0x0, 1)
                graphics.beginFill(Math.random() * 0xff, 0.3)
                graphics.drawRect(cell.shape.x, cell.shape.y, cell.shape.width, cell.shape.height)
                graphics.endFill()
            }else{
                for each(var sub:Cell in cell.subs) render(sub)
            }
        }
        
        private function findNeighbor(leaves:Array):void {
            var n:int = leaves.length
            var a:Rectangle, b:Rectangle
            for(var i:int=0; i<n; i++){
                for(var j:int=i+1; j<n; j++){
                    a = leaves[i].shape.clone()
                    b = leaves[j].shape.clone()
                    var edge:Boolean = (near(a.left,b.right) || near(a.right,b.left)) && (near(a.top,b.bottom) || near(a.bottom,b.top))
                    a.inflate(1, 1)
                    b.inflate(1, 1)
                    if(a.intersects(b) && !edge){
                        leaves[i].neighbors.push(leaves[j])
                        leaves[j].neighbors.push(leaves[i])
                    }
                }
            }
            function near(x1:Number, x2:Number):Boolean { return Math.abs(x2-x1) < 0.05 }
        }
        
    }
    
}

////////////////////////
// outside of package //
////////////////////////
import flash.geom.Rectangle

// node class
class Cell {
    
    public var shape:Rectangle
    public var neighbors:Array = []
    public var subs:Array
    
    public function Cell(shape:Rectangle = null) {
        this.shape = shape
    }
    
    public function divide(obstacle:Rectangle):void {
        if(shape.intersects(obstacle) == false) return
        if(isLeaf){
            subs = []
            push(shape.left, shape.top, obstacle.left, obstacle.top)
            push(obstacle.left, shape.top, obstacle.right, obstacle.top)
            push(obstacle.right, shape.top, shape.right, obstacle.top)
            push(shape.left, obstacle.top, obstacle.left, obstacle.bottom)
            push(obstacle.right, obstacle.top, shape.right, obstacle.bottom)
            push(shape.left, obstacle.bottom, obstacle.left, shape.bottom)
            push(obstacle.left, obstacle.bottom, obstacle.right, shape.bottom)
            push(obstacle.right, obstacle.bottom, shape.right, shape.bottom)
        }else{
            for(var i:int=0; i<subs.length; i++){
                if(obstacle.containsRect(subs[i].shape)){
                    subs.splice(i, 1)
                    i--
                }else subs[i].divide(obstacle)
            }
        }
        function push(x1:Number,y1:Number, x2:Number,y2:Number):Cell {
            if(x2 > x1 && y2 > y1){
                x1 = Math.max(x1, shape.left)
                y1 = Math.max(y1, shape.top)
                x2 = Math.min(x2, shape.right)
                y2 = Math.min(y2, shape.bottom)
                var cell:Cell = new Cell(new Rectangle(x1, y1, x2-x1, y2-y1))
                subs.push(cell)
                return cell
            }
            return null
        }
    }
    
    public function collectLeaves():Array {
        var Q:Array = [this]
        var leaves:Array = []
        while(Q.length){
            var C:Cell = Q.shift()
            if(C.isLeaf) leaves.push(C)
            else for each(var child:Cell in C.subs) Q.push(child)
        }
        return leaves
    }
    
    public function get isLeaf():Boolean { return subs == null }
    
}