Calculating Distance in a Hexagonal Grid

Lately, I've been working on a 2-D, hex-based strategy game, in the vein of the old classic, Civil War Generals 2.  Hex grids are a staple of wargames, like the old 5 Star SSI games (Panzer General and all of its descendants), although they've also turned up in some newer games, like Civilization 5 and Battle for Wesnoth.

Although they've been around forever, resources on coding hexmaps are somewhat scanty, in comparison to other things you might want to do with hobby game dev.  A list of some canonical articles:

• Isometric 'n; Hexagonal Maps Part 1
• Putting People, Creatures, Items, etc on Iso/Hex Maps, and still having it come out correctly
• Amit's Game Programming Information

Naturally, a lot of the same algorithms you'd use with square grids are equally valid on hex grids.  However, often times, those algorithms require some tweaking to work correctly with a hexagonal grid, and its not always easy to understand how they need to be tweaked without a good deal of iteration.

 

One thing that I found particularly difficult was understanding the correct way to compute distances in a hex grid.  Amit's site has some valuable information, but, as much of it is really old, featuring archived newsgroup posts with ascii art and code written in nearly defunct languages, or worse, links that no longer exist, it is really more difficult to understand than it need be.

 

I'll start with a brief overview of hexagonal grids, and their typical representation.

 

Below, you'll see a hexagonal grid.

Typically one would represent such a grid in code with a two-dimensional array of cells.

MapCell[][] map = new MapCell[10[10]

Now, you'll notice that each odd-numbered row is not directly beneath the row above it; rather, the odd rows are shifted half a hex-width over from the row above and below.  This has some important implications for calculating the neighbor of a given cell, namely that the x,y offsets into the underlying rectangular array are different depending on the y-coordinate of the starting cell.  Moving east-west in such a grid is always the same, but moving along the diagonals, (NE,SE,SW, NW) is different depending on which row you are in.

int dx = 0;
int dy = 0;
switch (facing) {
  case HexFacing.NE:
   dx = (y % 2 == 0) ? 0 : 1;
    dy = -1;
    break;
  case HexFacing.E:
    dx = 1;
    break;
  case HexFacing.SE:
    dx = (y % 2 == 0) ? 0 : 1;
    dy = 1;
    break;
  case HexFacing.SW:
    dx = (y % 2 == 0) ? -1 : 0;
    dy = 1;
    break;
   case HexFacing.W:
     dx = -1;
     break;
   case HexFacing.NW:
     dx = (y % 2 == 0) ? -1 : 0;
     dy = -1;
     break;
}



Calculating Distance
A side effect of this property of hex grids is that the standard distance algorithms, like Euclidian and Manhattan distance, don't work correctly without modification.  To calculate distance in a hex-grid, one first has to convert the rectangular array coordinates into what we’ll call hex-space.  A fuller discussion can be found at Clark Verbrugge’s Hex Grids, with all of the mathematics behind this.  This is the most concise and correct explanation I have yet found.  Anyway, here is the code:

public static int HexDistance(Point p1, Point p2) {

  int ax = p1.X - Floor2(p1.Y);

  int ay = p1.X + Ceil2(p1.Y);

  int bx = p2.X - Floor2(p2.Y);

  int by = p2.X + Ceil2(p2.Y)

  int dx = bx - ax;

  int dy = by - ay;

  if (Math.Sign(dx) == Math.Sign(dy)) {

     return Math.Max(Math.Abs(dx), Math.Abs(dy));

  }

  return Math.Abs(dx) + Math.Abs(dy);
}
 
private static int Floor2(int x) {
  return ((x >= 0) ? (x >> 1) : (x - 1) / 2);
}
private static int Ceil2(int x) {
  return ((x >= 0) ? ((x + 1) >> 1) : x / 2);
}