Mar 2013

Hexagonal grids are used in some games but aren’t quite as straightforward or common as square grids. I’ve been collecting hex grid resources for nearly 20 years, and wrote this guide to the most elegant approaches that lead to the simplest code, largely based on the guides by Charles Fu and Clark Verbrugge. I’ll describe the various ways to make hex grids (I’ve counted 74 so far!), the relationships between them, as well as some common algorithms. Many parts of this page are interactive; choosing a type of grid will update diagrams, code, and text to match.

  1. Angles, size, spacing, drawing
  2. Coordinate systems
  3. Coordinate conversions
  4. Neighbors
  5. Distances
  6. Line drawing
  7. Range
  8. Rotation
  9. Rings
  10. Field of view
  11. Hex to pixel
  12. Rounding to nearest hex
  13. Pixel to hex
  14. Map storage
  15. Wraparound maps
  16. Pathfinding
  17. More reading

The code samples on this page are written in pseudo-code; they’re meant to be easy to read and understand so that you can write your own implementation.


#Basics


Switch to or back to hexagons.

Hexagons are 6-sided polygons. Regular hexagons have all the sides (edges) the same length. I’ll assume all the hexagons we’re working with here are regular. The typical orientations for hex grids are horizontal (or “pointy top”) and vertical (or “flat top”).

Angles

In a regular hexagon the interior angles are 120°. There are six wedges, each an equilateral triangle with 60° angles inside. This is what we need for drawing hexagons: given a center and a size (distance from center to corner), corner i is at center + polar(size, 60° * i). In code you might write it as:

