How can we make it easy for characters to navigate a world that can be edited on the fly?

In Raid30, all pathfinding data is dynamically generated at the same time the map is loaded into gameplay. This means no manual setup is required when creating the map, and any changes are reflected instantly. I will use the level I created as an example in the last devlog to demonstrate how this works.

The first step is creating a series of "navigation nodes" that will be used to work out an efficient route from any point in the level to any other. Luckily, this game is 2D and based on a consistent tile size, making this fairly simple. Initially, a node of tile-size dimensions is placed at the map's origin of (0,0). Next, the node checks each cardinal direction for a wall, and if there is no wall there, duplicates itself. This continues until the entire map's floor space has been covered in nodes. We have now identified every navigable space in the level.

However, to have every free space be included in pathfinding would be highly inefficient, so the next step is to trim these down to only those required. We delete any node which is not either at the corner of a solid object, or on either side of a door.

This gives us the bare minimum nodes required to move to any part of the level. However, we also need to determine specific nodes that are suitable for character's to take cover at. For this, we include nodes which are behind solid objects with an empty space at one or more corners, and spaces behind cover objects like desks. The cover nodes track the relative direction of the cover they are are attached to, so that enemies can place cover in between themselves and the player to use it effectively.

When we include both the navigation and cover nodes, we get this result:

It may not appear we have trimmed down the number of nodes too dramatically, since most of the tiles in this map contain a node. However, we have made a distinction between navigation nodes and cover nodes - cover nodes contain useful information for the enemy AI but otherwise do not perform any other action, making them efficient, whilst the navigation nodes that will be used repeatedly during gameplay have been pared down significantly. This difference is most noticeable on larger, more open maps.

The next step is to check each navigation node, and keep a record of all other navigation nodes that it has a direct link to. We can then create a network of connected nodes like so.

Now, when we wish to have a character navigate to a specific point of the map, we run an A* pathfinding algorithm across this network. Each node will receive a "cost" based on the distance from the specified destination, and the character will move to the closest node currently visible to them with the lowest cost. Once they reach this node, they will then move to the node with the lowest cost again, and so on until the destination is visible to them, at which point they will simply move there directly.

The enemy will then be able to take cover, run to the player's position, or any other kind of movement required by their particular AI.