Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
1  
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
1  
Hmm, I have some fixing of code to do! –  Roy T. Apr 18 '12 at 6:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.