Why does my algorithm for pathfinding along waypoints not work? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions concerning problems with code you've written must describe the specific problem — and include valid code to reproduce it — in the question itself. See SSCCE.org for guidance.

Closed 8 years ago.

Improve this question

I wrote the following two functions to find a path from one waypoint to another however I get a segmentation fault, I am assuming it loops endlessly but I don't understand why since it should stop when the destination waypoint is found.

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

waypoint is a struct with members x, y and an array of links(of type *waypoint) which define to where you can walk from the waypoint.

getPath is supposed to return an array of all the waypoints along which you have to walk to get to the destination waypoint. checkDest is used to see if a particular waypoint lies on the path to the destination waypoint.

Can anyone tell me if this algorithm is utterly useless and if so suggest a better way of doing this, or if I just did a minor thing wrong.

Thank you very much in advance.

#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

It looks like you are blowing up in the constructor that calls malloc(). Which could be due to a loop in the nodes of your graph. This will causes infinite recursion and so yo'll run out of memory.

With this type of graph navigation algorithm you need to check you are NOT re-visting the same node. That's best done by adding a hash table of nodes visited and checking for a duplicate entry.

Put try/catch blocks around your duplicate detection so when you visit a node you have visited before you can print the nodes and determine the graph topology.