Performance optimization


Last week I spent some time rewiring the path computation algorithms for the enemy units. There was some scope to save both computation and memory by changing when and how the paths of each enemy unit are computed. The path computation is done by BFS analysis, as is typical for any tower defense kind of game. Once the grid has been computed though, each enemy can use it to compute its path. So far I was computing the entire paths from source cell to destination cell for each enemy and storing them at the start of their lifetime (as you can see in the "before" part of attached visualization). When the terrain changes due to tower addition/removal, this path is discared and new path is recomputed for each enemy unit. This seemed like a waste of resources and that's where I found some scope for optimization.

In the latest version, each enemy unit only computes the path 2 cells ahead of itself. This computation is obviously cheaper and also the results are small in length (the "after" part in the visualization). Therefore the discarding of memory will also be little when terrain changes. Using the heap profiler timeline in Chrome dev tools I could see that the memory churn was visibly smaller with these changes.

This allows the game to scale for larger number of enemy units. This in turn enables possibility of more number of waves with more number of enemy units. a.k.a more fun!

Files

foldwars-v11.zip 699 kB
19 days ago

Leave a comment

Log in with your itch.io account to leave a comment.