Point A to Point B: part 1

Welcome to my very first post! What is this blog about, you ask? Let's get right down to it.

I'm a composer, who wants to make a game, or at least a demo. I'll talk more about what my idea is with each post, but for now we'll focus on the basics, since that's about all my programming skills can handle.

I'm using javascript as my language for now, but we'll see where this goes.

The game will be a top-down strategy/RPG style game. In order to manage a team of characters, they will have to have some kind of individual movement AI. For nearly all the actions, the character will have to move from point A to point B on his/her own. Attacking is the most fun action, so here we go...

Action one: Attack.

You choose a "Hero", then choose an enemy. The Hero walks over, body-slams the sh*t out of the enemy and walks back to his home position. Easy, right? But what if there is something in his way?

When I first researched solutions for this simple problem (oh, how naive I was) I first encountered information about path-finding, and A* algorithms. Once my head stopped spinning, I stumbled across a much more elegant solution: vector fields.

To simplify the explanation, imagine each obstacle has anti-gravity. The closer you get to it, the more it "pushes" you away. This is nice, because as your movement vector pushes you in one direction, the force of the "anti-gravity" pushes you away, and eventually around said obstacle.

To illustrate, the green ball is moving to the right. As it approaches the obstacle, the obstacle exerts its "force" and pushes the ball away. As you can see in the exquisite to-scale drawing, the force is stronger based on proximity.


Great! Problem solved. NEXT!

Or not. Here's the issue (the first of many). The anti-gravity is exerted in all directions equally, which so as the green ball moves past the orange one (to the point where the orange ball is no longer an obstacle) he is STILL affected by its anti-gravity. Now, why would you want to avoid an obstacle you've already passed?

Well, some programmers have solved this by using a complex "look-ahead" to see just how in-the-way the obstacle is. But I found a much simpler solution. Math-geeks, prepare yourselves!

Cardioids

I heart cardioids. No, seriously. If you don't know what one is, plug this equation into a graphing calculator.
Imagine that normal anti-gravity is calculated in a circle (i.e. objects in all directions are treated equally) so why not use a cardioid? This allows us to calculate 100% anti-gravity on objects directly in our path, and scale to 0% for objects behind us. And multiplying the cardioid by a power increases the effect. These images show the circle vs. cardioid being applied to the moving player, aimed in the direction of the target.

"Shytor" is moving to the left. "M" is at 45 degree angle to his motion, so is sort of in the way. The colored lines represent the forces exerted on him due to anti-gravity. His resulting vector pushes him down a little, to avoid M.

Here, "Shytor" and "D" are moving toward their target, "Ultros". The colored lines protruding from Shytor represent the forces of anti-gravity exerted on him (I'll explain those in detail later). Both M and D are in his way (a little). D has nothing directly in his way, so there are no colored lines (very tiny ones). Without the cardioid, D would be more affected by M, but due to the scaling, the effect is negligible.

The result is a change in overall path. Notice the "circle" path continues to push away from orange ball, even after it is passed. Whereas, the cardioid, straightens out once it is clear. The perfectly to-scale anti-gravity vector lines (in red) show how the effect diminishes greatly as the green ball passes its target.

So that's the explanation. SHOW ME THE CODE!

This code would run each frame, and can be looped if there are multiple obstacles present. The "orange" object is the obstacle.

function moveObject(green,orange){
//first get the normalized vector of green's target 
//(i.e. which direction is he trying to move)
//this returns vector object with vx and vy properties
    var vector = normVec(green.pos,green.target.pos);
//convert the vector to an angle in radians, 0 is East
    var angle = Math.atan2(vector.vy,vector.vx);

//get the distance to the obstacle
    d = getDistance(green.pos,orange.pos);

//calculate the anti-gravity magnitude based on distance
//it's not really the mass, but the "width" of the obstacle
    var mass = (green.radius + orange.radius);
//multiply by "personal space" constant for math fudging
//this adjusts the strength of the anti-gravity
    var mass = mass * mass * 2;
//the magnitude of the effect as distance approaches the "mass" is 1 
    var mag = mass / (d * d);

//find the angle between the two objects (as an "x, y" vector)
//multiplying by the magnitude
    var v = normVec(orange.pos,green.pos,mag);
//convert the angle to radians
    var vTheta = Math.atan2(v.vy,v.vx);
//invert it to get the "anti-gravity force"
    var obsAngle = 0;
    if (vTheta >= 0) obsAngle = vTheta - Math.PI;
    else if (vTheta < 0) obsAngle = vTheta + Math.PI;

//get the difference between angles to the target and the obstacle
    delta = obsAngle - angle;
//invert if more than 180 deg, this keeps the value in a usable range
        if (delta > Math.PI) delta = delta - (2*Math.PI);
//invert if less than -180
        if (delta < -Math.PI) delta = delta + (2*Math.PI);

//make a unit cardioid, if the difference in angles is 0 effect is 1
//if angle is 180 effect is 0
    r = (1 + Math.cos(delta))/2;
//multiply the magnitude exponentially (optional)
    r = r * r * r;

//add the calculated anti-gravity force to the original vector
vector.vx += v.vx*r;
vector.vy += v.vy*r;

//after all anti-gravity is calculated then move the character
vector = normalize(vector);//normalize the new movement vector
//then call the movement function of the character
//basically multiply the direction vector by speed
//and move to the next frame
green.move(vector);
}

//helper functions
        function getDistance(a,b){
//provided the x.y position of two objects, find the distance
//cx and cy represent the center
                var x = b.cx - a.cx;
                var y = b.cy - a.cy;
                var d = Math.sqrt((x*x)+(y*y));
                return d;
        }
        function normVec(a,b,mag){
//find the direction vector between two points, multiplied by mag
                    if (!mag) mag = 1;
                var x = b.cx - a.cx;
                var y = b.cy - a.cy;
                var d = Math.sqrt((x*x)+(y*y));
                var v = {"vx": x / d * mag,"vy": y / d * mag};
                return v;
        }
        function normalize(v){
//normalizes a vector object to 1
                var d = Math.sqrt((v.vx*v.vx)+(v.vy*v.vy));
                var v = {"vx": v.vx / d,"vy": v.vy / d};
                return v;
        } 

Stay tuned for part 2 where I solve the next problem: choosing left or right!

The tile artwork is from "Wilderness Tile Set" art by Daniel Cook (Lostgarden.com). Thanks to him for making some great free artwork available!

Trevor Gast

Some say he’s half man half fish, others say he’s more of a seventy/thirty split. Either way he’s a fishy bastard.

0 comments: