AABB range queries test (no fancy datastructures, just cache optimized)

AABBNoTreeTest.hx

package;


import ds.AABB;
import flash.display.Graphics;
import flash.display.Sprite;
import flash.display.Stage;
import flash.events.Event;
import flash.events.KeyboardEvent;
import flash.events.MouseEvent;
import flash.filters.GlowFilter;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.Lib;
import flash.system.System;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
import flash.text.TextFormatAlign;
import haxe.Timer;
import openfl.display.FPS;


class AABBNoTreeTest extends Sprite {

	inline static var LEFT:Int = 37;
	inline static var UP:Int = 38;
	inline static var RIGHT:Int = 39;
	inline static var DOWN:Int = 40;

	var TEXT_COLOR:Int = 0xFFFFFFFF;
	var TEXT_FONT:String = "_typewriter";
	var TEXT_SIZE:Float = 12;
	var TEXT_OUTLINE:GlowFilter = new GlowFilter(0xFF000000, 1, 2, 2, 6);

	var QUERY_COLOR:Int = 0xFFCC00;
	var NORMAL_RESULTS_COLOR:Int = 0xFF0000;
	var RESULTS_ALPHA:Float = .5;
	var ENTITIES_ALPHA:Float = .1;
	var SPEED = 6;
	
	var stageWidth:Int;
	var stageHeight:Int;
	var fps:FPS;
	
	var text:TextField;
	var g:Graphics;
	var normalResults:Array<Entity> = [];
	var normalQueryInfo: { time:Float, found:Int } = null;
	
	var maxId:Int = 0;
	var unusedIds:Array<Int> = [];
	var entities:Array<Entity> = [];
	
	var startPoint:Point = new Point();
	var endPoint:Point = new Point();
	var queryRect:Rectangle = new Rectangle();
	var strictMode:Bool = true;
	var animMode:Bool = false;
	var dragging:Bool = false;

