.png)
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.
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!
0 comments: