*** UPDATED ***
Added JPS information, I added some information about the implementation in another post, be sure to check it.
Quite some time ago I released a C implementation of the A* algorithm using grids as the graph and a LinkedList for the OpenList, the topic can be found here:
After that I got really busy with a lot of different work and couldn't really touch the code for quite some time.
Recently I managed to put some work on it and implement a version using a binary heap for the open list, as well as a version that uses memory pooling. The pool would increase its size by 4096 * struct size each time it run out of elements.
My objective with this post is to show the performance gain you can expect to achieve by optimizing an A* implementation, so that people can decide if they should optimize their own. I won't release the code as of now because it is still a bit ugly and it depends on a container library that I use (it has no package yet, so people would need to compile themselves).
The tests were run on a core 2 duo 8400 3.00GHz, the code runs on a single thread.
The OS used was Ubuntu 12.04 32 bits.
All the times are in microseconds (10^6 = 1s).
Test on a random generated 64x64 map.
JPS + Pool + Heap: (first path) 118 | (following paths) 117.
My conclusion would be that optimization would be important only if your paths can get big. I used the list based version on a prototype dungeon game (something like a gauntlet), the monsters would only aggro players up to 20 squares distance, and the performance was not a issue at all.
Comments, questions and suggestions are always welcome.
Edited by KnolanCross, 20 January 2014 - 06:58 AM.