A reader asked about converting q,r coordinates for a hex into indices into a 1d array. In the hexagon guide I recommend using a hash table for small grids, and using an array of arrays for larger grids. But an array of arrays can often be condensed into a 1d array, if you can calculate the indices. I've calculated indices for a rectangular map before but I haven't done one for hexagonal maps. My initial thought was to use spirals but I think there's more straightforward way. After I wrote this page, Sander Evers pointed to a more clever and much simpler solution[1].
The top and bottom halves of a hexagonal map are trapezoids. That means we can calculate the sizes of each row. And we can also calculate the cumulative sum of those sizes, by using the formula for the area of a trapezoid. The cumulative sum gives us a function from r to index.
I'm going to assume this hexagonal map is centered at 0,0 and also assume that it's pointy top orientation. For a flat top orientation, you'll have to work out the math with rows and columns swapped.
The index of a hex(q, r) is the (start index of row r) plus (q minus the first column).
The first column of row r is max(0, MAPSIZE - r). (Note: MAPSIZE here is the "radius", 5 in the above diagram, not the "diameter".)
The row size is 1 + 2 * MAPSIZE - abs(r).
The start index is cumulative sum of the row size of each row above it. In theory we can calculate it by adding the previous row's row size and the previous row's start index. However, we want a closed formula for this, so we instead use the area of a trapezoid: (first row size + last row size) / 2 * num rows.
But there are two trapezoids, so to calculate the start index we need to know whether we're in the upper or lower trapezoid. Here's the code:
let firstRow = -MAPSIZE if (r <= 0) { let j = r - firstRow return areaOfTrapezoid(MAPSIZE + 1, MAPSIZE + j, j) } else { const areaOfUpperTrapezoid = areaOfTrapezoid(MAPSIZE + 1, 1 + MAPSIZE * 2, MAPSIZE + 1) let j = r - 1 return areaOfUpperTrapezoid + areaOfTrapezoid(MAPSIZE * 2, MAPSIZE * 2 - j + 1, j) }
And we need a helper function
function areaOfTrapezoid(first, last, rows) { return (first + last) / 2 * rows; }
In the diagram above I've displayed the calculated start index.
But this is for the forwards direction, from a hex to an index. We might also want the backwards direction, from an index to a hex. We need to invert the area of a trapezoid formula. It's a quadratic polynomial, representing a parabola. To invert it we need to solve the polynomial using the quadratic formula.
It was a great surprise to me to see the quadratic formula show up here.
Let's start with the upper trapezoid:
function areaOfTrapezoid(first, last, rows) { return (first + last) / 2 * rows; } let firstRow = -MAPSIZE; let j = r - firstRow let index = areaOfTrapezoid(MAPSIZE + 1, MAPSIZE + j, j)
Let's expand out the formula by inlining the areaOfTrapezoid function:
let firstRow = -MAPSIZE; let j = r - firstRow let index = (MAPSIZE + 1 + MAPSIZE + j) / 2 * j
and we can inline j:
let firstRow = -MAPSIZE; let index = (MAPSIZE + 1 + MAPSIZE + r - firstRow) / 2 * (r - firstRow)
and then inline `firstRow`:
let index = (MAPSIZE + 1 + MAPSIZE + r + MAPSIZE) / 2 * (r + MAPSIZE)
and simplify:
let index = (3 * MAPSIZE + 1 + r) / 2 * (r + MAPSIZE)
Then multiply out using the distributive rule:
let index = (3 * MAPSIZE * r + r + r * r + 3 * MAPSIZE * MAPSIZE + MAPSIZE + r * MAPSIZE) / 2
Note: when I do this kind of thing I'll calculate the value with each version of the expression, to make sure they give me the same result. If they don't that tells me one of my rewrite steps has a bug, and also tells me which rewrite step is incorrect. And I did catch bugs in the above rewrites. That's why I like to make code transformations with many small steps.
Finally we group the terms based on whether they're for r², r, or 1:
let index = 1/2 * r * r + (2 * MAPSIZE + 1/2) * r + (3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE)
Now we have a polynomial in terms of r, and we can solve for it using the quadratic formula. We have to rewrite one more time to use the quadratic formula:
0 = 1/2 * r * r + (2 * MAPSIZE + 1/2) * r + (3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index)
This matches the quadratic formula pattern a * r² + b * r + c = 0, with:
a = 1/2 b = 2 * MAPSIZE + 1/2 c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index
So we can apply the quadratic formula, r = (-b ± sqrt(b*b - 4*a*c)) / (2 * a):
function rowFromIndex(index) { let a = 1/2 let b = 2 * MAPSIZE + 1/2 let c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r }
It looks like the + variant is what we want, so I don't calculate the - variant. Does this work? Well, I tried it with a test program and it seems to work!
So if you have an index:
function firstColumn(r) { return -MAPSIZE - Math.min(r, 0) } function startIndexOfRow(r) { if (r <= 0) { // upper trapezoid return (3 * MAPSIZE + 1 + r) / 2 * (r + MAPSIZE) } else { // lower trapezoid return (3 * MAPSIZE + 2) / 2 * (MAPSIZE + 1) + (4 * MAPSIZE + 2 - r) / 2 * (r - 1) } } function hexFromIndex(index) { let r = Math.floor(rowFromIndex(index)) let q = (index - startIndexOfRow(r)) + firstColumn(r) return [q, r] }
This is only for the upper trapezoid. I need to do something similar for the lower trapezoid. I didn't show all the work here but it's in the test program.
a = -1/2 b = 2 * MAPSIZE + 3/2 c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index
So we can apply the quadratic formula, r = (-b ± sqrt(b*b - 4*a*c)) / (2 * a):
function rowFromIndex(index) { let a = -1/2 let b = 2 * MAPSIZE + 3/2 let c = 3/2 * MAPSIZE * MAPSIZE + 1/2 * MAPSIZE - index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r }
It looks like here too I want the + variant and not the - variant, although it's less obvious to me why. Do I need to worry about numerical stability? See this post[3] ; I think neither condition applies here. To avoid further numerical issues I can multiply the whole equation by 2, so that a, b, and c are all integers.
Putting everything together, I need to figure out which trapezoid I'm in, and then use the corresponding formula:
function rowFromIndex(index) { let crossoverIndex = (3/2 * MAPSIZE + 1) * (1 + MAPSIZE) if (index < crossoverIndex) { // Upper trapezoid let a = 1 let b = 4 * MAPSIZE + 1 let c = 3 * MAPSIZE * MAPSIZE + MAPSIZE - 2 * index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r } else { // Lower trapezoid let a = -1 let b = 4 * MAPSIZE + 3 let c = 3 * MAPSIZE * MAPSIZE + MAPSIZE - 2 * index let r = (-b + Math.sqrt(b*b - 4*a*c)) / (2 * a) return r } }
That's just the row. To get the hex:
function hexFromIndex(index) { let r = Math.floor(rowFromIndex(index)) let q = (index - startIndexOfRow(r)) + firstColumn(r) return [q, r] }
This was a fun afternoon puzzle to figure out.
Note: I might still have to worry about floating point precision, as floor() on 1.99999999999 is going to give a very different from from 2.0000000000. But as we're working with integers, I'm hoping it's not a problem. Hope is no guarantee though. So let's think through this a bit more. What is the worst that rowFromIndex could return? The indices are roughly evenly spaced per row, and rowFromIndex increases by +1 per row. The worst case will be the last column on the widest row, which will be 1/(2*MAPSIZE+1) away from an integer. The quadratic formula is using MAPSIZE*MAPSIZE in its calculations. When that squared difference is less than 10-16 (around DBL_EPSILON) we're in trouble, but that won't happen until the MAPSIZE is around 108, so I think we're ok. Experimentally, I started noticing issues around MAPSIZE somewhere between 107 and 108. I'm no expert on floating point math though.
Source code: the diagram and standalone test program.