为什么我的沿航点寻路的算法不起作用

Question

我编写了以下两个函数来查找从一个航点到另一个航点的路径，但是我得到了分段错误，我假设它无休止地循环，但我不明白为什么，因为它应该在找到目标航点时停止。

std::vector<waypoint> Area::getPath(waypoint currentWP, waypoint destWP)
{
    if(currentWP == destWP)
        return returnPath;
    for(unsigned int i=0; i<currentWP.links.size(); i++)
    {
        if(checkDest(*currentWP.links[i], destWP))
        {
            returnPath.push_back(*currentWP.links[i]);
            getPath(*currentWP.links[i], destWP);
        }
    }
    return returnPath;
}
bool Area::checkDest(waypoint currentWP, waypoint destWP)
{
    if(currentWP == destWP)
        return true;
    for(unsigned int i=0; i<currentWP.links.size(); i++)
    {
        if(checkDest(*currentWP.links[i], destWP))
            return true;
    }
    return false;
} 

航点是一个结构，具有成员 x、y 和一组链接（类型为 *航点），这些链接定义了您可以从航点步行到哪里。

getPath 应该返回一个包含所有航点的数组，您必须沿着这些路点步行才能到达目的地航点。 checkDest 用于查看特定航点是否位于通往目的地航点的路径上。

谁能告诉我这个算法是否完全没用，如果是的话，建议一种更好的方法来做到这一点，或者我只是做错了一件小事。

提前非常感谢你。

#0  0x00007ffff6bd29a5 in _int_malloc () from /usr/lib/libc.so.6
#1  0x00007ffff6bd4c50 in malloc () from /usr/lib/libc.so.6
#2  0x00007ffff747c35d in operator new(unsigned long) () from /usr/lib/libstdc++.so.6
#3  0x000000000040579a in __gnu_cxx::new_allocator<waypoint*>::allocate     (this=0x7fffff7ff1e0, __n=1) at /usr/include/c++/4.8.2/ext/new_allocator.h:104
#4  0x00000000004052cf in std::_Vector_base<waypoint*, std::allocator<waypoint*>     >::_M_allocate (this=0x7fffff7ff1e0, __n=1) at /usr/include/c++/4.8.2/bits/stl_vector.h:168
#5  0x0000000000404b1b in std::_Vector_base<waypoint*, std::allocator<waypoint*> >::_M_create_storage (this=0x7fffff7ff1e0, __n=1) at /usr/include/c++/4.8.2/bits/stl_vector.h:181
#6  0x0000000000403ccf in std::_Vector_base<waypoint*, std::allocator<waypoint*> >::_Vector_base (this=0x7fffff7ff1e0, __n=1, __a=...) at /usr/include/c++/4.8.2/bits/stl_vector.h:136
#7  0x0000000000402c33 in std::vector<waypoint*, std::allocator<waypoint*> >::vector (this=0x7fffff7ff1e0, __x=std::vector of length 1, capacity 1 = {...}) at /usr/include/c++/4.8.2/bits/stl_vector.h:312
#8  0x0000000000402771 in waypoint::waypoint (this=0x7fffff7ff1d0) at Waypoint.h:6
#9  0x0000000000409c3e in Area::checkDest (this=0x6ba3b0, currentWP=..., destWP=...) at Area.cpp:166
#10 0x0000000000409cdd in Area::checkDest (this=0x6ba3b0, currentWP=..., destWP=...) at Area.cpp:172
#11 0x0000000000409cdd in Area::checkDest (this=0x6ba3b0, currentWP=..., destWP=...) at Area.cpp:172

Answer 1

看起来你在调用 malloc（） 的构造函数中炸毁了。这可能是由于图形节点中的循环。这将导致无限递归，因此您将耗尽内存。

使用这种类型的图形导航算法，您需要检查您是否正在重新修订同一节点。最好通过添加访问的节点的哈希表并检查重复项来完成进入。

在重复检测周围放置 try/catch 块，以便在访问已访问过的节点时，才能打印节点并确定图形拓扑。