add(center, polar(size, 2 * PI / 6 * i)

or expanded out:

angle = 2 * PI / 6 * i
x_i = center_x + size * cos(angle)
y_i = center_y + size * sin(angle)

Switch to or back to hexagons.

To draw a hexagon in a vector drawing library, iterate over i:

for each 0 ≤ i < 6:
    angle = 2 * PI / 6 * i
    x_i = center_x + size * cos(angle)
    y_i = center_y + size * sin(angle)
    if i == 0:
        moveTo(x_i, y_i)
    else:
        lineTo(x_i, y_i)

Size and Spacing

Next we want to put several hexagons together. In the vertical orientation, the width of a hexagon is width = size * 2. The horizontal distance between adjacent hexes is horiz = 3./4 * width.


Switch to or back to hexagons.

The height of a hexagon is height = sqrt(3)/2 * width. The vertical distance between adjacent hexes is vert = height.

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.


#Coordinate Systems

Now let’s assemble hexagons into a grid. With square grids, there’s one obvious way to do it. With hexagons, there are multiple approaches. I recommend axial coordinates for most situations.

Offset coordinates

The most common approach is to offset every other column or row. I’m going to call the columns q and the rows r. You can either offset the odd or the even column/rows, so the horizontal and vertical hexagons each have two variants.


“odd-r” horizontal layout

“even-r” horizontal layout

“odd-q” vertical layout

“even-q” vertical layout

Cube coordinates

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.

Notice the three primary axes on the cube grid, and how they correspond to six hex grid diagonal directions; the diagonal grid axes corresponds to a primary hex grid direction.

Because we already have algorithms for square and cube grids, using cube coordinates allows us to adapt those algorithms to hex grids. I will be using this system for most of the algorithms on the page. To use the algorithms with another coordinate system, I’ll convert to cube coordinates, run the algorithm, and convert back.


Try: and: .

Study how the cube coordinates work on the hex grid. Selecting the hexes will highlight the cube coordinates corresponding to the three axes.


Switch to or back to hexagons.
  1. Each direction on the cube grid corresponds to a line on the hex grid. Try highlighting a hex with z at 0, 1, 2, 3 to see how these are related. The row is marked in blue. Try the same for x (green) and y (purple).
  2. Each direction on the hex grid is a combination of two directions on the cube grid. For example, northwest on the hex grid lies between the +y and -z, so every step northwest involves adding 1 to y and subtracting 1 from z.

The cube coordinates are a reasonable choice for a hex grid coordinate system. The constraint is that x + y + z = 0 so the algorithms must preserve that. The constraint also ensures that there’s a canonical coordinate for each hex.

There are many different valid 3-axis hex coordinate systems. Some of them have constraints other than x + y + z = 0. I’ve shown only one of the many systems. You can also construct 3-axis coordinates with x-y, y-z, z-x, and that has its own set of interesting properties, which I don’t explore here.

“But Amit!” you say, “I don’t want to store 3 numbers for coordinates. I don’t know how to store a map that way.”

Axial coordinates

The 2-axis coordinate system, sometimes called “trapezoidal”, is built by taking two of the three coordinates from a 3-axis coordinate system. Since we have a constraint such as x + y + z = 0, the third coordinate is redundant. I recommend using an axial coordinate system.


Switch to or back to hexagons.

There are many 3-axis systems, and many 2-axis systems. I’m not going to show all of the combinations in this guide. I’m going to pick q = x and r = z.

The advantage of this system over offset grids is that the algorithms are cleaner. 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. There are some algorithms that are even cleaner with cube coordinates, but for those, since we have the constraint x + y + z = 0, we can calculate the third implicit coordinate and use that, just for those algorithms.

Although the 2-axis system shares two of the three coordinates from the 3-axis cube system, the axes end up being quite different. The cube axes are set in 3-dimensional space, whereas we need two axes (basis vectors) in 2-dimensional space. The angle between axes here will be 60°. See the diagram below. You can also construct an axial system where the axes are separated by 120°.

Axes

Offset coordinates are the first thing people think of, because they match the standard cartesian coordinates used with square grids. Unfortunately one of the two axes has to go “against the grain”, and ends up complicating things. The cube and axial systems go “with the grain” and have simpler algorithms, but slightly more complicated map storage.

#Coordinate conversion

It is likely that you will use axial or offset coordinates in your project, but many algorithms are simpler to express in cube coordinates. Therefore we need to be able to convert back and forth.

# convert cube to axial
q = x
r = z

# convert axial to cube
x = q
z = r
y = -x-z

# convert cube to even-q offset
q = x
r = z + (x + (x&1)) / 2

# convert even-q offset to cube
x = q
z = r - (q + (q&1)) / 2
y = -x-z

# convert cube to odd-q offset
q = x
r = z + (x - (x&1)) / 2

# convert odd-q offset to cube
x = q
z = r - (q - (q&1)) / 2
y = -x-z

# convert cube to even-r offset
q = x + (z + (z&1)) / 2
r = z

# convert even-r offset to cube
x = q - (r + (r&1)) / 2
z = r
y = -x-z

# convert cube to odd-r offset
q = x + (z - (z&1)) / 2
r = z

# convert odd-r offset to cube
x = q - (r - (r&1)) / 2
z = r
y = -x-z

Note that I use a&1 (bitwise and) instead of a%2 (modulo) to detect whether something is even (0) or odd (1). When a is positive, they will produce the same result. However, when a is negative, programming languages differ on what they’ll return. In some languages, -1 % 2 == -1 and in other languages -1 % 2 == +1. In some languages it depends on which compiler and machine you use (!). If your hex coordinates are always non-negative, or if in your language/compiler/machine -1 % 2 == +1, then it makes no difference, and you can use a%2 instead of a&1. However, I prefer to use a&1 to avoid running into the issue with negative coordinates. (Implementation note: in many (all?) languages, & has lower precedence than + so be sure to parenthesize a&1.)

In addition to these transforms, your grid numbering scheme may be offset by Δq, Δr. Subtract these before applying the conversion to cubes and add them after converting back from cubes to hex.

#Neighbors

Given a hex, which 6 hexes are neighboring it? As you might expect, the answer is simplest with cube coordinates, still pretty simple with axial coordinates, and slightly trickier with offset coordinates. We might also want to calculate the 6 “diagonal” hexes.

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 [Δx, Δy, Δz] at compile time:

neighbors = [
   [+1, -1,  0], [+1,  0, -1], [ 0, +1, -1],
   [-1, +1,  0], [-1,  0, +1], [ 0, -1, +1]
]
d = neighbors[direction]
return Cube(x + d[0], y + d[1], z + d[2])

Axial coordinates

As before, we’ll use the cube system as a starting point. Take the table of [Δx, Δy, Δz] and convert into a table of [Δq, Δr] with your choice of assignments. In this guide I use q = x, r = z, so it’ll be the same table as for cube coordinates, with y omitted:

neighbors = [
   , , ,
   , , 
]
d = neighbors[direction]
return Hex(q + d[0], r + d[1])

Offset coordinates

With offset coordinates, the change depends on where in the grid we are. If we’re on an offset column/row then the rule is different than if we’re on a non-offset column/row.

As above, we’ll build a table of Δq and Δr. However this time there will be two arrays, one for odd columns/rows and one for even columns/rows. Each array with contain six elements [Δq, Δr]. Look at (1,1) on the grid map above and see how q and r change as you move in each of the six directions. Then do this again for (2,2).

neighbors = [
   [ , , ,
     , ,  ],
   [ , , ,
     , ,  ]
]
# note I use & 1 but mod 2 would work if it never returns -1
parity = q & 1
d = neighbors[parity][direction]
return Hex(q + d[0], r + d[1])

Grid:

However, for those of you who are curious, I’m going to show you how to derive a formula, from first principles. Feel free to skip the rest of this section.

First, be sure you understand the cube neighbor section above. There are six neighbors, and each increments one axis by 1 and decrements a different axis by 1, thus preserving the x + y + z = 0 constraint.

For each of the six directions, we have Δx, Δy, Δz. The key idea here is that we’ll start with q, r coordinates from the offset grid, convert them into cube coordinates x, y, z, then add  Δx, Δy, Δz, then convert back into offset coordinates q, r. This general principle works for all the algorithms on the page.

I’ll show how this works for a single offset grid type, “even-q”: These are the coordinate conversions for “even-q”, from the above section:

# convert cube to even-q offset
q = x
r = z + (x + (x&1)) / 2

# convert even-q offset to cube
x = q
z = r - (q + (q&1)) / 2
y = -x - z

I’m only going to show this for a single direction, northeast, with Δx = +1, Δy = 0, Δz = -1:

# (1) convert even-q offset to cube coords:
x = q
y = -x - z
z = r - (q + (q&1)) / 2

# (2) apply Δx, Δy, Δz:
x' = x + 1
y' = y
z' = z - 1

# (3) substitute eq (1) into eq (2):
x' = q + 1
y' = -x - z
z' = r - (q + (q&1)) / 2 - 1

# (4) convert back into even-q coords:
q' = x'
r' = z' + (x' + (x'&1)) / 2

