Cell to Cell Distance in a 2D Hexagonal Tile Map

I needed to grab the distance between any two cells in a hex grid, and I found it was more difficult than I originally thought it would be.. There were lots of blogs and theory sites which had distance formulas, but none of them worked for every cell in the grid, and most of them didn't work at all! Wtf! Most of them didn't even work on the grids they claimed they worked on.. I ended up creating my own distance function, feel free to use it if you find it handy!

FireTeams uses an isometric hex-tile grid for its game. Once your tiles have been made, these grids are fairly simple to create and implement. The only real trouble I had with this style of grid was grabbing the distance (measured by the number of tiles a unit would have to traverse) between any two tiles on the grid. Here's the function as a whole, I'll proceed to explain each part throughout the rest of the post:

Update: An anonymous poster found a bug in my implementation below, and graciously posted a fixed-up version! See the comments for his working algorithm. Thanks, Anonymous!!

---

var dx = Math.abs(start.x - end.x);
var dy = Math.abs(start.y - end.y);
var distance = 0;

if (dx < dy/2 )
      distance = dy;
else
      distance = dy + dx - Math.floor(dy/2.0);

if (start.y % 2 == 0)
      if (dy % 2 == 1 && start.x > end.x)
            distance--;
else
      if (dy % 2 == 1 && start.x < end.x)
            distance--;

return distance;

---

The distance formula wasn't as simple as it is in a standard square-tile grid. For one, the hex-tile grid allows units to move in exactly 6 directions instead of the 4 or 8 (if diagonal movement is allowed) directions of movement. Two, because of the nature of hex tiles, every other row or column (I guess this depends on how your tiles are oriented), is offset. The grid implementation I used is as follows:

When the tiles are layed out in this format, it's easy to see that the Y coordinates increase at approximately twice the rate as the X coordinates when traversing the tiles south. This gives us a really easy special case for the distance:

if (dx < dy / 2) distance = dy;

In other words, any time the horizontal distance is less than half the vertical distance, the shortest path between the two cells will always be the vertical distance. For example, starting at cell <0,0> on the grid above, the cells <0,7> through <3,7> can all be reached in exactly 7 steps.

In fact, the minimum distance between any two cells can be visualized pretty simply: travel diagonally towards the cell until your y-coordinates are the same, then travel horizontally until you've reached the cell. This leads us to the more general case for the distance between our hex tiles:

distance = dy + dx - Math.floor(dy / 2.0);

This term requires a slight bit of explaining. Since the shortest path between two cells require traveling vertically and horizontally, it makes sense to add the dy and dx terms together. This over-estimates the actual distance. This can be seen easily by looking at the distance to go from cell <0,0> to cell <4,7>. Adding the dx and dy terms (which are 4 and 7 respectively) give us a distance of 11, while the actual distance is only 8. The distance of 11 would be true if our unit were to travel directly south, then directly east. Since we are trying to get to cell <4,7> in the shortest distance, we would actually travel along the diagonal all the way down to cell <3,7>, and then move one more east to cell <4,7>. To compensate for this shorter distance, we can use our observation from above: when traveling south in a diagonal, the x-coordinate increases at half the rate the y-coordinate does. You can see on the grid, when traveling in the diagonal from <0,0> to <3,7>, the distance dx increases by 1 tile everytime dy increases by 2. The further we travel along a diagonal, the bigger this dx term gets. This increase in dx is not wanted in our calculation, since these extra tiles do not need to be traversed in order to get to our destination, so we want to subtract them. The term:

Math.floor(dy / 2.0)

gives us that extra distance generated for dx as dy increases, so we can simply subtract this from the addition of dy and dx to get our distance! Yay!

...Almost done! Most tiles will now give correct distances, but not all of them. There is still one more special case we have to tackle, and this is a direct cause of the offsetting done on a row x row basis. Because the X-coordinate is offset every other row, about 1/4 of our calculated tiles get calculated by 1 too many tiles. Cells sitting on the offset rows are overestimated by 1. In particular, depending on which row our start tile is in, either the tiles in the odd rows on the east of the start tile are overestimated, or the tiles on the west side of the tile are overestimated. This is an easy special case:

if (start.y % 2 == 0)
      if (dy % 2 == 1 && start.x > end.x)
            distance--;
else
      if (dy % 2 == 1 && start.x < end.x)
            distance--;

In other words, for the first half of the statement, if our start tile is in a non-offset row, and our dy term is even, and the destination tile is west of the start tile, then our distance will be over-estimated, and we should decrease by a value of 1. If our start tile is on an offset row, then the over-estimated tiles are to the east of the start tile.


So there you have it! A simple function for calculating the distance between any two cells in a hex-tile grid. I hope others find this useful as well! Cheers, and I hope everyone has a good Christmas Eve!