so i like hex grids, but i don't really like how they tend to have clunky, boxy edges. a nice property of square grids is that you can make long straight lines; standard hexagonal grids don't have this property, so you see a lot of weird crinkled wavy lines along edges.
so while working on some dungeon generation code, mostly by accident, i realized that there's a totally consistent way to render a hexagonal grid that has all those straight lines and clear edges. this grid stores all the same data as a standard hexagonal grid, but in my eyes it looks a not nicer. but this grid style does change the way a lot of the rendering math works, so this is a primer on some of the processes i used to draw these grids.
"rectification" is an operation where you essentially circumscribe a shape inside itself, by placing a point at the midpoint of every line, and then connecting all those new points together. you can also rectify a grid, which can get you a new kind of grid. if you rectify a hexagonal grid (or a triangular grid), you get a tri-hexagonal grid.
to actually render a grid: each individual hex is drawn vertex-adjacent, like this:
and then the gaps between each hex are filled in by synthesizing new geometry.
internally this is all powered by a render function:
render :: Hex -> V2 Float Float
render (Hex x y) = V2 rx ry
where
rx = fromIntegral x * 26
ry = fromIntegral x * 15 + fromIntegral y * (-30)(all actual code here will be in haskell, since that's the language i wrote this in, with only limited translation for non-haskell programmers. the javascript demos don't fully implement all the concepts i'm gonna be talking about; if you need to see actual code that implements all of this, you should check the actual code. hopefully the concepts will be clear enough even if the code is opaque.)
which says that the coordinate axes for this grid takes the form of an X axis at (26, 15) and a Y axis at (0, -30). this defines a coordinate system with non-orthographic oblique axes, like so:
there's a function in the code called adjacent that gets a fair amount of use, and it looks like this:
adjacent :: Hex -> [Hex]
adjacent (Hex x y) =
[ Hex x (y+1)
, Hex (x+1) (y+1)
, Hex (x+1) y
, Hex x (y-1)
, Hex (x-1) (y-1)
, Hex (x-1) y
]and defines in an easily-accessible way what tiles are adjacent to what other tiles.
this coordinate system isn't really specific to the rectified grid; it's just a standard hexagonal grid. rectification comes in when you want to start drawing hexes.
a combination of adjacent and render is used to plot hexes themselves. since the hexes are vertex-adjacent, each vertex for a hex tile lies at the midpoint between two hex centers. e.g., the hex points 2 2 and 2 1 are adjacent, and their shared vertex is at the midpoint between the points render $ Hex 2 2 and render $ Hex 2 1. so (^* 0.5) . render <$> adjacent (Hex 0 0) will get you the points needed to render a hex, since that's the midpoint of every coordinate adjacent to the 0,0 hex, and then you can displace those points to the correct position by adding render hex to each one. this incidentally means that the vertex points for a given hex are naturally aligned with the list of adjacent hexes that they share that vertex with.
rendering the hexes is pretty easy, but they don't naturally tessellate. this means there needs to be some additional geometry synthesis to get everything seamless.
internally, i call these filler triangles 'spandrels'. they have three points, but contain no data themselves; all they do is collect actual data from hexes and use that to synthesize connective geometry. because of that, they can contain up to six pieces of vertex data, since each hex they're adjacent to contributes two vertices, and the same vertex (geometrically) can contain different data between two hexes; e.g., hexes at different height values will contribute those different height values to the same point on the spandrel triangle. the code is:
data Spandrel a = Spandrel Int ConnectiveLayer
-- ()s in place to make it clear which two points each hex gives information about
(Maybe ( a, a, ())) -- from hex a
(Maybe ((), a, a)) -- from hex b
(Maybe ( a, (), a)) -- from hex c
deriving (Eq, Ord, Show, Read, Functor)which may or may not be helpful. you can ignore ConnectiveLayer for the time being. basically: internally each spandrel stores three edges, and they're specifically indexed based on which edge of the spandrel they correspond to.
each hex is edge-adjacent to six spandrels, while each spandrel is edge-adjacent to three hexes.
my math here is a little bit garbage since i was just throwing coordinate math at the problem at the time, but for my code and the way i draw spandrels, each Hex x y is edge-adjacent to the spandrels at coords
x , y * 2 -- top-left, red spandrel
x + 1, y * 2 + 3 -- top-right, orange spandrel
x + 1, y * 2 -- right, green spandrel
x , y * 2 + 1 -- bottom-right, teal spandrel
x + 1, y * 2 + 1 -- bottom-left, cyan spandrel
x , y * 2 - 2 -- left, purple spandrel
these coordinates are totally unrelated to the hex grid math; they're only really useful for uniquely identifying the correct adjacent spandrels. note that there's all the y * 2 stuff because spandrels are roughly twice as dense as hexes, so there are twice as many coordinates needed. if i had actually approached laying out this coordinate system with forethought, i would've fixed that bit where i had +3 and -2 instead of a more reasonable +2 and -1; spandrels are laid out kind of "backwards" so that they jump back and forth as the y coord increases. it's very not ideal, but it works.
this touches on something that will come up later a lot: hexes are never edge-adjacent to hexes, and spandrels are never edge-adjacent to spandrels. all edge resolution (for height or vertex coloring or what-have-you) happens solely at the intersection of hexes and spandrels, and the only data the spandrel needs to reasonably resolve edges is the two adjacent vertices from each of the three hexes it's adjacent to.
for my specific use, with a finite, bounded grid, i'm only interested in generating some spandrels -- i ignore ones that aren't adjacent to at least two hexes with data in them -- but for an infinite grid the process should be basically the same.
first, i slice my grid up into strips along the x axis (pictured above: each color is a strip), so that i have a bunch of hexes in rows. i have a function that takes a hex and its data, and outputs six incomplete spandrels, each with one edge set with the relevant vertex data. specifically, it outputs two sets of three spandrels: three 'behind' spandrels that also share edges with hexes on the x-1 strip, and three 'ahead' spandrels that also share edges with hexes on the x+1 strip. so i run that on all the hexes on each strip and combine them, to get two lists of incomplete spandrels, one all 'behind' spandrels and the other all 'ahead' spandrels.
'ahead' spandrels are incomplete, since we haven't yet processed the x+1 strip. but the 'behind' spandrels can be merged with the 'ahead' spandrels of the last strip to create a list of complete spandrels. so i pass the incomplete 'ahead' spandrels into the next processing function, so that they're around to be unified with the 'behind' spandrels. in the right diagram above: each blank hex touches two differently-colored columns of spandrels. the one to each hex's left is their 'behind' spandrels, where the one to each hex's right is their 'ahead' spandrels. thus, the 'ahead' spandels for one column of hexes match with the 'behind' spandrels for the next column of hexes.
the red spandrel strip represents the incomplete 'ahead' spandrel list, and the black spandrel strip represents the completed 'behind' spandrel list.
we can start with an empty list, representing the old 'ahead' spandrel data for the leftmost row (which by definition doesn't exist, since if there were tiles capable of contributing 'ahead' values then we'd have an earlier strip that we'd be starting on), and use the current strip to generate 'behind' and 'ahead' values. we merge the old 'ahead' values with the new 'behind' values to get a set of complete spandrels, and then we take the 'ahead' values and pass them along to the next strip. at the very end there are no tiles that can contribute 'behind' values to the 'ahead' values of the rightmost strip, so we use only the 'behind' values to synthesize the spandrels.
the actual process of merging spandrels goes like this:
availableSpandrelData :: (Int -> a) -> ConnectiveLayer -> Hex -> ([Spandrel a], [Spandrel a])
availableSpandrelData f con (Hex x y) = (,)
[ backleft (f 0) (f 5)
, backcenter (f 5) (f 4)
, backright (f 4) (f 3)
]
[ frontright (f 3) (f 2)
, frontcenter (f 2) (f 1)
, frontleft (f 1) (f 0)
]
where
backleft a b = Spandrel (y * 2 + 1) con
Nothing
(Just ((), a, b))
Nothing
backcenter a b = Spandrel (y * 2) con
(Just (a, b, ()))
Nothing
Nothing
backright a b = Spandrel (y * 2 - 1) con
(Just (a, b, ()))
Nothing
Nothing
frontleft a b = Spandrel (y * 2 + 2) con
Nothing
(Just ((), a, b))
Nothing
frontcenter a b = Spandrel (y * 2 + 1) con
Nothing
Nothing
(Just (b, (), a))
frontright a b = Spandrel (y * 2) con
Nothing
Nothing
(Just (b, (), a))which is a little heavy on magic numbers, sorry. in essence it's mapping each edge of the hex to a specific side and spandrel id. the 'back left' value there, for example, turns the vertices 0 and 5 into the B edge (since it's the second of the three Maybe edge values) on the spandrel with the id y * 2 + 1.
each hex generates six partial spandrels, since each hex is edge-adjacent to six spandrels. so that's six new spandrels that each have one edge set. these are merged together, first among each 'behind' row, and then when the 'behind' and 'ahead' rows are combined.
instance Semigroup (Spandrel a) where
Spandrel ix l as bs cs
<> Spandrel ix' l' as' bs' cs' =
Spandrel (if ix == ix' then ix else error "trying to merge invalid spandrels")
(if l == l' then l' else error "trying to merge spandrels on separate layers")
(p as as')
(p bs bs')
(p cs cs')
where
p ma mb = case (ma, mb) of
(Nothing, Nothing) -> Nothing
(Just _, Nothing) -> ma
(Nothing, Just _) -> mb
_ -> error "duplicate spandrel entries"the above code defines a way to merge two spandrels together, which will error if the spandrels in question are not actually 'the same' spandrel, i.e., having the same index and layer. so each hex in a strip generates six incomplete spandrels, and then all of those incomplete spandrels are sorted and selectively merged together using this function to combine the data of the various incomplete spandrels.
(since we only ever merge spandrels together when they all share the same x coordinate, they're indexed solely by y coordinate. but there are twice as many spandrels as there are hexes, so their y index is y * 2 or y * 2 + 1.)
when rendering, the spandrels are considered as left-facing and right-facing ones, and that influences how their data values are mapped to grid points, but that doesn't really change anything about how their values are accumulated. a spandrel's index also encodes whether it points left or right: odd indices point left, even indices point right.
so spandrels record those three points, and internally they're referred to as points (or edges) A, B, and C. each edge contains that point plus the next one, so the A edge is across points A and B, and likewise with B and B C, and C and C A.
there's some code that turns those indices and sides into actual world-space coords:
sidePt :: SpandrelPoint -> SpandrelSide -> V2 Float
sidePt point side = case (point, side) of
(PointingUp, A) -> 0.5 * (asV2 $ adjacent (Hex 0 0) !! 5)
(PointingUp, B) -> 0.5 * (asV2 $ adjacent (Hex 0 0) !! 4)
(PointingUp, C) -> 0.5 * (asV2 $ Hex (-2) (-1))
(PointingDown, A) -> 0.5 * (asV2 $ Hex (-1) 1)
(PointingDown, B) -> 0.5 * (asV2 $ adjacent (Hex 0 0) !! 0)
(PointingDown, C) -> 0.5 * (asV2 $ adjacent (Hex 0 0) !! 5)that's also kind of heavy on magic numbers, sorry. basically these are just picking the comparatively-arbitrary hex offsets that lead to constructing the spandrel tri such that it can then be correctly offset with render.
this takes us to 'what to do with spandrel data'. this depends a lot on what you actually want your tiles to represent and how you're drawing them. for me, the biggest concern was height. color can be interpolated in a variety of ways, but different heights required certain decisions to be made about how to handle discontinuities.
there are a few cases to consider:
(edge heights supplied to the spandrel drawn as dashed triangles; the one that i actually chose is drawn filled in. connective joins between discontinuities not drawn)
some of these are easier to handle than others.
for my purposes, i made the spandrels as seamless as possible, and broke ties by picking the lower point (or middle point, for three disagreeing values). the actual code for this got fairly gnarled-- i had a lot of code that thought in terms of "two sides agree, one disagrees", right, because the alternative is the mess of "A and B are equal, but C is different" and "A and C are equal, but B is different" and "B and C are equal, but A is different" all being considered different cases despite being symbolically equivalent. so i set up an enum type and wrote code that returned the relevant side enum with relevant data (e.g., twoEdgesSeamless :: (a -> a -> Bool) -> Spandrel a -> Maybe ((a, a, a), ((a, a), (a, a), SpandrelSide)), which returns the relevant spandrel datas for 1. the seamless triangle (the (a, a, a) part) and 2. the disagreeing side with its four edge values, plus which edge it is (the ((a, a), (a, a), SpandrelSide) part). this ended up pretty messy (look at that type signature!), but not as messy as not doing it would've been.
there are definitely other solutions, like detecting large slopes and bumping the spandrel around to create more craggy connections. ultimately a spandrel is an interpolation function, and you can have it do whatever you think looks good given the information it has.
(if you're familiar with opengl you might have noticed that those rules won't actually generate seamless geometry -- there will be t-intersections all over the place. this is true! i'd need to do another stitching-up pass across the final geometry to add vertices to turn t-intersections into matching corners, but that requires more context because that would require spandrels to know what's happening with their vertex-adjacent spandrels, so it's kind of a mess.)
when i was adding water surfaces i needed hex points to maybe have multiple associated hexes, which seemed like it could also cause problems with spandrel generation. this is where ConnectiveLayer comes from: hexes will pass on their connective layer to the spandrel, and spandrels will only merge if their index and their connective layer is equal. for my purposes, ground geometry is on layer 0 and water surfaces are on layer 1. this means water surface hexes will create spandrels between each other when necessary, and lake bed spandrels will create spandrels between each other when necessary, but there won't be a huge mess of busted geometry from the lake bed trying to make vertical joins between itself and adjacent water surfaces, since that would be bad.
another thing connective layers would be useful for is underground segments, which is something i didn't end up getting around to. underground layers would have both a floor and a ceiling (which would need to be drawn in reverse so they're down-facing), and they would have their own connective layer values so they don't break other geometry. but they would also have to have some extra connective logic, where the spandrels would have to look at the opposing spandrel and potentially stitch together to make cavern walls in certain contexts. i'm fairly sure that's doable, but i didn't quite get around to it.
what connective layers aren't capable of doing is correctly handling arbitrary low-level structures, like the inside and outside of a house. i wrote all this code for a landscape generator, so that a given layer could be considered as having no overhangs or interior bits. if that's not true then you'd need a more advanced connectivity model.
uhhhhh that's about it