Hello,

I'm new to AI programming and I need a pathfinding algorithm for my game which uses isometric tile maps (see below the screenshot in attachment). Player can move in the 8 cardinal directions (North, North East, East, etc.).

I successfully implemented the A* algorithm, however I think my heuristic is bad:

As you can see, the algorithm doesn't keep a straight diagonal to the goal. It's not natural at all, I can't let the player move this way.

I used this heuristic which is described as the best algorithm for grids that allow 8 directions of movement.

Here is how I implemented it in Java:

public final int ORTHOGONAL_COST = 14; public final int DIAGONAL_COST = 10; public float getHeuristicCost(final Point2D.Int source, final Point2D.Int target) { int dx = Math.abs(source.x - target.x); int dy = Math.abs(source.y - target.y) / 2; return ORTHOGONAL_COST * (dx + dy) + (DIAGONAL_COST - 2 * ORTHOGONAL_COST) * Math.min(dx, dy); }

I divided *dy* by 2 because of the map's style, it gives a path even weirder if I don't divide by 2.

I can understand the path isn't straight because this heuristic isn't fit for my map style, but which one should I use then?

Thank you.