I've done some tests to see which data structure is the most adapted for path finding. To keep a track, I will post the results here.
First, what I've done :
I've built a map based on the test small map but with every tile digged. It is a 50x50 tiles. There are only gold tiles on tiles y = 25 (with 1 holes on x = 3). I will upload the map with my next pull request.
Then, I've added in the code 2 loops with calls to GameMap->path function. The first that goes from tile 1-1 to 3-3 and the second from tile 1-1 to tile 49-49. On the first iteration, the path is displayed in the logs to make sure it is correct.
The first path (from 1-1 to 3-3) is called 300000 times and the second (from 1-1 to 49-49) is called 100 times.
First, I've tried to use for openList and closedList different data structures (sorted and unsorted). When using a sorted datastructure, I've removed the code that searches for the smallest AStar. For sorted vector/list, I've used std::sort after inserting an element in openList.
The results are :
With unsorted vector :
1-1 -> 3-3 : 21300ms
1-1 -> 49-49 : 40895ms
With sorted vector :
1-1 -> 3-3 : 22804ms
1-1 -> 49-49 : 43160ms
With unsorted list (current one used) :
1-1 -> 3-3 : 28471ms
1-1 -> 49-49 : 48191ms
With sorted list :
1-1 -> 3-3 : 51613ms
1-1 -> 49-49 : 53875ms
With multiset :
1-1 -> 3-3 : 48635ms
1-1 -> 49-49 : 74584ms
The most efficient data structure seems to be vector. Now, I'm gonna try to use some maps (at least for the closed list) to see if it is better. I bet we will end up with a situation where small paths will be faster with vectors and big paths with maps. We might have to decide if we keep only one datastructure for every cases or if we use others. I will post here the results.