A* Search keeps crashing

[Niven]

I'm attempting to implement A* search in one of my programs, but everytime I run it, it crashes. Relevant code:

bool SortShortestFirst( Path lhs, Path rhs )
{
    return (lhs.GetTotalLength() + lhs.GetDistancetoPoint(TargetPos_WM) <
            rhs.GetTotalLength() + rhs.GetDistancetoPoint(TargetPos_WM) );
}

bool LessThan(vec2 lhs, vec2 rhs)
{
    return lengthsquared(lhs) < lengthsquared(rhs);
}

void Agent::CalculatePath()
{
    vector<Path> Queue;
    vector<vec2> UsedNodes;

    UsedNodes.push_back(Position_WM);
    Queue.push_back(Path(Position_WM));

    while ( Queue[0].GetEnd() != TargetPos_WM )
    {
        for ( int x = -1; x < 2; x++ )
            for ( int y = -1; y < 2; y++ )
            {
                if ( x == 0 && y == 0 )
                    continue;
                vec2 Temp = Queue[0].GetEnd() + vec2(x,y);
                if ( Temp.x < 0 || Temp.x >= AGENT_WORLD_MODEL_SIZE_X || Temp.y < 0 || Temp.y >= AGENT_WORLD_MODEL_SIZE_Y )
                    continue;
                if ( WorldModel[int(Temp.x)][int(Temp.y)] == NOTPASSABLE )
                    continue;
                if ( !binary_search( UsedNodes.begin(), UsedNodes.end(), Temp, LessThan ) )
                {
                    UsedNodes.push_back(Temp);

                    Path NewPath = Queue[0];
                    NewPath.AddPoint(Temp);

                    Queue.push_back(NewPath);
                }
            }

        Queue.erase(Queue.begin());
        sort( Queue.begin(), Queue.end(), SortShortestFirst ); // Crashes here
    }

    ThePath = Queue[0];
}

The part that confuses me the most is that I have implemented A* before with no problem and I'm sure I'm doing essentially the same thing. Here's the code from when I implemented it before (The nodes here are a custom class while the nodes in the one that's crashing are glm::vec2. Also, the one below is iterative and meant to be called many times while the one that's crashing is meant to be called once):

bool ShortestFirst( Path lhs, Path rhs )
{
    return ( lhs.GetTotalDistance() + lhs.GetEnd()->Distance( EndNode ) <
             rhs.GetTotalDistance() + rhs.GetEnd()->Distance( EndNode ) );
}

void Map::Astar()
{
    sort( Queue.begin(), Queue.end(), ShortestFirst );
    Path NewPath = Queue[0];

    for ( int j = 0; j < NewPath.GetNumChildren(); j++ )
    {
        if ( !AlreadyUsedNode(NewPath.GetEnd()->GetChild(j)) )
        {
            UsedNodes.push_back(NewPath.GetEnd()->GetChild(j));

            Path Temp = NewPath;
            Temp.AddNode(j);

            Queue.push_back(Temp);
        }
    }
    for ( int j = 0; j < NewPath.GetNumParents(); j++ )
    {
        if ( !AlreadyUsedNode(NewPath.GetEnd()->GetParent(j)) )
        {
            UsedNodes.push_back(NewPath.GetEnd()->GetParent(j));

            Path Temp = NewPath;
            Temp.AddNode(-(j+1));

            Queue.push_back(Temp);
        }
    }
    Queue.erase(Queue.begin());

    sort( Queue.begin(), Queue.end(), ShortestFirst );
}

If you need any clarification with any of the code, just ask. Does anyone see where the problem could be?

[ne555]

http://www.cplusplus.com/forum/general/112111/

> Relevant code
http://www.eelis.net/iso-c++/testcase.xhtml (point 6)


> Does anyone see where the problem could be?
guessing, out of bounds access because `Queue' is empty

[Niven]

I checked the size of Queue before it crashed at it isn't empty, but I did find out that the program ceases to crash if I remove lines 30 and 31 (WorldModel is a 2d array of an enumerated type. NOTPASSABLE is one of it's possible values). Also (and I should have mentioned this before), the program sometimes throws an instance of std::bad_alloc when crashing (I know this that memory couldn't be allocated, but I'm not sure where it's trying to allocate memory. does std::sort allocated memory?)

http://www.eelis.net/iso-c++/testcase.xhtml (point 6)

Do you want me to provide my implementation of the Path class and data stored in WorldModel so others can compile this? The reason i didn't was that I felt that what I've provided so far is most likely all the code related to the crash.

Edit:
Figured out my problem. The search space was too large so the queue would end up holding enough data that the stack ran out of space. (Removing lines 30 and 31 allowed the algorithm to quickly find the straight line path to the target).

Edit 2:
That may not be the problem because I declared Queue and UseNodes globally to initalize them on the heap and the program still crashes. I also tried initializing them using new (Ex. Path* Queue = new Path[100] ) and it still crashed at the same place.

[ne555]

> the queue would end up holding enough data that the stack ran out of space
Queue is an std::vector
An std::vector uses dynamic memory allocation for its elements


> I felt that what I've provided so far is most likely all the code related to the crash.
¿what do you expect us to do?
Even if we do read your code line by line, very carefully, there is still some info that we not know (like the size of `WorldModel' and possible values for `Temp.{x,y}')

We've got debugging tools that we can't use because the code that you've provided does not compile.


> sort( Queue.begin(), Queue.end(), SortShortestFirst );
I can't see a reason for that to be the cause of the crash.
I think that you've corrupted the memory before that. Try to run through valgrind.


> the program sometimes throws an instance of std::bad_alloc when crashing
> I'm not sure where it's trying to allocate memory
debugger, backtrace,
check size passed to new[]... a really big number... ¿where does it come from?