Calculating distance on a hexagon grid

Question

What I am trying to do is find how many hexagons are in between two points on a hex grid. I have tried searching online for a formula but I have not been able to find one that matches the type of hex grid I am using.

The hex grid is laid out like this one with the same coordinate system: http://www.gamedev.net/index.php?app=core&module=attach&section=attach&attach_rel_module=ccs&attach_id=1962

I am aware that this may not be possible with this coordinate system but this is a last ditch effort before I go back and change it. Thank you very much in advance.

Answer 1

If you had used a coordinate system which goes along the grain of the hexes in two directions, you could have used:

distance = max(
     abs(dest.y - start.y),     
     abs(dest.x - start.x),
     abs((dest.x - dest.y)*-1 - (start.x - start.y)*-1)
)

However you didn't, you're using a squiggly coordinate system which goes with the grain along one direction only (horizontal). Luckily we can transform between the two using

straight.y = squiggle.y
straight.x = ciel(squiggle.y / -2) + squiggle.x

So, solving for distance using this system of equations gets you:

distance = max(
     abs(dest.y - start.y),     
     abs(ceil(dest.y / -2) + dest.x - ceil(start.y / -2) - start.x),
     abs(-dest.y - ceil(dest.y / -2) - dest.x + start.y  + ceil(start.y / -2) + start.x)
)

