About Collision detection alghorithms in AS3

Question

Ok. So there are several methods to implement Collision detection like R-trees, Quadtrees, BSP trees Recursive Dimensional Clustering (RDC). Or maybe more.

My problem is that I have about 6-8 enemies on stage, some of them moving some of them static and also I have the Hero who is shooting with three types of missiles at same time. So I get about 70-100 objects on stage at a time.

My question is, which algorithm to use for this type of problem, and which is the common practice? Also which is the most efficient?

I was thinking of implementing Quad trees but I read that thy can be slow, or I am wrong?

ps: Can I use Octal trees or they are strictly for 3D?

Answer 1

One, you're making a flash game. Two, your ammunition explodes. You don't need precision collision detection. If your methods are concise, 100+ objects will not impede you.

Loop through your enemies and check for distance. If the distance is less than X, explode, loop through the enemies again, using distance for relative damage.

// class variables
var baseDamage:Number = 50;
var splashMinDistance:Number = 72;
var splashMaxDistance:Number = 144;

var enemies:Array = // array of enemies
var ammunition:Array = // array of live ammo

function checkForContact() {
    var enemy:Enemy;
    var ammo:Ammo;

    var i:int, ic:int = enemies.length;
    var j:int, jc:int = ammo.length;

    for (i=0; i<ic; i++) {
        enemy = enemies[i];
            if (enemy == NULL) continue;
        for (j=0; j<jc; j++) {
            ammo = ammunition[j];
                    if (ammo == NULL) continue;
            if (contact(ammo, enemy)) {
                explode(ammo);
                ammo = NULL;
            }
        }
    }

    // sort ammo to remove nulls now that we're past
    // the time-sensitive part
}

function contact(ammo:Ammo, enemy:Enemy):Boolean {
    return (distance(ammo, enemy) < splashMinDistance);
}

function explode(ammo:Ammo) {
    var enemy:Enemy;
    var distance:Number;

    var i:int, ic:int = enemies.length;

    for (i=0; i<ic; i++) {
        enemy = enemies[i];
        distance = clamp(distance(ammo, enemy), splashMinDistance, Math.INT_MAX);
        if (distance > splashMaxDistance) continue;
        damageRatio = ((distance-splashMinDistance) / (splashMaxDistance-splashMinDistance));
        enemy.health -= baseDamage * damageRatio;
        if (enemy.health < 0) kill(enemy);
    }
}


function distance (o:Object, o2:Object) {
    var dx=o.x-o2.x;
    var dy=o.y-o2.y;
    return Math.sqrt(dx*dx+dy*dy);
}

Finally, you don't have to check for collision every frame. Again, you're making a flash game. Manage your expectations.

Answer 2

I guess I may not be that well educated to understand how spatial indexing data structures solve the problem of the intersection of two polygons. Perhaps you were going to check every polygon in a region around some other polygon for intersection?

But one solution I propose is the use of Minkowski Summing. Especially if all of your hitboxes are convex. You can Minkowski sum the hitbox of your missiles to the enemy hitboxes and reduce the problem to a point membership test of the missile to each enemy, though if your missile/enemies rotate, this becomes a more difficult problem.

Hopefully this is enough information to be helpful.

Answer 3

If you only have say, ten enemies and a hundred bullets or so I doubt any complex spatial structure will benefit you all that much. Checking every bullet against every enemy amounts to a thousand checks, and the gains in performance compared to maintaining a more complex structure is in my opinion too small.

Depending on how fast your game is, you could get away with checking for collisions every other frame (or even less often) instead of every frame. That'll give you a nice 100% performance boost on your collision detection.

I recommend simply doing this:

for each(var enemy:Enemy in _enemies){
    for each(var bullet:Bullet in _bullets){
         if(bullet.x > enemy.x - enemy.width / 2 && 
            bullet.x < enemy.x + enemy.width / 2 &&
            bullet.y > enemy.y - enemy.height / 2 && 
            bullet.y < enemy.y + enemy.height / 2){
                trace("collision!");
         }
     }
}