Implementing A-Star algorithm with hexes

Question

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;
}
else
{
    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?

Thanks.

Answer 1

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.