top of page

A* Optimization

After working with pathfinding in a lot of the game projects, but never having the time to optimize the system I built, I wanted to push the system to its limits by adding a ton of moving actors. I’ve always loved strategy games where a lot of units move on the screen and other games that utilize actors with their own separate behaviour, so this specialization project was the perfect time to dive deeper into pathfinding, since the project would be worked on for 5 weeks, half-time.

Goals

My goals in the beginning of the project was to optimize the pathfinding system to be able to handle something from a thousand to a million actors that continuously pathfind, along with building a heatmap to both visually show where most actors are on a map and in use in the calculation of a path, where it would be used to avoid areas on the map that have a lot of heat. In the beginning, I also had some plans which would have made the project much bigger, but they were quickly scrapped. The plan was to also make a traffic simulation that had cars stopping and waiting for others, while other cars used the heatmap to drive on other less occupied roads, but I didn’t want to over scope the project and get bogged down in a bunch of gameplay features.

I decided to use The Game Assembly’s own game engine TGE and the first week was mostly setting up the project and adding in all the basic functionality I needed into the project, which was rewriting my existing A* algorithm to work in the engine and trim its features down from previous projects that made it into somewhat of a blob. Here I also made a nodemap for the pathfinder to traverse and added objects that could use the pathfinder to move around. When the second week rolled around I had also added the heatmap to visually be shown on screen and I started connecting it to the pathfinding algorithm. In week two, I also added a basic collision system which I would use to block objects from moving through one another, but I didn’t use it in the end since it was mostly made for the traffic simulation part of the projects that, I by that point knew would not be finished in the time frame of the project. At the end of week two, I was done with a minimum viable product that I now could start optimization of.

From here on, I will talk more about optimizations and assume you know a bit about the A* algorithm. A common optimization to the A* algorithm is using a priority queue like a heap to process all the open nodes and find the lowest cost one. I started implementing a heap into the algorithm and it worked, but when I tested it in practice it actually performed worse than when I had a regular old sequence container as an open list. In use it was worse as a result of the amount of insertions it had to make to the open list, so it was faster to just search the sequence container for the lowest cost node. This could be because of my nodemap being a grid that the A* algorithm sometimes has to add a lot of connections from a single node or because the open node list never getting too big for a simple O(N) search to be able to handle. I feel like it was good that this optimizations failed, since it really made me aware to always test and measure if an optimization makes a difference or if it actually makes the program worse.

A big part of my optimization was threading the pathfinding along with the heatmap calculation, which helped me a lot in becoming more comfortable around threading and securing that only the thread you want to look and change data is using that data. I threaded my Pathfinder to separately handle all pathfinding on a different thread and used a message queue system to handle all the requests for paths from the different moving objects, which the pathfinder then would process so the main thread wouldn’t get slowed down.

Conclusion

In the end, I’m pretty happy with the project and by the amount of actors it can simultaneously handle. On my mid end computer it can run 100000 moving objects that update their path about 2 times every second with a nodemap consisting of 9821 nodes and still run at about 30 frames per second. One issue I didn’t have time to fix was the frame stuttering that happens when so many object are active, which is caused by the calculation of the heatmap that has to pause the pathfinding in order to update the weight of every node depending on how many objects are on that node.

bottom of page