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:

[attachment=19969:heuristic_bad.PNG]

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.

Are you sure the heuristic is what's wrong and not your overall traversal cost computation?

Hmm... what do you mean? I think I didn't implement such a thing ...

Sorry but I'm new to AI world...

I'd first try with the simplest implementation of your cost function and that is simple geometric distance between the two points. That is Math.sqrt(dx * dx + dy * dy). Get rid of that /2 in dy, just as the others said. If this doesn't work, then your problem is elsewhere :) Just then, when it works, you might go on with optimising the function to use integers only (for performance).

The diagonal cost is supposed to be greater than the orthogonal cost. Of course your pathfinder will choose to use all diagonals if those are cheaper. They cover more ground.

Also, if you have to throw in a divide by 2 for no apparent reason other than style, you have other problems too. Your pathfinding shouldn't have to be any different than if you draw the map with no skew.

I've taken into account your tips. Here is the code and the results:

public final int ORTHOGONAL_COST = 10;
public final int DIAGONAL_COST = 14;

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);
	
	return ORTHOGONAL_COST * (dx + dy) + (DIAGONAL_COST - 2 * ORTHOGONAL_COST) * Math.min(dx, dy);
}

[attachment=20008:diagonal_distance.PNG]

Maybe I don't get the expected result (straight diagonal line) because I don't handle the coordinates the right way? Below you can see how I do it:

[attachment=20009:grid_blank.PNG]

Is it right?

I'd first try with the simplest implementation of your cost function and that is simple geometric distance between the two points. That is Math.sqrt(dx * dx + dy * dy). Get rid of that /2 in dy, just as the others said. If this doesn't work, then your problem is elsewhere Just then, when it works, you might go on with optimising the function to use integers only (for performance).

Tried that too. Code & results:

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);
	
	return (float)Math.sqrt(dx * dx + dy * dy);
}

[attachment=20007:euclidean_distance.PNG]

As a very general rule, the heuristic is not to blame for bad quality of the results (as long as it's admissible). If your algorithm is picking a result you don't like among many possible results with the same cost, it means your cost function doesn't accurately reflect your preferences.

How can I adjust my cost function? I just try again and again until I find something that matches with what I want?

How can I adjust my cost function? I just try again and again until I find something that matches with what I want?

Yeah, I'm with ApochPiQ, I suspect the problem is that there are two functions to determine the next move, the cost to move to that new tile, and the heuristic to determine how close that move will get you to the goal.

For your case, you want to take the path that costs the least to move to (diagonals cost more) and yet yields the best H value, in your case the least distance to the goal.