That title is a doozy! Before we start, let me introduce those terms. First, Godot is the game engine I’m using on The Necromancer in the Shadows. Second, A-Star is a pathfinding algorithm commonly used in games. Third, raycasting is a technique also commonly used in video games to determine what object (if any) blocks a line-of sight.
A-Star pathfinding is an algorithm designed to find the shortest path between two points on a graph. For game programmers, this is useful for making AIs navigate around maps and obstacles. Godot has a built-in A-Star solver, but it has a major limitation: it’s not aware of its own world. It’s essenetially a low-level library that runs the actual A-Star algorithm, but you as the developer are responsible for loading all the points in.
The way this works out is that the built in A-Star class in Godot is great if you have a single tilemap that defines all the collisions, or some other way of working out what all the navigable and connected points in the scene are. But in my case, I have several tilemaps all with collision layers, and I also use sprites with StaticBodies for collisions as well (the animated trees in the game). So the built-in A-Star solver doesn’t work for me (it could, but it would be a lot of work to set up).
Godot also has a Navigation system built in, but this relies on you drawing the navigation paths for each of your boards, defining exactly where AIs can and can’t navigate to. That’s a lot of work too!
I wanted to find a pathfinding approach that was physics-aware, meaning it can interpret both the tilemaps and the sprites on the board, and navigate around all of those.
Godot’s Raycasting system is physics-aware, and in fact my first pass at AI pathfinding used Raycasting alone to figure out how far the AI could walk in a given direction. But this approach was too naive, so I needed a proper pathfinding algorithm.
The A-Star algorithm is pretty simple and not at all difficult to implement, so I decided to write a custom version that uses Raycasting to figure out which points are navigable. This approach works remarkably well, and has the major advantage of needing very little information about the map and scene. For most 2d top-down maps, this class should work with minimal modification.
Before jumping into the code let me briefly explain the A-star algorithm. It’s a little difficult to interpret the code, but conceptually it’s easy. The pathfinding algorithm needs three things: a start point, and end point, and a way to determine if a given point is navigable.
Internally, the algorithm maintains a queue of points to inspect as well as two sets of scores and a “history map”. The two scores are called the “g” score and the “f” score. Don’t be intimidated by the vague names. Both the g- and f-scores are functions of a point, meaning each point will have a different score. The g-score represents the cost (in our case, distance) of moving from the start point to the point in question. The f-score is a quick estimate of the distance from the point to the goal.
You start the algorithm by adding the start point to your queue, which we’ll call the “open set”. From there, the algorithm continues
while openSet.size() > 0. It goes something like this:
- Find the point in the open set with the lowest f-score. This will be your “focus point” for this iteration.
- If the focus point happens to be the goal, congrats! You’ve found a path. Return a reconstruction of the path.
- Figure out which of the focus point’s neighbors are navigable. In our case I use only 4 neighbors (up, down, left, right), but you could include diagonals, or use a hex-grid.
- For each neighbor, grab any existing g-score (or Infinity if not exists). The g-score may have been generated by a different path, so it’s possible a score exists.
- For that same neighbor, re-calculate the g-score by finding the focus point’s g-score, then adding the cell width to that.
- If your newly-calculated g-score is lower than the previous g-score for that neighbor, that means you’ve found a better path moving through “neighbor”. Record it like so: add it to the history map, update the neighbor’s gscore to the better one, and then calculate the neighbor’s f-score by adding a distance-remaining guess to the g-score. Finally, add the neighbor to the open set.
The loop then repeats from the next-best item in the open set.
It may be easier to mentally visualize the algorithm. From the start point, look at all the places you can go. Instead of meticulously measuring each neighbor’s path to the goal, just guess it, using the straight-line distance. Move to that point. Then repeat: look at all the places you can go. Which one of those places is both the closest to the start and the closest to the goal? Then move there and repeat. Any time you discover a potentially good path, you add that new point to the “open set” so you can re-visit it later. You move one step at a time, looking at each neighbor, and if you hit a wall, you backtrack to whatever the next-best looking path was. Eventually you’ll either run out of steam, or you’ll find the goal. Since you were writing down how you go to each point on the best path, you’re able to work backwards to the start, reconstructing the path you discovered.
Where does raycasting come in? That’s how the algorithm discovers which neighbors are navigable. Cast a short ray from the focus point to the neighbor, and if the ray doesn’t hit anything, the neighbor is navigable. If the ray does hit something, that means there’s a collision object there and the neighbor is not navigable.
Anyways, here’s some annotated code.
- To make score lookups and open set lookups fast, they all use Dictionaries (aka hash maps) instead of arrays. Therefore a method to serialize vectors is needed – I use the stringified version of the vector for the keys (
_vec_to_id). Edit: It turns out that GDScript Dictionaries can use vector objects as keys directly, so this stringifying is not necessary. I will update the code sample below within a day or two to reflect this.
- A-star itself does not need a grid necessarily, but I assume you are using one. Because we search in grid-steps, the start and end points need to first be normalized so that they’re an equal number of grid-steps apart. I choose the center of the grid for the raycasting and normalization (see
get_neighborsfunction is where the raycasting happens. This part requires the space_state dependency from the calling class (example below). I don’t know how expensive raycasting is in Godot, but in either case I’ve cached the results of the raycast from any given point, assuming that the environment around that point won’t change. If that’s a bad assumption for your game, remove the caching.
- It’s important to set a
max_iterationsfor the search. If two points are not connected, but there are no borders eg on the left side of your game, it’s possible for the algorithm to search all the way into x=-Inf in an infinite loop. I find that 1000 is a good maximum.
- This is an efficient algorithm and I’ve tested it with ~100 instances all pathfinding at once. However, it will slow down your game if you have 100 instances all failing to find paths and using up their 1000
max_iterationsonce per second on a timer. I guess my point is: while this is an efficient algorithm, you still have to use it carefully.
And here’s how you would invoke it from the outside:
Finally, here’s a little demo of the pathfinder in action. Both the player’s movement and the summoned skeleton’s movement are controlled by the pathfinder in this demo. The player moves to the position of the mouse click, while the skeleton tries to move to the player’s position. Watch as they navigate around trees and rocks: