# 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 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.

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.

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. Apr 18, 2012 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. Apr 19, 2012 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. Apr 20, 2012 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. Apr 17, 2012 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. Apr 17, 2012 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. Apr 17, 2012 at 21:44
• Hmm, I have some fixing of code to do! Apr 18, 2012 at 6:41