A star algorithm implementation problems
- by bryan226
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
