AStar optimization

[hwoarangmy]

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.

[Danimal]

i remember seeing something about this, ill look for it:

http://qiao.github.io/PathFinding.js/visual/

[hwoarangmy]

http://qiao.github.io/PathFinding.js/visual/

Interesting

As expected, the results are :
unsorted vector for openList and map for closedList :
1-1 -> 3-3 : 26653ms
1-1 -> 49-49 : 15815ms

map for openList and closedList :
1-1 -> 3-3 : 34815ms
1-1 -> 49-49 : 16561ms

So far, unsorted vector seems to be the best for the openList. Then, for small distances, vector is better for closedList. But for far distances, map is better for closedList.

[Bertram]

Heya

Interesting tests. I don't really know the code change you've done to use maps and vectors, but this typically a situation that makes me wonder whether you could use std::set instead of maps. Might give an interesting effect for far distance in closedList.

Just my two cents, though. Good luck on that.

[hwoarangmy]

I've tried with multiset and the performances were awfull. It seems like a sorted list is not the best in that case.

[Bertram]

Ok, good to know.