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 !