	var redraw:Bool = true;
	var overlay:Graphics;

	
	public function new () {
		super ();

		stageWidth = stage.stageWidth;
		stageHeight = stage.stageHeight;
		
		g = graphics;
		var overlaySprite:Sprite;
		stage.addChild(overlaySprite = new Sprite());
		overlay = overlaySprite.graphics;
		
		// insert random rects
		for (i in 0...3) {
			var o = getRandomObj();
			wrapInsert(o.rect.x, o.rect.y, o.rect.width, o.rect.height, o);
		}
		
		// insert random points
		for (i in 0...3) {
			var o = getRandomObj();
			o.rect.width = 0;
			o.rect.height = 0;
			wrapInsert(o.rect.x, o.rect.y, o.rect.width, o.rect.height, o);
		}
		
		overlaySprite.addChild(text = getTextField("", stageWidth - 230, 5));
		overlaySprite.addChild(fps = new FPS(5, 5, 0xFFFFFF));
		fps.visible = false;
		
		stage.addEventListener(MouseEvent.MOUSE_MOVE, onMouseMove);
		stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
		stage.addEventListener(MouseEvent.MOUSE_UP, onMouseUp);
		stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown);
		stage.addEventListener(Event.ENTER_FRAME, onEnterFrame);
		//quit();
	}
	
	/** Gets the next available id for a node, fecthing it from the list of unused ones if available. */
	private function getNextId():Int 
	{
		var newId = unusedIds.length > 0 && unusedIds[unusedIds.length - 1] < maxId ? unusedIds.pop() : maxId++;
		return newId;
	}

	public function wrapInsert(x:Float, y:Float, width:Float, height:Float, data:Entity):Void 
	{
		var id = getNextId();
		data.id = id;
		entities[id] = data;
	}
	
	public function wrapRemove(leafId:Int):Void 
	{		
		entities[leafId] = null;
		unusedIds.push(leafId);
	}
	
	public function drawRects(g:Graphics, list:Array<Entity>, color:Int, alpha:Float):Void 
	{
		for (e in list) {
			if (e == null) continue;
			var r = e.rect;
			g.lineStyle(1, color, alpha);
			if (r.width < .5 && r.height < .5) {
				g.drawCircle(r.x, r.y, 2);
			} else {
				//g.beginFill(color, alpha);
				g.drawRect(r.x, r.y, r.width, r.height);
				//g.endFill();
			}
		}
	}
	
	public function clamp(value:Int, min:Int, max:Int):Int 
	{
		if (value < min) return min;
		else if (value > max) return max;
		return value;
	}
	
	public function getRandomObj():Entity
	{
		var r = new AABB(Math.random() * stageWidth * .5 + 25, Math.random() * stageHeight * .6 + 25, Math.random() * 100 + 10, Math.random() * 100 + 10);
		var p = new Point(Math.random() * 2 - 1, Math.random() * 2 - 1);
		p.normalize(4);
		var obj = new Entity(p, r);
		return obj;
	}

	
	public function onKeyDown(e:KeyboardEvent):Void 
	{
		if (e.keyCode == 27) quit();
		
		if (e.keyCode == "C".code) {		// clear tree
			entities = [];
			redraw = true;
		} else if (e.keyCode == RIGHT) {		// add random leaf/leaves
			var count = e.shiftKey ? 10 : 1;
			for (i in 0...count) {
				var o = getRandomObj();
				if (Math.random() < .5) {	// 50% chance of inserting a point (rect with size 0)
					o.rect.width = 0;
					o.rect.height = 0;
				}
				wrapInsert(o.rect.x, o.rect.y, o.rect.width, o.rect.height, o);
			}
			redraw = true;
		} else if (e.keyCode == LEFT) {		// remove random leaf
			var leafId = entities.length - 1;
			while (leafId >= 0 && entities[leafId] == null) {
				leafId--;
			}
			if (leafId >= 0) {
				wrapRemove(leafId);
				redraw = true;
			}
		} else if (e.keyCode == "S".code) {		// toggle strictMode
			strictMode = !strictMode;
			redraw = true;
		} else if (e.keyCode == "A".code) {		// toggle animMode
			animMode = !animMode;
			redraw = true;
		}
	}
	
	public function onEnterFrame(_):Void 
	{
		if (animMode) {
			redraw = true;
			animate();
		}
		
		if (redraw) {
			query();
			g.clear();
			drawRects(g, entities, 0xFFFFFF, .1);
		}
		redraw = false;
		
		overlay.clear();
		overlay.lineStyle(2, QUERY_COLOR, .9);
		if (queryRect.width < .5 && queryRect.height < .5) {
			overlay.drawCircle(queryRect.x, queryRect.y, 2);
		} else {
			overlay.drawRect(queryRect.x, queryRect.y, queryRect.width, queryRect.height);
		}
		
		if (normalResults.length > 0) drawRects(overlay, normalResults, NORMAL_RESULTS_COLOR, RESULTS_ALPHA);
		
		updateText();
	}
	
	public function animate():Void 
	{
		for (e in entities) {
			if (e == null) continue;
			var aabb = e.rect;
			aabb.x += e.dir.x;
			aabb.y += e.dir.y;
			var center = new Point(aabb.getCenterX(), aabb.getCenterY());
			if (center.x < 0) {
				aabb.x = -center.x;
				e.dir.x *= -1;
			} else if (center.x > stageWidth) {
				aabb.x = stageWidth - aabb.width * .5;
				e.dir.x *= -1;
			}
			if (center.y < 0) {
				aabb.y = -center.y;
				e.dir.y *= -1;
			} else if (center.y > stageHeight) {
				aabb.y = stageHeight - aabb.height * .5;
				e.dir.y *= -1;
			}
		}
	}
	
	public function updateText():Void 
	{
		var mem = System.totalMemory / 1024 / 1024;
		text.text = 
		#if debug
			"MEM: " + toFixed(mem) + " MB     FPS: " + fps.currentFPS + "/" + stage.frameRate + "\n" +
		#end
			"\n        mouse-drag to\n       perform queries\n\n\n" +
			"entities         : " + Lambda.count(entities, function (e:Entity):Bool return e != null) + "\n\n" +
			"[S] strictMode   : " + (strictMode ? "ON" : "OFF") + "\n" +
			"[A] animMode     : " + (animMode ? "ON" : "OFF") + "\n\n" +
			"[RIGHT/LEFT] add/remove entity\n" + 
			"[C]          clear\n\n";
			
		if (normalQueryInfo != null) {
			text.text +=
				"query time       : " + toFixed(normalQueryInfo.time, 4) + "s\n" +
				"entities found   : " + normalQueryInfo.found;
		}
	}

	public function toFixed(f:Float, decimals:Int = 2):String 
	{
		var pow = Math.pow(10, decimals);
		return '${Std.int(f * pow) / pow}';
	}
	
	public function onMouseMove(e:MouseEvent):Void 
	{
		if (dragging) {
			endPoint.x = e.stageX;
			endPoint.y = e.stageY;
			
			queryRect.setTo(startPoint.x, startPoint.y, endPoint.x - startPoint.x, endPoint.y - startPoint.y);
			if (endPoint.x < startPoint.x) {
				queryRect.width = startPoint.x - endPoint.x;
				queryRect.x = endPoint.x;
			}
			if (endPoint.y < startPoint.y) {
				queryRect.height = startPoint.y - endPoint.y;
				queryRect.y = endPoint.y;
			}
			redraw = true;
		}
	}
	
	public function onMouseDown(e:MouseEvent):Void 
	{
		startPoint.x = e.stageX;
		startPoint.y = e.stageY;
		endPoint.x = e.stageX;
		endPoint.y = e.stageY;
		
		queryRect.x = startPoint.x;
		queryRect.y = startPoint.y;
		queryRect.width = 0;
		queryRect.height = 0;
		
		dragging = true;
	}
	
	public function onMouseUp(e:MouseEvent):Void 
	{
		dragging = false;
		redraw = true;
	}
	
	public function query():Void 
	{
		// normal
		normalResults = [];
		var startTime = Timer.stamp();
		var queryAABB = new AABB(queryRect.x, queryRect.y, queryRect.width, queryRect.height);
		for (e in entities) {
			if (e == null) continue;
			var aabb = e.rect;
			if (strictMode) {
				if (queryAABB.contains(aabb)) normalResults.push(e);
			} else {
				if (queryAABB.getIntersection(aabb) != null) normalResults.push(e);
			}
		}
		normalQueryInfo = { time:Timer.stamp() - startTime, found:normalResults.length };
	}
	
	public function getTextField(text:String = "", x:Float, y:Float):TextField
	{
		var tf:TextField = new TextField();
		var fmt:TextFormat = new TextFormat(TEXT_FONT, null, TEXT_COLOR);
		tf.autoSize = TextFieldAutoSize.LEFT;
		fmt.align = TextFormatAlign.LEFT;
		fmt.size = TEXT_SIZE;
		tf.defaultTextFormat = fmt;
		tf.selectable = false;
		tf.x = x;
		tf.y = y;
		tf.filters = [TEXT_OUTLINE];
		tf.text = text;
		return tf;
	}
	
	public function quit():Void 
	{
		#if (flash || html5)
			System.exit(1);
		#else
			Sys.exit(1);
		#end
	}

}

@:publicFields
class Entity
{
	var id:Int;
	var dir:Point;
	var rect:AABB;
	
	function new(dir:Point, rect:AABB):Void 
	{
		this.dir = dir;
		this.rect = rect;
		this.id = -1;
	}
}