Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

Fixing A-star

2007-07-28
2013-04-23
  • Hi, I recently installed S.C.O.U.R.G.E and it seems like a lot of fun. However, it was pretty clear that the pathfinding was broken.

    I've patched up a few of the problems and it works quite nicely now for me, but I'm not sure of the best way to get the changes into sourceforge. I'll just describe the changes here and let you update them if you like. All the changes are to the findPath function in util.cpp, and to the CPathNode class in util.h

    Core Problem: The Heuristic
    ---------------------------
    There's an odd heuristic being used:

    int DX = abs(dx - Node.x);
    int DY = abs(dy - Node.y);
    int Orthogonal = abs(DX - DY);
    int Diagonal = abs(((DX + DY) - Orthogonal)/2);
    Node.heuristic = Diagonal + Orthogonal + DX + DY;

    The last three lines are equivalent to:
    Node.heuristic = max(DX,DY)*2 + min(DX,DY);

    But the correct heuristic for square tiles that allow diagonal moves should be:
    Node.heuristic = max(DX,DY);

    The worst part is that the current heuristic is not even admissible, so this is not a proper A* and it will often not find the shortest path. The rest of the errors in the algorithm seem to be patches to make up for an invalid heuristic.

    Heap misuse
    -----------
    The whole point of a heap is that you can get the next largest item without sorting. With an admissible heuristic you never have to update values in the open list, and so you should never sort.

    This chunk has to be removed:
    // Check to see if already on OPEN
    for (int t=0; t<(int)OPEN.size(); t++) {
    ...
    }

    Now these two lines are irrelevant:
    sort_heap(OPEN.begin(), OPEN.end());// Ascending sort based on overloaded operators below
    and later on:
    make_heap( OPEN.begin(), OPEN.end() ); // Re-Assert heap, or will be short by one

    The other problem is that the STL heap seems to be a max-heap, but of course we need a min-heap to get the *shortest* path. The easiest way to make the heap work properly is to change the overridden operators in CPathNode, so:

    inline bool operator<(const CPathNode &b) {
        return this->f < b.f;
      }

    becomes:

    inline bool operator<(const CPathNode &b) {
        return this->f > b.f;
    }

    And do the same for the ">" operator. Now the heap provides the next node with minimum f(x) not maximum.

    Problem checking CLOSED list
    ----------------------------
    The CLOSED list is being checked before adding a node. It should be checked (and *then* have a node added) when nodes are first popped from the OPEN list.

    So straight after the line

    OPEN.pop_back();

    We should have (sorry if this is too long):

    // If at destination, break and create path below
        if ((BestNode.x == dx) && (BestNode.y == dy)) {
        CLOSED.push_back(BestNode);//add the goal to our path
          break;
        }
        // Check to see if already on CLOSED
        bNodeFound = false;
        for (int t=0; t<(int)CLOSED.size(); t++) {
                if ((BestNode.x == CLOSED[t].x) &&
                    (BestNode.y == CLOSED[t].y)) {
                  bNodeFound = true;
                  break;
                }
         }
        if(bNodeFound){
        continue;
        }
        CLOSED.push_back(BestNode);         // Push the BestNode onto CLOSED

    and then it continues to check whether too many nodes are on CLOSED etc.
    The CLOSED list should not be checked again when adding nodes.

    Removing zig-zags
    -----------------
    There is some comment about adding the neighbouring nodes in clockwise order to reduce zig-zags (or something). Anyway, there is a much easier way.

    First, the CPathNodes should keep their f, gone and heuristic values as doubles, not ints. In util.h:

    int f, gone, heuristic; // f = gone + heuristic

    becomes:

    double f, gone, heuristic; // f = gone + heuristic

    Which then allows a nice hack that prefers horizontal and vertical moves to diagonal ones, while leaving the heuristic admissible. The heuristic calculation can become:

    int DX = abs(dx - Node.x);
    int DY = abs(dy - Node.y);
    if(i % 2 == 0) //a diagonal move
        Node.heuristic = max(DX,DY)+0.5; //we discourage diagonals to remove zig-zagging
    else
        Node.heuristic = max(DX,DY);

    And now the pathing works great!

    I'm keen to keep working on the pathfinding for this game as it's a fun way to learn C++, but I'm hoping there's an easier way to contribute code. Some other really important changes are making the CPathNodes refer back to each other (not just keeping px and py values from their parent nodes), then the CLOSED list can be an unsorted hashtable which will be a *massive* speed up.

    Anyway, let me know if there's a way to help.

    Cheers,
    Jono

     
    • Blech. I just saw there is an SVN repository. I'll install it and try my hand at checking the update into the main trunk.
      Sorry about the previous stupidly long post!

      Cheers,
      Jono.

       
    • Gabor Torok
      Gabor Torok
      2007-07-28

      Hi, Please please fix it! :-) I sent you an email and I moved your post to our scourge list here:
      http://scourgeweb.org/tiki-view_forum_thread.php?forumId=4&comments_parentId=586
      Many thanks!
      --Gabor