Improved Pathfinding and Room Detection

I stopped doing any development on Sycamore Isle for about a week and instead played the game RimWorld quite a bit. Whilst playing I was impressed by the speed of the pathfinding and the “intelligence” of the A.I. and it made me realise that I was going to have to do a lot better. As a result I have now completely rewritten my pathfinding code and I’m seeing results up to 100x faster. I’ve decided to write up exactly what I have done in case this benefits anyone.

The first simple improvement I made was to use a binary heap instead of a regular list to manage the nodes parsed during the A* pathfinding algorithm. There are many implementations of a binary heap in C# out there so instead of writing my own I went with this one in the end, which seemed to give a massive improvement. It works by ensuring that the heap is sorted by the chosen value. This means I can just pop the best node off the top of the heap rather than searching through the list each time to find the best node to travel to out of the nodes that I’ve processed.

The other issue I had was to do with unreachable paths. In Sycamore Isle it just blindly parsed every single square in the map to see if it could find a route – which is exactly how A* pathfinding works. Before I introduced the priority queue this took quite a while on a map of only 100x100. After I introduced the priority queue this took way less time, but as the size of the map increases this is going to be an issue again. I noticed in RimWorld that when you asked someone to go to somewhere unreachable they immediately knew they couldn’t get there – clearly something magic was happening. Fortunately, Tynan, the RimWorld developer created a video which gives out a lot of detail on how he does this – as well as covering a few other optimisations which I’ll cover shortly.

Firstly Tynan splits the world into ‘rooms’, areas of the map which are inaccessible from other areas, and gives these a unique number. When a destination is in a different room he can then immediately state that there is no path by comparing these numbers. This is now something I have implemented as well and it works extremely well. I needed to be able to detect rooms at some point anyway so this is quite useful. He doesn’t explain how he detects rooms but I’ll cover my method shortly.

More interestingly, Tynan also explains how he splits the map into small ‘sectors’ which can be used to improve both the performance and intelligence of finding the nearest object of a type. Whilst I had no major speed issues with this, I think it is a problem I’m also going to have further down the line so it made sense to implement a similar system. Again, he doesn’t explain how he creates these sectors so I’ll cover how I did this myself. My method may not be the best, but it seems performant enough and definitely works.

The first thing I do is use a simple flood fill algorithm to split the map into a series of at most 8 x 8 blocks (there’s some good pseudocode for a basic flood fill algorithm on Wikipedia which I used). If an adjacent block is marked as ‘solid’ (i.e. it can’t be walked through) then a new sector is started, joining up with any other solid blocks it’s attached to. Again, this conforms to the sector grid size so one solid wall could be split up into numerous sectors. This is all done within a while loop which iterates through every block while there’s still blocks which don’t belong to a sector. Once this is all done you end up with a map which looks somewhat like this, where each colour is a different sector:

Now that the sectors are sorted it becomes a lot easier to group these together into rooms. To do this I run another similar flood fill process and store all ‘traversable’ and ‘non-traversable’ adjacent sectors for each sector. These are easily recognisable by seeing if the nodes in each sector are ‘solid’ or not. I can now just recursively loop through the list of traversable sectors to find my rooms - it’s a simple as that. The second flood fill I do is probably a bit unnecessary and I’m sure there’s a smarter way of doing it (Tynan mentions storing hashes for the edges of each section and matching them up), but it doesn’t seem worth the time as this process will actually only run once and isn’t that intensive. Once that’s all done you end up with this, where each colour is a different 'room'. Note that I class walls themselves as their own room:

Performance wise the process takes around half a second on 1000 x 1000 map, which is about as big as they’re likely to get. This only runs at the start of the game as well, so I’m pretty happy with that. The tricky bit comes when you update a block as you want to avoid reprocessing the whole map. Instead I only update the sector, and adjacent sectors if it’s on the edge, that the updated block is in. I haven’t worked out a smart way of re-joining the adjacent sectors back into their existing room without re-doing the room they’re in, but it still seems fairly quick – even when the “room” is the whole map – taking around 30-50ms. I’m not quite happy with that but it will do for now. On smaller maps, or within smaller rooms, this is significantly faster, and it will only update when there’s a block change from solid or back so I’m not expecting this to be an issue. It will also run on a separate thread so it shouldn’t cause any framerate drops.

As mentioned above this has actually made the pathfinding up to 100x faster in certain situations so it was definitely worth doing. Now that I have room detection in place I can also start making smarter AI which can detect different types of rooms and adjust their behaviour accordingly (for example, dining rooms, bedrooms etc.) which will be my next task. I actually initially wrote this code in a small MonoGame project which I'm happy to share with anybody who wants it. Feel free to also message me on twitter if you also want more details.