# (5) substitute eq (3) into eq (4)
q' = q + 1
r' = r  - ( q + (q&1)) / 2 - 1   + (q + 1 + ((q + 1)&1)) / 2
   = r  + (-q - (q&1) - 2) / 2   + (q + 1 + (1 - (q&1))) / 2
   = r  + (-q - (q&1) - 2        +  q + 1 +  1 - (q&1))  / 2
   = r  + (   -2 * (q&1)) / 2
   = r - (q&1)

So that’s it! We’ve worked through some math and it simplifies down to q' = q + 1 and r' = r - (q&1). (For this case, y doesn’t play a role, but it does in other situations.) That’s just for one direction, and only for even-q offset grids, but that’s how it works. For those of you who are compiler/language enthusiasts, this is defining evenQ_neighbors(H) as map(cube_to_evenQ, cube_neighbors(evenQ_to_cube(H))), then inlining all that code and greatly simplifying. It’s the type of work an compiler optimizer would do for you.

You can either work through all the cases, or you can perform the conversions at runtime (which likely will be optimized out by your compiler), or you can precalculate everything and put the results into lookup tables. I used lookup tables for my last game.

Diagonals

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).

diagonals = [[+2, -1, -1], [+1, +1, -2], [-1, +2, -1],
             [-2, +1, +1], [-1, -1, +2], [+1, -2, +1]]
d = diagonals[direction]
return Cube(x + d[0], y + d[1], z + d[2])

As before, you can convert these into 2-axis by dropping one of the three coordinates, or convert to offset by precalculating the results.

#Distances

