Before delving further into my procedural generation series, I’m taking a slight detour to talk about pathfinding. Pathfinding is typically used to simulate AI intelligence. In short, it creates a graph of all pathways through the current scene and calculates the shortest route from the current position to a target position (typically the player’s position).
My goal is quite complex. My goal is to create an easy-to-use, preferably automated, pathfinding system for 2D platformer/’metroidvania’ situations. When I was young, I absolutely loved a game called, Metroid Fusion. It was a typical Metroid game that followed the well-known formula. However, it introduced a new danger in the form of a Samus (the protagonist) clone, referred to as the SA-X.
The SA-X would show up during different segments of the game and was practically hunting the player. These portions of the game made me very anxious and had my palms sweating like Battle Toads on a bad day. The AI felt SO smart to my ten year old self who was too scared of the enemy to even think twice about trying to break the system. Apparently, the SA-X wasn’t actually so smart…
Here she runs back and forth as you stand on the other side of this morph-ball tunnel. Hilarious, but it’s something that I want to fix. I want to recreate this feeling that I had. The feeling that it doesn’t matter what you do. The enemy WILL find you.
I’ve broken down the problem into several steps (I may break it down further as I run into problems) and we will look at the first today.
STEP 1: The Global Solver
First we will take a look at the global solver. The global solver is our path. If you were to take a screenshot of a level and draw a line through the level, from enemy to player, that would be the job of the global solver. Later we will cover the local solver. The local solver tells the AI how to get from node to node (more on this later) along our path. For example, when to jump rather than look for a ladder. The local solver would have helped the SA-X use its morph ball ability rather than turn around and look for other options.
There are a few options for global solvers, but A* is most popular and probably the most well-documented. I’ll quickly talk about A* (pronounced A-Star) for those of you who haven’t worked with this algorithm before.
The A* Algorithm
The A* algorithm is a process for efficiently plotting a path between two points on a graph of nodes. Nodes are basically data structures used to plot data for a graph traversal problem. Pathfinding is commonly used in top-down games, like turn-based, tactics RPGs. Think the Fire Emblem series. In Fire Emblem, each grid square is represented by a node. The node has an (x, y) position as well as a list of pointers to its neighboring nodes. We use this list of neighbors to navigate from node to node within our algorithm.
In Game Maker, you may let your nodes be actual objects and initialize a room like this:
var obj;
for (var i = startx; i < endx; i += NODE_WIDTH) {
for (var j = starty; j < endy; j += NODE_HEIGHT) {
obj = instance_create(i, j, oNode);
obj.passable = true;
obj.F = 0; // F-Cost = (G + H)
obj.G = 0;
obj.H = 0;
obj.parent = -1;
obj.cost = 1; // Cost of moving through node
obj.neighbors = ds_list_create();
}
}
If you have done any pathfinding work before, you have probably heard of depth first search (DFS) and breadth first search (BFS). If so, you will have probably asked yourself why you don't try to calculate the most appropriate node to move to next rather than blindly guess and exhausting all options (as you would with DFS). This is pretty much what A* is. It's actually a special case of Dijkstra's algorithm that uses projected costs to guess the correct combination of movements.
First, let's figure out the cost of moving from node to node.
F = G + H
As shown above, each node has an F-cost. That F-cost is found by combining a G-cost and an H-cost. But what are those? G is the cost that it took to get to the current node, while H is our guess of what it will cost to get to the target node from the current node. Basically, cost from start plus cost to finish. The H cost is known as our heuristic. The heuristic is not an algorithm, but an intuitive series of steps that allows us to guess and approximate solutions. If your H is solid, then A* will find the shortest path from A to B very quickly, if not then your performance just goes down from there. Hardly ever is your H going to be "perfect". In my case, H will take A LOT of tweaking because I will be weighing different maneuvers like running, jumping, wall jumping, climbing ladders, etc. That will come later.
The first step to implementing the A* algorithm is to create an open list and a closed list. During each iteration, we'll look at the neighbors of the current node, and add the one with the LOWEST F-cost to the open list. We will iterate through this and eventually add all of the "best picks" to our closed list. Honestly, this part is best described via pseudo-code or by watching a video demonstration.
Here, I'll Wikipedia that for you:
function A*(start,goal)
// The set of nodes already evaluated.
closedset := the empty set
// The set of tentative nodes to be evaluated, initially containing the start node
openset := {start}
// The map of navigated nodes.
came_from := the empty map
// Cost from start along best known path.
g_score[start] := 0
// Estimated total cost from start to goal through y.
f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
while openset is not empty
current := the node in openset having the lowest f_score[] value
if current = goal
return reconstruct_path(came_from, goal)
remove current from openset
add current to closedset
for each neighbor in neighbor_nodes(current)
if neighbor in closedset
continue
tentative_g_score := g_score[current] + dist_between(current,neighbor)
if neighbor not in openset or tentative_g_score < g_score[neighbor]
came_from[neighbor] := current
g_score[neighbor] := tentative_g_score
f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
if neighbor not in openset
add neighbor to openset
return failure
function reconstruct_path(came_from,current)
total_path := [current]
while current in came_from:
current := came_from[current]
total_path.append(current)
return total_path
Again, in short (this is meant to be a study, not a tutorial), you start with the initial node and keep track of the nodes that need to be traversed in some form of priority queue or list. This is the open list. Nodes with a lower F-cost get a higher priority. During each iteration, the node with the highest priority is removed from the open list, the F-cost of its neighbors are updated and added to the open list. The algorithm continues until the goal node has the lowest F-cost in the list. That F-cost is basically the length of the shortest path. If done correctly, you will assign parent nodes along the shortest path and iterate backwards along them to find your path between nodes.
There are TONS of papers, examples, and studies on the A* algorithm. I don't necessarily want to go in depth, myself. However, this was the first step to accomplishing our platformer pathfinding. My plan is to use A* to find the shortest path between a set of way-points that we will setup later. In a platformer, every tile doesn't need to be a node. We only need nodes at specific landmarks like before a jump, the end(s) of platforms, or at the top and bottom of ladders. Our global solver will use A* to find the connections between these nodes. Later our local solver will tell our objects how to traverse the terrain between any pair of nodes.
Here is my A* algorithm running after my first night of work on this project. Here you can see the algorithm finding the path from (0, 0) to (mouse_x, mouse_y) in real time.
-Z
Zack Bell Games 