# Pointy top hexagonal A* pathfinding

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 euclidian 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 nodes column number and r is its row number. Im 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 its not working out quite like that. As you can see in this pic, 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.

-

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.

-
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. –  Aeacus Apr 18 '12 at 10:21
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. –  amitp Apr 19 '12 at 15:23
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. –  Aeacus Apr 20 '12 at 10:00

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.

-
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. –  amitp Apr 17 '12 at 15:41
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. –  Roy T. Apr 17 '12 at 18:14
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. –  amitp Apr 17 '12 at 21:44
Hmm, I have some fixing of code to do! –  Roy T. Apr 18 '12 at 6:41