Before programming any significant part of the mechanics that one day could form a game, from the beginning I knew that I should base everything on a three dimensional map inspired by the legendary Dwarf Fortress. One should be able to manipulate that map as well: from digging into the mountains to building enormous castles. For that I needed to build from scratch a reliable pathfinding system. That led me to realize I would need to reinforce the pathfinding system with a hierarchical one, as I’ve shown in previous articles. Now that the implemented system satisfies me for the most part, I still had to figure out everything that needed to change once the user replaced a tile (of the around 32 thousand I’m working with at the moment). When a tile gets replaced, its movement rules will likely change, and the pathfinding system needs to update itself without blocking the entire program.
Every tile has an associated region number it belongs to, and those numbers get referenced by the edges of every sector. Those edges are used to know whether you can exit from a sector in those directions, and the adjacent sectors reference the region numbers of the sector of origin as well. That means that after replacing a tile, the next pathfinding request needs to receive updated data regarding the involved regions and sectors. Fortunately it’s not necessary to regenerate the corresponding sectors and edges after every tile gets replaced, just before the next pathfinding request. So I can get away with changing dozens of tiles, and I only launch the code that regenerates the corresponding sectors and edges immediately before the next pathfinding request. Months ago I programmed a tasks scheduler that launches programmed tasks when a turn ends.
- Whenever any tile of a sector (16x16x8) changes, it needs to be regenerated, because any change in the region numbers could have invalidated the edges not only of that sector but of the adjacent ones.
- Every single edge of that sector needs to be regenerated.
- From the adjacent sectors I only needed to regenerate the opposite edges. For example, from the western sector I regenerate the eastern edge.
I already had programmed a regions visualized. The following video shows how the regions have changed after creating a few structures.
The tiles replaced involved around three sectors. The regenerated regions understand that the stairs and the inside of the buildings are reachable. The region centers have been moved appropriately.
The following videos show different examples I used to push the limits of the hierarchical pathfinding system. Thanks to one of them I figured a nasty bug in the code that recognized the western edges. It caused some agents to become unable to walk left from one tile to the next, even if they were on an open space in same z level.
Although I’ll have to write some upgrades, for example allowing two agents that block each other’s path to find an intermediate tile instead of just resetting the route, now I can move on to programming parts more specific to the game I wanted to make: the agents’ bodies, or the artificial intelligence that handles finding food, building stuff, etc. I hope the pathfinding system keeps behaving in the meantime.