Beyond Dijkstra’s

 Introduction

Pathfinding algorithms are important to many fields of computer science as finding the fastest way to get from point A to point B is a common problem. Video games also need to solve this problem as long as a game involves non-player characters (NPC). Well executed implementations of pathfinding are necessary for making a game immersive but can be complicated and computationally expensive. Pathfinding in 2D games, while simpler than in 3D games, is not trivial and has plenty of room for optimization and interesting features.

There are mainly two situations where 2D pathfinding can take place: with or without gravity. Games with gravity are commonly platformers like Super Mario Bros where the player is constantly pulled towards the bottom of the screen. Games without gravity are similar to The Legend of Zelda where the player stays in place when they stop performing inputs. Games with gravity often feature a more limited movement suite for non-player characters such as moving left or right and maybe jumping. Gravity does impose some complications, however, as the NPC is not in full control of their movement. Games without gravity allow for more freedom of movement for NPCs but that adds a level of complexity as more options are available. We will discuss what pathfinding looks like without gravity because that scenario better reflects a game I’m working on.

Standard Algorithms

Dijkstra’s algorithm for finding the shortest path between two points is a well-known pathfinding algorithm because of its general purpose utility. The approach starts with the idea that to get from point A to point B, there are many other points along the way that you would have to visit. The algorithm finds the shortest path to points other than B since  the shortest path to another point C may help us find the shortest path to B.

Dijkstra’s works on graphs with no sense of space

Because Dijkstra’s algorithm is general purpose, it doesn’t take into consideration the physical space that our game and many others take place in. Dijkstra’s approach has no idea if moving from point A to C will get you closer to B. A small tweak produces the A* (A Star) algorithm. A* assumes that if B has a lower distance as the crow flies to C than another point D but are the same walking distance from A, we should analyze C before D. Sometimes this assumption fails if a roundabout path is necessary but it usually saves a significant amount of computation for the same results.

Tilemap Integration

Many 2D games use tilemaps to structure their levels or scenes. Tilemaps are made by dividing the level into a grid where each cell or tile includes a sprite for visuals and some collision rules. These collision rules determine if the entities in the game should be able to walk through the tiles or get stopped. They are important to pathfinding as they define what impedes a straight path from A to B and so what must be navigated around. Pathfinding algorithms only work for individual points so each tile in the tilemap must be subdivided to allow for more fine grain movement. Because the algorithm is defined with a grid, NPCs can only walk in one of the eight cardinal directions which isn’t realistic but can be resolved in later steps of the process.

Because NPCs have an area defined for collision and pathfinding algorithms only work for points, NPCs bump into walls because there is a mismatch between where they think they walk and where they actually can. This behavior also leads to situations where the NPC is constantly trying to move closer to a wall but can’t because the wall is pushing them away. One way to avoid this issue is by marking the area around the wall as an obstacle based on how large the NPC is. This ensures that any point the NPC thinks it can occupy won’t require them to also be partially inside of a wall.

Making skirts around the walls allows for accurate pathfinding

Grid Reuse

Because the pathfinding grid is determined by the physical size of the NPC, multiple grids are necessary if we have NPCs of differing sizes. This isn’t ideal because this restriction can lead to lower quality paths if we try to lump sizes of NPCs together and use only a few grids for pathfinding. This is because the exact size of an NPC is not fully reflected by the grid. It can also lead to performance penalties as multiple regions of data are used for very similar purposes which reduces cache locality.

For each cell in a pathfinding grid, instead of only storing if it is traversable or not I instead store the distance from the cell to the closest wall. This way I can determine if cells are traversable by checking if the distance to a wall is greater than the size of the NPC. This way I can store all of the data for pathfinding in one place and use it differently for each path computed. Unfortunately, it only works perfectly for NPCs that have certain shapes for collision areas such as circles or squares.

Tracking distance also allows for neat contour graphs

Final Touches

The result of the algorithm, so far, involves many intermediate points even if the path from A to B is a straight shot. Because the NPC’s movement is restricted to eight directions, paths can be simplified greatly while encoding the exact same information. Instead of telling an NPC to walk up one unit of distance a dozen times, we can just tell them to walk up for a dozen units. This reduces the individual points along the path to only the important ones which helps with our next alteration.

Further changes can be made to the path to allow an NPC to not only move in eight directions. By refining small parts of our path, such as B,C,D, we can make the path shorter and more realistic. We change the path if a straight line from B to D is possible by updating the B,C,D path to just B,D. This ensures that for a very simple straight path from A to B, a direct path will be taken. If the path B, D isn’t possible, however, we can repeatedly test the points between C and D to see if B can reach them to improve the path the best we can.

The path first gets less verbose, then more accurate

Conclusion

Well executed pathfinding in a video game can help make it more immersive as the NPCs behave in realistic ways. In order to increase performance, standard pathfinding algorithms can be altered by factoring in the physical nature of our game. Additional processing can ensure that the outputted path is both simple and high quality. I argue that storing the distances from each cell is better than storing multiple pathfinding grids. I already brought up one downside, see if you can find more downsides to my approach and how they might be mitigated.