I’m having some trouble implementing the A* algorithm in a 2D tile based game.

The problem is basically that the algorithm gets stuck when something gets in its direct way (e.g. walls) Note that it only allows Horizontal and Vertical movement.

Here's a picture as it works fine across the map without something in its direct way: (Green tile = destination, Blue = In closed list, Green = in open list)

This is what happens if I try to walk 'around' a wall:

I calculate costs with the F = G + H formula:

G = 1 Cost per Step

H = 10 Cost per Step //Count how many tiles are between current-tile & destination-tile

The functions:

short c_astar::GuessH(short Startx,short Starty,short Destinationx,short Destinationy)
{
                hgeVector Start, Destination;
                Start.x = Startx;
                Start.y = Starty;
                Destination.x = Destinationx;
                Destination.y = Destinationy;

                short a = 0; short b = 0;
                if(Start.x > Destination.x) a = Start.x - Destination.x;
                else a = Destination.x - Start.x;
                if(Start.y > Destination.y) b = Start.y - Destination.y;
                else b = Destination.y - Start.y;

                return (a+b)*10;
}

short c_astar::GuessG(short Startx,short Starty,short Currentx,short Currenty)
{
                hgeVector Start, Destination;
                Start.x = Startx;
                Start.y = Starty;
                Destination.x = Currentx;
                Destination.y = Currenty;

                short a = 0; short b = 0;
                if(Start.x > Destination.x) a = Start.x - Destination.x;
                else a = Destination.x - Start.x;
                if(Start.y > Destination.y) b = Start.y - Destination.y;
                else b = Destination.y - Start.y;

                return (a+b);
}

At the end of the loop I check which tile is the cheapest to go according to its F value:

Then some quick checks are done for each tile (UP,DOWN,LEFT,RIGHT):

                           //...CX are holding the F value of the TILE specified
                           //            Info:                                        C0 = Center (Current)
                           //                                                           C1 = UP
                           //                                                           C2 = DOWN
                           //                                                           C3 = LEFT
                           //                                                           C4 = RIGHT
                           //Quick checks
                           if(((C1 < C2) && (C1 < C3) && (C1 < C4)))
                           {
                                           Current.y  -= 1;
                                           bSimilar  = false;
                                           if(DEBUG) hge->System_Log("C1 < ALL");
                           }
                           //.. same for C2,C3 & C4

If there are multiple tiles with the same F value:

