One of the classic problems with the A* pathfinding algorithm that Rimworld (and nearly every other remotely similar game) uses for pathfinding is its behavior when there is no path from source to destination. It tries to find a path to the destination, and just keeps trying, scanning square after square, until it has covered the entire map and finally realizes there is nowhere else to go. This massive computational burden causes a performance dip which manifests as a hitch in gameplay as that one frame takes ten times longer than the others to render.

This can become a serious problem in EC. Say you put a weapon in a room with no entrance. Raiders attack. Your colonists, looking for a weapon, try to path to the inside of the closet. And they fail, and fail, and fail, and the game grinds to a halt.

This problem is finally solved in EC.

Every walkable square in the map is marked with a zone index number. We use an optimized flood-fill algorithm to go over the map and fill out each walkable region with the same zone index. As long as we keep our region indices updated, all a colonist has to do is check that the region index where they’re standing matches the one where they want to go. If they don’t, don’t try to path. We thus avoid the A* performance hit on unpathable destinations. The regions look a bit like this (created with random walls for testing purposes):

As a comparison, here’s a version with an earlier visualization. The more I learn about game programming the more I understand that writing good visualizations for yourself is key. It takes a while, but the payoff in ease of debugging is worth it.

And as a random bonus shot, here’s what it looks like in the Unity editor view. EC actually renders in 3D, and sometimes looks snazzy that way. I may end up exploring the 3D angle more.

Now the key challenge is making sure these regions stay updated. I can regenerate them all in about 5.5 milliseconds right now on a 200×200 map, which isn’t bad. But that’s not good enough to do every frame and forget about it. I’ll need to detect changed conditions like walls being built or blown up and regenerate the local reachability indexes. The world of EC is rather unstable, what with the constant threat of colonist psychosis and marauding pirates. So I expect reachability to change a lot.