3. pathfinding (A*, heat map)

The next step is adding enemies and using pathfinding so they can find their way to my base. Which will be looked at in this post. For now I am cutting back on the amount of code I post, because it may show too much of my project and is mostly outdated already. This means I will treat this more as a log than a tutorial.


In an earlier (c#) project I implemented an A* pathfinding class which I translated to Java. For each enemy I spawned I calculated the path to the nearest distance tile. Turns out I implemented Dijkstra's instead of A* (actually A* behaving like Dijkstra's) which kind of clogged my entire app when using ~50 enemies (oops). After fixing this it went a lot better, but still awfully slow. For each enemy object (using the OOP principle) I searched a path, saved it locally (in the object) and traversed the path at a certain speed. I implemented the path traversal by looking at the next node and moving the NPC towards it.

A* saving paths

All this calculating the paths and throwing them away shortly after was a huge waste, so for each starting location I saved the path in a Map. When the path had already been calculated it simply looked it up and retrieved it, if not it would still calculate the path. This sped up my code a bit but I was still not satisfied.

I rethought my approach and wondered why I would actually use A*, turns out there were no good reasons. From my Artificial Intelligence course I remembered using a heatmap in Google's Ant Challenge, that seemed like a better solution.


In order to test this idea I quickly created a new project: a heatmap creator, which takes a map as input (the .txt file for now) and spits out a nice heatmap (also a .txt file). Why this way? It would be a waste of resources to continously calculate the heatmap when loading a map. The map can always be altered during gameplay or anything.

Somewhere in a later stage, when random maps are being created I would have to calculate the heatmap while loading or creating the map but that should not be an issue.

This change improved my game's speed considerably, but also had me change a LOT of code. I do have a back up (edit: faulty back up, shit) but it was a rather poor one (I commented out all the A* code and wrote the Heat map code inbetween). Once I am back at my desktop I may sort through all the code and get the A* version working to put some benchmarks for A* here.

Some benchmarks

Note: for these benchmarks I used my actual code using an Entity System (which I will post about later),  Fog of War, without movement and improved drawing code. I may update the code from the earlier posts when I made some more progress with my project. They are also only useful when comparing them with the A* version.

For all benchmarks I ran the game for 5000 frames and created one enemy every 5 ms, up till 500 total.

Laptop (Acer Aspire 6935)
time/frame in ms ~0.18 ~0.18 ~0.17
frames per second 551 546 578
HTC Desire HD
time/frame in ms 19 22 19
frames per second 51 44 50
First generation ASUS transformer
time/frame in ms 13 13 13
frames per second 78 78 78
time/frame in ms ~0.08 ~0.08 ~0.09
frames per second 1151 1196 1071

The results are not bad, but I noticed quite some garbage collections in LogCat. I have removed many causes of the recurrent GC earlier by removing certain allocations or recycling variables. The cause of these GC must be the creation of enemies in my Entity System.

Rounding up

In this post we have moved away from the world creation for a bit and focused on enemy creation and pathfinding. At first I tried using A* to let enemies find the best path to their destination, but this was too slow. After improving A* by saving the used paths the results were still far from optimal so I switched to a heat map, which saved me a lot of processing power.

Though, the frame rates are still a little low on the Desire HD. In the next post I will take a small detour and perform some optimizations.

comments powered by Disqus