September 2019

Pathfinding was one of the first features I worked on for Knights of Frontier Valley. In those early days, game programming was still a hobby that I had recently picked up next to my busy day job. While pathfinding didn’t seem to be an easy thing to do, and, therefore, maybe not ideal to get one’s feet wet, it seemed essential to have characters being able to move around on the map without running into stuff. So I jumped right in.

From my day job at the time I already knew that many pathfinding implementations were based on A* (“A-Star”) – a freely available, proven, and fairly easy-to-implement algorithm. For A* to work, the map in question needs to be divided into navigable units, such as road segments or map tiles. My game map was already tile-based for the visualization of the terrain, so using those same tiles for pathfinding seemed like a natural thing to do (inspired by playing pen & paper DnD in the 80s, I was using hex tiles for the wilderness map, and square tiles for dungeons and towns).

For A*, a “travel cost” is assigned to each tile. Tiles representing a more difficult type of terrain (such as hills or swamps) will get a higher cost than those that are easy to pass through (such as grass or light forest). The algorithm then calculates the cheapest path of tiles between a given start and end tile. Tiles that are completely inaccessible to the particular character (maybe water or steep mountains) can be skipped in the search for a path, so that the route will always lead around them.
The inner workings of A* are available on Wikipedia, and I got it coded up in less than a day. It felt great – that was easy!

But my premature feeling of success quickly got caught up by reality when I realized that A* has certain shortcomings, some of which would be game-breaking for a game like this. For instance, paths created by A* are just as granular as the size of the map tiles fed in. There is no moving “within tiles”; the algorithm just hops from tile to tile. This means that the resolution of the path depends on the size of the tiles. With larger tiles, the path isn’t very detailed and can’t take smaller turns. However, with shrinking tile size, the computational effort for A* grows exponentially, possibly leading to performance issues on weaker systems when many characters move across the map at the same time and frequently re-route.

Large tiles might be fine for games with very simple character movement. A strategy game for example, in which units just move from tile to tile on a strategic overview map, might get by with A* in its most basic form. But Knights of Frontier Valley wasn’t such a game, and characters were supposed to be able to walk, run, fly, or swim to any accessible spot on the map, unrestricted by tiles and their size.

A* also doesn’t guarantee that the path comes out as something that can be perceived as “natural” (e.g., as a straight line between two points with no blockage in between). If there is more than one route with equally cheap cost, A* will semi-randomly pick one, which might be one that includes a seemingly unnecessary detour.

Those were severe issues, but the real showstopper was the fact that tile-based movement, which usually leads from tile center to tile center, cannot produce a straight path if the change in x coordinates between start and end tile isn’t the same value as the change in y coordinates. As an example, the path from one tile to another tile, one that is located two tiles over and one tile down, is not a straight line when travelling over the centers of each tile the path needs to cross. That meant that most paths would never look natural.

For our strategy game example this might still be acceptable. In such a game, it doesn’t really matter if a path isn’t as straight as it could be, since it has little to no negative effect on gameplay. As long as characters don’t need to spend more movements points to get to their destination, it’s probably ok.

For most games, however, such a simple form of movement would not be appropriate, and that included Knights of Frontier Valley. Paths were meant to always look natural.

It become clear that A* could only be the beginning of my pathfinding implementation. What had started as a one-day coding effort, now turned into a major project of weeks and eventually months of path refinement. By coming up with each idea for an improvement by myself, I probably ran into every rookie mistake imaginable, and might have violated some best practices here and there. But in the end, it turned out to be the fun learning experience it was meant to be, and most importantly: it worked.

The first and most important change was to have characters travel between waypoints (“control points”) instead of just tiles. Control points are defined by x/y floating point screen coordinates (to simplify, think pixel coordinates), and therefore allow for an infinitely fine navigation to anywhere within a tile.

Therefore, I added a second step in which a set of rough control points was determined within the path of tiles provided by A*. Those rough control points were subsequently optimized via a series of line-of-sight checks between each path segment. Once a refined set of control points is available, the path got evaluated from each end to see if it could be further optimized (straightened) by removing redundant control points.

As needed, additional control points were also added during this step to route around corners of inaccessible tiles that were crossed.

The resulting paths now were highly granular, efficient, and naturally looking, while still following the rough A* tile path to make sure the character always stayed on the cheapest tiles from start to end. It was a huge improvement, but work was far from completed.