Cube coordinates

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(x1-x2) + abs(y1-y2). In a cube grid, Manhattan distances are abs(x1-x2) + abs(y1-y2) + abs(z1-z2). The hex distance is half that:

function hex_distance(Cube(x1, y1, z1), Cube(x2, y2, z2)):
    return (abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)) / 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 hex_distance(Cube(x1, y1, z1), Cube(x2, y2, z2)):
    return max(abs(x1 - x2), abs(y1 - y2), abs(z1 - z2))

In the diagram, the max is highlighted. Also notice that each color indicates one of the 6 “diagonal” directions. You can also use the max of |Δx-Δy|, |Δy-Δz|, |Δz-Δx| to figure out which of the 6 primary directions a hex is in.

Axial coordinates

In the 2-axis system, the third coordinate is implicit. Let’s convert 2-axis to cube (3-axis) to calculate distance. We do this by filling in the third coordinate, which can easily be calculated given the constraint x + y + z = 0 (I’m using x = q and z = r here but many configurations are possible):

function hex_distance(Hex(q1, r1), Hex(q2, r2)):
    var x1 = q1
    var z1 = r1
    var x2 = q2
    var z2 = r2
    var y1 = -(x1 + z1)
    var y2 = -(x2 + z2)
    return (abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)) / 2

This can be greatly simplified, to this:

function hex_distance(Hex(q1, r1), Hex(q2, r2)):
    return (abs(q1 - q2) + abs(r1 - r2)
          + abs(q1 + r1 - q2 - r2)) / 2

If you write q1 + r1 - q2 - r2 as q1 - q2 + r1 - r2, and if you use the “max” form instead of the “divide by two” form, you get the “difference of differences” approach described here. No matter which way you write it, 2-axis hex distance is derived from the Mahattan distance on cubes.

Offset coordinates

This is trickier. The simplest way to do this is to convert offset coordinates to cube coordinates, then use cube distance. This pattern will repeat for several of the algorithms; sometimes the code can be simplified, as shown above for axial neighbors and distances.

#Line drawing

How do we draw a line from one hex to another? I’m going to show a simple algorithm that may or may not be suitable for your needs, then offer pointers to other resources that have other algorithms.

The strategy here is to evenly sample the line at N+1 points, and figure out which hexes those samples are in. This is called linear interpolation.

  1. The first question is, what is N? Simple: N is the hex distance between the endpoints. (The DDA Algorithm sets N to the max of the distance along each axis. We want to do the same in cube space, which happens to be the same as the hex grid distance.)

  2. The next step is to evenly sample N+1 points between point A and point B. Using linear interpolation, each point will be A * (1 - i/N) + B * i/N, for values of i from 0 to N, inclusive. In the diagram these sample points are the dark blue dots.

  3. The final step is to convert each sample point back into a hex. The algorithm is covered later on this page.

Putting these together, to draw a line from A to B:

N = hex_distance(A, B)
for each 0 ≤ i ≤ N:
    draw hex at hex_round(A * (1 - i/N) + B * i/N)

Implementation note: in many languages, when i and N are of type int, i/N will be 0. Make either i or N into a float by using 1.0*i/N or float(i)/N. Another implementation note: sometimes lines will look more consistent if you add a tiny value like Cube(1e-6, 1e-6, -2e-6) to one of the endpoints before starting the loop.

The above interpolation algorithm is simple and reasonably fast. You can optimize it further by rewriting A * (1 - i/N) + B * i/N as A + (B - A) * i/N, then precalculating (B - A) and 1.0/N. Multiplication can be turned into repeated addition. You’ll end up with something like the DDA algorithm. If you need an alternative to the simple algorithm I presented, take a look at:

#Movement Range

Coordinate range

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

We can work backwards from the hex distance formula, distance = max(|Δx|, |Δy|, |Δz|). To find all hexes within N steps, we need max(|Δx|, |Δy|, |Δz|) ≤ N. This means we need all three of: |Δx| ≤ N and |Δy| ≤ N and |Δz| ≤ N. Removing absolute value, we get -N ≤ Δx ≤ N and -N ≤ Δy ≤ N and -N ≤ Δz ≤ N. This is expressed as a nested loop:

