Since I'm interested in hex grids, I've been reading up on coordinate
systems. The coolest I've found is the use of Generalized Balanced
Ternary to enumerate hexes, groups of 7 hexes, groups of groups, and so
on, recursively. I thought I'd tell the group about it since for all its
mathematical weirdness it seems easier to work with than a zigzagged
axis, skewed axis, or symmetrical xyz axis system (although I've only
just started to implement it).
Here's a somewhat comprehensible ASCII rendering:
15 11
55 51 14 10 13
54 50 53 16 12 35 32
56 52 05 01 34 30 33
45 41 04 00 03 36 32
44 40 43 06 02 25 21
46 42 65 61 24 20 23
64 60 63 26 22
66 62
And at
http://www.pyxisinnovation.com/pyxwiki/index.php?title=General_Balanced_Ternary_%28GBT%29_Arithmetic
you can see the same kind of diagram more clearly. (Note that the digits
are base-7, despite "ternary" being in the name). You might notice that
the numbers in my ASCII are arranged differently than those in the
pictures. They're to a certain extent arbitrary, and the arrangement I'm
using produces nicer-looking arithmetic than others I've seen. Looking
at one of the diagrams, you'll see that the arrangement of the digits
1-6 about the origin hex numbered 0 is repeated in the first digits of
the surrounding superhexes (groups of hexes, and groups of groups) on
the next layer of the pattern, and will repeat again ad infinitum.
Now that you have a general idea what you're looking at, I'll list some
advantages of this strange system:
* Addresses are single numbers which can be used directly to index hexes
in an array.
* Addition, negation, and multiplication on addresses are useful
geometrical operations.
* No redundant information to store or recompute, as in the symmetrical
xyz system.
* Unlike the xyz or skewed axis systems, which naturally produce strange
trapeziodal map boundaries, it produces a roughly circular map.
* Because of its recursive structure, it's amenable to a tree
implementation. If you don't want circular maps, just pick a good size
for your map subsections, and use a 7-branched tree node for each
higher level of the structure, allocating arrays only where you need
them.
From now on I'll call it GBT2 (the 2 means it's 2-dimensional--imagine
it's subscripted). Understanding plain old balanced ternary (BT) will
make the operation of GBT2 clearer. BT is a number system that uses
three digits: a positive digit, a negative digit, and a zero
digit. Here's a number line annotated in decimal and BT:
-5 . -++
-4 . --
-3 . -0
-2 . -+
-1 . -
0 . 0
1 . +
2 . +-
3 . +0
4 . ++
5 . +--
You can see that a negative number is simply the positive number of the
same magnitude with + and - exchanged. To make it more similar to the
GBT2 notation I'm using, here's an expanded version using 1 instead of
+, and using 2 instead of - (representing a negative version of 1, not
twice its value):
-7 . 212
-6 . 210
-5 . 211
-4 . 22
-3 . 20
-2 . 21
-1 . 2
0 . 0
1 . 1
2 . 12
3 . 10
4 . 11
5 . 122
6 . 120
7 . 121
Looking at this, you can see that it's self-similar. The 2, 0, 1
(negative to positive) pattern repeats each time we add a digit. Each
new digit adds a a new layer of numbers with a trio the size of the
original trio on either side of the original. 1 and 2 represent a step
down (on the screen), and a step up, respectively. More significant
digits indicate bigger steps--steps of b^n, where b is 3, the base, and
n is the zero-based index of a digit. So in a 3-digit number, the most
significant digit represents a step of 3^2=9, the next most 3^1, and the
least significant 3^0=1.
The important thing to note is that when we add 1+1 in BT, we get 12
(alternatively, + plus + equals +-), a number that's in the 1 supertrio,
and not the 0 supertrio we started in. The BT addition table is set up
so that when you add digits together, you get a carry digit moving you
to the correct trio (possibly 0, leaving you in the same trio), and a
remainder, locating you in the correct part of that trio. GBT2 works the
same way, except instead of digits indicating directions on a 1d number
line, they indicate directions on a 2d plane.
So here's the good part. Below is the diagram again. Knowing that
addition is supposed to "just work", using this diagram we can derive
the addition tables for GBT2 (using this particular configuration of
numbers--any will work, but the tables may come out funny-looking,
albeit functional). Looking at the middle, we can see that 4 and 3 are
on opposite sides of 0, at the same distance. This means they are each
other's additive inverse, and 4+3=0. We can put that in the table, and
do the same for the other opposing pairs. Then, moving on we can try
1+3. The diagram indicates that when we take a step in direction 1, then
take a step in direction 3 (relative to 0, not stepping from 1 towards
the hex labeled 3--that would be direction 2), we're in hex 34. So mark
down that 1+3=34. It looks weird, but at least the least significant
digit makes sense--that's where this particular arrangement of numbers
pays off. Anyway, repeat this procedure for every pair of single-digit
numbers, and you produce a complete addition table. We don't need
multi-digit tables, since addition, as usual, proceeds digitwise.
15 11
55 51 14 10 13
54 50 53 16 12 35 32
56 52 05 01 34 30 33
45 41 04 00 03 36 32
44 40 43 06 02 25 21
46 42 65 61 24 20 23
64 60 63 26 22
66 62
And that's it! Adding 3 to an index repeatedly will take repeated steps
to the right. Adding 4 would step to the left. Adding 36 will step to
the right by twos. Negating a number is accomplished by subtracting it
from 7, and multiplication performs rotations.
It looks weird at first, but the more you look at it, the more it makes
sense. You'd need to implement GBT2 arithmetic, but you'd need to
implement arithmetic on coordinates for any game, so that's no special
problem.
For more info you can see:
Pictures! And you can see here how a spiral arrangement for the digits
makes arithmetic look funny.
http://local.wasp.uwa.edu.au/~pbourke/texture_colour/shm/
A mathematical description. Good arrangement of digits. Explains
multiplication. Has tables.
http://www.scribd.com/doc/64994973/74/Generalized-Balanced-Ternary
Where I first encountered the system.
http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/AV0405/MARTIN/Hex.pdf
Make any sense?