Calculating distance on a hexagon grid

Question 1

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

Question 2

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.

Question 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 |        |
 --------------------------

Question 4

To find a shortest path between two hexes:

Starting from one hex,
While on different rows, follow a diagonal towards to other row.
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.

Question 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.

Question 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).

Question 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.

Question 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.