for each -N ≤ Δx ≤ N:
    for each -N ≤ Δy ≤ N:
        for each -N ≤ Δz ≤ N:
            if Δx + Δy + Δz = 0:
                results.append(H.add(Cube(Δx, Δy, Δz)))

This loop will work but it’s somewhat inefficient. We’re selecting a large cube in 3D and intersecting it with the x + y + z = 0 plane to get the hexes we want. It can be written more efficiently by incorporating the x + y + z = 0 constraint directly into the loop ranges:

for each -N ≤ Δx ≤ N:
    for each max(-N, -Δx-N) ≤ Δy ≤ min(N, -Δx+N):
        Δz = -Δx-Δy
        results.append(H.add(Cube(Δx, Δy, Δz)))

This loop iterates over exactly the needed coordinates. In the diagram, the lines show the bounding ranges for x, y, z. (Also might be useful: if you only require two of the three constraints to be true, you’ll end up with a star shape instead of a hex shape.)

Intersecting ranges

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 region is expressed as inequality constraints of the form -N ≤ Δx ≤ 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 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 ≤ Δx ≤ N into a more general form, xmin ≤ x ≤ xmax, and set xmin = H.x - N and xmax = H.x + N. We’ll do the same for y and z, and end up with this generalization of the code from the previous section:

for each xmin ≤ x ≤ xmax:
    for each max(ymin, -x-zmax) ≤ y ≤ min(ymax, -x-zmin):
        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.

Obstacles

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 4 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.

visited = set()
add start to visited
fringes = [[start]]
for each 1 < k ≤ movement:
    fringes[k] = []
    for each cube in fringes[k-1]:
        for each 0 ≤ dir < 6:
            neighbor = cube.add(Cube.direction(dir))
            if neighbor not in visited, not blocked:
                add neighbor to visited
                fringes[k].append(neighbor)

#Rotation

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 shoves each coordinate one slot to the right:

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

A rotation 60° left shoves each coordinate one slot to the left:

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

As you play with diagram, notice that each 60° rotation flips the signs and also physically “rotates” the coordinates. 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.

You can then convert these into axial or offset coordinates. See this stackexchange discussion for other ways to calculate rotation.

#Rings

Single ring

To find out whether a given hex is on a ring of radius R, calculate the distance from that hex to the center and see if it’s R. To get a list of all such hexes, take R steps away from the center, then follow the rotated vectors in a path around the ring.

H = direction(4).scale(R)
results = []
for each 0 ≤ i < 6:
    for each 0 ≤ j < R:
        results.append(H)
        H = neighbor(H, i)

In this code, H starts out on the ring, shown by the large arrow from the center to the corner in the diagram. I chose corner 4 to start with because it lines up the way my direction numbers work but you may need a different starting corner. At each step of the inner loop, H moves one hex along the ring. After 6 * R steps it ends up back where it started.

Spiral rings

Traversing the rings one by one in a spiral pattern, we can fill in the interior:

results = [Cube(0, 0, 0)]
for each 1 ≤ k ≤ N:
    H = direction(4).scale(k)
    for each 0 ≤ i < 6:
        for each 0 ≤ j < k:
            results.append(H)
            H = neighbor(H, i)

This is a different way to calculate movement range.

#Field of view

Given a location and a distance, what is visible from that location, not blocked by obstacles? There are clever ways to do this but I’m only going to show a brute force method. Note that it may not produce the results you want.

The “ray casting” algorithm is to enumerate each of the hexes on the exterior (the ring), then try to draw a line to it. Stop when the line reaches an obstacle. Note that ray casting is neither the most accurate nor the fastest approach; see my article on 2d visibility calculation for more.

Clark Verbrugge’s guide describes a “start at center and move outwards” algorithm to calculate field of view. Also see the Duelo project, which has an an online demo of directional field of view and code on Github.

#Hex to pixel

For hex to pixel, it’s useful to review the size and spacing diagram at the top of the page. For axial coordinates, the way to think about hex to pixel conversion is to look at the basis vectors. In the diagram, the arrow A→Q is the q basis vector and A→R is the r basis vector. The pixel coordinate is q_basis * q + r_basis * r. For example, B at (1, 1) is the sum of the q and r basis vectors.