That will get you the Manhattan distance between two hexes using only their coordinates (Assuming I didn't make any typos transposing x and y, since your grid is rotated 90 degrees from mine). However you must buy a cookie for my middle school algebra teacher for it to work, otherwise I will have messed up the distributive property.

Note: May require fiddling to work with negative coordinates, I didn't check.

Answer 2

Thanks @user2709663 and @jonathankoren for providing answers. I spend a lots of time with your answers, but found both of this has some problems. Or at least the type of grid considered for those answers are not stated clearly. However, I found a very nice tutorial and code implementation of this problem, along with a library for managing hex grid at: http://www.redblobgames.com/grids/hexagons/ (library code: http://www.redblobgames.com/grids/hexagons/implementation.html). I also implement a matlab version of the distance code for the "odd-q" vertical layout as follows:

function f = offset_distance(x1,y1,x2,y2)
    ac = offset_to_cube(x1,y1);
    bc = offset_to_cube(x2,y2);
    f = cube_distance(ac, bc);
end

function f = offset_to_cube(row,col)
    %x = col - (row - (row&1)) / 2;
    x = col - (row - mod(row,2)) / 2;
    z = row;
    y = -x-z;
    f = [x,z,y];
end

function f= cube_distance(p1,p2)
    a = abs( p1(1,1) - p2(1,1));
    b = abs( p1(1,2) - p2(1,2));
    c = abs( p1(1,3) - p2(1,3));
    f =  max([a,b,c]);
end

Here is a matlab testing code

sx = 6;
sy = 1;
for i = 0:7
    for j = 0:5
        k = offset_distance(sx,sy,i,j);
        disp(['(',num2str(sx),',',num2str(sy),')->(',num2str(i),',',num2str(j),')=',num2str(k)])
    end
end

Answer 3

The accepted answer is incorrect. I was initially suspicious of it when it mentioned using orthogonal coordinates on non-orthogonal axes, but running the code against my own solution shows that the over estimation of the distance compounds.

The actual correct solution is:

def hexDistance(start, dest):
  if (start.x == dest.x):
    return abs(dest.y - start.y)
  elif (start.y == dest.y):
    return abs(dest.x - start.x)
  else:
    dx = abs(dest.x - start.x)
    dy = abs(dest.y - start.y)
    if start.y < dest.y:
      return dx + dy - int(math.ceil(dx / 2.0))
    else:
      return dx + dy - int(math.floor(dx / 2.0))

This uses the hex->square representation:

        ------        
 ------  0, +1 ------ 
 -1, +1 ------ +1, +1  
 ------  0,  0 ------ 
 -1,  0 ------ +1,  0  
 ------  0, -1 ------ 
        ------        

 --------------------------
| -1, +1 |  0, +1 | +1, +1 |
|--------------------------
| -1,  0 |  0,  0 | +1, 0  |
|--------------------------|
|        |  0, -1 |        |
 -------------------------- 

Answer 4

To find a shortest path between two hexes:

1. Starting from one hex,
2. While on different rows, follow a diagonal towards to other row.
3. While on the same row, go straight towards the other hex.

Let's call the difference in the x direction dx and the difference in the y direction dy. If dy / 2 > dx, you don't have to do step two, so the distance is simply dy. Otherwise, the distance is dy + (dx - dy / 2). Unless I made a mistake.

Answer 5

M H Rasel linked this post in his previous answer: Hexagonal Grids. Following this excellent post, I figured out that I needed cube coordinates; that gives the easiest way to calculate the distances. Here is a code snippet in Kotlin:

data class Point(val x: Int, val y: Int, val z: Int) {

    fun distance(b: Point): Int {
        return (abs(x - b.x) + abs(y - b.y) + abs(z - b.z)) / 2
    }

}

var x = 0
var y = 0
var z = 0

val p1 = Point(x, y, z)    // starting position

val steps = "ne,ne,ne".split(",")    // go to North-East 3 times

for (direction in steps) {
    when(direction) {
        "n"  -> { ++y; --z }
        "ne" -> { ++x; --z }
        "se" -> { ++x; --y }
        "s"  -> { --y; ++z }
        "sw" -> { --x; ++z }
        "nw" -> { ++y; --x }
    }
}

val p2 = Point(x, y, z)    // we arrived here
val dist = p1.distance(p2)    // the result is here (in this example: 3)

Edit: I assume a flat-topped hex grid.

Answer 6

Here is a suboptimal, but not TOO suboptimal (should be O(n)) algorithm:

First, make a function that determines if a hexagon at a certain place in the hex grid intersects a line segment with a certain start point and end point (for example, calculate the six lines it is made up of and do something like: http://alienryderflex.com/intersect/ .)

Second, make a function that determines which hexagon on the hex grid a point is in.

Now, write your algorithm like this:

• Keep a list of all hexagons that the line segment has overlapped so far
• Start with the hexagon that the start of the line segment is in
• For each hexagon surrounding the most recently overlapped one, if it is not in the list, see if the lin segmente intersects that hexagon. If so, make this the new head of the list and repeat
• If we run out of hexagons to test, return the list we have made

I would suggest that you test the case of a line segment being exactly parallel to and running along the seam between hexagons, to see if you get the hexagons on one side, both sides or neither (and thus stopping).

Answer 7

If tiles on the grid can potentially become blocked then you are interested in the A* (or A-Star) maze-solving algorithm: http://labs.makemachine.net/2010/03/a-star-maze-solver/

The mechanism used in this video applies to a grid of squares, but with hardly any extra coding one could apply it to a hexagon mesh. For every tile, the solver knows which tiles to try next because the tiles store pointers to their surrounding tiles. In a grid of squares each tile would store a maximum of 4 pointers (maximum because they only store pointers to unblocked tiles), and the only difference in your case would be storing a maximum of 6 pointers.

If tiles are always traversable then A* will still certainly get the job done, however there is likely a faster way. If I'm interpreting your question correctly you're interested not in a distance, but in a whole-number count of the number of hexes between 2 given hexes? Try the following:

class Coord {
    int x;
    int y;
}

int dist(Coord hex1, Coord hex2) {
    int xSteps = Math.abs(hex1.x - hex2.x);
    int ySteps = Math.abs(hex1.y - hex2.y);

    return Math.max(xSteps, ySteps) + Math.abs(xSteps - ySteps);
}

Why you may ask? This question is about determining how many times we must move vertically or horizontally as opposed to diagonally. We want to move diagonally as much as possible, otherwise we're not being smart about our distances. Math.abs(xSteps - ySteps) is the number of non-diagonal moves we must make. Add to that the greater of the distances of x and y, and you're done.

Answer 8

If your hexagonal tiling has directions: N, NE, SE, S, SW, NW like in Advent of Code 2017 problem 11 and you offset the goal to be at (0,0) (by subtracting your position from target beforehand) the following logic worked for me:

def distance(self):
    # Take diagonal steps towards self.x == 0
    steps = abs(self.x)
    # y moves closer to 0 by steps because moving diagonal, but never moving too far
    if self.y > 0:
        # Might still be positive, but never negative
        y = max(self.y - steps, 0)
    else:
        # Might still be negative, but not positive
        y = min(self.y + steps, 0)
    # You move 2 positions north/south by a single move so divide y's by 2
    return abs(y) // 2 + abs(steps)

I think it might work for the hex grid with directions EAST and WEST instead of NORTH and SOUTH like yours, by just switching the roles of x and y. In that case you would move towards self.y == 0 diagonally (if needed) etc.

Answer 9

Here is an answer for C# and Offset "even-r" coordinates. Check this arctile first: https://www.redblobgames.com/grids/hexagons/

static int distanceBetweenCells(int x1, int y1, int x2, int y2)
{
    Vector3 evenr_to_cube(int row, int col)
    {
        int q = col - ((row + (row % 2))/2);
        int r = row;
        return new Vector3(q, r, -q - r);
    }
    Vector3 point_1 = evenr_to_cube(x1, y1);
    Vector3 point_2 = evenr_to_cube(x2, y2);
    int a = (int)Math.Abs(point_1.X - point_2.X);
    int b = (int)Math.Abs(point_1.Y - point_2.Y);
    int c = (int)Math.Abs(point_1.Z - point_2.Z);
    return Math.Max(a, Math.Max(b, c));
}

You can easily modify this for your kind of coordinates using the article above.

Answer 10

Image explaining the coordinate system

so, sadly i don't know which coordinate system you used back then, cause the link does not work anymore, but most of the solutions posted here did not work for me. This is the coordinate system i used:

        ------        
 ------  0, +1 ------ 
 -1, +1 ------ +1, 0  
 ------  0,  0 ------ 
 -1,  0 ------ +1, -1  
 ------  0, -1 ------ 
        ------        

 --------------------------
| -1, +1 |  0, +1 |        |
|--------------------------|
| -1,  0 |  0,  0 | +1, 0  |
|--------------------------|
|        |  0, -1 | +1, -1 |
 -------------------------- 

And this is the code / formula that worked for me for the points (x1,y1) and (x2,y2):

    public int distance(int x1, int y1, int x2, int y2){ //distance of hexfields, 1 is source 2 is target
        int dx = Mathf.Abs(x1 - x2);
        int dy = Mathf.Abs(y1 - y2);

        if(dx == 0){ return dy; }
        else if(dy == 0){ return dx; }
        else{
            if(x2 < x1 && y2 < y1){ //empty Corner
                return dx+dy;
            }else if(x2 < x1 && y2 > y1){ //Filled Corner
                return Mathf.Max(dx, dy);
            }else if(x2 > x1 && y2 < y1){ //Filled Corner
                return Mathf.Max(dx, dy);
            }else if(x2 > x1 && y2 > y1){ //empty Corner
                return dx+dy;
            }else return 0;
        }

    }

This could of course be optimized in terms of code quality but might be easier to understand as it is right now

Answer 11

Here's a direct calculation method that relies on four transformations that map all inputs into the area between a positive y vector and a 30 degree vector. First consider the flat stacked hexes the y axis. The x axis will be the wiggly one.

1. Translate the first coordinate to 0,0
2. Fold the left half on to the right half preserving the y axis
3. Fold the area between the downward 30 degree vector and the y axis over the area between the y axis and the upward 30 degree vector. The downward 30 degree vector will map onto the upward 30 degree vector.
4. Fold the area below the upward 30 degree onto the area between the y axis and the upward 30 degree vector.

After all this, the shortest path is upward 30 degrees to the target x and straight up to the target y.

def range x1, y1, x2, y2
  # translate x1,y1 to origin and 
  # and fold left half over right side
  rx = (x2 - x1).abs
  ry = y2 - y1 - (rx % 2) * (x1 % 2)

  # fold along 30deg downward
  if ry <= -rx / 2
    ry = ry.abs - rx % 2
    # rx remains unchanged
  else   
    # fold along 30deg upward
    if ry < rx / 2
      c = rx / 2 - ry # steps down from 30deg line
      ry = rx / 2 + (c + (rx % 2)) / 2
      rx -= c  # rx update must be after ry
    end
  end
  rx + ry - rx / 2
end