Final Simulation Results


Final Simulation Results for BGMAPS benchmark

Final Simulation Results for Custom RTS Maps

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.

About these ads

About Bobby
I'm a programmer at Ubisoft. My work interests include Animation and Artificial Intelligence. All opinions are my own!

One Response to Final Simulation Results

  1. Brandon says:

    Awesome post. I’ll be sure to bookmark your blog.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: