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.