Next, I added a little optimization for simple routes. If the path was short (maybe even remained within the same map tile) or stayed on the same terrain all the way, running A* (and optimizing the resulting path) was overkill. I added a step (pre-A*) to check for this condition, and in the current implementation characters will now simply move from start to end point in a straight line in those cases. It was a simple change, but it actually applied to a high percentage of routes, saving a good number of CPU cycles.

My characters were now walking from one control point to the next in the most efficient way: in straight lines, taking sharp turns at the waypoints. This is not how a person would walk in real life, so a mechanism was needed to smooth the path and make characters move in a more natural way.

That change was accomplished through so-called “Catmull-Rom splines”. In a post-processing step, this mechanism transforms the trajectory between control points from sharp turns into naturally looking, smooth curves.

Fine tuning was needed here – if the smoothing effect was too strong, it could make the adjusted path deviate so much from the original that the character would again run into obstacles the path was meant to avoid.

(Side note: the libGDX framework I’m using comes with both an A* and a Catmull-Rom implementation; however, I discovered this only after I already wrote my own A* code. I also wrote my own Catmull-Rom implementation, since libGDX’s variant has a parametrization issue. In order to avoid a curvature that’s too strong and also the forming of cusps at the turns, the parameters fed into Catmull-Rom have to be “centripetal”, which isn’t the case in libGDX.
A great writeup about this can be found here.)

By now, I had accomplished that my characters would take efficient routes around terrain blockage, and move between the path’s waypoints in a natural manner. But this was still not good enough.

One day, Knights of Frontier Valley would play in a dynamic world with many obstacles other than inaccessible terrain (such as buildings or pieces of furniture), and all kinds of characters would be roaming the map, possibly temporarily blocking someone else’s path.
To account for those dynamic entities, I added an “entity avoidance” step to the logic, which would check whether any of the path segments lead through another entity’s personal space. If so, the path was left as it was, but with a little detour added to go around the blockage. That way, characters wouldn’t completely change course just because a moving obstacle temporarily gets in their way.
To make sure that any dynamic blocker will be detected, characters re-compute their paths every second. This is why performance is so critical for pathfinding.

The entity avoidance step is complex for a number of reasons. The logic has to be smart enough not to get stuck in an endless loop of re-routing if the detour itself is currently blocked. It also needs to ensure that the most efficient detour path is taken, checking various possible ways to get around an obstacle. Then, it must detect that certain flat items aren’t path blockers (e.g., rugs or corpses).
And lastly, this phase of pathfinding is also the step where some world interactions are evaluated, such as handling a closed door along the path. When such a door blocks movement, the character should still walk up to it, but then stop and be given options on how to deal with the situation (options for this example include actions to kick the door in, spy through the keyhole, use a key, pick the lock, cast a spell, or even set a wooden door on fire).

And that’s it! That’s how far I currently am with pathfinding. Soon, when dozens of characters are roaming the world and large buildings are placed across the city maps, there may be more changes needed.
But for now, the complete mechanism to calculate paths in Knights of Frontier Valley goes like this:

1) Check for a simple path: if the character can go to the destination without crossing more expensive/impassable terrain or another entity’s personal space, stop here and simply have the character walk in a straight line.

2) A*: if this is not a straight route as per step 1, calculate the cheapest path of tiles as a rough guideline.

3) Determine control points: calculate one control point per tile – either where the line of sight between the previous control point and the destination crosses the tile’s outline, or, if that line is blocked, at the tile’s center.

4) Straighten the path from one side: Walk through all path segments from start to end, and remove redundant control points (those where a line of sight between the two neighboring control points exists and doesn’t lead over more expensive terrain).

5) Route around tile corners: if necessary, add control points to nearby tiles with the same cost to route around blocking corners.

6) Straighten the path from the other end: Repeat steps 4 and 5, this time starting at the end point. Now the path is as short and straight as it can possibly be without adding to its cost.

7) Route around dynamic entities: Check each segment between neighboring control points to see whether it leads through a map entity’s space. Add additional control points around that entity if possible, making sure the detour is the shortest possible one. If no detour around the entity is possible, it is a hard blocker (in the game, this could manifest as an enemy guarding a hallway).

8) Smoothen the path: with the final control points now being available, use Catmull-Rom splines to make the trajectory look more natural, while taking care that the adjusted path doesn’t cross any obstacles.

Until next time,
Martin