- Blackout
- Faster Than Light
- Hex Board
- Invariants
- Listening To OEIS
- Logic Gates
- Penrose Maze
- Syntactic Sugar
- Terminal Colors

- Traffic Engineering with Portals
- Algebra and Data Types
- What's a Confidence Interval?
- Uncalibrated quantum experiments act clasically
- Pixel to Hex
- Linear vs Binary Search
- There and Back Again
- Tree Editor Survey
- Rust Quick Reference
- The Prisoners' Lightbulb
- Notes on Concurrency
- It's a blog now!

If you make a game or other application with a *hex grid* in it, one of the
problems you run into is telling what hex your cursor is on. You need to convert
from screen coordinates to hex coordinates.

I just found an elegant way to do this, that I haven’t seen elsewhere. It’s the
simplest *branchless* approach I’ve seen.

Our end goal is to determine which hexagon the cursor is on, so we need some way to name the hexagons—a coordinate system. There are many coordinate systems for hex tilings. We’ll use the one that Red Blob Games calls cube coordinates. (Everything on that site is golden.)

On a *square* grid, you can get a coordinate system by labeling each square with
its row and column number. On a hex grid, there are three orientations of “rows”. To
get a coordinate system, we’ll label each hex `(x, y, z)`

where `x`

is the
column, `y`

is the left-slanted-row, and `z`

is the right-slanted row.

Here’s what this coordinate system looks like, where the hex with “x, y, z” in it is the origin hex:

You might notice that we managed to use three numbers to label hexagons arranged
on a plane, despite there being only two degrees of freedom. As a result,
there’s an invariant: `x + y + z = 0`

.

If instead of using integers `(x, y, z)`

we use floats `(fx, fy, fz)`

, then we
can extend this coordinate system to be able to name *a point on the plane*,
rather than a hex.

The relationship between fractional hex coordinates and integer hex coordinates
is that (for example) the point `(fx, fy, fz) = (-1.0, 1.0, 0.0)`

is the center
of the hex `(x, y, z) = (-1, 1, 0)`

. Integer coordinates name hexes; fractional
coordinates name points.

Satisfyingly, these fractional coordinates also obey the invariant that
`fx + fy + fz = 0.0`

.

Now let’s say your cursor is at this star, and we want to figure out the (integer!) coordinates of the hex it’s on:

The first step is to convert the cursor position to fractional hex coordinates. This is easy; it’s a linear transformation:

```
cx = cursor_x / hex_size
cy = cursor_y / hex_size
fx = (-2/3) * cx
fy = (1/3) * cx + (1/sqrt(3)) * cy
fz = (1/3) * cx - (1/sqrt(3)) * cy
```

(`hex_size`

is the distance from the center of a hex to one of its corners, in
screen units.)

This gives the fractional coordinates `(-2/3, 2/3, 0)`

for the star.

Now we just need to convert fractional hex coordinates into integer hex
coordinates. You’d think this would be easy, but it’s not. The obvious thing to
do is to round `x`

, `y`

, and `z`

to the nearest integer. Rounding like this
works for a *square coordinate system*, but it doesn’t work for hexes.

The trouble is that, even though the *fractional* hex coordinates obey ```
fx +
fy + fz = 0.0
```

, after rounding they might not. And if this invariant is
violated, the coordinate isn’t even valid; it isn’t clear which hex it’s
supposed to be referencing. (This isn’t merely a floating-point rounding issue.
It applies to real numbers too. The rounding simply doesn’t work.)

Red Blob Games gives a nice way to
patch up this
rounding issue. But it uses a couple of `if`

statements, and that just won’t
do. We’re going to do it *branchless*.

The trick will be to divide the hexes up into triangles, and first determine
which of these *triangles* we’re in. We’ll call our new triangle coordinates
`a`

, `b`

, and `c`

, which tell which left-slanted-column, row, and
right-slanted-column the triangle is in, respectively. This is similar to the
hex coordinates, but rotated.

Converting from fractional hex coordinates `(fx, fy, fz)`

to integer triangle
coordinates `(a, b, c)`

happens to be very easy:

```
a = ceil(fx - fy)
b = ceil(fy - fz)
c = ceil(fz - fx)
```

This gives `(a, b, c) = (ceil(-4/3), ceil(2/3), ceil(2/3)) = (-1, 1, 1)`

, which
you can see is the correct triangle.

Finally, we have to figure out which hex the triangle we’re on is part of.
To do this, take the differences of `a, b, c`

and divide by 3:

```
x = round((a - c) / 3)
y = round((b - a) / 3)
z = round((c - b) / 3)
```

We get `(x, y, z) = (round(-2/3), round(2/3), round(0)) = (-1, 1, 0)`

.

And that’s it! We have integer hex coordinates that obey the invariant ```
x + y +
z = 0
```

, and tell us exactly which hex we’re on.

`ceil`

?Actually `floor`

works too. You just have to go one way or the other because the
center of the origin hex `[fx, fy, fz] = [0.0, 0.0, 0.0]`

is *at the boundary
of* six triangles.

Look at what happens to the *center* of a hex where `[fx, fy, fz]`

are all
integers:

```
a = ceil(fx - fy) = fx - fy
b = ceil(fy - fz) = fy - fz
c = ceil(fz - fx) = fz - fx
a - c = (fx - fy) - (fz - fx)
= 2fx - fy - fz
= 3fx // adding fx + fy + fz = 0
x = round((a - c) / 3) = round(3fx / 3) = fx
```

Thanks to Evan, for reading a draft of this post.

April 28, 2020

*RSS Feed*