If you have a matrix library, this is a simple matrix multiplication; however I’ll write the code out without matrices here. For the x = q, z = r axial grid I use in this guide, the conversion is:

x = size * sqrt(3) * (q + r/2)
y = size * 3/2 * rx = size * 3/2 * q
y = size * sqrt(3) * (r + q/2)
Axial coordinates: or

The matrix approach will come in handy later when we want to convert pixel coordinates back to hex coordinates. All we will have to do is invert the matrix. For cube coordinates, you can either use cube basis vectors (x, y, z), or you can convert to axial first and then use axial basis vectors (q, r).

For offset coordinates, we need to offset either the column or row number (it will no longer be an integer). After that you can use a q and r basis vector, aligned with the x and y axes:

x = size * sqrt(3) * (q + 0.5 * (r&1))
y = size * 3/2 * rx = size * sqrt(3) * (q - 0.5 * (r&1))
y = size * 3/2 * rx = size * 3/2 * q
y = size * sqrt(3) * (r + 0.5 * (q&1))x = size * 3/2 * q
y = size * sqrt(3) * (r - 0.5 * (q&1))
Offset coordinates:

Unfortunately offset coordinates don’t have basis vectors that we can use with a matrix. This is one reason pixel-to-hex conversions are harder with offset coordinates.

Another approach is to convert the offset coordinates into cube/axial coordinates, then use the cube/axial to pixel conversion. By inlining the conversion code then optimizing, it will end up being the same as above.

Note that the above conversions are for hex q=0, r=0 being centered at x=0.0, y=0.0. If you want to center that hex elsewhere, add the desired center to the x, y you get.

#Rounding to nearest hex

Given a cube coordinate (x, y, z), round each component to the nearest integer, (rx, ry, rz). However, although x + y + z = 0, after rounding we do not have a guarantee that rx + ry + rz = 0. So we reset the component with the largest change back to what the constraint rx + ry + rz = 0 requires. For example, if the y-change |ry-y| is larger than |rx-x| and |rz-z|, then we reset ry = -rx-rz. This guarantees that rx + ry + rz = 0.

function hex_round(Cube(x, y, z)):
    rx = round(x)
    ry = round(y)
    rz = round(z)

    x_diff = abs(rx - x)
    y_diff = abs(ry - y)
    z_diff = abs(rz - z)

    if x_diff > y_diff and x_diff > z_diff:
        rx = -ry-rz
    else if y_diff > z_diff:
        ry = -rx-rz
    else:
        rz = -rx-ry

    return Cube(rx, ry, rz)

For non-cube coordinates, the simplest thing to do is to convert to cube coordinates, use the rounding algorithm, then convert back.

This algorithm is based on Charles Fu’s article. His code contains the additional optimization that if rx + ry + rz = 0 then there’s no need to look at the error values and reset the largest component.

#Pixel to Hex

One of the most common questions is, how do I take a pixel location (such as a mouse click) and convert it into a hex grid coordinate?

  1. We’re going to first get an approximate axial coordinate location by inverting the hex-to-pixel axial conversion.
  2. Then we’re going to find the closest hex to that by one of many techniques.

The approximate location is easiest to calculate using axial coordinates, and finding the closest hex is easiest to calculate using cube coordinates. If you’re using axial or cube, no problem; it’s easy to go back and forth. But if you’re using offset coordinates, you need to get the approximate location with axial, then find the closest hex with cube, then convert the cube to your choice of offset coordinates.

1. Approximate location, axial

To convert from hex coordinates to pixel coordinates, we multiplied q, r by basis vectors to get x, y. You can think of this as a matrix multiply. Here’s the matrix for “pointy top” hexes:

⎡x⎤            ⎡ sqrt(3)   sqrt(3)/2 ⎤   ⎡q⎤
⎢ ⎥  =  size × ⎢                     ⎥ × ⎢ ⎥
⎣y⎦            ⎣  0           3./2   ⎦   ⎣r⎦

Converting from pixel coordinates back to hex coordinates is straightforward. We can invert the matrix:

