Hexagonal Grids

Hexagons are 6-sided polygons. Regular hexagons have all the sides the same length. I'll assume all the hexagons we're working with here are regular. The typical orientations for hex grids are vertical columns (flat topped) and horizontal rows (pointy topped).

Hexagons have 6 sides and 6 corners. Each side is shared by 2 hexagons. Each corner is shared by 3 hexagons. For more about centers, sides, and corners, see my article on grid parts^[4] (squares, hexagons, and triangles).

In a regular hexagon the interior angles are 120°. There are six “wedges”, each an equilateral triangle with 60° angles inside. Each corner is size units away from the center. In code:

function pointy_hex_corner(center, size, i):
    var angle_deg = 60 * i - 30°
    var angle_rad = PI / 180 * angle_deg
    return Point(center.x + size * cos(angle_rad),
                 center.y + size * sin(angle_rad))

To fill a hexagon, gather the polygon vertices at hex_corner(…, 0) through hex_corner(…, 5). To draw a hexagon outline, use those vertices, and then draw a line back to hex_corner(…, 0).

The difference between the two orientations is a rotation, and that causes the angles to change: flat topped angles are 0°, 60°, 120°, 180°, 240°, 300° and pointy topped angles are 30°, 90°, 150°, 210°, 270°, 330°. Note that the diagrams on this page use the y axis pointing down (angles increase clockwise); you may have to make some adjustments if your y axis points up (angles increase counterclockwise).

In math, the "circumradius" is the distance from the center to a corner (I call this size); the "inradius" is the distance from the center to the middle of an edge. The "maximal diameter" is twice the circumradius; the "minimal diameter" is twice the inradius. Wikipedia^[5] has more.

Size and Spacing#

Next we want to put several hexagons together. The size is the distance from the center to any corner. In the pointy orientation, a hexagon has width w = sqrt(3) * size and height h = 2 * size. The sqrt(3) comes from sin(60°).

The horizontal distance between adjacent hexagon centers is w. The vertical distance between adjacent hexagon centers is h * 3/4.

Some games use pixel art for hexagons that does not match an exactly regular polygon. The angles and spacing formulas I describe in this section won't match the sizes of your hexagons. The rest of the article, describing algorithms on hex grids, will work even if your hexagons are stretched or shrunk a bit, and I explain on the implementation page how to handle stretching.

Another way to look at hexagonal grids is to see that there are three primary axes, unlike the two we have for square grids. There's an elegant symmetry with these.

Let's take a cube grid and slice out a diagonal plane at x + y + z = 0. This is a weird idea but it helps us make hex grid algorithms simpler. In particular, we can reuse standard operations from cartesian coordinates: adding coordinates, subtracting coordinates, multiplying or dividing by a scalar, and distances.

Sometimes we don't have obvious algorithms for hex grids, but we do have algorithms for cube grids. Using cube coordinates allows us to adapt cube grid algorithms to work on hex grids. To use the algorithms with another coordinate system, we can convert to cube coordinates, run the algorithm, and convert back.

Axial coordinates#

The axial coordinate system, sometimes called “trapezoidal” or “oblique” or “skewed”, is built by taking two of the three coordinates from a cube coordinate system. Since we have a constraint x + y + z = 0, there's some redundancy, and we don't need to store all three coordinates. This diagram is the same as the previous one, except I don't show y:

There are many choices of cube coordinate system, and many choices of axial coordinate system. I'm not going to show all of the combinations in this guide. I've chosen q for "column" = x and r as "row" = z. This choice is arbitary, as you can rotate and flip the diagrams to make many different assignments of ±x,±y,±z to q,r.

The advantage of this system over offset grids is that the algorithms are cleaner when you can use add, subtract, multiply, and divide on hex coordinates. The disadvantage of this system is that storing a rectangular map is a little weird; see the map storage section for ways to handle that. In my projects, I name the axes q, r, s so that I have the constraint q + r + s = 0, and then I can calculate s = -q - r when I need the third coordinate for algorithms that work better with cube coordinates.

Moving one space in hex coordinates involves changing one of the 3 cube coordinates by +1 and changing another one by -1 (the sum must remain 0). There are 3 possible coordinates to change by +1, and 2 remaining that could be changed by -1. This results in 6 possible changes. Each corresponds to one of the hexagonal directions. The simplest and fastest approach is to precompute the permutations and put them into a table of Cube(dx, dy, dz) at compile time:

