I recently posted about some preliminary results for my prototype algorithm, I now have the final results for both BGMAPs and my own set of RTS style game maps. Both sets of maps were sized at 512×512. The RTS maps are simple island style maps which I made more complex that the average RTS map found today just to increase the difficulty of the problem. In increasing the complexity I’ve also reduced the length of straight line paths available at which my prototype excels in that way I’ve handicapped it a little. Even so on RTS style maps my silly algorithm kills A*, furthermore there the memory costs are over 10x lower than required by A*. Unfortunately my RTS maps are artificial and so I cannot state that my approach will work beyond a doubt in real world RTS maps (even though I’m pretty sure it would ).
The initial prototypes I presented had some flaws and were not complete algorithms in the sense that they wouldn’t always return a solution if one existed. My new versions are complete in that sense. There was a lot of tweaking, prodding and changing necessary to achieve this and the search times have gone up marginally.
The performance of the prototypes isnt bad on the BG maps test set but unfortunately the graph doesnt show the full picture, there are certain rare cases in which the solution returned by my approach is GROSSLY sub-optimal (over 100% suboptimal in fact) and the time take to find this “amazing” solution is nearly double the time needed for A*. This poor behavior is due to the spatial layout of the BG maps, which focus on numerous dead end winding tunnels.
I would like to investigate the efficiency of the algorithm within real world RTS maps as well as on FPS maps so if any game devs reading this post can send me some top down JPGs of their game levels I would really appreciate it. I now just need to finish writing up my last chapter of my thesis and submit it. I will be posting the full thesis on this blog which will include all the necessary info on my prototypes which I’m naming the Spatial A* algorithm.
PS! it is necessary to mention that these results are pre-smoothing and so the path optimality will be greatly improved with a post-processing smoothing step.