⎡q⎤     ⎡ sqrt(3)/3    -1./3 ⎤   ⎡x⎤
⎢ ⎥  =  ⎢                    ⎥ × ⎢ ⎥ ÷ size
⎣r⎦     ⎣     0         2./3 ⎦   ⎣y⎦

Here’s the corresponding code for “pointy top” axial hexes:

q = (1./3*sqrt(3) * x - 1./3 * y) / size
r = 2./3 * y / size

And here’s the code for “flat top” axial hexes:

q = 2./3 * x / size
r = (-1./3 * x + 1./3*sqrt(3) * y) / size

This gives us a real number for q and r, in axial coordinates; in the next step we turn these into integers.

Note that the above conversions assume for hex q=0, r=0 is centered at x=0.0, y=0.0. If you want to center that hex elsewhere, subtract the desired center from the x, y before converting.

2. Find the nearest hex

Once we have fractional hex coordinates from step 1, we need to convert them into integer hex coordinates. You might want to use round() or floor(). That works for square grids but it’s a little trickier for hex grids.

2a. Using hex rounding

Use hex rounding to convert the fractional coordinate above into an integer cube coordinate.

Once you have the cube coordinate, convert that into the coordinate system you use.

2b. Guess and test

Use regular rounding to get a first guess to the hexagon. Scan its neighbors and itself, and pick the one closest with Euclidean distance. This works because a regular hex grid also happens to satisfy the Voronoi property: the hexagon contains all points that are closer to its center than to any other hexagon center.

Unlike hex rounding, this approach doesn’t require you to use cube coordinates. It’s often simpler if you’re using offset coordinates, because you can make a guess directly in offset coordinates instead of using axial coordinates as above.

2c. Pixel map

Instead of scanning the neighbors each time, note that the answer is always the same relative to the position you’re given. You can store the answer in a 2D array or bitmap. Given a screen location x, y, make an initial guess q0, r0. If that hexagon is centered at x0, y0, so you can store dq, dr for each x - x0, y - y0. Then the answer will be q0 + dq, r0 + dr. I’ve used this in a previous project but for future projects I’ll use hex rounding.

An advantage of this technique is that it works at the pixel level instead of the geometric level, so you get precise control of what happens for the points on the boundary between two hexes.

3. Other approaches

There are other approaches that don’t fit into the “find an approximate location” then “find the nearest hex” steps above.

Geometry

By looking at the geometry of hexagons you can narrow down a pixel location to either one, two, or three hexagons, typically by dividing hexagons into smaller shapes. You can then use the edges between hexes to determine which subshape the pixel coordinate is on. There are a variety of shapes you can use. Here are some articles to read with details:

These are natural ways to approach the problem but I find that hex rounding is more elegant, conceptually simple, and less error prone (fewer cases to handle).

Branchless Method

All the pixel to hex conversions I’ve seen use branches or a lookup table. I was mystified when Charles Chambers sent me pixel to hex conversion code that uses floor() five times, but no branches. First, divide x and y by size * sqrt(3); then find q, r with:

temp = floor(x + sqrt(3) * y + 1)
q = floor((floor(2*x+1) + temp) / 3);
r = floor((temp + floor(-x + sqrt(3) * y + 1))/3);

How does it work? I admit I don’t yet fully understand this one. Charles uses the floor() function to divide space into rhombuses which make up hexagonal rows. If you look at subexpressions in the “inner” calls to floor(), 2 * x, x + sqrt(3) * y, and -x + sqrt(3) * y, you’ll notice that they’re dot products of (x, y) with the three basis vectors aligned with the hex grid. Each “outer” call to floor() combines two of the dot products.

If you’re using this for your own project, note that the q, r here are for a different axial form than the one I use in this guide. See this comment from Kenneth Shaw for a version that works with axial coordinates.

I suspect that extending this to work with cube coordinates directly will help me understand how it works.

#Map storage in axial coordinates

One of the common complaints about the 2-axis coordinate system is that it leads to wasted space when using a rectangular map; that’s one reason to favor an offset coordinate system. However all the hex coordinate systems lead to wasted space when using a triangular or hexagonal map. We can use the same strategies for storing all of them.


Shape:

