# Pathfinding Pt.1

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
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

return failure

function reconstruct_path(came_from,current)
total_path := [current]
while current in came_from:
current := came_from[current]
total_path.append(current)
``` ``` 