# A star algorithm implementation problems

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:

EDIT

Thanks DeadMG, I rewrote the algorithm last week and got it somewhat working.

But the heuristics are still some faulty.

As you can see here it prefers a uneven path on an straight way:

The heuristics function:

float c_astar::GetH(cTILEext TILEX)
{
short a = 0; short b = 0;
if(TILEX.Tile.Position.x > Destination.x) a = TILEX.Tile.Position.x - Destination.x;
else a = Destination.x - TILEX.Tile.Position.x;
if(TILEX.Tile.Position.y > Destination.y) b = TILEX.Tile.Position.y - Destination.y;
else b = Destination.y - TILEX.Tile.Position.y;

float h = a+b;

//Tie-Breaker
float dx1,dy1,dx2,dy2;
dx1=dy1=dx2=dy2 = 0;

if(TILEX.Tile.Position.x > Destination.x) dx1 = TILEX.Tile.Position.x - Destination.x;
else dx1 = Destination.x - TILEX.Tile.Position.x;

if(TILEX.Tile.Position.y > Destination.y) dy1 = TILEX.Tile.Position.y - Destination.y;
else dy1 = Destination.y - TILEX.Tile.Position.y;

if(Start.x > Destination.x) dx2 = Start.x - Destination.x;
else dx2 = Destination.x - Start.x;

if(Start.y > Destination.y) dy2 = Start.y - Destination.y;
else dy2 = Destination.y - Start.y;
float cross = abs(dx1*dy2 - dx2*dy1);

h += cross*0.001;

return h;
}


I used the Tie-Breaker as described here. What am I doing wrong?

Regards, bryan226

-
What DeadMG said, and why are you guessing G? G should be a known calculable value that tells you exactly how much it costs to get to any given tile using the path selected thus far. H is a rough guess of how far the goal is from any given tile. – John McDonald Jun 29 '12 at 22:15