var cube_directions = [
    Cube(+1, -1, 0), Cube(+1, 0, -1), Cube(0, +1, -1), 
    Cube(-1, +1, 0), Cube(-1, 0, +1), Cube(0, -1, +1), 
]

function cube_direction(direction):
    return cube_directions[direction]

function cube_neighbor(cube, direction):
    return cube_add(cube, cube_direction(direction))

As before, we'll use the cube system as a starting point. Take the table of Cube(dx, dy, dz) and convert into a table of Hex(dq, dr):

var axial_directions = [
    Hex(+1, 0), Hex(+1, -1), Hex(0, -1), 
    Hex(-1, 0), Hex(-1, +1), Hex(0, +1), 
]

function hex_direction(direction):
    return axial_directions[direction]

function hex_neighbor(hex, direction):
    var dir = hex_direction(direction)
    return Hex(hex.q + dir.q, hex.r + dir.r)

Moving to a “diagonal” space in hex coordinates changes one of the 3 cube coordinates by ±2 and the other two by ∓1 (the sum must remain 0).

var cube_diagonals = [
    Cube(+2, -1, -1), Cube(+1, +1, -2), Cube(-1, +2, -1), 
    Cube(-2, +1, +1), Cube(-1, -1, +2), Cube(+1, -2, +1), 
]

function cube_diagonal_neighbor(cube, direction):
    return cube_add(cube, cube_diagonals[direction])

As before, you can convert these into axial by dropping one of the three coordinates, or convert to offset/doubled by precalculating the results.

In the cube coordinate system, each hexagon is a cube in 3d space. Adjacent hexagons are distance 1 apart in the hex grid but distance 2 apart in the cube grid. This makes distances simple. In a square grid, Manhattan distances are abs(dx) + abs(dy). In a cube grid, Manhattan distances are abs(dx) + abs(dy) + abs(dz). The distance on a hex grid is half that:

function cube_distance(a, b):
    return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2

An equivalent way to write this is by noting that one of the three coordinates must be the sum of the other two, then picking that one as the distance. You may prefer the “divide by two” form above, or the “max” form here, but they give the same result:

function cube_distance(a, b):
    return max(abs(a.x - b.x), abs(a.y - b.y), abs(a.z - b.z))

The maximum of the three coordinates is the distance. You can also use the max of abs(dx-dy), abs(dy-dz), abs(dz-dx) to figure out which of the 6 “wedges” a hex is in; see diagrams here.

1. First we calculate N=10 to be the hex distance between the endpoints.
2. Then evenly sample N+1 points between point A and point B. Using linear interpolation, each point will be A + (B - A) * 1.0/N * i, for values of i from 0 to N, inclusive. In the diagram these sample points are the dark blue dots. This results in floating point coordinates.
3. Convert each sample point (float) back into a hex (int). The algorithm is called cube_round.

Given a hex center and a range N, which hexes are within N steps from it?

We can work backwards from the hex distance formula, distance = max(abs(x), abs(y), abs(z)). To find all hexes within N steps, we need max(abs(x), abs(y), abs(z)) ≤ N. This means we need all three to be true: abs(x) ≤ N and abs(y) ≤ N and abs(z) ≤ N. Removing absolute value, we get -N ≤ x ≤ +N and -N ≤ y ≤ +N and -N ≤ z ≤ +N. In code it's a nested loop:

var results = []
for each -N ≤ x ≤ +N:
    for each -N ≤ y ≤ +N:
        for each -N ≤ z ≤ +N:
            if x + y + z = 0:
                results.append(cube_add(center, Cube(x, y, z)))

This loop will work but it's somewhat inefficient. Of all the values of z we loop over, only one of them actually satisfies the x + y + z = 0 constraint on cubes. Instead, let's directly calculate the value of z that satisfies the constraint:

var results = []
for each -N ≤ x ≤ +N:
    for each max(-N, -x-N) ≤ y ≤ min(+N, -x+N):
        var z = -x-y
        results.append(cube_add(center, Cube(x, y, z)))

This loop iterates over exactly the needed coordinates. In the diagram, each range is a pair of lines. Each line is an inequality (a half-plane^[20]). We pick all the hexes that satisfy all six inequalities.

