One challenge I’ve encountered while working on Stone Monarch has been the implementation of pathfinding. Unity comes with a built-in pathfinding solution, but it really only works on static environments. In an RTS game, the environment is procedurally generated before each game and it is constantly changing as players build new buildings.
One of my guidelines while working on this project has been to re-use existing frameworks whenever they fit my needs instead of writing everything from scratch. Although it’s rewarding to build your own game engine from scratch, my goal is to finish the game and I don’t have enough free time to do unnecessary work.
I decided to use Aron Granberg’s A* Pathfinding Project as the basis for the pathfinding engine for the game. If it had worked out of the box, this would be a pretty boring blog post, but there were a lot of challenges to overcome to adapt the project to fit my needs.
A* Pathfinding Project comes with it’s own navmesh implementation, but like Unity’s implementation it doesn’t work well when the environment is constantly changing.
The fastest graph type to update is the grid graph, but it wouldn’t work for Stone Monarch because I need pathfinding to work in 3D space. The layered grid graph might have worked in a sort of OK way, but it still doesn’t allow for arbitrary elevation changes and it would have really limited the game design.
This left the most generic graph type, the point graph. It uses a Unity GameObject to represent each point in the graph. This allows for enough flexibility to represent pretty much any pathfinding scenario, and it would allow me to easily store pathfinding points along with prefabs for buildings.
Unfortunately, when I first did a test generating a point graph, the game took several minutes to start, and thereafter it ran at an extremely poor frame rate. I needed to use around 16,000 pathfinding nodes to represent just the points for the starting terrain and apparently that was too much for my computer to handle. After a bit of debugging, I figured out that the slowdown wasn’t so much from the pathfinding algorithm itself as from having so many GameObjects in the scene. There is a lot of overhead that comes with a GameObject that isn’t really being used when it represents a pathfinding node.
An example of pathfinding nodes in the game. Note the ability to go up ladders and walk on the top of structures.
Instead, I modified the point graph to accept lists of Vector3s as nodes instead of GameObjects. I still wanted to be able to position the graph nodes as GameObjects in my prefabs, to keep the workflow for adding new buildings simple. To do this, I made buildings read in the positions of their pathfinding nodes when they are instantiated, and and then destroy the corresponding GameObjects. Over time, this keeps the number of GameObjects low. The terrain, as a special case, generates all its pathfinding points from the terrain data and never creates GameObjects.
Each building has a unique id, and it passes that id to the pathfinding graph along with its list of points when it is instantiated. The graph keeps track of this mapping in a dictionary, so that when a building gets destroyed it can easily find the graph nodes that need to be deleted along with that building.
The pathfinding set up for one building. The blue dots are pathfinding points that will get deleted after they are ingested into the system.
This method was really effective in reducing the cost of using a point graph. I was able to eliminate frame rate issues and significantly reduce the time taken for the initial scan and subsequent updates.
As the game keeps getting more complex, I’ve continued to run into issues with update speeds from time to time. Aron Granberg has done a good job of optimizing the hottest paths of the code, but as I keep getting more nodes in the scene I keep finding new areas that need to be optimized. Since I only have to support this one game (and not a framework for anyone to use), it’s easier to find performance shortcuts that fit my specific use case.
Despite my continued modifications, having a working system from the start that I can swap parts out of as I go has been a big advantage in keeping the game playable. I can iterate on it when necessary without getting distracted for too long. It also really helped to have a working example of a pathfinding system to learn from.