Issue with A* pathfinding. Compiles, but acts strangely

Question

I recently took a stab at the A* search algorithm. I've tried it before to no avail, but I've had a level of success this time. It always finds a path, unless it can't (obviously) and it's USUALLY close to the shortest one. Other times it acts really screwy as in adds one too many times, goes in a zig zag pattern, moves in the wrong direction randomly. It's very strange. Screenshot here.

Code below:

int manhattan( Coord a, Coord b )
{

    int x = abs(b.x-a.x);
    int y = abs(b.y-a.y);
    return x+y;

}

std::vector<Coord> AStar( std::vector< std::vector< int > > grid, Point start, Point end )
{

    //The current 'focal' point.
    Point *cur;

    //The open and closed lists.
    std::vector< Point* > closed;
    std::vector< Point* > open;

    //Start by adding the starting position to the list.
    open.push_back( &start );

    //Just so it knows whether or not to try and reconstruct a path.
    bool error = true;

    while( open.size() > 0 )
    {

        //The current point is the first entry in the open list.
        cur = open.at(0);

        if( cur->getPos() == end.getPos() )
        {

            error = false;
            break;

        }

        //Add in all the neighbors of the current point.
        for( int y = -1; y <= 1; y++ )
        {

            for( int x = -1; x <= 1; x++ )
            {

                int curX = cur->getPos().x+x;
                int curY = cur->getPos().y+y;

                int movCost = 10;

                //If it is a diagonal, make it cost 14 instead of 10.
                if( (y == -1 && x == -1)||
                    (y ==  1 && x == -1)||
                    (y == -1 && x ==  1)||
                    (y ==  1 && x ==  1))
                {

                    movCost = 14;
                    //continue;

                }

                Coord temp( curX, curY );
                bool make = true;

                //If it is outside the range of the map, continue.
                if( curY >= grid.size() || 
                    curX >= grid.size() )
                {

                    continue;
                }

                /*

                These two loops are to check whether or not the point's neighbors already exist.
                This feels really sloppy to me. Please tell me if there is a better way.

                */
                for( int i = 0; i < open.size(); i++ )
                {

                    if( temp == open.at(i)->getPos() )
                    {

                        make = false;
                        break;

                    }

                }

                for( int i = 0; i < closed.size(); i++ )
                {

                    if( temp == closed.at(i)->getPos() )
                    {

                        make = false;
                        break;

                    }

                }

                //If the point in the map is a zero, then it is a wall. Continue.
                if( (grid.at(temp.x).at(temp.y) == 0 ) ||
                    ( temp.x<0 || temp.y < 0 ) )
                {

                    continue;

                }

                //If it is allowed to make a new point, it adds it to the open list.
                if( make )
                {

                    int gScore = manhattan( start.getPos(), Coord( curX, curY ) );
                    int hScore = manhattan( end.getPos(), Coord( curX, curY ) );
                    int tileCost = grid[curX][curY];
                    int fScore = gScore+hScore+tileCost;

                    open.push_back( new Point( curX, curY, fScore, cur ) );

                }

            }

        }

        //It then pushes back the current into the closed set as well as erasing it from the open set.
        closed.push_back( cur );
        open.erase( open.begin() );

        //Heapsort works, guranteed. Not sure if it's a stable sort, though. From what I can tell that shouldn't matter, though.
        open = heapsort( open );

    }

    std::vector<Coord> path;

    if( error )
    {

        return path;

    }

    //Reconstruct a path by tracing through the parents.
    while( cur->getParent() != nullptr )
    {

        path.push_back( cur->getPos() );
        cur = cur->getParent();

    }

    path.push_back( cur->getPos() );

    return path;

}

Anyway! Thanks for any help ahead of time! If you want to give me some helpful tips or any other help that would be awesome! Thanks very much! :^)

Answer 1

I can see that you're trying to make diagonals more expensive here:

            int movCost = 10;

            //If it is a diagonal, make it cost 14 instead of 10.
            if( (y == -1 && x == -1)||
                (y ==  1 && x == -1)||
                (y == -1 && x ==  1)||
                (y ==  1 && x ==  1))
            {

                movCost = 14;
                //continue;

            }

But you don't actually use movCost elsewhere in your code.

Instead, your cost function only uses Manhattan distance:

                int gScore = manhattan( start.getPos(), Coord( curX, curY ) );
                int hScore = manhattan( end.getPos(), Coord( curX, curY ) );
                int tileCost = grid[curX][curY];
                int fScore = gScore+hScore+tileCost;

Which explains the diagonally zig-zagging paths:

By the way, there is one more logical error in your code: in A*, the g-cost should be calculated as the actual cost from the start to the current node, not estimated like you have using your manhattan() function. You should be saving the cost along with your points in your open and closed sets.

In future, you should turn on all compiler warnings and don't ignore them. This will catch mistakes that are easy to miss, like unused variables.