If you need to find hexes that are in more than one range, you can intersect the ranges before generating a list of hexes.

You can either think of this problem algebraically or geometrically. Algebraically, each hexagonally-shaped region is expressed as inequality constraints of the form -N ≤ dx ≤ +N, and we're going to solve for the intersection of those constraints. Geometrically, each region is a cube in 3D space, and we're going to intersect two cubes in 3D space to form a cuboid^[21] in 3D space, then project back to the x + y + z = 0 plane to get hexes. I'm going to solve it algebraically:

First, we rewrite constraint -N ≤ dx ≤ +N into a more general form, xmin ≤ x ≤ xmax, and set xmin = center.x - N and xmax = center.x + N. We'll do the same for y and z, and end up with this generalization of the code from the previous section:

var results = []
for each xmin ≤ x ≤ xmax:
    for each max(ymin, -x-zmax) ≤ y ≤ min(ymax, -x-zmin):
        var z = -x-y
        results.append(Cube(x, y, z))

The intersection of two ranges a ≤ x ≤ b and c ≤ x ≤ d is max(a, c) ≤ x ≤ min(b, d). Since a hex region is expressed as ranges over x, y, z, we can separately intersect each of the x, y, z ranges then use the nested loop to generate a list of hexes in the intersection. For one hex region we set xmin = H.x - N and xmax = H.x + N and likewise for y and z. For intersecting two hex regions we set xmin = max(H1.x - N, H2.x - N) and xmax = min(H1.x + N, H2.x + N), and likewise for y and z. The same pattern works for intersecting three or more regions, and can generalize to other shapes^[22] (triangles, trapezoids, rhombuses, non-regular hexagons).

If there are obstacles, the simplest thing to do is a distance-limited flood fill (breadth first search). In this diagram, the limit is set to moves. In the code, fringes[k] is an array of all hexes that can be reached in k steps. Each time through the main loop, we expand level k-1 into level k. This works equally well with any of the hex coordinate systems (cube, axial, offset, doubled).

function hex_reachable(start, movement):
    var visited = set() # set of hexes
    add start to visited
    var fringes = [] # array of arrays of hexes
    fringes.append([start])

    for each 1 < k ≤ movement:
        fringes.append([])
        for each hex in fringes[k-1]:
            for each 0 ≤ dir < 6:
                var neighbor = hex_neighbor(hex, dir)
                if neighbor not in visited and not blocked:
                    add neighbor to visited
                    fringes[k].append(neighbor)

    return visited

Given a hex vector (difference between one hex and another), we might want to rotate it to point to a different hex. This is simple with cube coordinates if we stick with rotations of 1/6th of a circle.

A rotation 60° right (clockwise ↻) shoves each coordinate one slot to the right →:

          [ x,  y,  z]
to    [-z, -x, -y]
to [y,  z,  x]

A rotation 60° left (counter-clockwise ↺) shoves each coordinate one slot to the left ←:

      [ x,  y,  z]
to        [-y, -z, -x]
to           [  z,  x,  y]

As you play with diagram, notice that each 60° rotation flips the signs and also physically “rotates” the coordinates. Take a look at the axis legend on the bottom left to see how this works. After a 120° rotation the signs are flipped back to where they were. A 180° rotation flips the signs but the coordinates have rotated back to where they originally were.

Here's the full recipe for rotating a position P around a center position C to result in a new position R:

1. Convert positions P and C to cube coordinates.
2. Calculate a vector by subtracting the center: P_from_C = P - C = Cube(P.x - C.x, P.y - C.y, P.z - C.z).
3. Rotate the vector P_from_C as described above, and call the resulting vector R_from_C.
4. Convert the vector back to a position by adding the center: R = R_from_C + C = Cube(R_from_C.x + C.x, R_from_C.y + C.y, R_from_C.z + C.z).
5. Convert the cube position R back to to your preferred coordinate system.

It's several conversion steps but each step is simple. You can shortcut some of these steps by defining rotation directly on axial coordinates, but hex vectors don't work for offset coordinates and I don't know a shortcut for offset coordinates. Also see this stackexchange discussion^[23] for other ways to calculate rotation.

Given a hex, we might want to reflect it across one of the axes. With cube coordinates, we swap the coordinates that aren't the axis we're reflecting over.