The navigation system of Unto Deepest Depths

I’ve received a few viewer questions about how different aspects of the pathfinding and navigation logic work in Unto Deepest Depths, so today let’s do a deep dive into those systems!

The anatomy of a level

Before we can talk about how to navigate a level, we need to know what a level even is. In Unto Deepest Depths, levels are semi-procedurally generated. The level layouts themselves are chosen from a pool of layouts that I’ve designed, but the contents of a given level, such as the placement and types of units you encounter, are procedurally generated based on the player’s progress. The layouts are simple scenes composed of a single TileMap that contains whatever design I want that map to have.

The TileSets used by each layout are pretty standard, but they do contain custom data properties about how that tile should be processed during gameplay - is_solid and blocks_movement. The is_solid property is for walls and other cells that should block both movement and line of sight queries, whereas the blocks_movement property is for low-lying objects or holes in the ground that block movement but not attacks. These two properties, plus the absence of them to signal that a cell is both open and traversable, are all I need to set up the game grid, so now let’s look at how that works.

Building the grid

When the player enters battle, the level generator selects a random map layout and loads its contents into the game. Some battles, such as boss battles or special events, use fixed maps that just need light initialization, but the end result will be the same - when the level generator is finished setting things up, the desired map is now a part of the level. At this point, though, there is no navigation data, simply a TileMap that looks correct, but still need to be parsed into usable data, and that’s where the Navigation autoload comes in.

As the name suggests, the Navigation autoload is an Autoloaded script responsible for answering questions about the grid, including how to pathfind from one cell to another and if and where unit actions are blocked. I chose an autoload because it easily makes the grid information available to anything in the game that uses it without needing to worry too much about deep dependency injections, though that’s certainly an option if you have a more complex project you’re working on. For instance, the unit AI evaluates whether or not a move is good based on if it will move them closer to an opponent and, since autoloads are globally available, the check is as simple as this:

var distance = Navigation.get_movement_cell_path(
    unit_cell,
    target_cell
)

Once the level TileMap has been loaded, the Navigation autoload takes the TileMap node and generates navigation data from it using Godot’s AStar2D class. This is done by iterating over every cell, creating a node in the graph for it, and connecting it to its adjacent neighbors to support the grid-based movement of UDD. Note that I chose not to use the built-in AStarGrid2D class as there are instances, such as with teleporters, where I need navigation connections that are more complex that simple grid adjacency, but that may be an option for you.

# Truncated for clarity

var all_cells: Array[Vector2i] = []
var blocks_movement_cells: Array[Vector2i] = []
var map_bounds: Rect2i

func init_level(tilemap: TileMap) -> void:
	map_bounds = tilemap.get_used_rect()
    astar_grid = AStar2D.new()
	
	# Create nodes in AStar for each cell
	all_cells = tilemap.get_used_cells(0)
	var id = 0
	for cell in all_cells:
		id += 1
		astar_grid.add_point(id, cell)
		
        # Check custom data for what type of cell it is
		var cell_data = tilemap.get_cell_tile_data(0, cell)
        if cell_data:
		    if cell_data.get_custom_data('is_solid'):
			    astar_grid.set_point_disabled(id, true)
		    elif cell_data.get_custom_data('blocks_movement'):
			    blocks_movement_cells.append(cell)
	
	# Connect cells
	for cell in all_cells:
		var cell_right = cell + Vector2i.RIGHT
		var cell_down = cell + Vector2i.DOWN
		var cell_down_right = cell + Vector2i(1, 1)
		var cell_up_right = cell + Vector2i(1, -1)
		
        var cell_id = astar_grid.get_closest_point(cell, true)
		var cell_id_right = astar_grid.get_closest_point(cell_right, true)
		var cell_id_down = astar_grid.get_closest_point(cell_down, true)
		var cell_id_down_right = astar_grid.get_closest_point(cell_down_right, true)
		var cell_id_up_right = astar_grid.get_closest_point(cell_up_right, true)
		
        # Distance check to ensure that the closest cell found is actually the cell we want
		if astar_grid.get_point_position(cell_id_right).distance_to(cell_right) < 0.1:
			astar_grid.connect_points(cell_id, cell_id_right)
		
		if astar_grid.get_point_position(cell_id_down).distance_to(cell_down) < 0.1:
			astar_grid.connect_points(cell_id, cell_id_down)
		
		if astar_grid.get_point_position(cell_id_down_right).distance_to(cell_down_right) < 0.1:
			astar_grid.connect_points(cell_id, cell_id_down_right)
		
		if astar_grid.get_point_position(cell_id_up_right).distance_to(cell_up_right) < 0.1:
			astar_grid.connect_points(cell_id, cell_id_up_right)

As I’m building the grid, I also take the custom cell data mentioned previously and change what I’m doing depending on those properties. For is_solid cells, those astar nodes are immediately disabled since they should always block everything. For blocks_movement cells, though, things get a bit more complicated since whether or not those cells should be considered solid or open depends on the question being asked, so those nodes are kept enabled for now, but the cell is added to an array of blocks_movement cells so I can grab them again later.

