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.
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.
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.