Notice in the diagram that the wasted space is on the left and right sides of each row (except for rhombus maps) This gives us three strategies for storing the map:

  1. Ignore the problem. Use a dense array with nulls or some other sentinel at the unused spaces. At most there’s a factor of two for these common shapes; it may not be worth using a more complicated solution.
  2. Use a hash table instead of dense array. This allows arbitrarily shaped maps, including ones with holes. When you want to access the hex at q,r you access hash_table(hash(q,r)) instead. Encapsulate this into the getter/setter in the grid class so that the rest of the game doesn’t need to know about it.
  3. Slide the rows to the left, and use variable sized rows. In many languages a 2D array is an array of arrays; there’s no reason the arrays have to be the same length. This removes the waste on the right. In addition, if you start the arrays at the leftmost column instead of at 0, you remove the waste on the left.

    To do this for arbitrary convex shaped maps, you’d keep an additional array of “first columns”. When you want to access the hex at q,r you access array[r][q - first_column[r]] instead. Encapsulate this into the getter/setter in the grid class so that the rest of the game doesn’t need to know about it. In the diagram first_column is shown on the left side of each row.

    If your maps are fixed shapes, the “first columns” can be calculated on the fly instead of being stored in an array.

    • For rectangle shaped maps, first_column[r] == -floor(r/2), and you’d end up accessing array[r][q + r/2], which turns out to be equivalent to converting the coordinates into offset grid coordinates.
    • For triangle shaped maps as shown here, first_column[r] == 0, so you’d access array[r][q] — how convenient! For triangle shaped maps that are oriented the other way (not shown in the diagram), it’s array[r][q+r].
    • For hexagon shaped maps of radius N, where N = max(abs(x), abs(y), abs(z), we have first_column[r] == -N - min(0, r). You’d access array[r][q + N + min(0, r)]. However, since we’re starting with some values of r < 0, we also have to offset the row, and use array[r + N][q + N + min(0, r)].
    • For rhombus shaped maps, everything just matches nicely, so you can use array[r][q].

#Wraparound maps

In some games you want the map to “wrap” around the edges. In a square map, you can either wrap around the x-axis only (roughly corresponding to a sphere) or both x- and y-axes (roughly corresponding to a torus). Wraparound depends on the map shape, not the tile shape. To wrap around a rectangular map is easy with offset coordinates. I’ll show how to wrap around a hexagon-shaped map with cube coordinates.

Corresponding to the center of the map, there are six “mirror” centers. When you go off the map, you subtract the mirror center closest to you until you are back on the main map. In the diagram, try exiting the center map, and watch one of the mirrors enter the map on the opposite side.

The simplest implementation is to precompute the answers. Make a lookup table storing, for each hex just off the map, the corresponding cube on the other side. For each of the six mirror centers M, and each of the locations on the map L, store mirror_table[M.add(L)] = L. Then any time you calculate a hex that’s in the mirror table, replace it by the unmirrored version.

For a hexagonal shaped map with radius N, the mirror centers will be Cube(2*N+1, -N, -N-1) and its six rotations.

#Pathfinding

If you’re using graph-based pathfinding such as A* or Dijkstra’s algorithm or Floyd-Warshall, pathfinding on hex grids isn’t different from pathfinding on square grids. The explanations and code from my pathfinding tutorial will work equally well on hexagonal grids.

  1. Neighbors. The sample code I provide in the pathfinding tutorial calls graph.neighbors to get the neighbors of a location. Use the function in the neighbors section for this. Filter out the neighbors that are impassable.
  2. Heuristic. The sample code for A* uses a heuristic function that gives a distance between two locations. Use the distance formula, scaled to match the movement costs. For example if your movement cost is 5 per hex, then multiply the distance by 5.

#More

My code isn’t great but if you want to take a look, the core algorithms and data structures are in Haxe and compiled down to Javascript: Cube.hx, Hex.hx, Grid.hx, ScreenCoordinate.hx; the UI code is in Javascript and uses D3.js for visualization: ui.js and cubegrid.js (for the cube/hex animation).

There are lots more things I wanted to do for this guide but didn’t have time. I’m keeping a list on Trello. Do you have suggestions for things to change or add? Comment below.