forked from: forked from: Peak

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

// forked from shaktool's forked from: Peak
package
{
	import flash.display.*;
	import flash.events.*;
	import flash.filters.*;
	import flash.geom.*;
	import flash.text.*;
	import flash.utils.*;
	
	[ SWF( width=465, height=465, frameRate=20, backgroundColor=0x000000 ) ]
	public class Peak extends Sprite
	{
		private const WIDTH: Number = 465;
		private const HEIGHT: Number = 465;
		
		private var nodes: Array = [];
		private var highs: Array = [];
		private var lows: Array = [];
		private var rootNode: Octree;
		private var stillLooking: Boolean = false;
		
		public function Peak()
		{
			var i: int;
			for ( i = 0; i < 600; i++ )
			{
				nodes.push( new Octree() );
			}
			for ( i = 0; i < 60; i++ )
			{
				highs.push( new Region( 1 ) );
			}
			for ( i = 0; i < 600; i++ )
			{
				lows.push( new Region( 0 ) );
			}
			
			rootNode = takeNode();
			rootNode.region = takeRegion( 0 );
			rootNode.min = [ 0, 0 ];
			rootNode.length = WIDTH;
			rootNode.octave = 0;
			
			stage.addEventListener( Event.ENTER_FRAME, generate );
			//stage.addEventListener( MouseEvent.MOUSE_MOVE, generate );
			stage.addEventListener( MouseEvent.CLICK, getStatus );
			generate();
		}
		
		public function takeNode(): Octree
		{
			if ( nodes.length == 0 ) throw new Error( "no more nodes" );
			var node: Octree = nodes.pop();
			if ( node.alive ) throw new Error( "node is alive" );
			node.alive = true;
			return node;
		}
		
		public function takeRegion( res: int ): Region
		{
			var stack: Array = [ lows, highs ][ res ];
			if ( stack.length == 0 ) throw new Error( "no more regions" );
			var region: Region = stack.pop();
			if ( region.alive ) throw new Error( "region is alive" );
			region.alive = true;
			return region;
		}
		
		public function releaseNode( node: Octree ): void
		{
			if ( !node.alive || node.children != null || node.parent != null || node.region != null ) throw new Error( "node not clean" );
			node.children = null;
			node.region = null;
			node.parent = null;
			node.alive = false;
			nodes.push( node );
		}
		
		public function releaseRegion( region: Region ): void
		{
			if ( !region.alive ) throw new Error( "node still alive" );
			region.alive = false;
			var stack: Array = [ lows, highs ][ region.res ];
			stack.push( region );
		}
		
		public function getStatus( event: Event = null ): void
		{
			throw new Error( nodes.length + ", " + lows.length + ", " + highs.length );
		}
		
		public function generate( event: Event = null ): void
		{
			graphics.clear();
			graphics.lineStyle( 0 );
			stillLooking = true;
			lookForChange();
			draw( rootNode );
		}
		
		public function cleanNode( node: Octree ): void
		{
			var i: int;
			var j: int;
			for ( i = 0; i < 2; i++ )
			{
				for ( j = 0; j < 2; j++ )
				{
					var child: Octree = node.children[ i ][ j ];
					if ( child.region ) releaseRegion( child.region );
					child.region = null;
					if ( child.children ) cleanNode( child );
					releaseNode( child );
				}
			}
			node.children = null;
		}
		
		public function lookForChange(): void
		{
			var queue1: Array = [ rootNode ];
			var queue2: Array = [];
			var splitNode: Octree = null;
			var joinNode: Octree = null;
			var splitDistance: Number = 999999999;
			var joinDistance: Number;
			
			while ( true )
			{
				if ( queue1.length == 0 ) break;
				
				for each ( var node: Octree in queue1 )
				{
					if ( node == null ) throw new Error( "null node" );
					if ( node.region == null && node.children == null ) throw new Error( "null properties" );
					if ( node.region != null && node.children != null ) throw new Error( "conflicting properties" );
					if ( node.min == null ) throw new Error( "null min" );
					
					var halfLength: Number = node.length * 0.5;
					var center: Array = [ node.min[ 0 ] + halfLength, node.min[ 1 ] + halfLength ];
					var offset: Array = [ mouseX - center[ 0 ], mouseY - center[ 1 ] ];
					var distance: Number = Math.sqrt( offset[ 0 ] * offset[ 0 ] + offset[ 1 ] * offset[ 1 ] );
					
					var i: int;
					var j: int;
					
					distance /= node.length;
					var priority: Number = distance * distance * distance + node.octave * 0.5;
					
					if ( priority < 27.0 )
					{
						// wanna split
						if ( node.region != null && node.region.res != 1 )
						{
							if ( splitNode == null || ( splitDistance > priority ) )
							{
								splitNode = node;
								splitDistance = priority;
							}
						}
					}
					else
					{
						// wanna join
						if ( node.children != null || node.region.res == 1 )
						{
							if ( joinNode == null || joinDistance < priority )
							{
								joinNode = node;
								joinDistance = priority;
							}
						}
					}
					
					if ( node.children != null )
					{
						for ( i = 0; i < 2; i++ )
						{
							for ( j = 0; j < 2; j++ )
							{
								queue2.push( node.children[ i ][ j ] );
							}
						}
					}
				}
				
				if ( joinNode != null )
				{
					if ( joinNode.children != null )
					{
						cleanNode( joinNode );
						joinNode.region = takeRegion( 0 );
						return;
					}
					if ( joinNode.region != null && joinNode.region.res == 1 )
					{
						releaseRegion( joinNode.region );
						joinNode.region = takeRegion( 0 );
						return;
					}
				}
				
				queue1 = queue2;
				queue2 = [];
			}
			
			if ( splitNode != null )
			{
				releaseRegion( splitNode.region );
				splitNode.region = null;
				if ( splitNode.octave == 6 )
				{
					splitNode.region = takeRegion( 1 );
				}
				else
				{
					splitNode.split();
					for ( i = 0; i < 2; i++ )
					{
						for ( j = 0; j < 2; j++ )
						{
							var child: Octree = takeNode();
							if ( child == null ) throw new Error( "child is null" );
							child.min = [ splitNode.min[ 0 ] + splitNode.length * 0.5 *  i, splitNode.min[ 1 ] + splitNode.length * 0.5 *  j ];
							child.length = splitNode.length * 0.5;
							child.region = takeRegion( 0 );
							child.octave = splitNode.octave + 1;
							splitNode.children[ i ][ j ] = child;
						}
					}
				}
			}
		}
		
		public function draw( node: Octree ): void
		{
			if ( node.region )
			{
				var color: uint = ( node.octave + node.region.res ) * 30;
				graphics.beginFill( ( color << 16 ) + ( color << 8 ) + ( color << 0 ) );
				graphics.drawRect( node.min[ 0 ], node.min[ 1 ], node.length, node.length );
				graphics.endFill();
			}
			else
			{
				for ( var i: int = 0; i < 2; i++ )
				{
					for ( var j: int = 0; j < 2; j++ )
					{
						draw( node.children[ i ][ j ] );
					}
				}
			}
		}
	}
}

class Octree
{
	public var min: Array;
	public var length: Number;
	public var octave: int;
	public var children: Array = null;
	public var region: Region = null;
	public var parent: Octree = null;
	public var alive: Boolean = false;
	public function split(): void { children = [ [ null, null ], [ null, null ] ]; }
}

class Region
{
	public var res: int;
	public var alive: Boolean = false;
	public function Region( res: int ) { this.res = res; }
}