Point A to Point B: part 2

8:36 PM collision avoidance , javascript 0 Comments

Okay. So we solved the issue of optimizing our anti-gravity obstacle avoidance algorithm by using a cardioid. What problem could possibly be next?

Well, how about, what happens if the obstacle is straight ahead?

Choosing Left or Right

It is possible, and even likely, that the obstacle will be directly in the path of the character. So if anti-gravity of the obstacle is pushing in the exact opposite direction of the movement vector, what happens when you get too close to the obstacle?
The forces eventually cancel out, or it's possible that the anti-gravity will exceed the movement vector. Normally the obstacle is outside the direct path, and the character gets nudged more and more as he moves closer, eventually rolling around. But with perfect math in a digital game, THIS is possible.


The solution is simple to you or me... just pick a direction and go around, duh?! But computers aren't so clever... they need to be told what to choose.

In this perfect scenario, the angle of anti-gravity is exactly 180 from the angle of the path. Ideally, this is when we want to adjust our path the most, since there is something REALLY in our way. So, let's just adjust the angle of anti-gravity by 90 degrees!
The red line is the initial anti-gravity vector, the blue line is the new adjusted version.

Done. Solved! Wait, but now we are making a huge adjustment. As soon as the obstacle is not directly in our path (probably after one frame) we'll only be making the same small adjustment... so let's scale the adjustment. If the angle of anti-gravity is off by 180 degrees, we adjust a lot, if it is off by 90 or less, we don't adjust.
Here's the code:

//get the difference between the path vector and the obstacle
//invert it as necessary get a result between -180 and 180
delta = vTheta - angle;
if (delta > Math.PI) delta = delta - (2*Math.PI);
if (delta < -Math.PI) delta = delta + (2*Math.PI);
            
    if (delta != 0) {
        //this creates an inverted quarter ellipse 
        //that we use to scale the adjustment smoothly
 if (Math.abs(delta)>=Math.PI/2)var r2 = 1 - Math.sqrt(1 - Math.pow(((2 * Math.abs(delta)) - Math.PI) / Math.PI,2));
 else {var r2 = 0;}// if delta > 90 degrees

        var theta = Math.PI*r*r2/2;
        //one method of correcting the sign if the angles are negative
        var dir = Math.abs(delta)/delta;
        var aTheta = vTheta - (theta * dir);
    } else {
        var aTheta = vTheta;
    }

//this calculates the vector of the new blue line
//as seen in the diagrams above
av.vx = Math.cos(aTheta)*mag;
av.vy = Math.sin(aTheta)*mag;
//then add these to the movement vector! 

The result is a nice fluid movement around the object. It even makes the path react a bit sooner, so your character isn't waiting to the last minute to make a reasonable adjustment. In this code, it chooses left (d*mn hippy!).


Done. Solved! Or not. Stay tuned for part 3, where I discuss another scenario we must overcome. What if there are 2 obstacles perfectly evenly spaced directly in our path?