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:
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:
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.
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:
So if you have hexes which must be around 50 px wide, we can arbitrarily choose 52 px and use the transform: 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.