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.

A-Star explained

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.

Notes:

  • 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 normalize_point)
  • The get_neighbors function 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_iterations for 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_iterations once per second on a timer. I guess my point is: while this is an efficient algorithm, you still have to use it carefully.
class_name RaycastAStar

var openSet = {}
var cameFrom = {}
var gScore = {}
var fScore = {}
var space
var excludes = []
var neighbors_map = {}
var max_iterations = 1000
const GRID_SIZE = 32

# Simple vector serialization. We serialize most vectors so we can use them as dict keys
func _vec_to_id(vec: Vector2) -> String:
	return str(vec.x)+","+str(vec.y)
	
# Finds the (serialized) point in the openSet with the smallest fScore
func find_smallest_fscore():
	var smallestScore = INF
	var smallestPoint = null
	
	for pointId in openSet:
		var point = openSet[pointId]
		if fScore[pointId] and fScore[pointId] < smallestScore:
			smallestScore = fScore[pointId]
			smallestPoint = pointId
	
	return smallestPoint

# Heuristic distance between two points. In this case, actual distance.
# This is straight-line distance though, and ignores any obstacles.
func h_dist(end, start):
	return (end - start).length()

# Uses raycasting to find the traversable neighbors of the given position
# Caches results
func get_neighbors(vec):
	var vecId = _vec_to_id(vec)
	if neighbors_map.has(vecId):
		#print("Had vector in neighbors map")
		return neighbors_map.get(vecId)
		
	var targets = [
		vec + Vector2(GRID_SIZE, 0),
		vec + Vector2(-GRID_SIZE, 0),
		vec + Vector2(0, GRID_SIZE),
		vec + Vector2(0, -GRID_SIZE),
	]
	var valid = []
	
	for target in targets:
		var result = space.intersect_ray(vec, target, excludes)
		# There's nothing there, so we can visit the neighbor
		if not result:
			valid.append(target)
	
	neighbors_map[vecId] = valid
	return valid
	
# Works backward, looking up ideal steps in cameFrom, to reproduce the full path
func reconstruct_path(current):
	var currentId = _vec_to_id(current)
	var total_path = [current]
	
	while cameFrom.has(currentId):
		current = cameFrom[currentId]
		currentId = _vec_to_id(current)
		total_path.push_front(current)
	
	return total_path

# Normalizes a point onto our grid (centering on cells)
func normalize_point(vec):
	return Vector2((round(vec.x / GRID_SIZE) * GRID_SIZE) + (GRID_SIZE/2), (round(vec.y / GRID_SIZE) * GRID_SIZE) + (GRID_SIZE/2))
	
# Entrypoint to the pathfinding algorithm. Will return either null or an array of Vector2s
func path(start, end, space_state, exclude_bodies):
	
	var iterations = 0
	
	# Update class variables
	space = space_state
	excludes = exclude_bodies
	
	start = normalize_point(start)
	end = normalize_point(end)
	var startId = _vec_to_id(start)
	var goalId = _vec_to_id(end)
	
	cameFrom = {}
	openSet = {}
	openSet[startId] = start
	gScore = {}
	fScore = {}
	
	gScore[startId] = 0
	fScore[startId] = h_dist(end, start)
	
	# As long as we have points to visit, let's visit them
	# But not more than max_iterations times.
	while openSet.size() > 0 and iterations < max_iterations:
		# We're going to grab the current best tile, then look at its neighbors
		var currentId = find_smallest_fscore()
		var current = openSet[currentId]
		
		# We reached the goal, so stop here and return the path.
		if currentId == goalId:
			return reconstruct_path(current)
		
		openSet.erase(currentId)
		
		# "neighbors" are only accessible spaces as discovered by the raycaster
		var neighbors = get_neighbors(current)
		for neighbor in neighbors:
			var neighborId = _vec_to_id(neighbor)
			var neighborGscore = INF

			# We've seen this neighbor before, likely when passing through from a different path.
			if gScore.has(neighborId):
				neighborGscore = gScore[neighborId]
				
			# This is the "new" gScore as taken through _this_ path, not the previous path
			var tentative_gscore = gScore[currentId] + GRID_SIZE

			# If this path is better than the previous path through this neighbor, record it
			if tentative_gscore < neighborGscore:
				# This lets us work backwards through best-points later
				cameFrom[neighborId] = current
				# gScore is the actual distance it took to get here from the start
				gScore[neighborId] = tentative_gscore
				
				# fScore is the actual distance from the start plus the estimated distance to the end
				# Whoever has the best fScore in the openSet gets our attention next
				# Therefore we are always inspecting the current best-guess-path
				fScore[neighborId] = tentative_gscore + h_dist(end, neighbor)
				
				# This would allow revisiting if the heuristic were not consistent
				# But in our use case we should not end up revisiting nodes
				if not openSet.has(neighborId):
					openSet[neighborId] = neighbor
			pass
		
		pass
		iterations += 1
	
	# No path found
	return null
	

And here’s how you would invoke it from the outside:

class MyAIChar

# Save it as an instance variable so that you get the benefits of caching the raycast results
# Probably would work fine if you moved this to navigate_to though.
onready var astar_solver = RaycastAStar.new()

func navigate_to(target):
	# Don't let my body block my own raycaster
	var excludes = [self]
	# This is the dependency that the AStar solver needs in order to raycast
	var space_state = get_world_2d().direct_space_state
	var astar_results = astar_solver.path(global_position, target, space_state, excludes)

	# We found a path. astar_results will be an Array of Vector2 points
	if astar_results:
		walk_targets = astar_results
	else:
		# No path found, either because the points are not connected,
		# or because max_iterations was reached before discovering the path
		pass

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:

Pathfinding Demo