Take the 2-minute tour ×

To start, let me say that I'm a beginner and this program is my first attempt at "flying solo" as it were, so please be patient if I sound like a moron.

I have a grid of hexes, and I want to use A* to find a path from one to another.

The hex tiles fit inside an 80 by 80 square, are stored internally as a 2 dimensional array, and referenced in the code by those 2D co-ordinates (i.e, hex[0,0], hex[1,0] etc).

They are displayed to the screen with the "staggering" transformation:

if (X % 2 == 0)
    X = (X / 2) * 120;
    Y = Y * 80;
    X = ((X / 2) * 120);
    Y = (Y * 80) + 40;

I have my A* implementation set up, but obviously, two hexes out of the 6 adjacent to each hex are counted as being 2 away rather than 1, and which two differs depending on whether X is odd or even.

I've tried to read up on ways to calculate the correct difference, but I'm not sure where to begin implementing any of the varying methods I've seen around. Is there a simple transformation that I can make to the co-ordinate system I already have purely for the purposes of calculating distance between hexes, or a formula I can use?


share|improve this question
This question is confusing. The distance between the centers of any two adjacent hexes is the same. That's the whole point of using hexes. Why would you count two of them as being two units away? You say "obviously" like it is obvious what you're talking about but I assure you it is not. –  Eric Lippert Dec 21 '11 at 18:22
A picture of the hexes with their array coordinates drawn would help a lot for visualising your problem. –  George Duckett Dec 21 '11 at 18:26
I think something's missing here. X gets the same values in both branches. –  Dialecticus Dec 21 '11 at 18:29
@Eric he used obviously as in "I have bad algorithm obviously, because two adjacent hexes in it are counted as two hexes away". –  Dialecticus Dec 21 '11 at 18:36
@EricLippert: The problem is if you map hex coordinates like that, you can't use the usual Manhattan distance, which is what I suspect OP was using –  Amadan Dec 21 '11 at 18:51

1 Answer 1

up vote 1 down vote accepted

If I am not mistaken, this should do it:

int HexDistance(int x1, int y1, int x2, int y2) {
  int y1d = (y1 << 1) | (x1 & 1);
  int y2d = (y2 << 1) | (x2 & 1);
  int dx = Math.Abs(x2 - x1);
  int dyd = Math.Abs(y2d - y1d);
  return (dx < dyd) ? (dyd - dx) / 2 + dx : dx;

Assuming the grid is like this:

X:   0  1  2  3  4  5  6                                                    
Y:   0     0     0     0
        0     0     0
     1     1     1     1
        1     1     1
     2     2     2     2

where verticals and diagonals are adjacent, but horizontals aren't.

Basically, first renumber the y coordinates: in even columns, double them; in odd columns, double and add 1. This gives the following grid:

X:   0  1  2  3  4  5  6                                                    
Y:   0     0     0     0
        1     1     1
     2     2     2     2
        3     3     3
     4     4     4     4

Now, if things are on diagonal, it's easy. If horizontal is bigger, then just count the horizontal difference; if vertical is bigger, count the vertical difference till diagonal, then add the horizontal difference.

EDIT: I had an error again. Serves me right for trying to code at 5am. Apologies; hope this is okay.

share|improve this answer
Thanks alot Amadan. Using that function returns the right distance between any two hexes on my grid, from their co-ordinates in my rectangular array. –  user1110391 Dec 22 '11 at 10:34

Your Answer


