Trying to work out how the hexagonal equivalent of a [quadtree](http://en.wikipedia.org/wiki/Quadtree) works (visually). ---- I've actually started going down path of each level overlapping the hexes of the previous level: ![overlapping hexes](http://f.cl.ly/items/1x2T2J3F391L3Y2Z011c/Screen%20Shot%202012-08-16%20at%201.09.57%20AM.png) ---- What's neat about that is each *edge* gets hex at the finer level (potentially useful for some of the applications I have in mind) ---- So each hex has *7* children, the central one (we'll call **0**) and *6* others which we can number clockwise from top right **1**-**6**. ---- A hex can then be identified by a dotted-path such as `3.5.0.2.1`. ---- This scheme may allow for partitioning of maps across servers while, as a result of the overlap, provide a basis by which information about adjacent hexes can be shared between those servers. ---- Going to start coding some of this up at https://github.com/jtauber/hexlib ---- Just realized, starting to implement this, that each hex actually has two addresses, each one based on one of the two "parents" it overlaps. ---- To find the sub-hex (i.e. the hex one level finer) in any direction is trivial. The sub-hex in the `3` direction from `[4, 2]` is `[4, 2, 3]`. A more involved question is what's the same-level hex's address in a given direction? ---- In one case, this is still trivial. If we're on a hex ending in a `0` the same-level hex in direction `d` has an address just replacing the `0` with `d`. For example: the hex in direction `2` from `[3, 5, 0]` is `[3, 5, 2]`. ---- __________ /\ /\ / \ 6 / \ / \____/ \ / 5 / \ 1 \ /_____/ 0 \_____\ \ \ / / \ 4 \____/ 2 / \ / \ / \ / 3 \ / \/________\/ # ---- In the diagram above, by considering the inverse we can see that if the hex addresses ends in a number that is the "opposite" of the direction we want to go, the new address just replaces the last digit with a `0`. By opposite here, we mean: 1 <-> 4 2 <-> 5 3 <-> 6 ---- * if direction <= 3, opposite = direction + 3 * if direction > 3, opposite = direction - 3 ---- Notice that direction `5` from the `.1` hex in is the same as direction `1` from the `.5` hex. In this, and other similar cases, the result is just the number "in between", with the proviso that `6` is between `5` and `1` and `1` is between `6` and `2`. ---- If we call the tail address `t` and the direction `d` then: * if (t - d) == 2, result is d + 1 (== t - 1) * if (t - d) == -2, result is d - 1 (== t + 1) ---- The "opposite" scenario we described above is actually just: * if (t - d) == 3, result is 0 * if (t - d) == -3, result is 0 ---- At some point, might want to explore using `-3`, `-2`, `-1`, `1`, `2`, `3` as the directions rather than `1`, `2`, `3`, `4`, `5`, `6`. ---- I have this crazy idea to cast all this in a fantasy settings with mages deriving all this in some conlang of terminology. ---- There's something a little weird about the "two addresses". Now `0.1` and `1.4` are the same, which means that `0.1.4` and `1.4.4` are the same and `0.1.1` and `1.4.1` are the same. What's "weird" is that `1.4.4` is entirely enclosed in `0` not `1` and `0.1.1` is entirely enclosed in `1` not `0`. Which means you can't rely on prefix alone for containment. I wonder if that makes this whole idea a non-starter. ---- ![two levels of hex showing addresses](http://f.cl.ly/items/3D0M1B3G3r0f3X1n3N1x/Screen%20Shot%202012-08-26%20at%207.18.00%20AM.png) ---- is `1.4.1` and `0.1.1` being the same *in addition* to the non-`0` hexes having two names anyway? So there are actually *four* names for `1.4.1`? ---- Actually, `1.4.1` seems to have only one other name: `1.0.4`. So `1.4.1`, `0.1.1` and `1.0.4` are the same hex. The `1.4.1` vs `1.0.4` distinction is just the usual one of being named after one of the overlapped parents. ---- ![three levels of hex showing ambiguous naming](http://f.cl.ly/items/3V2H1t3Q2I32432v2z2i/Screen%20Shot%202012-08-26%20at%206.39.04%20PM.png) ---- `1.4.1` and `1.0.4` is a distinction we like because it gives us a name for the edge from either side. As you can see in the diagram above, the issue is the two names for the `.0` hex: `0.1.0`/`1.4.0`. ---- These two names come about not because of overlapping parents (`.0` hexes don't have overlapping parents) but because the single parent has two names due to *its* overlapping parents. ---- It seems that `1.4.1` and `1.0.4` are fine but should never be called `0.1.1`. The heuristic is that `0.1.1` isn't under `0` so should not be a valid name. We just need to make that more concrete. ---- I'm wondering if another way to look at it is, from the `.1` version of a hex's name, you can only go next in the direction `3`, `4` or `5`. If you want to go in the direction `1`, `2` or `6`, you have to use the `.4` version of the name. ---- Luke Hatcher pointed me to [Amit's Thoughts on Grids](http://www-cs-students.stanford.edu/~amitp/game-programming/grids/) which is highly relevant here (although taking a different , more general and single level approach). ---- See (also via Luke Hatcher) ---- * from `.1` you can only go `3`, `4`, `5` * from `.2` you can only go `4`, `5`, `6` * from `.3` you can only go `5`, `6`, `1` * from `.4` you can only go `6`, `1`, `2` * from `.5` you can only go `1`, `2`, `3` * from `.6` you can only go `2`, `3`, `4` ---- Just discovered [General_Balanced_Ternary_(GBT)_Arithmetic](http://www.pyxisinnovation.com/pyxwiki/index.php?title=General_Balanced_Ternary_(GBT)_Arithmetic) which seems highly related. ---- The difference between a GBT approach and what I was working on above is that I have lower-level hexes on the *edges* whereas GBT has lower-level hexes on the vertices.