Staggered Isometric Pathfinder

Question

I have a problem trying to figure out how to implement a path finding system for a staggered isometric map.

I read the A* algorithm and tried to see how it would manifest on an isometric map and the results brought me here.

So the problem lies here (I'm sorry about the cheap display)

So , I'm currently on the green tile (2,3) and I try to find a path to the red tile (3,1).

Based on A* algorithm I try to calculate the F value of adjacent tiles (I did this only for those 3 tiles).
As the image displays the F value of (2,1) is lower than (2,2) and this is the mother of all problems , the diagonal tiles with j+2 and j-2 will have (almost) every time a lower F value than the "logical" choice.
So instead of going to (2,2) it will go to (2,1).

How can I solve this problem? Can somebody give me some hints on what should I do?

Answer 1

Based on the given values, it looks like your H is not admissible. Since it takes 10 to get from (2,3) to (2,2), I assume it should take 10 to get from (2,2) to (3,1), but your H says it takes 20 (i.e. you overestimate).

One possible H is the direct distance to the target (either something like Manhattan distance or Euclidean).

At our first step, we explore all neighbours. Our G values will look like: (G = green, R = red)

    14
  10  10
14   R  14
  10  10
G   14

Let's take H as something like Manhattan distance, where 14 is a diagonal jump and 10 is a move to a direct neighbour. This is actually be the perfect heuristic for this example, as it's exactly the same as the actual distance. This will be different once there are obstacles in the path.

Then we get H values as:

    34
  24  30
14   R  34
  10  24
G   14

So our F values (= G + H) are:

    48
  34  40
28   R  48
  20  34
G   28

Then you find the minimum, which is 20, explore all it's (unexplored) neighbours and find the minimum, which will be the goal in this case.

Note that it's a easy mistake to stop as soon as one of the neighbours is the target, rather than the node we are currently exploring. An admissible heuristic doesn't guarantee that we'll find the optimal path to the target if we do this.