DevLog #6 - Navigation tech dive

Welcome to our sixth devlog for Red Dust Colony!

This month has been quite eventful for us. A recent move consumed much of our spare time with packing, unpacking, furniture hunting, endless hardware store trips, and painting. Most of our development work focused on bug fixing, resolving colonist AI edge cases, updating older UI elements to match the current style, and adding UI and overlay to the priority tool:

While these tasks were crucial, they don't make for the most exciting devlog material. So today, instead of our usual "what we've been up to" format, I'll take you on a deep dive into our navigation system, which required significant iteration and technical design to get right.

The Challenge

Colonists need to efficiently find and perform work, including using crafting tables, picking up and delivering items, locating the nearest toilet, finding suitable beds, and choosing to spend time in areas that meet their needs (comfortable temperature, ample air supply).

These tasks must be performed quickly. The current map size limit (subject to change) is 400x400, totaling around 160,000 tiles depending on building occupation. Colonists don't simply choose the closest work; they prioritize based on importance. Since different tasks can have varying priorities for different colonists, the number of combinations grows rapidly.

While pathfinding on a map or maze is intuitive for humans, it's computationally expensive for computers. Various techniques exist, but A* is the most commonly used. You can learn about it in detail from this excellent article, but essentially, starting from the initial point, we explore all reachable cells, prioritizing those closer to the target destination.

This approach works well, but if the destination is unreachable, all accessible cells will be checked. This becomes problematic when multiple colonists perform this search multiple times per second.

The game's support for configurable doors means that not all tiles are guaranteed to be accessible by all colonists. This complicates matters significantly but also allows for more interesting behavior later, such as the potential addition of roomba-like robots with their own trapdoors.

Regions

One of our first steps was to split the map into "regions," inspired by a video from Tynan Sylvester about his solution for Rimworld. Regions are collections of connected cells of the same type from a navigation perspective. They're also relatively small, being "masked" by a lower resolution grid.

Since each cell in a region is reachable from any other cell in the same region, the A* algorithm can run on this data. Taking our 400x400 max size map example again, if a region can be up to 12x12 in size, we only need to process 34*34=1,156 regions instead of 160,000 cells – a significant reduction.

Doors

While navigation within walls, doors, and outside areas is consistent for every colonist, the inclusion of doors changes navigation data based on permissions.

To account for this, we consider tiles under doors as a different type than those that aren't, placing them in separate regions.

Rooms

Since data outside of doors can be shared between colonists, it makes sense to group regions. We call these groupings "Rooms." Rooms, along with regions and tiles, maintain a ledger of accessible elements within them, such as pickup and dropoff points for items, crafting locations, bed access points, and pretty much anything else related to AI.

All cells within a room are connected, meaning navigation is definitely possible between any two cells in the same room. However, this doesn't mean that cells in different rooms aren't connected. To answer this question, we need to know which colonist is asking.

Islands

Combining rooms and doors, we introduce the concept of "Islands." An island is a collection of all rooms accessible by going through doors that a colonist can use. This means that colonists with different permissions use different islands.

Let's look at an example with three colonists, some doors, and an airlock:

Beatrice can freely walk everywhere, so from her perspective, everything is on the same island.

Caroline isn't allowed through the airlock, so from her point of view, there are two islands: one for the outside and one for the inside. She can walk through both but can't move between them.

Finally, we have Ethan. Unlike Beatrice, he can use the airlock but isn't allowed through the two marked doors. This means that from his perspective, there are three islands: one containing two rooms, the hallway, and all of the outside, and two separate islands for the blocked rooms.

With this system, we can quickly determine if there's a path between two points without intensive calculations, assuming we know which colonist is asking. Like cells, regions, and rooms, islands also keep a ledger of all interaction points, allowing us to quickly find, for example, all available beds for a given colonist.

One Final Trick

From any tile, colonists can travel in 8 directions.

Straight directions are straightforward: if there's an obstacle, traversal is prohibited.

With diagonals, the condition is more complex. Traversal is prohibited not only when there's an obstacle on the target tile but also when there are obstacles in the adjacent tiles.

Here's the trick: instead of checking for obstacles around each tile during navigation, this data is precomputed. When navigation changes (e.g., a building is constructed), all adjacent cells are checked, and for each of the 8 directions, we store the end result. This works exceptionally well because computers work with powers of 2, and 8 is exactly the number of bits in a byte, the smallest storable data unit.

The most complex aspect of this system is maintaining all this data. There are numerous details to keep track of for quick navigation checks and path creation. Many changes occur throughout the game: terrain mining, building construction and deconstruction, and door permission changes all affect the data. Since these updates can happen multiple times per second, the system needs to run fast. With every small change, only the data around the change gets invalidated, reconstructed, and stitched back together. Rooms can grow, split, or merge.

While complex, this combination of techniques allows the game to perform these calculations very quickly. There's still room for improvement, but navigation is not currently the bottleneck in our system.

Looking Ahead

We're excited about the potential this navigation system unlocks for Red Dust Colony. As we continue to refine and optimize our game, we'll keep you updated on our progress and any new features or improvements we implement. Thank you for your continued support and interest in our project. Stay tuned for more updates!