What methods can be used to smoothen out A* paths found on a hexagonal grid? At the moment the paths are rather all over the place. I'm thinking of a way of making the algorithm favour going straight ahead over making a turn, and perhaps doing this in the heuristic for example Here labelling each side then in the search recording which side lead to that cell and favouring investigating the cell which lines up on the edge with the same label. So entering the cell at 1 will favour leaving at 1. i think it'll work but there may be a better way I've overlooked, any ideas?

Are you trying to say you want to prefer paths with fewer turns, but which appear to go further out of the way? I think I would prefer the opposite when working with hexes, but if you want to do this I expect you can add a tiny extra cost to outgoing nodes of different directions to the way you came in, for example.

Actually after viewing it with an overlay I think there's something wrong with my algorithm. I've used this basic algorithm before on a square based grid and it's worked well, so I'm thinking it's something to do with the heuristic I'm using:

Here's the source file in question:
route pather search

And here's the heuristic

float hCost =   ((destCoord.x - i->x) * (destCoord.x - i->x)) +                ((destCoord.y - i->y) * (destCoord.y - i->y)) +                ((destCoord.x - i->x) * (destCoord.y - i->y));

Quote: Original post by M_Johnson
And here's the heuristic

float hCost =   ((destCoord.x - i->x) * (destCoord.x - i->x)) +                ((destCoord.y - i->y) * (destCoord.y - i->y)) +                ((destCoord.x - i->x) * (destCoord.y - i->y));

The 3rd line in your heuristic can be negative, and I doubt its what you want
(ie. large dx and large negative dy can lead to small heuristic)

Iftah.

[Edited by - Iftah on November 6, 2007 10:24:04 AM]

Found out what was giving me bad paths and it wasn't the heuristic, it was a bug in the function "getAccessibleCoordinates". I'll have to track down the guy who wrote it.

I was wrong, your heuristic cannot be negative,
but I still think it is wrong, if I understand it correctly.

It may produce the fine path, but it will probably take much longer to calculate.

Imagine:
destCoord.x = 50, i->x = 40,
destCoord.y = 40, i->y = 50

h() = 100+100+(-100) = 100,

and but the same distance:
destCoord.x = 40, i->x = 50
destCoord.y = 40, i->y = 50
h() = 100+100+100 = 300

add absolute value to the third line to make it symmetric along the diagonals.

I agree with Kylotan - adding an extra cost would be the way to go..