Trying to work out how the hexagonal equivalent of a quadtree works (visually).

I've actually started going down path of each level overlapping the hexes of the previous level:

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.

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.

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 which is highly relevant here (although taking a different , more general and single level approach).

See http://www.redblobgames.com/grids/hexagons/ (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 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.