Improving the load time- Optimizing A* Pathfinding

One of the biggest issues I noted from the District Arcade was that the load time was absolutely horrible. I haven’t seen the same effect when I run in the Unity Editor, which was strange. Looking in to things, I remembered that I load the distance between cities in the built version, but I skipped it in the editor to save a few seconds. I allowed that bit of code to run in the editor, and proved that in fact that was the issue that was causing the game to take so long to load!

Okay, so I had figured that out, the next question then was, how can I improve it? I ran the Unity profiler, and noticed that I had a very large amount of GC memory. I figured I would try to reduce that memory footprint.

I should add that I’ve open sourced my A* algorithm. This algorithm fundamentally requires that each instance uses a class to represent that data. That whole class was included in the data queue. This could result in huge amounts of data! I decided to reduce the node to something simple that was queued, that pointed to the main node.

These smaller nodes allowed the system to run much faster, using about 10% of the memory! Running this on my computer brought a start from about a minute to about 15-20 seconds, which while acceptable, is still a long time.

Next I worked on threading. I set up the per-calculated data system in it’s own background thread, started at the earliest moment that it can be. This caused some really serious background effects. I had limited threading support in the A* algorithm. While trying to improve it, I realized I wasn’t releasing the mutex after using it. Once I started releasing the mutex, the speed delay dropped to something useable, but still a bit jerky.

Finally, I looked in to optimizing the algorithm itself. Looking at it, I determined that I had quite a bit of space that I really didn’t need to store. I reduced the data by half that is stored, giving even more speed boosts! I can now create a typical world in about 5 seconds! The jerkiness seen above disappeared almost completely!

The bottom line is, when you have something that is taking an absurd amount of time, using the profiling tools available to you, and other tricks to try and figure out how to improve your performance. You can really dramatically improve things!

If you haven’t yet, feel free to like me on Facebook, join my Google Group, subscribe to my Sub Reddit, or follow me on Twitter, where you are likely to get frequent updates! You can also subscribe to the Old Ham Media YouTube Channel, where I post frequent videos showing the progress of gameplay and more! Finally, follow me on Twitch, and help me develop games!