Clever Hex Grid Method

[paul-d...@sbcglobal.net]

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?

[Gerry Quinn]

In article <87k43h9...@sbcglobal.net>, paul-d...@sbcglobal.net
says...

> 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).

[details omitted]

Is a 'skewed axis' system just an ordinary square grid with only two of
the diagonal directions valid?

I'm going to have to say that I think that is simplest (and lends itself
easily to a single numeric index if you want that)! But good luck with
your new concept.

- Gerry Quinn

[paul-d...@sbcglobal.net]

Gerry Quinn <ger...@gmail.com> writes:

> In article <87k43h9...@sbcglobal.net>, paul-d...@sbcglobal.net
> says...
>> 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).
>
> [details omitted]
>
> Is a 'skewed axis' system just an ordinary square grid with only two of
> the diagonal directions valid?

I think so, if I understand you right. A skewed axis keeps one axis the
same as a rectangular grid, but has the other proceed somewhat
diagonally. And an xyz system is the same as that, except with the
implicit z axis made explicit (which I understand makes some of the math
easier, like calculating distances).

[Gerry Quinn]

In article <87fwe59...@sbcglobal.net>, paul-d...@sbcglobal.net
says...

> Gerry Quinn <ger...@gmail.com> writes:

> > Is a 'skewed axis' system just an ordinary square grid with only two of
> > the diagonal directions valid?
>
> I think so, if I understand you right. A skewed axis keeps one axis the
> same as a rectangular grid, but has the other proceed somewhat
> diagonally. And an xyz system is the same as that, except with the
> implicit z axis made explicit (which I understand makes some of the math
> easier, like calculating distances).

I've never needed distances, but I think they should be straightforward.
Something like:

dist = sqrt( dy ^ 2 + ( dx - dy / 2 ) ^ 2 )

[In other words, negate the skew and then use the standard Euclidean
formula.]

- Gerry Quinn

[paul-d...@sbcglobal.net]

I thought it was more of a sqrt(x^2 + y^2 + (x - y)^2). Because we can
view a hex grid as the set of cubes with coordinates for which x + y + z
= 0, and z = x - y, so the distance between cube centers can be computed
with the plain old 3d distance formula. I could be wrong though.

[Gerry Quinn]

In article <87boos9...@sbcglobal.net>, paul-d...@sbcglobal.net

You are using hexes in three dimensions? I was assuming two, though the
formula can be extended anyway.

- Gerry Quinn

[paul-d...@sbcglobal.net]

No, a 2-dimensional hex grid can be considered as cubes in 3d, as I
understand it.

[chalup]

On Feb 21, 7:40 pm, paul-donne...@sbcglobal.net wrote:
> Gerry Quinn <gerr...@gmail.com> writes:
> > In article <87fwe59jpa....@sbcglobal.net>, paul-donne...@sbcglobal.net
> > says...

> >> Gerry Quinn <gerr...@gmail.com> writes:
>
> >> > Is a 'skewed axis' system just an ordinary square grid with only two of
> >> > the diagonal directions valid?
>
> >> I think so, if I understand you right. A skewed axis keeps one axis the
> >> same as a rectangular grid, but has the other proceed somewhat
> >> diagonally. And an xyz system is the same as that, except with the
> >> implicit z axis made explicit (which I understand makes some of the math
> >> easier, like calculating distances).
>
> > I've never needed distances, but I think they should be straightforward.
> > Something like:
>
> > dist = sqrt( dy ^ 2 + ( dx - dy / 2 ) ^ 2 )
>
> > [In other words, negate the skew and then use the standard Euclidean
> > formula.]
>
> > - Gerry Quinn
>
> I thought it was more of a sqrt(x^2 + y^2 + (x - y)^2). Because we can
> view a hex grid as the set of cubes with coordinates for which x + y + z
> = 0, and z = x - y, so the distance between cube centers can be computed
> with the plain old 3d distance formula. I could be wrong though.

The easier formula is (abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)) / 2

[Gerry Quinn]

In article <877gzf9...@sbcglobal.net>, paul-d...@sbcglobal.net

Oh I see - as if you are looking down on a slice through a stack of
cubes in isometric view.

Might be an interesting approach if you are using a 3d engine for
graphics.

I'm comfortable with the 2D skewed array approach, though - it's what
I've always used.

- Gerry Quinn

[paul-d...@sbcglobal.net]

Right, Q*bert style, sort of.

[Konstantin Stupnik]

> Make any sense?

Most important problem with hexes is ... our world is mostly square
aligned :)
Most buildings are parallelepipeds (or combined of parallelepipeds),
most roads are connected at a straight angle.
While hexes have this all-directions-fairness, it's still looks odd.

[paul-d...@sbcglobal.net]

Yeah... but at least you can produce less aliased curves and diagonals
with hexes. I totally see what you're saying, but I'm also sick of the
geometrical limits of square grids. You might say that, having
experienced decades of square grid artifacts, I'm ready to jump at the
chance to experience some hex grid artifacts.

But I've been thinking about ways to mask the grid anyway. I don't think
it needs to look super odd. Part of the reason hex grid games look odd,
IMO, is because they emphasize the grid more than a lot of square games
do. Fallout doesn't look weird (even though it actually is very weird,
using perspective tricks to pretend its buildings have square
corners). I don't plan to do that, but I've been thinking about ways to
make off-axis walls look straight. For example, for diagonal walls I can
make the visual wall straight, and pad it out with trees, pillars,
statues, furniture, and what have you. That won't work for very long
walls, or for every wall without looking weird, but it's usable:

##############
##T T##
## ##
##T T##
## ##
##T T##
###### ######

I can also throw in geometrical disturbances, like a fountain, perhaps.

##############
##T ###
## ~~##
##T ~~s##
## ~~##
##T ###
###### ######

If it's not a wall, and is for purely visual effect, like a road,
there's no need for its boundaries not to be mid-hex and travel any
which way.

Of course I can also produce gentler non-axis-aligned lines. The further
off diagonal it gets, the fewer jogs I need to have. This doesn't look
worse than an aliased rectangular grid semi-diagonal.

###### #
##### ##
#### ###
##### ##
#### ###
### ####
#### ###
### ####
## #####

It's amenable to a the straight-wall with trees technique too, of
course.

#####T #
##### ##
#### T##
####T ##
#### ###
### T###
###T ###
### ####
## T####

On top of all that, while many urban constructions are broadly
rectangular, you can find all manner of strangely shaped office high
rises and roads in any older part of town criss-cross at crazy angles. A
town in which all the roads were set at 120 degree angles wouldn't be
stranger than a town in which all the roads were right at 90 degree
angles. And of course, I never said I was making an urban game to begin
with. Maybe it takes place in a forest, or maybe I need accurate yurt
geometry. ;-)

So I don't think geometry is going to be a bigger problem than it would
be with a square grid. I think I'll just open up a variety of organic
and approximately circular shapes, while still being able to produce
nice-looking rectangles.

[Gerry Quinn]

In article <ji78f1$l7r$1...@speranza.aioe.org>,
konstanti...@gmail.com says...

I've been thinking about this a bit. Any new roguelike I make will be
long in gestation, but I like hexes in many ways. At the same time I am
aware of their disadvantages.

Some ideas I have had:

1. Use hexes for caves and outdoor areas, but use squares for
habitations. This isn't all that difficult, as you can easily abstract
away the detailed geometry from most of your code. Probably some
abilities/spells would be stronger or weaker in a hex environment, but
that should at least add to tactics if not immersion. (I know some feel
differently about tactics/immersion. I liked that in my game Lair of
the Demon Ape you could control how much time the monsters had to move
based on the length of your own move, but it did excite some adverse
responses.)

2. Use hexes and squares on the same map. Certain rectangular areas
would be mapped to a one geometry, in a matrix of the other. The big
problem is transition cells, and also transparency to the user.

3. Accept that rhombic rooms are okay. In other words, rooms that are
rectangular in most games would instead be shaped like:


# # # # # #
# # # # # # #
# # # # # # #
# # # # # # #
# # # # # #

(use fixed width font)

I'm leaning towards option 3. I think that knocking off the two acute
corner squares would go a long way to stop rhombic rooms from being
tactically odd. And if all rooms had this configuration, players would
get used to it.

- Gerry Quinn