2D and 3D Hexagonal Coordinate Systems
coordinates, fcc, game, hexagonsI 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).
_____ _____
_____/ \_____ _____/-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 ( ).
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.
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.
(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,-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).