Boost Graph - 大图上的 Astar 非常慢

Question

目前我的 Pathfinding 系统遇到了一些问题，它在我的大图上 "anormally" 很慢：

我的图表

图形属性：16814 个顶点/61512 条边
图是有向的。
每个顶点都有一个子图的 ID（岛 ID）→ 子图之间没有解，但总是在同一个子图中。

图的每个顶点定义为：

类型（岩石、沙子……）。
身高

最后一条规则，地球没有连接到海洋（所以我们有很多子图）。

我的 Astar 配置

我的启发式非常经典：我计算当前顶点位置和目标位置之间的点。

我没有预先计算边的权重。我使用 "complexe" 算法（取决于步行者的速度，地面的种类，如果我们向上或向下）

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;
}

问题

目前，当我计算一条路径时，执行时间不到 1ms 到 1 秒。路径解决方案仅在 8 或 80 个顶点之间，我没有按比例计算的时间。（所以 8 个顶点路径可能需要 1 秒，80 个顶点路径需要 1 毫秒）。

我用 visual Studio 做了一个快速分析：boost 是我的瓶颈。

代码和测试数据

所有完整的代码和测试数据都可以在我的GitHub.

上找到

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

easy/small 演示不会遇到我的问题。只是复杂的情况。所有图表均由同一程序生成（未发布）。

我的测试程序输出

我的测试程序真的是虚拟的： - 我从一个节点开始进入我的图表 - 我在此之后使用 XXX 个节点（使用索引）并计算路径。

输出：

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

问题

我的问题在哪里？（错误的提升使用/错误的图表/提升限制）
Boost 是解决寻路问题的好选择（另一个库）？
我们可以优化我的图形数据吗（最好的提升算法，减少数据重复，...）？

谢谢！

Answer 1

好的！我发现了我的问题。

目前，Bug 在我的启发式实现中，它不计算当前节点和目标之间距离的平方。它只是使 "quasi random" 启发式。

此外，就我而言

boost::astar_search

性能不如

boost::astar_search_tree

最后，我也优化了我的图形（删除虚拟边）。

新统计数据：

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

Boost Graph - 大图上的 Astar 非常慢

Boost Graph - Very slow Astar on big graph

c++

boost

graph

boost-graph

我的图表

我的 Astar 配置

问题

代码和测试数据

我的测试程序输出

问题