It’s actually a switch for DOWNLEFT,UPRIGHT.. etc. Here’s one of it:

   case UPRIGHT:
         {
                //UP
                Temporary = Current;
                Temporary.y -= 1;

                bTileStatus[0] = IsTileWalkable(Temporary.x,Temporary.y);

                if(bTileStatus[0])
                {
                       //Proceed normal we are OK & walkable
                       Tilex.Tile                 = map.at(Temporary.y).at(Temporary.x);

                       //Search in lists
                       if(SearchInClosedList(Tilex.Tile.ID,C0)) bFoundInClosedList[0] = true;
                       if(SearchInOpenList(Tilex.Tile.ID,C0)) bFoundInOpenList[0]  = true;


                       //RIGHT
                       Temporary = Current;
                       Temporary.x += 1;

                       bTileStatus[1] = IsTileWalkable(Temporary.x,Temporary.y);

                       if(bTileStatus[1])
                       {
                              //Proceed normal we are OK & walkable
                              Tilex.Tile                 = map.at(Temporary.y).at(Temporary.x);

                              //Search in lists
                              if(SearchInClosedList(Tilex.Tile.ID,C0)) bFoundInClosedList[1] = true;
                              if(SearchInOpenList(Tilex.Tile.ID,C0)) bFoundInOpenList[1]  = true;

                              //*************************************************
                              //     Purpose: ClosedList behavior
                              //*************************************************
                              if(bFoundInClosedList[0] && !bFoundInClosedList[1])
                              {
                                    //UP found in ClosedList. Go RIGHT
                                    return RIGHT;
                              }
                              if(!bFoundInClosedList[0] && bFoundInClosedList[1])
                              {
                                    //RIGHT found in ClosedList. Go UP
                                    return UP;
                              }
                              if(bFoundInClosedList[0] && bFoundInClosedList[1])
                              {
                                    //Both found in ClosedList. Random value
                                    switch(hge->Random_Int(8,9))
                                    {
                                    case 8:
                                           return UP;
                                           break;
                                    case 9:
                                           return RIGHT;
                                           break;
                                    }
                              }

                              //*************************************************
                              //     Purpose: OpenList behavior
                              //*************************************************
                              if(bFoundInOpenList[0] && !bFoundInOpenList[1])
                              {
                                    //UP found in OpenList. Go RIGHT
                                    return RIGHT;
                              }
                              if(!bFoundInOpenList[0] && bFoundInOpenList[1])
                              {
                                    //RIGHT found in OpenList. Go UP
                                    return UP;
                              }
                              if(bFoundInOpenList[0] && bFoundInOpenList[1])
                              {
                                    //Both found in OpenList. Random value
                                    switch(hge->Random_Int(8,9))
                                    {
                                    case 8:
                                           return UP;
                                           break;
                                    case 9:
                                           return RIGHT;
                                           break;
                                    }
                              }
                       }
                       else if(!bTileStatus[1])
                       {
                              //RIGHT is not walkable OR out of range
                              //Choose UP
                              return UP;
                       }
                }
                else if(!bTileStatus[0])
                {
                       //UP is not walkable OR out of range
                       //Fast check RIGHT
                       Temporary = Current;
                       Temporary.x += 1;

                       bTileStatus[1] = IsTileWalkable(Temporary.x,Temporary.y);

                       if(bTileStatus[1])
                       {
                              return RIGHT;
                       }
                       else return FAILED; //Failed, no valid path found!
                }
         }
         break;

A log for the second picture: (Cut down to ten passes, because it’s just repeating itself)

-----------------------------------------------------
PASS: 1 | C1: 211 | C2: 191 | C3: 211 | C4: 191
DOWN + RIGHT SIMILAR
Going DOWN
-----------------------------------------------------
PASS: 2 | C1: 200 | C2: 182 | C3: 202 | C4: 182
DOWN + RIGHT SIMILAR
Going DOWN
-----------------------------------------------------
PASS: 3 | C1: 191 | C2: 193 | C3: 193 | C4: 173
C4 < ALL
Tile(12.000000,6.000000) not walkable. MAX_F_VALUE set.
-----------------------------------------------------
PASS: 4 | C1: 182 | C2: 184 | C3: 182 | C4: 999
UP + LEFT SIMILAR
Going UP
Tile(12.000000,5.000000) not walkable. MAX_F_VALUE set.
-----------------------------------------------------
PASS: 5 | C1: 191 | C2: 173 | C3: 191 | C4: 999
C2 < ALL
Tile(12.000000,6.000000) not walkable. MAX_F_VALUE set.
-----------------------------------------------------
PASS: 6 | C1: 182 | C2: 184 | C3: 182 | C4: 999
UP + LEFT SIMILAR
Going UP
Tile(12.000000,5.000000) not walkable. MAX_F_VALUE set.
-----------------------------------------------------
PASS: 7 | C1: 191 | C2: 173 | C3: 191 | C4: 999
C2 < ALL
Tile(12.000000,6.000000) not walkable. MAX_F_VALUE set.
-----------------------------------------------------
PASS: 8 | C1: 182 | C2: 184 | C3: 182 | C4: 999
UP + LEFT SIMILAR
Going LEFT
-----------------------------------------------------
PASS: 9 | C1: 191 | C2: 193 | C3: 193 | C4: 173
C4 < ALL
Tile(12.000000,6.000000) not walkable. MAX_F_VALUE set.
-----------------------------------------------------
PASS: 10 | C1: 182 | C2: 184 | C3: 182 | C4: 999
UP + LEFT SIMILAR
Going LEFT
-----------------------------------------------------

Its always going after the cheapest F value, which seems to be wrong.

If someone could point me to the right direction I'd be thankful.

Regards, bryan226