Boost Graph - Very slow Astar on big graph

Currently I have some trouble with my Pathfinding system which is "anormally" slow on my big graph:

My Graph

Graph properties: 16814 vertices / 61512 edges
Graph is directed.
Each vertex has an ID of subgraph (Island ID) → No solution between subgraph BUT ALWAYS inside same subgraph.

Each vertex of graph is defines by:

type (rock, sand, ...).
height

Last rule, earth is not connect to ocean (so we have many sub-graph).

My Astar configuration

My heuristic is very classic: I compute dot between current vertex position and goal position.

I don't have a pre-compute weight for edges. I use "complexe" algo (depends of speed of walker, kind of ground, if we go up or down)

float PathWorld::updateWeight(const Agent& agent, const EdgeInfo& edgeInfo) const
{
    const Agent::Navigation& navigation = agent.getNavigation();

    const auto& fromTerrain = edgeInfo._from->_terrain;
    const auto& toTerrain   = edgeInfo._to->_terrain;

    const float mean = (navigation._speed.at(fromTerrain._type) + navigation._speed.at(toTerrain._type)) * 0.5f;
    const float diff = BT::Maths::clamp((1000.0f + toTerrain._height - fromTerrain._height) / 1000.0f, 0.5f, 2.0f);

    return edgeInfo._distance / mean * diff;
}

Issues

Currently, the execution time take less than 1ms to 1 second when I compute one path. The path solution is just between 8 or 80 vertices and I don't have proportionnal time. (So 8 vertices path can take 1 second and 80 vertices path take 1 ms).

I make a quick profiling with visual Studio: boost is my bottleneck.

Code and testing data

All complete code and testing data can be found on my GitHub.

https://github.com/Rominitch/myBlogSource/tree/master/DEMO/TestPathfinding

The easy/small demo don't suffer of my issue. Just complexe case. All graphes was generated by same program (not published).

My Testing program output

My testing program is really dummy: - I take a node to start into my graph - I take XXX nodes after this (using index) and compute path.

Outputs:

Statistics:
 Start node: Ocean H= 0 SubGraph= 2
 nbValid: 2053/15000   (valid path / number of path computed)
 min / max: 1/75       (number of vertex in path computed)
 min time for one path: 0 ms
 max time for one path: 7 ms

Statistics:
 Start node: Forest H= 100 SubGraph= 1
 nbValid: 1420/1500
 min / max: 1/76
 min time for one path: 0 ms
 max time for one path: 558 ms

Statistics:
 Start node: Swamp H= 50 SubGraph= 1
 nbValid: 601/1000
 min / max: 1/51
 min time for one path: 0 ms
 max time for one path: 1246 ms

Statistics:
 Start node: Clay H= 300 SubGraph= 22
 nbValid: 138/15000
 min / max: 1/12
 min time for one path: 0 ms
 max time for one path: 0 ms

Questions

Where is my issue ? (bad boost using / bad graph / boost limitation)
Boost is a good choose to resolve pathfinding (another library) ?
Can we optimize my graph data (best boost algo, reduce data duplication, ...) ?

Thanks !

Solution

Ok ! I found my issue.

Currently, Bug was inside my heuristic implementation which doesn't compute square of distance between current node and goal. It's just make a "quasi random" heuristic.

Moreover, in my case

boost::astar_search

is less performant than

boost::astar_search_tree

Finally, I optimized my graph too (remove dummy edges).

New stats:

Statistics:
  Start node: Ocean H= 0 SubGraph= 2
  nbValid: 2028/15000
  min / max: 1/145
  min time for one path: 0 ms
  max time for one path: 13 ms
  mean: 0 ms
  Global time: 1845 ms

Statistics:
  Start node: Forest H= 100 SubGraph= 1
  nbValid: 1420/1500
  min / max: 1/92
  min time for one path: 0 ms
  max time for one path: 13 ms
  mean: 0 ms
  Global time: 1232 ms

Statistics:
  Start node: Swamp H= 50 SubGraph= 1
  nbValid: 601/1000
  min / max: 1/50
  min time for one path: 0 ms
  max time for one path: 11 ms
  mean: 0 ms
  Global time: 504 ms

Statistics:
  Start node: Clay H= 300 SubGraph= 23
  nbValid: 138/15000
  min / max: 1/17
  min time for one path: 0 ms
  max time for one path: 1 ms
  mean: 0 ms
  Global time: 115 ms