This post is the third part of the talk I gave on the WTM and belongs to this root post.

We call pathfinding to the process by which the machine calculates the shortest or fastest path from its position to the position of its target.

Pathfinding sits on the border between Autonomous Movement and Decision Making, because usually we first decide where we want to go, then pathfinder works out how to get there, and finally we move to the goal using a movement control system.

Through this post we’ll see several ways and tools used for calculating a path.

1. Graph theory

Definition

Before getting into the algorithms, I’d like to explain three basic concepts from graph theory, just to get the jargon.

We will imagine our game map as something like this:

The whole thing will be called Graph. The round shapes are Nodes, and the black lines connecting each node to its neighbors will be called Connection. Math dudes may be a bit upset because they use other words for this concepts (edge, vertex…), so I’d like to clarify that I’m using this concrete words because they’re the ones used by computer science and, furthermore, by gdxAi.

So keep them in mind: Graph, Node, Connection.

Before using the algorithm, we must apply a discretization of the space, which consists in converting our infinite map in a set of finite nodes. For instance in the following image, I’ve used a grid to divide the space in cells:

Implementation

Our map implements the Graph interface. It stores a list of all the nodes on the graph, as well as the methods needed to access them.

Each Node keeps its coordinates and a reference to its neighbors.

Finally, Connections contains a reference to the two nodes that it is connecting, and a cost. The cost can be whatever we want, usually the time or the distance between nodes, and this is the key indicator to verify that indeed our route is the shortest or the fastest.

2. Indexed A*

Definition

Now that we have a manageable number of nodes, we’ll apply our algorithm. There exist several ways to achieve this, but the most popular at the moment in video games is the Indexed A* algorithm.

Very briefly, this algorithm works like this: reusing the previous graph:

Imagine we are at node 1, and we’d like to go to the node 6.

First, we evaluate our neighbors, and select the one that is closer to the goal. In this case, node 5. Then we apply the same process to the selected node, the neighbor closer to the goal is node 4. We keep going until we reach the goal or until we get into a dead-end. The result, in this case, would be the node path [1, 5, 4, 6].

Implementation

Once we’ve built our graph system, we can go ahead with the Pathfinder:

Use the PathFinder interface and implement its method searchNodePath. This method is fed by a starting node (our position), an end node (the goal), and a Heuristic.

The heuristic is the function that will tell us which node is the one that is “closer to the goal”, more or less accurately depending on our preference. Greater precision requires greater amount of resources, so find the harmony between accuracy and performance.

The outPath is passed as a parameter for performance reasons, but actually it is the path that will be calculated inside the method. The result is a GraphPath.

3. Hierarchical Pathfinding

Definition

Hierarchical pathfinding plans a route in much the same way as people would. You plan an overview route first, and then split it into stages. Each stage of the path will consist of another route plan.

I’ll take myself as an example. I live in Valencia now, but I was born in Vitoria. On holidays, I go back to visit my family and friends. How do I get in there?

First, I plan the general route:

1. Drive the car to the train station.
2. Take a train to Vitoria.
3. Be driven home.

That’s what I have on my mind the day before.

The next day, when starting my journey, I start developing the first step:

1. Drive the car to the train station

1.1. Drive to the highway

1. 2. Take exit 5

1. 3. Drive the road to the train station

For now, I don’t care about what will I do when reaching the train station, I just focus on the step I’m performing.

When I reach the train station, I develop stage 2:

2. Take a train to Vitoria

2.1. Go to the ticket machine

2.2. Print the ticket

2.3. Look for the platform at the screens

2.4. Walk to the platform

2.5. Wait for the train

2.6. Go inside the train

Then I start developing stage 3 and so on, until I reach my goal.

This technique, called “Divide and Conquer“, consists in splitting a huge problem in smaller and more manageable chunks, allowing us to focus in only one chunk at a time.

This type of pathfinding provides a lot of advantages, among others:

• Once we’ve plotted the general route, we can just focus on the current step, evading from the rest.
• In video games, it usually happens that the target changes, that won’t be a problem for us because in that case, we just discard the remaining path from the step we were in, and calculate the new general path.
• We are able to solve really complex paths, because we can divide them over and over until we can solve the next step directly.

Implementation

The implementation is very much the same as the traditional pathfinder, actually we use the same interface. The only difference is that the graph will be classified by levels, meaning, our graph is now a HierarchicalGraph.

The pathfinding algorithm must be implemented in each level recursively. Use the setLevel method to switch the graph into each level.

4. References

I wrote this detailed post about pathfinder 2 months ago, so half of the work was fortunately done. Here‘s an amusing site where to play with pathfinding algorithms. Wikipedia and Amit are also very illustrative, particularly the latter has a dedicated shrine in my living room and I’d be proud to kiss his feet.

The package provided by gdxAi for Pathfinding implementation can be consulted here.

5. Overview

• Graph theory is relevant. wiki
• gdxAi uses the Indexed A* algorithm. wiki
• Hierarchical Pathfinder divides to conquer. wiki

This is the end of the content of the talk, go back to the root post to see the recorded talk and the Prezi presentation ->