More pixel to hex approaches

from Red Blob Games

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. Here are some of the others I’ve found. Most of these can work directly with offset and doubled grids.

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 hex rounding, this approach doesn’t require you to use cube coordinates. It’s just as simple with offset or doubled as with axial coordinates.

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.

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.

Geometric approach

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:

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.

Justin Pombrio has a visual explanation of the branchless method[8].

Email me , or tweet @redblobgames, or comment: