/**
* Copyright arumajirou ( http://wonderfl.net/user/arumajirou )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/4aSs
*/
// forked from arumajirou's quadrant tree test
package {
import flash.display.Sprite;
import flash.display.Graphics;
import flash.geom.*;
import flash.events.*;
import flash.text.*;
[SWF( width="1024", height="1024", frameRate="60" )]
public class FlashTest extends Sprite {
public static var tex : TextField = new TextField();
private var space : cSpaceManager;
private var test : testObject = new testObject();
public function FlashTest() {
// write as3 code here..
var tf : TextFormat = new TextFormat();
tf.color = 0x01;
tf.size = 24;
tex.defaultTextFormat = tf;
tex.autoSize = TextFieldAutoSize.LEFT;
addChild( tex );
addChild( test );
test.x = parent.stage.stageWidth / 2;
test.y = parent.stage.stageHeight / 2;
space = new cSpaceManager( new Rectangle(0,0,stage.stageWidth,stage.stageHeight) );
parent.addEventListener( MouseEvent.MOUSE_MOVE, this.release );
}
public function release( e : MouseEvent ) : void
{
space.init();
test.x = e.stageX;
test.y = e.stageY;
// tex.text = Math.round( test.x ) + ":" + Math.round( test.y ) + "\n";
var id : int = space.registObject( test ).id;
// tex.text = ( id + "\n" );
drawArea( space.getTree() );
}
public function drawArea( tree : Vector.<cSpace> ) : void
{
const g : Graphics = graphics;
g.clear();
for( var i : int = 0 ; i <= cSpaceManager.DEPTH ; i++ )
{
var sx : int = 0;
var sy : int = 0;
var ofs : int = Math.floor( ( Math.pow( 4, i ) - 1 ) / 3 );
var par : int = Math.floor( Math.pow( 4, i ) );
for( var j : int = 0 ; j < par ; j++ )
{
var len : int = tree[ ofs + j ].object.length;
if( len > 0 )
{
// tex.appendText( "Lev:" + i + " :num:" + j + ":len:" + len + "\n" );
for( var m : int = 0 ; m <= i ; m++ )
{
var n : int = ( j >> ( ( i - m ) * 2 ) ) & 3;
// tex.appendText( "n:" + n + "/:" + j + ":m:" + m + ":" );
var parlen : int = stage.stageWidth / Math.pow( 2, m );
sx += ((n&1) * parlen);
sy += (((n>>1)&1) * parlen);
drawRect( sx, sy, parlen, parlen );
}
// tex.appendText( "\n" );
}
}
}
/*
for each( var k : cSpace in tree )
{
tex.appendText( k.object.length + ":" );
}
*/
}
private function drawRect( sx : int, sy : int, w : int, h : int ) : void
{
w -= 1;h -= 1;
const g : Graphics = graphics;
g.lineStyle( 1, 0x00aaff );
g.moveTo( sx, sy );
g.lineTo( sx + w, sy );
g.lineTo( sx + w, sy + h );
g.lineTo( sx, sy + h );
g.lineTo( sx, sy );
}
}
}
import flash.display.*;
import flash.geom.*;
interface iCharacter
{
function process() : void;
function draw( v : Vector3D ) : void;
function getBoundingRect() : Rectangle;
}
class testObject extends Sprite implements iCharacter
{
public const R : int = 4;
public function testObject()
{
const g : Graphics = graphics;
g.clear();
g.lineStyle( 1, 0x0000ff );
g.drawCircle( 0, 0, R );
}
public function process() : void
{
}
public function draw( v : Vector3D ) : void
{
}
public function getBoundingRect() : Rectangle
{
return new Rectangle( x - Math.round(R / 2), y - Math.round(R / 2), R, R );
}
}
class cSpace
{
private var parent : cSpace;
private var child : Vector.<cSpace>;
public var object : Vector.<iCharacter>;
public function cSpace( p : cSpace = null )
{
parent = p;
child = new Vector.<cSpace>();
object = new Vector.<iCharacter>();
init();
}
public function addChild( c : cSpace ) : void
{
child.push( c );
}
public function addObject( o : iCharacter ) : void
{
object.push( o );
}
public function init() : void
{
// child.splice( 0, child.length );
object.splice( 0, object.length );
}
}
class cSpaceManager
{
// public static const DEPTH : int = 7;
public static const DEPTH : int = 6;
public static const PARTITION_NUMBER : int = Math.pow( 2, DEPTH );
private var tree : Vector.<cSpace>;
private var space : Rectangle;
private var baseLength : int;
public function cSpaceManager( s : Rectangle = null )
{
space = s;
baseLength = space.width / PARTITION_NUMBER;
tree = new Vector.<cSpace>();
var max : int = Math.pow( 4, DEPTH + 1 ) / 3;
for( var i : int = 0 ; i < max ; i++ )
{
tree.push( new cSpace() );
}
init();
}
public function init() : void
{
var max : int = Math.pow( 4, DEPTH + 1 ) / 3;
for( var i : int = 0 ; i < max ; i++ )
{
tree[ i ].init();
}
}
private function shift( n : int ) : int
{
n = ( n | n << 8 ) & 0x00ff00ff;
n = ( n | n << 4 ) & 0x0f0f0f0f;
n = ( n | n << 2 ) & 0x33333333;
return ( n | n << 1 ) & 0x55555555;
}
private function getPartitionedID( xx : int, yy : int ) : int
{
return ( shift( xx ) | ( shift( yy ) << 1 ) );
}
public function getSpaceID( lx : int, ly : int, rx : int, ry : int ) : Object
{
var idb : int = getPartitionedID( rx, ry );
var id : int = getPartitionedID( lx, ly ) ^ idb;
var result : int = 0;
while( id > 0 )
{
result += 2;
id >>= 2;
}
return { "level" : DEPTH - Math.floor(result / 2), "id" : ( idb >> result ) };
}
public function registObject( o : iCharacter ) : Object
{
const r : Rectangle = o.getBoundingRect();
var re : Object = getSpaceID( r.left / baseLength, r.top / baseLength, r.right / baseLength, r.bottom / baseLength );
tree[ Math.floor(( Math.pow( 4, re.level ) - 1 ) / 3) + re.id ].addObject( o );
// FlashTest.tex.appendText("depth:" + re.level + ":id:" + re.id + "\n");
// FlashTest.tex.appendText("index:" + Math.floor(( Math.pow( 4, re.level ) - 1 ) / 3 + re.id) + "\n");
return re;
}
public function getTree() : Vector.<cSpace>
{
return tree;
}
}