c++ - Boost Graph-大图上非常慢的Astar

目前，我的寻路系统遇到了一些麻烦，该系统在我的大图上“通常”很慢:

我的图

图形属性:16814个顶点/ 61512边

图是有向的。

每个顶点都有一个子图ID(岛ID)→同一子图内的子图之间始终无解，但始终有效。

图的每个顶点定义为:

类型(岩石，沙子等)。

高度

最后一条规则是，地球不与海洋相连(因此我们有许多子图)。



我的Astar配置

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

我没有边缘的预先计算权重。
我使用“复杂”算法(取决于步行者的速度，地面的种类，如果我们向上或向下)

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

问题

目前，当我计算一条路径时，执行时间不到1毫秒到1秒。路径解决方案仅在8或80个顶点之间，而我没有比例时间。 (因此8个顶点路径可能需要1秒，而80个顶点路径则需要1 ms)。

我使用Visual Studio进行了快速分析:提高瓶颈是我的瓶颈。

代码和测试数据

所有完整的代码和测试数据都可以在我的GitHub上找到。

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

简单/小型演示不受我的困扰。只是复杂的情况。
所有图形均由同一程序(未发布)生成。

我的测试程序输出

我的测试程序真的是假的:
-我进入一个节点进入图表
-在此之后，我将使用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是解决寻路的好选择(另一个库)？

我们可以优化我的图形数据吗(最佳提升算法，减少数据重复，...)？

谢谢 !

最佳答案

好 !我发现了我的问题。

目前，Bug在我的启发式实现中，该实现不计算当前节点与目标之间的距离平方。
它只是使“准随机”启发式。

而且，就我而言

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