Hi. In this tutorial I will show you how to use QuadTree implementation in AS3 to detect whether a Hero object on the stage colide with many Enemy objects.
I asume you have installed FlashDevelop and created AS3 blank project called CollisionDetection in folder with same name.
Firstly I reused a code from
other site but mine code is implemented fully in AS3 and is fitted to suit my needs i.e checking if a Hero object collides with many Enemies. First I recommend read the tutorial from the site before implementing it in AS3. Roughly QuadTree is a data structure that has 4 and only 4 child nodes. It is the same principal as binary tree except it has two child nodes.
How do we use the QuadTree structure to detect collision detection???
Well we can create arrays of objects and use "for loops" to cycle trough each object and check for collision, but the problem that arises is that we might have many operations per frame (in games) so that might crash flash or not work at all on slower computers. So we use a QuadTree to separate the 2D space in 4 subparts and check if there is a collision between objects in a smaller area.
There is no need to check objects that are on the different sides of the stage.
During the separation we check if objects are fitted in quadrant. If there are many objects in a given quadrant we separate that quadrant into again four subquadrants and check again.
First create three folders uder the root of the FlashDevelop project. Call them CollisionDetectionPkg, EnemyPkg, and HeroPkg.
In CollisionDetectionPkg add new blank AS3 class and name it QuadTree.as.
In EnemyPkg add new AS3 class and name it Enemy.as
In HeroPkg follows the same thing, add blank class Hero.as
Our Main.as class will be manager for adding multiple enemies and also do all the stuff for checking and retrieving objects that might collide with Hero object.
QuadTree.as
package CollisionDetectionPkg
{
import flash.display.DisplayObject;
import flash.display.Sprite;
import flash.geom.Rectangle;
public class QuadTree
{
private var _stage:DisplayObject;
private var MAX_OBJECTS:int = 10;
private var MAX_LEVELS:int = 5;
private var level:int;
private var objects:Array; // sprites that are put on the stage
private var bounds:Rectangle;
private var nodes:Array; //array of QuadTree objects
/*
* Constructor
*/
public function QuadTree(pLevel:int, pBounds:Rectangle, stage:DisplayObject)
{
_stage = stage;
level = pLevel;
objects = new Array();
bounds = pBounds;
nodes = new Array(4);
}
/*
* Clears the quadtree
*/
public function clear():void
{
for (var i:int = 0; i < objects.length; i += 1)
{
if (objects[i] != null)
{
objects.splice(i, 1);
}
}
for (var j:int = 0; j < nodes.length; j += 1)
{
if (nodes[j] != null)
{
nodes.splice(j, 1);
}
}
}
/*
* Splits the node into 4 subnodes
*/
private function split():void
{
var subWidth:int = int(bounds.width / 2);
var subHeight:int = int(bounds.height / 2);
var x:int = int(bounds.x);
var y:int = int(bounds.y);
nodes[0] = new QuadTree(level + 1, new Rectangle(x + subWidth, y, subWidth, subHeight), _stage);
nodes[1] = new QuadTree(level + 1, new Rectangle(x, y, subWidth, subHeight), _stage);
nodes[2] = new QuadTree(level + 1, new Rectangle(x, y + subHeight, subWidth, subHeight), _stage);
nodes[3] = new QuadTree(level + 1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight), _stage);
}
/*
* Determine which node the object belongs to. -1 means
* object cannot completely fit within a child node and is part
* of the parent node
*/
private function getIndex(pRect:Rectangle):int
{
var index:int = -1;
var verticalMidpoint:Number = bounds.x + (bounds.width / 2);
var horizontalMidpoint:Number = bounds.y + (bounds.height / 2);
// Object can completely fit within the top quadrants
var topQuadrant:Boolean = (pRect.y < horizontalMidpoint && pRect.y + pRect.height < horizontalMidpoint);
// Object can completely fit within the bottom quadrants
var bottomQuadrant:Boolean = (pRect.y > horizontalMidpoint);
// Object can completely fit within the left quadrants
if (pRect.x < verticalMidpoint && pRect.x + pRect.width < verticalMidpoint)
{
if (topQuadrant)
{
index = 1;
}
else if (bottomQuadrant)
{
index = 2;
}
}
// Object can completely fit within the right quadrants
else if (pRect.x > verticalMidpoint)
{
if (topQuadrant)
{
index = 0;
}
else if (bottomQuadrant)
{
index = 3;
}
}
return index;
}
/*
* Insert the object into the quadtree. If the node
* exceeds the capacity, it will split and add all
* objects to their corresponding nodes.
*/
public function insert(pRect:Sprite):void
{
if (nodes[0] != null)
{
var index:int = getIndex(pRect.getRect(_stage));
if (index != -1 && nodes[index] != null)
{
nodes[index].insert(pRect);
return;
}
}
objects.push(pRect);
if (objects.length > MAX_OBJECTS && level < MAX_LEVELS)
{
if (nodes[0] == null)
{
split();
}
var i:int = 0;
while (i < objects.length)
{
var index1:int = getIndex(objects[i].getRect(_stage));
if (index1 != -1 && nodes[index1] != null)
{
nodes[index1].insert(objects[i]);
objects.splice(i, 1);
}
else
{
i += 1;
}
}
}
}
/*
* Return all objects that could collide with the given object
*/
public function retrieve(returnObjects:Array, pRect:Sprite):Array
{
var index:int = getIndex(pRect.getRect(_stage));
if (nodes[0] != null && index != -1 && nodes[index] != null)
{
nodes[index].retrieve(returnObjects, pRect);
}
for (var i:int = 0; i < objects.length; i += 1)
{
if (objects[i] != null)
{
returnObjects.push(objects[i]);
}
}
return returnObjects;
}
}
}-----------------------------------------------------------------------------------------------------------------
Enemy.as
our Enemy is 50x50 white rectangle with red border
package EnemyPkg
{
import flash.display.Sprite;
import flash.events.Event;
/**
* ...
* @author SpinnerBox
*/
public class Enemy extends Sprite
{
private var unitSprite:Sprite;
private var _main:Main;
public function Enemy(main:Main)
{
_main = main;
unitSprite = new Sprite();
unitSprite.graphics.lineStyle(2, 0xff0000, 1);
unitSprite.graphics.beginFill(0xffffff, 1);
unitSprite.graphics.drawRect(-25, -25, 50, 50);
unitSprite.graphics.endFill();
addChild(unitSprite);
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}
public function destroy():void
{
removeEventListener(Event.ENTER_FRAME, onEnterFrame);
_main.stage.removeChild(this);
}
private function onEnterFrame(e:Event):void
{
this.x -= 2;
}
}
}--------------------------------------------------------------------------------------------------------
Hero.as
Our hero is 60x60 white rectangle with green border
package HeroPkg
{
import flash.display.Sprite;
/**
* ...
* @author SpinnerBox
*/
public class Hero extends Sprite
{
private var unitSprite:Sprite;
public function Hero()
{
unitSprite = new Sprite();
unitSprite.graphics.lineStyle(2, 0x00ff00, 1);
unitSprite.graphics.beginFill(0xffffff, 1);
unitSprite.graphics.drawRect(-30, -30, 60, 60);
unitSprite.graphics.endFill();
addChild(unitSprite);
}
}
}---------------------------------------------------------------------------------------------------------
and Main.as
In main we add ENTER_FRAME listener to add new enemies and to check collisions using the QuadTree constructed in the constructor.
Note: We can use hitTestObject function only on DisplayObject or Sprite types of objects in AS3 so in insert() and retrieve() we send Sprite type of object instead of Rectangle and then we get the bounding rectangle by using getRect() function and sending main.stage object to it like this
objects[i].getRect(_stage);Remeber that
_stage = main.stage. Once that our Hero rectangle has collided with enemy the enemy object gets destroyed.
package
{
import CollisionDetectionPkg.QuadTree;
import EnemyPkg.Enemy;
import flash.display.Sprite;
import flash.events.Event;
import flash.display.StageScaleMode;
import flash.geom.Rectangle;
import HeroPkg.Hero;
/**
* ...
* @author SpinnerBox
*/
public class Main extends Sprite
{
private var enemyArray:Array;
private var enemy:Enemy;
private var hero:Hero;
private var unitCounter:uint = 0;
private var unitRate:uint = 40;
private var quadTree:QuadTree;
public function Main():void
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e:Event = null):void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
// entry point
stage.scaleMode = StageScaleMode.NO_SCALE;
quadTree = new QuadTree(0, new Rectangle(0, 0, 700, 550), this.stage);
enemyArray = new Array();
hero = new Hero();
hero.x = 100;
hero.y = 200;
stage.addChild(hero);
addEventListener(Event.ENTER_FRAME, onEnterFrame);
}
private function onEnterFrame(e:Event = null):void
{
hero.x = stage.mouseX;
hero.y = stage.mouseY;
if (unitCounter >= unitRate)
{
for (var i:uint = 1; i <= 5; i += 1 )
{
var enemy:Enemy = new Enemy(this);
enemy.x = 750;
enemy.y = i*100;
stage.addChild(enemy);
enemyArray.push(enemy);
}
unitCounter = 0;
}
else
{
unitCounter += 1;
}
quadTree.clear();
for each( var newEnemy:Enemy in enemyArray)
{
quadTree.insert(newEnemy);
}
var returnObjects:Array = new Array();
quadTree.retrieve(returnObjects, hero);
for (var k:int = 0; k < returnObjects.length; k += 1)
{
// Run collision detection algorithm between enemies and hero
if (returnObjects[k].hitTestObject(hero))
{
if (returnObjects[k].parent != null)
{
returnObjects[k].destroy();
returnObjects.splice(k, 1);
}
}
}
// clear memory from returned objects
for (var m:int = 0; m < returnObjects.length; m += 1)
{
if (returnObjects[m] != null)
{
returnObjects.splice(m, 1);
}
}
// clear enemies if they reach x = -100
for (var j:uint = 0; j <= enemyArray.length; j += 1 )
{
if (enemyArray[j] != null && enemyArray[j].x < -100)
{
enemyArray[j].destroy();
enemyArray.splice(j, 1);
}
}
}
}
} Final result: When green square touches red square they get destroyed.
I tried the compiled swf file on old Intel Celeron machine and it works still fairlly smooth.
Again thanks to
TutsPlus and
Steven Lambert for his awesome tutorial. Cheers :)
