More pixel to hex approaches

 from Red Blob Games
31 Jan 2015

There are several different ways to convert a pixel location into a hex coordinate. On the main page I cover what I consider to be the simplest approach, reusing the hex_round() function that we already used in line drawing. But there are many other approaches that I’ve found or that readers have sent to me. Some are faster. Some are more flexible. Some handle edge cases better. I’m collecting them on this page.

 1  Tested algorithms#

These are the algorithms I’ve tested myself, with code on this page, and the output of running that code. All of these tests are for pointy-topped hexes, and some of the algorithms use a helper function from the main page[1]:

function pixelToPointyHexFraction(x, y) {
    let q = sqrt(3) / 3 * x + -1/3 * y;
    let r = 2/3 * y;
    return {q, r};
}

The first algorithm is the hex_round function from the main page. It uses three round() calls, three abs() calls, and two if/else branches.

Using hex_round()

If you look closely at the lines below or above the white hexagon, the boundary between the blue and red hexagons is not perfectly straight. There’s a (literal) edge case there that hex_round() treats inconsistently due to numerical precision / float errors. A reader says that changing 2/3 * y to (1 - 1/3) * y in the pixelToPointyHexFraction code will help.

 1.1. Charles Chambers

Back in 2013, Charles Chambers sent me pixel to hex conversion code that has five floor() calls. 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? Charles uses the floor() function to divide space into rows of rhombuses. Two rhombuses and two half-rhombuses make one hexagon. 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.

Algorithm from Charles Chambers

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 my guide, but I’ve modified my sample code here to match my guide.

 1.2. Kenneth Shaw

Kenneth Shaw posted a simplification of Charles Chambers’s algorithm:

Algorithm from Kenneth Shaw

 1.3. James McNeill

James McNeill’s site playtechs has a great hex grid guide[2] including pixel to hex. He uses two separate affine transformations, one that makes q easy to calculate and one that makes r easy to calculate. There are six floor() calls.

1.3.1. Eric Gradman

Eric Gradman’s numpy code[3] is an implementation of the playtechs algorithm:

Algorithm from Eric Gradman

1.3.2. Saevax

Saevax’s method[4] is based on the playtechs hex guide, inlining and simplifying the code:

Algorithm from /u/Saevax

 1.4. Justin Pombrio

Justin Pombrio has a visual explanation of his algorithm[5], which elegantly has five calls (three ceil, two round):

Algorithm from Justin Pombrio

 1.5. BorisTheBrave

BorisTheBrave’s algorithm[6] is a variant of Justin Pombrio’s (two ceil, one floor, two round):

Algorithm from BorisTheBrave

 1.6. Mark Steere

Mark Steere’s method[7] looks elegant, with five floor() calls:

Algorithm from Mark Steere

 1.7. Jacob Rus

Jacob Rus’s algorithm[8] has three round(), two abs(), and one if. His page has diagrams, interactive demos, and code showing how it works.

Algorithm from Jacob Rus

 1.8. vaxquis

vaxquis sent me some code for pixel to hex, with each hexagon formed out of one rhombus and two triangles. There are two floor() for the rhombus and two if to handle the triangles.

Algorithm from vaxquis

 2  Guess and test#

If you can somehow guess a location within a hex of the true answer, you can then correct the guess. 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 the geometric algorithms listed above, guess and test doesn’t require you to use cube/axial coordinates. It works the same with offset or doubled coordinates.

 3  Pixel map#

The geometric algorithms above work on pure polygons, but they don’t always match up with a pixel grid. There are three issues, two of which are fixed easily:

The first issue is that you may need to adjust the x, y to point to the center of the pixel instead of the top left of the pixel. Do this by calling pixelToHex(x + 0.5, y + 0.5).

The second issue is that if you want to align to integer pixel boundaries you will need to adjust the width or height of the hexagon, one of which has a sqrt(3) in it. In this diagram you can see that of the hexagons is slightly different in shape and alignment because the width has a sqrt(3) (non-integer value) in it:

Hexagon width = sqrt(3)⨉6 = 10.3923 pixels

To solve this we can stretch or shrink the hexagons slightly to make them line up with the pixel grid, so that they all are the same shape. The math on the main page doesn’t support this, but the implementation page does. In this case I set the width to be 10 ÷ (sqrt(3) ⨉ 6) times what it normally would be:

Hexagon width rounded to 10 pixels

The third issue is that these hexagons may not look nice (symmetric, etc.), and may not match your desired pixel boundaries, especially if you have pixel art. The flaws are more easily seen when the pixels are large relative to the hexagons:

Hexagon width rounded to pixels

For more control, work directly with pixels. Compute or decide on the answer per pixel and store it in an array or bitmap. Hand tune the boundaries to make them look nice. You can get precise control so that it can fit your pixel grid.

A global pixel map would be to store the answer in an array or bitmap the size of the screen or game map. An array would contain pairs (q:int, r:int), or a bitmap could contain q in the red channel and r in the green channel. However, this array may be large.

For many hexagon sizes, especially if adjusting for pixel art, the pixel boundaries will repeat in an offset pattern:

Hexagon pattern repeats

If you have a repeating pattern, you can use a local pixel map. Each pixel inside the pixel map will be an offset relative to the hexagon at the top left of the pixel map. You’ll need to:

  1. Calculate which rectangle the pixel is in.
  2. Calculate which hexagon is at the top left of that rectangle.
  3. Calculate which pixel within the rectangle.
  4. Look up in the pixel map the hexagon offset relative to the top left hexagon.
  5. Add that pixel’s offset to the top left hexagon.

For example you might determine rectangle’s top left is at hexagon q:5, r: 1. Then you look at the pixel within the rectangle, and see that its offset is q:-1, r: +1. Then you add the two, and get q:4, r: 2 as the final hexagon in the lookup.

It’s more steps but the main advantage is that a local pixel map will be much smaller than a global pixel map, and it will also work on an infinite map. You may be able to use a rectangle even smaller than the one I show in the diagram. The disadvantage of the local pixel map is that it only works when all the hexagons follow a repeating pattern.

Another advantage of a pixel-perfect approach, whether global or local, is that you can handle the borders between hexagons. David Johnson[9] has a multipage guide for hex grids that builds a global pixel map. He takes into account the width of the borders, explains the theory, and has interactive demos.

A system I used for an old game[10] encodes the pixel boundary in an array. Many of the algorithms listed below use the repeating rectangle approach for lookups.

 4  More algorithms#

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:

Do you have any other algorithms for this list?

The visual tests on this page are generated by this source code.

Email me , or tweet @redblobgames, or comment: