I'd suggest simple Euclidean distance. Think about how the cost estimate works. You take the distance traveled so far plus the heuristic of the rest of the distance. If you use Manhattan distance and a cost of 14 for diagonal, this is how it pans out:

• Travelling 1 unit horizontally towards the target costs 10 and gets you 10 closer.
  
• Travelling 1 unit vertically towards the target costs 10 and gets you 10 closer.
  
• Travelling 1 unit diagonally towards the target costs 14 and gets you 20 closer.
  
  So of course it would pick diagonal paths first.
  
  Edit: Also I believe that using the Manhattan distance if a unit can travel diagonally actually makes it an inadmissible heuristic. The heuristic should never overestimate the remaining cost. Not that I'm morally against inadmissible heuristics - they can cut down the search space nicely. But they aren't good if you're doing them by accident.

Thanks everybody for your help, it seems it is the Manhattan heuristic after all. I found a program called PathDemo which allows you to test and modify a variety of path finding algorithms. The image below shows A* using both the Euclidien and Manhattan distances for a heuristic.



The path found using the Euclidiean distance is definitely more natural. So that's solves one problem, but presents another: How do I caculate the Euclidean distance? Traditionally it is simply sqr((ax-bx)^2+(ay-by)^2), but that won't work for me because I am using a staggered iso grid in which each X grid co-ordinate actually represents 2 different tiles depending on if the Y co-ordinate is odd of even.



I just can't seem to crack it. Any help would be greatly appreciated!

Oh dear, the way you're handling X values is... unusual. I would use co-ordinates as if the tiles were flat and axis aligned. You could convert it before getting distance, e.g:

yadjusted = y;
xadjusted = x - floor(y/2); // can go negative.

Hopefully my sleepy brain got that right. ;)

Thanks Jefferytitan,

The formular for xadjusted is correct, but the yadjusted is a little off.



Both red tiles are 2 below the yellow tile. But, according to your formular, the leftmost tile is 3 below (2 - 5 = -3). However, I noticed a correlation between your two formulars, and this works:

x adjusted = x - floor(y/2)

x distance = (A.x - floor(A.y/2)) - (B.x - floor(B.y/2))
y distance = (A.x - floor(A.y/2)) - (B.x - floor(B.y/2)) - (A.y - B.y)

So, using pythagoras, I calculated the correct Euclidiean distance, but the strange thing is, it hasn't changed my paths. They still favour the same long straight lines shown in my original screenshot (in dark red). I've decided the staggered iso grid only adds an extra layer of compexity to my problem, so I will re-write the code for a square grid and see if I can achieve my desired zig zags there.

On a side note, Jefferytitan, you mentioned my staggered grid is unusual. The alternative of a titled square grid means that if I want the entire screen to be filled with tiles, then some squares with have negative co-ordinates, shown below (the top left and bottom left white regions).



And seeing as there are no negative array cells, this was not an option.

Thanks again! I'm open to all suggestions.

[size=8]VICTORY!

I re-implemented A* from scratch and found the problem!

I am using a 3d array to store the G, H, F, ParentX and ParentY values for each tile during the search. But the thing is, in Multimedia Fusion 2, arrays are unable to store floating point values. All non-whole numbers are rounded down to the closest integer. The Heuristic is rarely a whole number and that was the direct cause of my A* blues.

My solution was to use a cost of 1000 orthogonal and 1400 diagonal as opposed to 10 and 14 allowing for the equivalent of 2 decimal places of percision.

However, if you examine the G, H and F values for each square, you will notice they don't quite match 1000 and 1400. This is because I am multiplying every G value by 0.9925 and every H value by 0.0075 to break the tie between F values which would otherwise be the same for multiple tiles. This causes A* to favour tiles which are closer to the target.



Thank you everybody for your help.

Yarrr! Until next tyme me hearty!

You can't do an array of floats? Whoa...

Not in Multimedia Fusion 2. The closest would be a string array, in which you would convert the float to a string before you store it, and then back to a float when you retrieve it. Obviously, this is not very efficient.

But, now I've solved the problem, I will re-write the code in c++, although that would have worked from the beginning. Silly integer arrays!