After all of this, the grid is initialized and the Navigation autoload can start answering questions about it, so let’s now look at the two primary use cases of the autoload: calculating a path from one cell to another, and answering questions about unit actions.

Pathfinding

While pathfinding exists in Unto Deepest Depths, it’s not actually used to let units move directly, but rather to answer AI related questions about the distance to other units to help them determine what move to make. This is done with the following function in the Navigation autoload:

func get_movement_cell_path(start: Vector2, end: Vector2) -> PackedVector2Array:
	var cell_ids = []
	
    # Temporarily disable cells that only block movement
	var blocking_cells = blocks_movement_cells
	for cell in blocking_cells:
		var cell_id = astar_grid.get_closest_point(cell, false)
        # Make sure the cell we're trying to disable is the right one, and is not already disabled
        # aka, "is_solid" overrides "blocks_movement"
		if astar_grid.get_point_position(cell_id).distance_to(cell) < 0.1 and !astar_grid.is_point_disabled(cell_id):
			astar_grid.set_point_disabled(cell_id, true)
			cell_ids.append(cell_id)
	
	var start_id = astar_grid.get_closest_point(start)
	var end_id = astar_grid.get_closest_point(end)
	
	var path = astar_grid.get_point_path(start_id, end_id)
	
    # Re-enable temporarily disabled cells
	for id in cell_ids:
		astar_grid.set_point_disabled(id, false)
	
	return path

This function is pretty standard pathfinding for the AStar class, with the exception of how the blocks_movement cells are handled. Recall that those cells are stored, but not disabled, upon level initialization. Therefore, to get a valid movement path, I temporarily disable those cells, get a path between my desired cells, and then enable the temporarily disabled cells once again.

As this is the only traditional pathfinding I do in Unto Deepest Depths, let’s now look at how unit actions require the use of the grid.

Unit actions

For dealing with unit actions, the specifics depend on what action is querying the navigation system. Check out how units work if you need a refresher on the specifics, but the short version is that every move and attack is defined as an array of relative coordinates and an enumerator value for how collisions or other overlaps should be handled, called the block mode. The archer, for instance, can shoot targets several cells away, but will halt its shot at the first “thing” it hits. Let’s look at how one of its shots will get processed.

To shoot to the right, the archer has an action that lists the cells [1, 0], [2, 0], [3, 0], [4, 0], [5, 0] as the cells it can hit, relative to its current cell. When checking how this shot should actually be executed, it will convert these relative cell coordinates into world cell coordinates and then scan those cells, in order, until it finds something to hit. If the archer is at cell [4, 4], then the cells to check will become [5, 4], [6, 4], [7, 4], [8, 4], [9, 4].

After converting relative coordinates to actual, Navigation.get_ac_block_point is called (“AC” is a holdover term from the early days of development and in this instance refers to an action that has been normalized to world coordinates), which takes the desired action and returns which cell, if any, is blocking that action. The block mode of the action will determine how to handle this, such as truncating on the blocking cell, ignoring it, etc, and that is taken care of elsewhere (see the units post for more info on that), so the Navigation autoload just needs to return the blocking cell to the caller. If no blocking cell is found, a Vector2 with infinite cells is returned as that’s easy to check for and keeps the type system happy.

# Simplified for clarity

func get_ac_block_point(ac: ActionInstance, is_movement: bool = false) -> Vector2:
	var blocking_objects = get_all_level_objects()
	
    var units_cells: Array = get_other_unit_cells()
	
	for i in range(ac.cells.size()):
		var cell = ac.cells[i]

        if is_movement and blocks_movement_cells.has(cell):
            return cell
		
        # Truncate actions to map bounds
		if !map_bounds.has_point(cell):
			if i > 0:
				return ac.cells[i - 1]
			return cell
		
		var cell_id = astar_grid.get_closest_point(cell, true)
		
        # Can't move through a disabled, ie solid, cell
		if astar_grid.is_point_disabled(cell_id):
			return cell

        # Some level objects block actions
		for obj in blocking_objects:
			if cell == bj.cell:
				return cell
        
        # Units also block actions
		for ucell in unit_cells:
			if cell == ucell:
				return cell
	
    # Return a default Vector2 if no blocking cell is found
	return Vector2(INF, INF)

Wrapup

And that’s how I build and use navigation data in Unto Deepest Depths. The source TileMap has information on the properties of each cell, that information is parsed into an AStar2D instance, and then conditionally used as required by the other elements of the game. Hopefully that helps clear a few things up. If you’re looking to do something similar in your own project, do keep in mind that Unto Deepest Depths has a very specific, and limited, set of features compared to the typical tactics game, and I have designed my systems to meet the needs of this specific project, so don’t worry about it if you need something a bit different.