Lately, I’ve been working on a new game project which is very different than all the other ones I’ve done so far. I’m planning on waiting until it gets a little further before I write about it in detail on this blog, but I ran into an interesting technical challenge and I’d like to discuss how I solved it.
To implement the game mechanics I need a graph of nodes, with various connections between each node. I have a need to find the shortest path between two nodes, where the path is calculated by the sum of the length of all connections as part of the path.
I started out with a simple recursive algorithm that started from each node and worked backwards to find all possible paths to get to it, and used a map to store the best connection to move, given a certain intermediate node and a certain destination node. This worked really well, although after around 13-14 iterations on a graph with many connections it started taking over a second to compute and them getting exponentially worse.
One option was for me to search for a more proper algorithm to find the shortest path, and I am sure this has been perfected by programmers over the last few decades. But I had a secondary requirement to also store all non-optional paths as well, so some of those algorithms probably wouldn’t suffice.
Looking at my recursive function, I realized that there really wasn’t much going on in terms of sub-functions it called that do any significant calculation. If there was, I could try to optimize those or cache up some result. But the question remained – what was taking up all the time?
Looking at the function again I saw that I was passing four different arguments into it. If you have ever studied assembly, you probably know that there are several instructions just to push and pull each of these to and from the stack, and since the function is called so frequently I thought that maybe this added up to a big chunk of the total time.
I decided to test my hunch by making all the parameters into global variables. I purposefully didn’t use class variables since I knew there would be extra lookups required, translating to extra work for the CPU.
It was a bit of work to make this transformation, since for non-pointer variables I had to manually save the state before calling the recursive function, and then re-set it. But this was only for two of the variables since the other two were pointers anyway which were supposed to change (one was the map which stored the nodes that had already been traversed so far, and I already had code to adjust that when returning from the recursive function).
The resultant code was a bit harder to follow, but the performance was significantly better. For the test case I was using I was able to get several more iterations before it got significantly slow (>1 second), if I remember correctly to at least 19-20 iterations.
If I keep adding nodes and connections eventually it still gets slow again, but I will probably put limits on these anyway so I may be safe with this solution for the time being.
Although I enjoy designing games from a high level, after many years of coding I still enjoy these types of algorithmic challenges, and the satisfaction of a well-tuned function.
Mobile Game Development 