Collision detection using QuadTree in AS3

Question

Ok. I managed to make and use QuadTree for my collision Detection alghorithm and it works just fine. I have my enemies and put them in the QuadTree, than retrieve the candidates that could possibly collide with my hero. That is hitTestObject() many agains one.

The problem I reached is how to test fastly whether some of the enmies collide with my hero's bullets. Roughly I have 4-6 bullets on the stage at same time. In this case I have hitTstObject 4-6 bullets against many enemy objects, which in turns gives me for cycle in for cycle so even using quad tree after a while things start to lag on the stage :)

I used this tutorial quadtree in java to develop m alghorithm but it works fine only in the above case. What should I do in this circumstance? Use another algorithm for many agains many or ?

Roughly this is the code

 bulletsQuadTree.clear();
 for (var bIndex:uint; bIndex < allEnemies.length; bIndex += 1 )        
 {
  bulletsQuadTree.insert(allEnemies[bIndex]);
 }

for (var bc:uint = 0; bc < bullets.length; bc += 1 )
{
    var enemiesCollideBullets:Array = new Array();
    bulletsQuadTree.retrieve(enemiesCollideBullets, bullets[bc]);

    for (var dc:uint = 0; dc < enemiesCollideBullets.length; dc += 1 )
    {
        if (enemiesCollideBullets[dc].hitTestObject(bullets[bc]))
        {
            enemiesCollideBullets[dc].destroy();
            enemiesCollideBullets.splice(dc, 1);
        }
    }
}

So this happens on each frame which are many operations per frame :(

Each bullet is treated as a hero and an array of enemies is returned for each bullet that could possibly collide with.

Answer 1

If you want to improve the performance of this loop, change this line:

enemiesCollideBullets[dc].hitTestObject(bullets[bc]);

The actionscript hit test functions are slow. A much better approach for bullets is to check for the distance.

var distanceSquared:number = (bullet.width/2 + object.width/2) * (bullet.width/2 + object.width/2);
if((bullet.x - object.x)* (bullet.x - object.x) + (bullet.y - object.y)* (bullet.y - object.y) < distanceSquared) {
// its a hit!