Posts 2D and 3D Hexagonal Coordinate Systems
Post

2D and 3D Hexagonal Coordinate Systems

I want to make a video game with hexagonal tiles instead of square tiles. One of the first challenges I’ve run into is finding a coordinate system for referencing the tiles in my game.

2D Hexagons

With squares on a grid, using (x, y) coordinates is straightforward. Turns out there are similar techniques for hexagonal grids. One of the techniques linked in that guide is called “Cube Coordinates,” which use a (x, y, z) triple to refer to each hexagon, with the stipulation that the sum of the three numbers must be 0 (which forces each hexagon to have a single unique triple).

1
2
3
4
5
6
7
8
9
10
11
               _____                                _____
         _____/     \_____                    _____/-2  2\_____
   _____/     \_____/     \_____        _____/-1  2\__0__/-2  1\_____
  /     \_____/     \_____/     \      /0   2\_-1__/-1  1\__1__/-2  0\
  \_____/     \_____/     \_____/      \_-2__/0   1\__0__/-1  0\__2__/
  /     \_____/     \_____/     \  ->  /1   1\_-1__/0   0\__1__/-1 -1\
  \_____/     \_____/     \_____/      \_-2__/1   0\__0__/0  -1\__2__/
  /     \_____/     \_____/     \      /2   0\_-1__/1  -1\__1__/0  -2\
  \_____/     \_____/     \_____/      \_-2__/2  -1\__0__/1  -2\__2__/
        \_____/     \_____/                  \_-1__/2  -2\__1__/
              \_____/                              \__0__/

The nice feature about this system is that it’s hexagonally symmetrical, which simplifies a lot of algorithms (like pathfinding and calculating distance).

Another nice feature of this coordinate system is that one of the (x, y, z) coordinates is degenerate, meaning given any two of the three I can derive the third (since x + y + z = 0). So my game only needs to store two of the three coordinates.

There are some other nice features and good things to know, but the hexagon guide I linked earlier covers it all better than I could cover.

3D Hexagons

I want my game to have 3D motion, like digging holes, exploring caves, and building structures. However, all the resources I’ve found so far for making hexagonally-based maps for video games assumed a flat 2D map. Somehow I need to extend the hexagonal map into 3D space.

The first technique I considered was to stack hexagonal maps one directly on top of the other. In this arrangement, a hexagonal space would have six neighbors to the sides, one above, and one below. However, one of the main points of using hexagons instead of squares is to get more accurate distances, and stacking hexagons like this diminishes that benefit.

The other option for stacking hexagonal layers is to offset them, so that each hexagon has three neighbors above and three below, giving 12 neighbors total. There are two ways1 of doing this: FCC and HCP lattices, which stand for Face-Centered Cubic and Hexagonal Close Packing, respectively.

Here’s an ASCII diagram of FCC and HCP for reference. Each diagram depicts a single sphere on the origin marked by (*) surrounded by all 12 of its neighbors—three on top marked (A), three below marked (B), and six to the side marked ( ).

1
2
3
4
5
6
7
8
9
         FCC             HCP

 L1    (A) (A)          (A) (A)    L1
 __      (A)      __      (A)      __
       ( ) ( )          ( ) ( )
 L2  ( ) (*) ( )      ( ) (*) ( )  L2
 __    ( ) ( )    __    ( ) ( )    __
         (B)            (B) (B)
 L3    (B) (B)            (B)      L1

The difference is that FCC alternates between three types of layers—marked L1, L2, and L3—while HCP alternates between only two types of layers—marked L1 and L2.

FCC is more symmetrical around the central point, so I’ll stick with that one from here on out.

Close-packed cannonballs in FCC lattice Image by Funkdooby (CC BY-SA 2.0)

For a different visualization of FCC packing, here’s a pyramid of cannonballs. Cannonballs are traditionally stacked in a square pyramid, where each horizontal layer is a square grid of cannonballs. The other faces of the pyramid are layers of spheres arranged hexagonally.

FCC 3D Coordinate System

The four hexagonal layers in FCC packing give me a structure that I can use for a coordinate system. Similar to the two-dimensional case—which used a degenerate third coordinate—I will use 4 coordinates instead of the strictly necessary 3, giving a degenerate fourth coordinate.

Here’s the same diagram for FCC repeated to show the four different layers: again using ( ) to depict the neighbors in the same layer as the origin, and using (A) and (B) to represent the two sandwiching layers.

1
2
3
4
5
6
7
  (A) (A)      (B) ( )      ( ) (B)      ( ) ( )
    (A)          ( )          ( )          (B)
  ( ) ( )      (B) ( )      ( ) (B)      (A) (A)
( ) (*) ( )  (B) (*) (A)  (A) (*) (B)  ( ) (*) ( )
  ( ) ( )      ( ) (A)      (A) ( )      (B) (B)
    (B)          ( )          ( )          (A)
  (B) (B)      ( ) (A)      (A) ( )      ( ) ( )

And now I can assign coordinate quadruples to each point in the FCC structure. I’ve been careful to assign the As and Bs only once to each point in the diagrams above, so now I can represent A with 1 and B with -1 so that the sum of the coordinates for any point is 0.

1
2
3
4
5
6
7
        ( 1,-1, 0, 0) ( 1, 0,-1, 0)
              ( 1, 0, 0,-1)
        ( 0,-1, 0, 1) ( 0, 0,-1, 1)
( 0,-1, 1, 0) ( 0, 0, 0, 0) ( 0, 1,-1, 0)
        ( 0, 0, 1,-1) ( 0, 1, 0,-1)
              (-1, 0, 0, 1)
        (-1, 0, 1, 0) (-1, 1, 0, 0)

Knowing the coordinates for these 12 neighboring points, I can build off of them to find the coordinates for any other point in the FCC space.

Final Thoughts

I’m still not certain this is the best coordinate system to use for representing an FCC world in a video game. It might be more convenient to use regular 2D coordinates with a z-layer coordinate thrown in. I’ll have to try to use this coordinate system to know.

This system does have some nice properties, though. Similar to the 2D “Cube Coordinates”, this coordinate system is hexagonally symmetrical, and only 3 of the 4 numbers need to be stored. Additionally, when points share two of the four coordinates (for example, ( 1,-1, 0, 0) and (-1, 1, 0, 0) share a trailing 0, 0) they lie on a straight line (in hexagon-terms).

Footnotes

  1. There is technically an infinite variety, but most of them are disorderly. See the mention of “Barlow packings” here