Pointy top hexagonal A* pathfinding

Question

I'm trying to create a game with a hex based map with the points at the top. I have most of it working, however the path finding is being a little awkward. The heuristic I'm using is called Euclidean I believe and is like so:

var dx:Number = destinationNode.c - node.c;
var dy:Number = destinationNode.r - node.r;
return Math.sqrt((dx * dx) + (dy * dy));

Node is the node the unit is currently on, c is the node's column number and r is its row number. I'm using these as a simpler x and y coords. I'm trying to limit the unit to 3 hex moves in one round, so initially I thought it'd be as simple as IF returned heuristic < 3 unit can move to that hex, however it's not working out quite like that.

enter image description here

As you can see in the pic above, the bottom right selected hex with the "1 + 9 = 3.162277" is moveable to in 3 moves, however the hex with "9 + 1 = 3.162277" on the far right would need 4 moves to reach it. Can anyone offer any advice on how to make this work?

EDIT: My problem was being caused because I was using a Cartesian coordinate system and was just staggering every other Y coord. Fixed this by making the Y axis go down at a 60 degree angle. Thanks to amitp for the links that showed me what I was doing wrong.

Answer 1

The A* heuristic is an estimate. It usually does not give you the true distance.

You can calculate distances exactly on a hexagonal grid. See section 4 of Clark Verbrugge's hex grid guide, and then section 2. Alternatively, see aaz's answer on this stackoverflow post.

• Aeacus: Those answers look good, but only problem now is I have the hexes set out in a square system rather than the y co-ord being at a 60 degree angle (which im guessing is causing all the problems). Ach well now to figure out how to do that with my current code.
• amitp: Yes, the square system is common. See section 4 of the article for conversion from the square to the 60° system. For my last hex game, I used the square system everywhere, and only converted for calculating distances.
• Aeacus: I was able to figure out some fairly simple code to change the positions of the hexes by staggering the new hexes y value every time a loop had a factor of 2. Meant i could still easily have a rectangle border around the hexes but the y coord was at the 60 degree angle.

Answer 2

You have to plot the entire path and then only do the first 3 moves. The place within 3 squares with the best score isn't necessarily on the path to where you want to go.

Also your heuristic is an estimate, and from what I can tell, Euclidian is more than good enough for you, although it sometimes underestimates a little in your case.

• amitp: True, you don't need sqrt for sorting, but A* also uses the heuristic for addition (adding the heuristic to the cost), and there the sqrt does matter.
• Roy T.: I have to double check this in my own implementation, I think it doesn't matter because as long as you haven't found the path the heuristic part of the cost is on the same scale. But it could interfere if (ActualCost + H) is a false overestimate to the goal because of a large H and a low ActualCost thus violating the 'admissible heuristic' clause of the H in A*. I've edited the optimization out of my answer for now.
• amitp: Yep, not only is it an overestimate, but (ActualCost + H) when H is large assigns too much weight to the H portion and too little to the G portion. In other words, when picking the best item from the Open set, it's mostly guided by H, and G doesn't play much of a role. This turns A* into best-first search, which isn't bad, but it may not be what you wanted.
• Roy T.: Hmm, I have some fixing of code to do!