News for hackers. Stuff that matters.
Re:Hexagonal grids for games by drostie on Monday June 03, 2013 @04:09AM (#5811979)
If you ignore the fact that the vertical and horizontal aren't scaled the same (which can be part of the last step in the rendering code) then you can define a hexagon as six lines in [x y] space, as defined by their endpoints:

    [[0 0]  [0 2]]
    [[0 0]  [1 -1]]
    [[0 2]  [1 3]]
    [[1 -1] [2 0]]
    [[1 3]  [2 2]]
    [[2 0]  [2 2]]
These can be lexicographically ordered, meaning that if you construct a set of lines transformed by [(min p1 p2) (max p1 p2)] rather than a list of [p1 p2], you'll never have doubled lines -- the integer comparisons are exact, and each line has a canonical representation. Moving along the "horizontal" above is translation by [2 0] while moving along the diagonal is translation by [1 3], so it really is integers all the way through.

Since these translations [2 0] and [1 3] are the same distance in the real grid, our final scaling for the actual points is [x y] -> [x y/sqrt(3)]. As you note, rounding sqrt(3) inconsistently may create problems where not all hexes appear the same size, but we can fix that by using a rational approximation to 1/sqrt(3). Here are the first few best-rational-approximations to 1/sqrt(3) as determined by its continued fraction:

    0, 1, 1/2, 3/5, 4/7, 11/19, 15/26, 41/71, 56/97, 153/265, 209/362
So if you have hexes which must be around 50 px wide, we can arbitrarily choose 52 px and use the transform:

    [x y] -> [26*x, 15*y]
And then we get integer-pixel-perfection, by stating by fiat that our hexes are not perfect but just good enough. Since we chose a great approximation the error is actually only 0.74% so people presumably won't really notice.

There are no comments on this comment yet.