Pathfinding by Radnen
From Spheriki
So, you might want to have pathfinding in your videogame but don't know where to start? In this tutorial I'll show you exactly how to make a pathfinding tutorial in Sphere.
It requires:
- Sphere - You having read: Star Pathfinding for Beginners - Some formal logic / CS skill
This is a more advanced tutorial since my methodologies differ from the article above. This one assumes you are pathing over an NxN field where N is in the set of all Integers.
Disclaimer: I do not yet cover Obstructions. This will be done later as an extension of this project! We are only traversing an NxN field as so you can get the pathing concept down first.
Contents |
Node Setup
A pathfinding system works exactly like a linked list. You have a data structure that contains some data, and points to another node next in line (the node being of the same data structure).
// A basic node example:
function PathNode(x, y)
{
this.x = 0; // relative x position
this.y = 0; // relative y position
this.f = 0; // g + h added
this.g = 0; // distance from start
this.h = 0; // distance to finish
this.next; // next node in path
}
/* A Perfect Memberwise Copy */
PathNode.prototype.copy = function(other)
{
this.x = other.x;
this.y = other.y;
this.f = other.f;
this.g = other.g;
this.h = other.h;
this.next = other.next;
}
x, y in my version of A* are fields that represent some integer that is diagonal to or orthogonal to some parent node. This numbers is relative by 1 unit. A node to the north would have a y value 1 higher than some parent.
f, g, h are standard informative components that define a pathing node.
G = distance from the previous node to this node. G is in the set of {10, 14}.
- G is 10 on all orthogonal directions. - G is 14 on all diagonal directions.
H = distance from the node to the end position. H is in the set of all Integers.
- found by running a heuristic.
F = final distance, that is the initial G + H, this is the most important number.
I also introduce a memberwise copy. This is so that I can create a clone of a node that is needed to advance us one step further.
Pathing Setup
Current node and Adjacent Nodes.
What does it mean to have an NxN field of nodes? A computer can't allocate an infinite field, so what are we to do?
My solution is to only hold info that is important. The two most important pieces are the current node you are on and it's surrounding nodes.
var Pathfinder = ({
adjacent: [new PathNode(), new PathNode(), new PathNode(),
new PathNode(), null , new PathNode(),
new PathNode(), new PathNode(), new PathNode()],
start: {x: 0, y: 0},
end : {x: 0, y: 0},
To setup our initial node we need a function to do this:
findStart: function() {
n = new PathNode();
n.x = this.start.x;
n.y = this.start.y;
n.f = n.h = n.g = 0;
return n;
},
findStart tells the pathfinder to create a new node as our start and to fill in it's initial data. We supply a start x and y. The f, g, h are set to zero because the distance to itself is zero and we don't need to concern ourselves with any directional data since we've no idea where to step next. It then returns this node.
Now we need to find all of the adjacent nodes to this node. The field as you recall is NxN, so we can't store all nodes in this field, so we store only those that are adjacent to the starting node (even if it were at 0, 0 since negatives are included too).
/* Fill out temporary adjacent array with known moves: */
findAdjacent: function(parent) {
// figure out relative positions:
this.adjacent[0].y = this.adjacent[1].y = this.adjacent[2].y = parent.y - 1;
this.adjacent[3].y = this.adjacent[5].y = parent.y;
this.adjacent[6].y = this.adjacent[7].y = this.adjacent[8].y = parent.y + 1;
this.adjacent[0].x = this.adjacent[3].x = this.adjacent[6].x = parent.x - 1;
this.adjacent[1].x = this.adjacent[7].x = parent.x;
this.adjacent[2].x = this.adjacent[5].x = this.adjacent[8].x = parent.x + 1;
Here we are given a parent (in the first case our initial position). Now we are to fill in the adjacent nodes with relative numbers.
Those that exist to the left are nodes 0, 3 6 Those that exist at the top are nodes 0, 1, 2 That exist to the right: 2, 5, 8 and the bottom: 6, 7, 8 Same x: 1, 7 Same y: 3, 5
After filling in the relative directions, (I know its not too pretty) you've got yourself a "minigrid".
Next we step through this minigrid and apply some information:
var i = 9;
while (i--) {
if (i == 4) continue; // this is the parent so we skip it.
// figure out herustics:
if (i % 2 == 0) this.adjacent[i].g = parent.g+14; // diagonals cost more
else this.adjacent[i].g = parent.g+10; // orthogonals less.
this.findHeuristic(this.adjacent[i]);
}
},
I use "%2" as a method to find which are orthogonal and not. Orthogonal nodes only exist in the array as nodes positioned on odd numbers, so only odd numbered nodes get 10 added. The rest get 14. Why? Because moving diagonal in this case would take more time even though you may travel more distance. So this is needed to counteract that trade off.
Notice I'm always re-utilizing this adjacency array. I never allocate more than those 8 objects in the array. This is why I introduced the copy method onto the node. I need it so we don't overwrite nodes we need, we are to copy them instead. You'll see me do this later.
findHeuristic is explained below:
/* this is applied after g is added to some node 'n'*/
findHeuristic: function(n) {
n.h = 10*(Math.abs(n.x-this.end.x) + Math.abs(n.y-this.end.y));
n.f = n.g + n.h;
},
This uses the Manhattan distance algorithm. It's actually why we use 10 and 14 for "g". h would end up being some multiple of these as well. The Manhattan distance algorithm is:
10*(|current_y - end_y| + |current_x - end_x|)
This is basically a distance formula like Pythagoras Theorem but it's not as complex and favors straight paths rather than angular paths. See the heuristic appendix for more info on heuristic algorithms. We multiply by 10 as an integer rounding effect because we don't want out "g" of 14 to be 1.4 since its a messier number to work with.
So after we've filled in our adjacent nodes, we must step through to the next closest node!
/* takes a step closer to destination;
and adds to a chain of steps */
step: function(parent) {
// look for smalles 'f' value:
var i = 9;
var f = this.adjacent[0].f;
var index = 0;
while (i--) {
if (i == 4) continue;
if (this.adjacent[i].f < f) {
f = this.adjacent[i].f;
index = i;
}
}
this.adjacent[index].next = parent;
var n = new PathNode();
n.copy(this.adjacent[index]);
return n;
},
This function takes a parent node (at the beginning, the initial node), and looks through all of its adjacent nodes. The node with the smallest 'f' score is the node that's closer to the goal than any other node. We keep track of this node.
"this.adjacent[index]" points to the node closest to the goal. There could be several, but any one is great. I think the way I did it is that this one will favor down-right before left-up so if there's a fork left/right it'll pick right. This is attributed by either using "++ from 0" or "-- from 8" in the loop. I use "-- from 8", so it'll go to the bottom-right most node before going to the top-right most... Anyways, we give it's next node the parent node and return a copy of it. Why? Because we want to construct a list indifferent from adjacent nodes. This list would be considered our "closed" nodes. Adjacent nodes are the "opened" nodes. (Read the article to understand clearer).
So, now we have a new node that contains within it the previous step. We now need to step again. I do this in the main calling function:
doPath: function(x1, y1, x2, y2) {
this.start.x = x1;
this.start.y = y1;
this.end.x = x2;
this.end.y = y2;
var current = this.findStart();
while (current.x != this.end.x || current.y != this.end.y)
{
this.findAdjacent(current);
current = this.step(current);
}
return this.follow(current); // current is actally 'finish' here.
},
doPath is the function that brings it all together. You call this to set your initial and final (x, y) coords. Then it assigns a start node with findStart. It then goes into a loop checking to see if the current node (initially start) is at the finish. Because it's not it will step through and keep adding onto current the next node. What we get is a singly linked list. With the start node pointing to the next nodes. But there's a problem.
Start -> step0 - > step1 - > step2
Do you see a problem here? We end on step2, not start. So how do we start when we ended on finish!? We must traverse backwards through this list to get to start. Traversing backwards implies traversing forwards, therefore if you can get from the finish to the start then you can surely get from the start to the finish. I do this in another function I call "follow". Because we "follow" the path:
/* follows the path and returns a list of points */
follow: function(current) {
var arr = [];
// to follow meabs to backtrack, but we'll just unshift to the array:
while (current != null)
{
arr.unshift({x: current.x, y: current.y});
current = current.next;
}
return arr; // contains points from start to destination:
},
Because we are following the list backwards we need to add backwards to an array. This array contains the points we've been through.
Say we path from (0, 0) to (3, 0), the list would look like this:
- step3 (3, 0) -> step2 (2, 0) -> step1 (1, 0) -> Start (0, 0) -> NULL
But our array needs to look like this:
- [(0, 0), (1, 0), (2, 0), (3, 0)]
Thankfully JS has the unshift method. This makes our life easier since we need only traverse once. Also notice that the treaverse stops when current is equal to null. That is because the next node after start doesn't exist!!
Processing the Data
Thta's entirely up to you. This code gives you a list of points. This could be tiles, pixels, sections, quadrants etc. The biggre their representation (say tiles) the faster the algorithm would work for you. Going through 10 tiles is faster than 160 pixels, but then you'd need tile based movement.
An RTS would treat this as waypoint data where a waypoint is some scalar away.
A waypoint of 24 would equate:
- 24 * [(0, 0), (1, 1), (2, 2)] = [(0, 0), (24, 24), (48, 48)].
Just move your RTS units in the direction of the waypoint and you're good to go.
Tip: To get an angle between points: (p1 and p2 are two points that come from the array).
- Math.atan2(p1.x - p2.x, p1.y - p2.y)
If you're cool enough you can try to "stringify" this into literal directions or rewrite the code to construct literal directions: E, N, S, W
- if (p1.x - p2.x) is > 0 then add E (etc.)
Appendix A: Heuristics
Manhattan Distance: [g = 10 (orthogonal) or 14 (diagonal)]
- H = 10 * (|x1 - x2| + |y1 - y2|)
Diagonal Distance: [g = 1 (always)]
- H = 1 * max(|x1 - x2|, |y1 - y2|)
This one will favor diagonals more, you can try it out! Notice the restriction on "g".
Euclidean Distance: [g = 1 (always)]
- H = 1 * sqrt((x1 - x2)^2 + (y1 - y2)^2)
Notice the euclidean distance is pretty much the Pythagoras Theorem. It's also going to be the slowest case. It assumes you can move in any angle. This won't work for our purposes because the only angles we have are either orthogonal (90deg) or diagonal (45deg). So don't use this one.
