In games such as RimWorld, Oxygen Not Included, Space Haven and Red Dust, having a predictable building system is crucial to the design of the game as it allows for modularity of base design, and consistent setup replication. This is achieved using a grid system which in turn opens up the doors to many possible design choices and optimisations. When it comes to navigation, Unity comes with a built in solution that works on arbitrary meshes. Because of this requirement, the functionality is somewhat limited. 

Red Dust implements a custom navigation system that has better performance, and works even when the navigation agents have different permissions, like a colonist not being allowed to use a certain door or airlock. Fast queries can also be made, for instance, a colonist locating the closest source of food, or the closest unused bed. In the following article I will go over how this was implemented, why certain choices were made and what could still be improved in the future.

Typically when people think about navigation they think about path finding and for the most part that's correct. The term navigation applies to a wider range of things but the data structures needed are generally the same.

Let's take a look at the structure for the navigation cell:

‍

‍

Flags are set by grid entities like walls, buildings and doors. Walls and terrain tiles will typically set the navigation flags to fully blocked while doors will block navigation on their sides and allow navigation through them. While flags are easy to set, they are not particularly easy to use. For instance, let's say a navigation agent wants to travel in the North-West direction. This can be blocked by either a North flag or a west flag. A better way to do this is to use a byte, which happens to have exactly 8 bits that we need for the navigation directions, 4 cardinal and 4 diagonal.

To transform navigation flags to the neighbours byte we first need to gather all the flags around each cell. Since we don't want to allow navigation outside the map we consider cells outside it as blocked:

‍

‍

Now we go through each direction and check if the flags are set. Navigation is blocked if either the current cell or the neighbour cell has a flag to block it. This ends up being easier for cardinal directions since we only have two checks. For instance when we check navigation to the west direction, we need to check the current flag for the west flag and the west neighbour cell for the east flag.

‍

‍

In order to do path finding on a grid we start from a point and then expand towards the target position. Expanding is done using a frontier that's typically implemented as priority queue with the priority defined as the heuristic between the start position and the end position, in this case just the diagonal distance. There are multiple heuristics that yield interesting results and I strongly suggest reading further into this for people who are interested. Without using a heuristics function we end up with what is called a flood fill which can be very useful if we don't know the position of what we're searching for.

The maximum map size in Red Dust is 512 by 512 which means there are 2.6 million cells that potentially need to be processed. Suppose a colonist (navigation agent) tries to find the path to a cell that is inaccessible. A* could quickly turn into a needless flood fill that would process all the tiles on the map for nothing. In Red Dust this would not happen because of other checks but the potential for large numbers of processed cells is there. It would be much better if we could somehow process groups of cells instead of processing them one by one.

‍

To do this we first split the map in chunks of 12 by 12. The size of the chunks could be lower or higher but this size has performed the best when doing profiling. If we'd process the chunks instead of the cells when navigation needs to be done we'd only have to process a maximum of 1849 chunks which is 0.7% of the number of cells. This is obviously not going to be this simple but splitting the map in chunks is a good starting point as it allows us to split the problem in something more manageable.

‍

Chunks alone aren't very useful. We need to split the map in groups of cells that are connected to each other, i.e, cells that have a guaranteed path to any other cell in the group without leaving the group. In Red Dust, these are called Regions. They are created in the space of the chunks and when needed multiple regions can exist in the space of a single chunk. In order to create one, we use the starting map position to perform a flood fill, while not stepping outside the limits of the chunk.

‍

‍

Extents here is the bounding box of the region while limits is the chunk. We make sure to clamp the limits so we don't get out of the bounds of the map and then we apply a flood fill on the starting position continuously adding cells to the list. The region type can be either None, in the case of blocked cells, Normal for cells that can be traversed or Portal for doors and airlocks but more on that later.

‍

‍

In order to used regions instead of cells for navigation, we need to know how they are connected. To figure this out we need to look at what connected regions share: Edges. If two regions have the same edge it means they must be connected so this is an ideal candidate to use as a key for a look up table. Our grid system unfortunately does not allow the use of edges since we can only refer to positions of cells but if always consider the cells on top for horizontal edges and the cells on the right for vertical edges we can get around this.

The code for edges is fairly simple. We just need to know the starting position, the length and the direction. Since we're going to use these a a key for a lookup table ( a C# Dictionary) we also compute a unique Hash

‍

‍

In order to create these edges, we go through all cells in a region and check if they are at the edge. We do this for all 4 directions. For instance when we look for an edge in the north direction, we check that the cell above the one we're checking belongs to a different region. When we find a cell that's at the edge, we go sideways and expand as much as the cells allow it. If the cell is not at the edge we add it to a set so we don't check it again in the future.

‍

‍

The code for this is a bit long so let's go over it bit by bit:

‍

We declare our usage sets for each of the 4 directions and we call the Sweep function on every cell for each direction. Normally these are reused in order to avoid extra allocations but they are as they need to be declared here.

‍

‍

In the FindEdges function, we check if the cell was already processed, or if it's invalid. If these checks fail it means we've found a cell that is at the edge. From here we expand on one side and the the opposite side keeping track of the count of cells. If we're checking for top edges we need to expand on the left and right. For this cycle clockwise through the directions and store that in "cwDir".

‍

‍

After this we go ahead and set up the edge. We make sure to apply the offsets for the top and right edges and and we update our lookup tables. If an edge already exists, it means that there's another region that shares it, and in this case we have a link

‍

‍

Here's the CheckLocation function that verifies if a position is or not on an edge:

‍

Now that we have our regions created and linked together using edges we can use them to calculate paths at a region level.

First we create our normal data structures, like the frontier priority queue, costs lookup table and origin lookup table:

‍

‍

Next, we start going through the frontier and check if the current region contains our end point. If so, our search is over and we can generate our path using the origins lookup table:

‍

‍

If the current region does not contain the end point it means we need to keep looking so we go through each of the current region's neighbours and add them to the frontier. We use the diagonal distance from the center of the region to the end point as the heuristic:

‍

This concludes the first part of the article. Using regions significantly speeds up the navigation speed. We can also use regions to store important locations such as items, work places and leisure activity places for our colonists. Instead of searching for such things using a grid we can quickly find out which of these locations are actually closer to the colonists.

The system presented here was inspired by Tynan Sylvester's video about the region system in Rimworld: https://www.youtube.com/watch?v=RMBQn_sg7DA . Back when I wrote this code I did quite a bit of research but his video stuck to me the most, so much so that this is why the term "Region" is used.

The code presented here was slightly altered in order to simplify it since some of the details were left out.

In the next article we'll talk about rooms, islands and navigation groups. These are all needed for the logistics system in Red Dust to work as intended.