Accidents Do Happen

7:57 PM collision detection , javascript 0 Comments

So after four great posts about how to avoid collisions, now it's time to talk about collision detection.

Our characters are now successfully moving from point A to point B and usually avoiding each other. Just like in real life though, when it's crowded, people bump into each other. This looks like a job for Collision Detection!

The concept is pretty simple: in my sample, each entity is described by a circle, or more practically, a center point and a radius. We merely determine if they overlap or touch. Solved.

UNLESS you also want to know the point of collision and the force of the collision. Then you need some fancy vector math. Here's a great link to explain the details. I'll break it down into the important steps though.

Step 1: Did the objects collide?

This is easy math. We take the sum of the radii of each object (since they are all treated like circles). If the distance between their centers is less than sum of the radii, the objects have collided. Since the Math.sqrt() function is somewhat costly, it's faster to skip the square root when determining the distance and use the square fo the sum of the radii.

Step 2: What was the collision point?

Some more simple math. The collision occurs at a point directly between the centers of the two circles. DUH. If the objects have an equal radius it will be exactly between them. If they are different sizes though, we just use the radii to create a ratio*. If (x1,y1) and (x2,y2) are the centers then the collision point (x,y) can be calculated thus.

 And because this is true:
...point 1 and 2 can be reversed.

*Note: Since we only check for collisions each frame, this method does not account for the fact that the true time of collision actually happened between frames. Thus, the "true" collision point is usually different. However, for the sake of simplicity, this method is more practical.

Step 3: How hard did they hit?

Now we get some fancy math. When two objects collide, they exert force on each other and "bounce" like pool balls. Newton was a smart guy. This is the code to calculate everything. It returns the new velocity for the "guy" passed to the function. You can add that to his movement vector to simulate bounce, or apply it as the new velocity if it is free-floating in space.

function findCollisions(guy){
    var velx = 0;
    var vely = 0;
    var collided = false;
    //loop through all the other objects
    for (var c in dict){
        if (guy === c) continue; //skip yourself
        if (!dict[c].collisions) continue;//skip if collisions are off
        var haloSq = dict[guy].halo.cr + dict[c].halo.cr;
        haloSq *= haloSq; //use the square to save rooting...
        var dist = getDistanceSq(dict[guy].pos,dict[c].pos);
        if (dist.ds > haloSq) continue; //they did not collide
        else if (dist.ds <= haloSq) { //they collided
            //find the collision point
            var collisionPointX = ((dict[guy].pos.cx * dict[c].halo.cr) + (dict[c].pos.cx * dict[guy].halo.cr)) / (dict[guy].halo.cr + dict[c].halo.cr);
            var collisionPointY = ((dict[guy].pos.cy * dict[c].halo.cr) + (dict[c].pos.cy * dict[guy].halo.cr)) / (dict[guy].halo.cr + dict[c].halo.cr);
            //find the TOTAL velocity of the collision
            var xVelocity = dict[c].vel.vx - dict[guy].vel.vx;
            var yVelocity = dict[c].vel.vy - dict[guy].vel.vy;
            //use the dot product to calculate the "exit" velocity
            var dotProduct = -dist.x * xVelocity + -dist.y * yVelocity;
            if (dotProduct > 0){
                collided = true;
                var collisionScale = dotProduct / dist.ds;
                var xCollision = dist.x * collisionScale;
                var yCollision = dist.y * collisionScale;
                //The Collision vector is the speed difference projected on the Dist vector,
                //thus it is the component of the speed difference needed for the collision.
                var combinedMass = dict[guy].mass + dict[c].mass;
                var collisionWeightA = 2 * dict[c].mass / combinedMass;
                //var collisionWeightB = 2 * dict[guy].mass / combinedMass;
                velx -= collisionWeightA * xCollision;//new vel for dict[guy]
                vely -= collisionWeightA * yCollision;
                //new vel for activeGuyDict.Allies[c]...not necessary since it will be calculated on another pass
                //B.xVel -= collisionWeightB * xCollision;
                //B.yVel -= collisionWeightB * yCollision;
                //draw a green dot at the collision point
                ctx.fillStyle = "green";
                ctx.fillRect(collisionPointX-2,collisionPointY-2,4,4);
            }
        }
    }
    if (collided) return {nvx:velx,nvy:vely};//return the new vector to change after all collisions have been detected and calculated
    else return null;
}

This is a fully functioning script that demonstrates my own collision avoidance/detection algorithm at work. It isn't the fastest algorithm, but it functions well enough with 32 entities on the screen. For the purposes of my own demo, there will probably be no more than 12 characters on the screen at once, so this will do fine.

Instructions:

Press any key to load the entities.
Press R to organize them into a circle.
Press B to have them randomly switch places.
Press T to split them into 3 groups that will move to a target on the opposite side of the circle.
Press G to split them into two groups. They will organize into block formations.
Press B to have them exchange sides.
Press P to organize them into two vertical lines.
Press B to have them invert the line and switch sides.

The entities turn red after a collision, until they reach their target.