Need help understanding a posted algorithm (calculating step distance between hexagons on a grid)

Question

I have been hunting for an answer on how to accurately calculate the distance between 2 hexagons on a hexagon grid as a number of hexs or "steps".

I came across this posting and it seems to be the correct solution as I have my hexagons setup exactly how Torben describes, however I am trying to figure out the algorithm he is proposing. Specifically:

mydistance((x1,y1), (x2,y2))
     = if x1>x2 then mydistance((x2,y2), (x1,y1))
       else if y2>=y1 then x2-x1 + y2-y1
       else max(x2-x1, y1-y2)

I am pretty sure he is describing an algorithm however, I am getting lost on what he means by "mydistance((x2,y2), (x1,y1))" etc. I figure he probably meant the formula for a distance between 2 points? I tried that and its not working out :( Furthermore, he says it on top before the = and that's just throwing me off.

Can anyone make an accurate idea what he means?

Thanks!!!

EDIT (IMPORTANT) ---- Here is an image of my hexagon grid pattern to shed some light: Please visit http://www.bart4president.com/test/hexGrid.jpg

Here is a clipping of the original posting below:

---

I prefer a numbering where both x and y correspond to straight lines of hexes, i.e., letting x increase (with constant y) by going right and y increase (with constant x) by going 60 degrees down from right (assuming (0,0) is top left corner).

This way, if you move in one of the three "natural" directions, you either have constant x, constant y or constant (x+y).

That makes calculation of distances etc. easier, as you don't have to sepcial-case on odd and even rows.

I assume you know the hex coordinates and want to find the distance in number of hexes while moving across edges.

If you had used the alternative numbering I described above, the distance is calculated as follows:

mydistance((x1,y1), (x2,y2))
 = if x1>x2 then mydistance((x2,y2), (x1,y1))
   else if y2>=y1 then x2-x1 + y2-y1
   else max(x2-x1, y1-y2)

With the numbering shown on the webpage you sited, you can calculate distance as follows:

yourdistance((x1,y1),(x2,y2))
 = mydistance((x1 - y1 `div` 2,y1), (x2 - y2 `div` 2,y2))

I.e., convert to the simpler coordinate system and calculate distance in that. You convert by subtracting half the y coordinate (rounded down) from the x coordinate.

Torben

Answer 1

For comparison, here's my code for calculating the distance between two hexes:

/**
 *  Hex distance calculation
 */
public static int distance(int x1, int y1, int x2, int y2) {
    int dx=x2-x1;
    int dy=y2-y1;

    if (dx*dy>0) {
        return Maths.abs(dx)+Maths.abs(dy);
    } else {
        return Maths.max(Maths.abs(dx),Maths.abs(dy));
    }
}

(x1,y1) and (x2,y2) are the co-ordinates of the two hexes you want to calculate the distance between. Note that these co-ordinates are not at right angles like they would be on a square grid: increasing x and increasing y are 60 degrees apart.

Answer 2

In hexagonal coordinate system such that the y-axis was at a 60-degree angle to the x-axis. This avoids the odd-even row distinction. The distance in hexagonal coordinate system is:

dx = x1 - x0
dy = y1 - y0

if sign(dx) == sign(dy)
    abs(dx + dy)
else
    max(abs(dx), abs(dy))

You can convert (x', y) from your coordinate system to (x, y) in this one using:

x = x' - floor(y/2)

So dx becomes:

dx = x1' - x0' - floor(y1/2) + floor(y0/2)

Careful with rounding when implementing this using integer division. In Java for int y floor(y/2) is (y%2 ? y-1 : y)/2.

Answer 3

You write:

I am pretty sure he is describing an algorithm however, I am getting lost on what he means by "mydistance((x2,y2), (x1,y1))" etc. I figure he probably meant the formula for a distance between 2 points?

Just to pick up on that point, as the comment on your question hinted at but neither of the answers seems to have addressed:

The statement mydistance((x2,y2), (x1,y1)) is a recursive call to the function that is being defined. In this case, if the function is called with x1>x2 then the function is called again with the points swapped.