Sign in to follow this  
chiranjivi

Failed A* implementation

Recommended Posts

I'm taking a first shot at trying to implement A*, and have written a little app that creates a grid with passable/impassable squares and allows the user to set start and end points, then calculates and draws in the best path from start to end using A*. I've been referring to this tutorial while trying to write the code. Anyway, the pathfinding works - kinda - in that it always returns a pretty good path, but sometimes not the best one? If I give it a maze or something, it does fine (linked due to size): http://i42.tinypic.com/54vog0.png. But then here's a fairly simple short path it got wrong: big l rest in peace Here's the code. I put it on pastebin, where I think it is easier to read: http://pastebin.com/ZWKXbbKN, but I'll also put it here in case you don't want to open another browser tab or w/e.
struct coord
{
    int gx, gy;
};

struct node
{
    int ny, nx, cost_path, cost_heuristic, cost_sum;
    coord parent;
};

void find_path ( coord initial, coord target, vector<coord> &moves )
{
    bool found = false;
    bool searching = true;

    list<node> open;
    list<node> closed;

    node start_node, best_node;
    coord new_coord;

    start_node.nx = initial.gx;
    start_node.ny = initial.gy;
    start_node.cost_heuristic = 10 * ( sum_delta ( start_node.nx, start_node.ny, target.gx, target.gy ) );
    start_node.cost_sum = start_node.cost_heuristic;
    start_node.cost_path = 0;

    open.push_back(start_node); // add the start node to the open list before beginning search loop

    while ( searching == true ) // while we have not found the target
    {
        best_node.cost_sum = 9999999; // just to make sure we pick a valid open node

        if ( open.size() == 0 ) // if there are no nodes on the open list, we have failed to find a path
        {
            searching = false;
        }

        for ( list<node>::iterator i = open.begin(); i != open.end(); ++i ) // find best open node
        {
            if ( i->cost_sum < best_node.cost_sum ) { best_node = *i; }
        }

        if ( best_node.ny == target.gy && best_node.nx == target.gx ) // are we adding the target node to the closed list?
        {
            closed.push_back(best_node); found = true; searching = false;
        }

        closed.push_back(best_node); // add the best node from the open list to the closed node list

        for ( list<node>::iterator i = open.begin(); i != open.end(); ++i ) // and remove it from the open list
        {
            if ( i->ny == best_node.ny && i->nx == best_node.nx ) { open.erase(i); --i; }
        }

        for ( int x = -1; x <= 1; ++x ) for ( int y = -1; y <= 1; ++y ) // evaluate its neighbouring nodes
        {
            // make sure the square we are testing is inside the boundaries of the map
            if ( best_node.ny+y > -1 && best_node.ny+y < 16 && best_node.nx+x > -1 && best_node.nx+x < 16 )
            {
                bool not_walkable_or_closed = false;

                if ( gridmap[best_node.ny+y][best_node.nx+x] == 1 ) { not_walkable_or_closed = true; } // ignore unwalkable nodes

                for ( list<node>::iterator i = closed.begin(); i != closed.end(); ++i ) // and those on the closed list
                {
                    if ( i->nx == best_node.nx+x && i->ny == best_node.ny+y ) { not_walkable_or_closed = true; }
                }

                if ( not_walkable_or_closed == false ) // if the node is walkable and not on the closed list
                {
                    bool found_on_open_list = false;

                    for ( list<node>::iterator i = open.begin(); i != open.end(); ++i ) // does it exist on the open list already?
                    {
                        if ( i->nx == best_node.nx+x && i->ny == best_node.ny+y ) // node exists on the open list already
                        {
                            found_on_open_list = true;

                            int cost_to_reach; // if move is orthogonal, movement cost is 10, if diagonal, 14
                            if ( x + y == 1 || x + y == -1 ) { cost_to_reach = 10; } else { cost_to_reach = 14; }

                            if ( i->cost_path > ( best_node.cost_path + cost_to_reach ) ) // if this path is less costly than old path
                            {
                                new_coord.gx = best_node.nx;                            // adjust the new_coord object to store
                                new_coord.gy = best_node.ny;                            // the location of the new parent square

                                i->parent = new_coord;                                  // assign the square's new parent,
                                i->cost_path = ( best_node.cost_path + cost_to_reach ); // and change the pathing cost and the
                                i->cost_sum = ( i->cost_path + i->cost_heuristic );     // path-plus-heuristic cost accordingly
                            }
                        }
                    }

                    if ( found_on_open_list == false )  // if this is the first time we have pathed to this square
                    {
                        new_coord.gx = best_node.nx;    // adjust the new_coord object to store
                        new_coord.gy = best_node.ny;    // the location of the new parent square

                        node new_node;                  // create a new node
                        new_node.nx = best_node.nx+x;   // and record its
                        new_node.ny = best_node.ny+y;   // co-ordinates and
                        new_node.parent = new_coord;    // its parent square

                        int cost_to_reach; // if move is orthogonal, movement cost is 10, if diagonal, 14
                        if ( x + y == 1 || x + y == -1 ) { cost_to_reach = 10; } else { cost_to_reach = 14; }

                        // update the new node's pathing, heuristic, and sum costs
                        new_node.cost_path = ( best_node.cost_path + cost_to_reach );
                        new_node.cost_heuristic = 10 * ( sum_delta ( new_node.nx, new_node.ny, target.gx, target.gy ) );
                        new_node.cost_sum = ( new_node.cost_path + new_node.cost_heuristic );

                        open.push_back(new_node);       // add this new node to the open list
                    }
                }
            }
        }
    }
    /* code that runs backward from best_node through its parents and adds each successive coord to the moves vector */
}

Apologies in advance for what I am sure to anyone half-competent is very bad code. I am entirely new to programming altogether and am trying to focus on making things work first, then maybe later think about making them work non-terribly. Lastly, the app itself is here (~400kb), if anyone wants to see for themselves the way in which it gets things wrong. (Left click to assign start point, right click for end point, middle click to block or unblock a grid square).

Share this post


Link to post
Share on other sites
Your heuristic is wrong, that's all.

The "pain" for moving a diagonal in your heuristic will currently (I'm assuming - you didn't post it) give a total of 2 for a diagonal move - +1 for sideways and +1 for up/down.

If you fix that to give the true trig distance (1.414 instead of 2) then you'll probably find that it picks your green line as expected.

Share this post


Link to post
Share on other sites
Hi,

The way I understand it, he did use 14 for diagonals and 10 for orthogonal movements.

I didn't read your code carefully, I just wanted to remind you that A* does not guarantee the best path in all cases, it is an approximation. If you need the best path, use Djikstra (but keep in mind it will be less efficient).

Good Luck,
Rosália

Share this post


Link to post
Share on other sites
Actually I missed that bit - I skimmed the code and assumed the heuristic would be in another function. There looks to be one in the init stuff.

I agree that A* isn't perfect, but I would also expect it to pick the green line in this case - it's not that imperfect.

Maybe the code bails when it find the first path and not the best? I can't really read the code well tbh. I struggled a long time when I wrote my own version of this because it's a really nasty thing to get right. Reading someone elses isn't any easier! :)

Share this post


Link to post
Share on other sites
Just did the math. The green line costs 86 and the red line costs 98, so the bug is in the algorithm after all.

Can't post anything more useful than that other than to check that once a path is found it still continues to try and find a better one.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this