Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

enter image description here

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

enter image description here


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:

enter image description here

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;

    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

share|improve this question
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

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

Is the entire point of F. Your heuristic is crackers. You should use something like Manhattan distance to target (ignoring obstacles) as the value of heuristic, (yours is pretty close but you need to ditch the *10) and then 1 cost/step for G. Also, your G estimate does not actually give the length of the path, because it does not include the idea that you had to take a detour, giving you quite inaccurate results.

Fixing these two problems should give you actual results for A*.

share|improve this answer
Thanks @DeadMG. I made some progress on it, but the heuristics function is still some faulty I guess. Could you take a look at the updated Question? – bryan226 Jul 6 '12 at 22:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.