4
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

Reset to default
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – Aeacus
    Commented Apr 18, 2012 at 10:21
  • \$\begingroup\$ 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. \$\endgroup\$
    – amitp
    Commented Apr 19, 2012 at 15:23
  • \$\begingroup\$ 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. \$\endgroup\$
    – Aeacus
    Commented Apr 20, 2012 at 10:00
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – amitp
    Commented Apr 17, 2012 at 15:41
  • \$\begingroup\$ 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. \$\endgroup\$
    – Roy T.
    Commented Apr 17, 2012 at 18:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – amitp
    Commented Apr 17, 2012 at 21:44
  • 1
    \$\begingroup\$ Hmm, I have some fixing of code to do! \$\endgroup\$
    – Roy T.
    Commented Apr 18, 2012 at 6:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .