Update: Also see Amit’s guide to hex grids[1] (2013), where I further explore the ideas Charles Fu posted here.
This page contains a message that Charles Fu posted to rec.games.programmer in 1994, plus a collection of messages that people emailed to me directly. This is the most elegant hexagonal coordinate system I’ve seen; for a different system, see my article on grids[2]. —Amit
From: ccwf@plato.klab.caltech.edu (Charles Fu) Newsgroups: rec.games.programmer Subject: Re: Which point is in the hex? Date: 4 Jun 1994 16:47:28 GMT
In article <2sinkh$kj@controversy.math.lsa.umich.edu>, Zachary S. Delproposto <zsd@umich.edu> wrote: >:Joseph Hlebasko (hlebasko@lilly.com) wrote: >: |2 \| is x above or below the line? You can use Y=MX+B and search >: this way (brute force) >: |____\ or if your hexes are small enough you can pre-calculate >: the coords and store in >: a table and do a table search. >This is a very good description, and is quite similar to what I did in >a program I wrote. However, the triangle part was easy -- I used >the region functions in the Windows API (now under DOS, it's a bit >more difficult!).
Am I the only one who has found all the solutions presented so far less than elegant? Maybe it’s just my mathematical background. Anyways, I presented my solution to this problem in this group, oh, almost a decade ago now. Since I didn’t save the article :-), I put pencil to paper and rederived the results. (Actually, this is slightly cleaner than my original solution: I’ve improved a little over the years. :-) Basically, for hex grids I advocated using a symmetric system of three axes each 120 degrees apart (obviously, one is redundant). For example, have x increasing to the right, y increasing to the upper left, and z increasing to the lower left. Then, your hexes will have coordinates like this:
____
/ \\
____/ 0 1-1\\____
\ // \
-1 1 0 \____// 1 0-1\___
/ \\ /
____/ 0 0 0\\____/ 2 -1 -1
\ // \
-1 0 1 \____// 1-1 0\__
/ \\ /
____/ 0-1 1\\____/
\ // \
\____// \The formula for which hex a point belongs to is then
____ ____ _
rint { rint(r) - [ 0.5 - max |rint(r )-r | ] sum rint(r ) }
i i i i iwhere r is your ungridded position, rint is your rounding function of choise, and the top bar indicates a vector. The zig-zag is not directly relevant and is explained at the end of the article.
Of course, this is just a pretty formula and not an efficient implementation. An efficient implementation would go something like this:
/* doubles x, y, and z hold the initial raw ungridded position */
double rx, ry, rz;
int ix, iy, iz, s;
ix = rx = rint(x);
iy = ry = rint(y);
iz = rz = rint(z);
s = ix + iy + iz;
if(s) {
double abs_dx = fabs(rx-x),
abs_dy = fabs(ry-y), abs_dz = fabs(rz-z);
if(abs_dx >= abs_dy && abs_dx >= abs_dz) ix -= s; /* abs_dx is max. */
else if(abs_dy >= abs_dx && abs_dy >= abs_dz)
iy -= s; /* abs_dy is max. *.
else iz-=s;
}
/* ix, iy, iz now hold the coordinates of the hex. */Obviously, further machine implementation optimizations can be made depending upon the speed with which doubles can be cast to ints, whether or not rint and fabs are inlined and implemented in hardware, whether or not your machine uses a IEEE floating point representation, pipelining issues, and so forth. The if-else if-else can also be improved.
Note that the algorithm is symmetric in x,y,z since the axes are symmetric. Also, x+y+z is always zero. These two facts make algorithms more intuitive and bugs much easier to spot. Similarity in instructions may also improve chances for compiler or hand optimization. If desired, z can be computed whenever needed to reduce the memory usage by a few measly bytes.
Of course, if you don’t use my coordinate system, you will need to convert in and out of it. This should be pretty simple. For example, if you use the popular system with x increasing by one every hex to the right and y increasing by one every hex up with y going 0.5,1.5,2.5,... on the odd columns, then your x is the same as my x and your y is just offset from mine by x/2 (and my z=-x-y as pointed out above).
**mathematical details below--not for the fain-hearted**
How was the above formula derived? The insight is that a uniform hex grid is the isometric projection of an infinite grid of unit cubes whose centers satisfy the equation x+y+z=0. Thus, hairy problems with hexes in 2-D become nicer problems with cubes in 3-D in very much the same way that using homogenous coordinates linearizes projective transformations.
(An isometric projection is an orthographic, i.e., non-perspective, projection onto the x+y+z=0 plane. It is one of the standard views used by draftsmen: the one with x, y, and z 120 degrees from each other, just like my axes.)
In this particular case, the problem of determining which hex contains a given point becomes the trivial problem of which cube contains a point. The rest of the code just transforms from the x+y+z=0 plane to the cube grid and vice versa. That’s it.
With the cube grid system, problems like counting the number of hexes between points also becomes trivial. The system also has interesting bizarre properties such as lines of constant x zigzagging to follow hex sides as shown in the diagram above. If you want a Euclidean metric, just stick with the rotated coordinate system and avoid the fancy projection except when discrete hexes are needed.
Final note: my advocacy of this approach got no support when I first posted it years ago. Perhaps it will stir more interest now. There does seem to be a gradual trend toward mathematical literacy amongst game designers and CG programmers. Perhaps there’s hope for me yet. :-)
-ccwf
... Anatomy is very poor... See how that muscle connects?... And
that perspective, _yeesh_!... Do you know what a _vanishing point_
is? And as for _faces_...
-Scott McCloud, _Understanding Comics_Along the same lines, Bram de Greve writes:
From: Bram de Greve To: amitp@CS.Stanford.EDU Subject: Distance in hexaconal grids with Isometric Cube Coordinates Date: Wed, 17 Nov 1999 20:50:44 +0100 (MET)
Hi,
I have here a very simple method to calculate the “walk-distance” between 2 hexagons with ISOMETRIC CUBE COORDINATES. I think that it might be worth to be published because it’s very simple and very handy, but isn’t mentioned at your pages yet. At least, I didn’t found it.
With “walk-distance” I mean how many hexagons do you have to walk over to reach another one.
Let us call the 2 hexagons H1 and H2 with the isometric cube coordinates (x1,y1,z1) and (x2,y2,z2).
Now the distance is given by:
1/2 * [ Abs(x1-x2)+Abs(y1-y2)+Abs(z1-z2) ]
You see it is very simple.
And of course, if one should need the “light-distance” you may use pythagoras. With “light-distance” I mean the distance between the 2 centers of the hexagons, measured in 1 straight line. It’s given by
[ (x1-x2)^2 + (y1-y1)^2 + (z1-z2)^2 ] ^ (1/2)
Regards,
Bram
Cris Fuhrman writes that the distance can alternatively be expressed as:
distance = max [ abs(x1-x2), abs(y1-y2), abs(z1-z2) ]
It appears that when x+y+z = 0, this approach is equivalent to the 1/2 of the sum approach, but I (Amit) was not sure how to prove it.
Ariel Birnbaum offers this:
From: Ariel Birnbaum To: amitp@cs.stanford.edu Subject: Hex Grid - missing proof Date: Mon, 22 Jan 2007 13:24:54 +0200
Here’s a possible proof:
If x=x1-x2, y=y1-y2, z=z1-z2, then x+y+z=x1+y1+z1-(x2+y2-z2)=0.
Hence it suffices to show that:
( |x| + |y| + |z| ) / 2 = max { |x|, |y|, |z| }, for x+y+z=0.Assume wlog that max { |x|, |y|, |z| } = |x|. Also wlog, assume x to be nonnegative. If x=0, the claim is trivial, so we assume x to be positive. If y is also positive, then z=-(x+y), and we see that |z|=|x|+|y| > |x| which contradicts the previous assumption. Hence y is nonpositive, similarly for z. We then have:
|x|+|y|+|z| = x - y - z = x - (y+z) = x + x = 2x = 2|x|
which proves the claim. For the case where x is negative, we just negate the whole vector and proceed as above.
Matt Walker offers this:
To: amitp@cs.stanford.edu From: Matt Walker <matt.r.walker@gmail.com> Subject: Isometric cube coordinate distance proof Date: Sun, 18 Feb 2007 09:21:54 -0600
I thought I’d lend a hand (I’m not claiming it’s elegant, but I do think it’s a proof):
x1 + y1 + z1 = 0 x2 + y2 + z2 = 0 x1 + y1 + z1 = x2 + y2 + z2 show: 1/2 (|x1 - x2| + |y1 - y2| + |z1 - z2|) = max(|x1 - x2|, |y1 - y2|, |z1 - z2|) 1/2 (|x1 - x2| + |y1 - y2| + |z1 - z2|) = 1/2 (|y2 - y1 + z2 - z1| + |y1 - y2| + |z1 - z2|) = 1/2 (|-(a + b)| + |a| + |b|) = 1/2 (|a + b| + |a| + |b|) case 1: sign(a) = sign(b) = 1/2 (|a| + |b| + |a| + |b|) = |a| + |b| = max(|a| + |b|, |a|, |b|) = max(|a + b|, |a|, |b|) = max(|x1 - x2|, |y1 - y2|, |z1 - z2|) case 2: sign(a) ~= sign(b), |a| > |b| = 1/2 (||a| - |b|| + |a| + |b|) = 1/2 (|a| - |b| + |a| + |b|) = |a| = max(|a| - |b|, |a|, |b|) = max(||a| - |b||, |a|, |b|) = max(|a + b|, |a|, |b|) = max(|x1 - x2|, |y1 - y2|, |z1 - z2|) case 3: symmetric for |b| > |a|