Note that this is an old Usenet thread from 1992. See the google groups archive[1]. My own writeup is on this page[2] (2013), with visual guides to hex distance and x,y to hex algorithms.
Minor note: the getAngle() function has logic to handle dx=0, dx>0, etc., but in modern code you can use atan2(dy,dx) which has all that logic built in.
Question from Greg Kuperberg
Article: 8616 of rec.games.programmer, by Greg Kuperberg, Dec 3, 1992
>Does anyone have an insights and/or algorithms for resolving x,y mouse
>hits on a hex grid?
Say your grid is enumerated like this:
__ __ __
/03\__/24\__/45\
\__/13\__/34\__/
/02\__/23\__/44\
\__/12\__/33\__/
/01\__/22\__/43\
\__/11\__/32\__/
/00\__/21\__/42\
\__/ \__/ \__/
and say that the origin is the bottom left corner of the 00 hexagon.
I'll use Warwick Allison's parameters also:
(mx,my) = mouse coordinate
h = height of hexagon
tw = width of hexagon horizontal side
cw = width of side triangle
-- = cw
____
/ \ |
/ \ | = h
\ / |
\____/ |
---- = tw
Then we can divide the region into cw+tw x h sized rectangles in a
sideways brick-layer's pattern so that the rectangles are almost in the
same place as the hexagons:
_______ ______
/| \ | /| \ |
/ |01 \|_____|22 \|
\ | /| \ | /|
\|___/_|11 \|___/_|
/| \ | /| \ |
/ |00 \|___/_|21 \|
\ | /| \ | /|
\|___/_| \|___/_|
The idea is to assume first that if the mouse landed in rectangle ij
then it landed in hexagon ij and then correct if the mouse position is
in one of the two triangular flaps. I'll compute two numbers tx and ty
which index the hexagon that the user clicked in. All my arithmetic is
in integers and I assume that division is never rounded up, and,
compatibly, remainders are always non-negative. I also assume h, the
height of a hexagon, is even. Here's the code:
tx = mx/(cw+tw); rx = mx%(cw+tw);
my += tx*h/2;
ty = my/h; ry = my%h;
rx = tw+cw-rx;
ry -= h/2;
if(2*cw*ry > rx*h) {tx++; ty++;}
if(2*cw*ry < -rx*h) tx++;Reply - Paul Gyugyi
Article: 8688 of rec.games.programmer, by Paul Gyugyi, Dec 10, 1992
Here's an old post that I wrote up a while ago. It deals with
dividing the game map into triangles and doing hit-testing.
There are ways to increase the speed of the routines, and
the math gets easier if you adopt another numbering scheme,
but the routines here are tested and used with my MS Windows
hexmap editing program.
Updates to this posting, with faster computations, would be nice.
We should make a FAQ on this subject.
Routines to convert from (x,y) coordinate to Hex sheet numbering.
I. Background and definition
I am writing a computerized version of the Task Force StarFire
game, using Actor, which is a smalltalk-like environment running
under Microsoft Windows. The syntax of Actor is similar to C.
I will try to put the routines in C-like format for this posting.
These routines could best be used as hit-testing for mouse
clicks. Given an (x,y) mouse position, it will give you the hex
label. I also use it to find neighboring hexes, taking the
center of the hex my starship is in, adding one unit of distance
at the current angle I am facing, and finding the label of that
hex. That way my dialog boxes can give all information in hex
numbers so the program is easy to use with maps. Note that the
center to center (x,y) distance is NOT the same as the number of
hexes between two points distance. Hex 1014 is 18 hexes from hex
0101, but only about 15.5 units in (x,y) space. I wrote a
routine that 'counts' the hexes between two hexes, and I'll
include that at the end.
The map I am working with is layed out like this:
_____ _____ _____
/* \ 0200 / \ 0400 / \
/ 0101 \_____/ 0301 \_____/ 0501 \
\ / \ / \ /
\_____/ 0201 \_____/ 0401 \_____/
/ \ / \ / \
/ 0102 \_____/ 0302 \_____/ 0502 \
\ / \ / \ /
\_____/ 0202 \_____/ 0402 \_____/
and the cartesian (x,y) coordinates I use have (0,0) at the upper
left corner of hex 0101 (at the *), with x increasing to the
right, and y increasing downward. One distance of 1 in the (x,y)
system is defined as the inter-hex center to center distance,
also equal to the smallest diameter of the hexagon.
II. Algorithm
The algorithm is a two step process. I could collapse the two
steps into one large formula, but I thought you'd like to
understand how I got it.
I create three new axis, centered on the (x,y) origin. The H-
axis runs vertically (the same as the y axis). The E-axis is a
line sloping upwards at +30 deg. The X-axis (sorry about the use
of the same letter) runs downwards at -30 deg. Given an (x,y)
point, I project the vector from the origin to the point onto
each axis and record the length of the projection. I then take
that length, double it (to make the math easier), and truncate
towards negative infinity (Careful, since int(-4.12) = -4. I use
instead the floor() function. i.e. floor(3.42) = 3, floor(-4.12)
= -5, floor(-3) = -3 ). This gives me a tripple (H,E,X) which
places the point within a triangle on the board. If you draw the
three axis, and draw perpidicular lines to them at 1/2 unit
intervals, it will divide the board up like this:
Hex 0101 (H,E,X) inside each triangle.
____________
/\ /\ Every triangle in the
/ \ 0,0,0 / \ same row has the same
/ \ / \ H value, every triangle
/ \ / \ along the \ direction has
/ 0,-1,0 \ / 0,0,1 \ Hex 0201 the same E value, and
/__________\/__________\____________ every triangle along
\ 1,-1,0 /\ 1,0,1 //\ 1,1,2 /\ the / direction has
\ / \ // \ / \ the same X value.
\ / \ // \ / \
\ / \ // \ / \
\ / 1,-1,1 \ // 1,0,2 \ / 1,1,3 \
\/__________\/__________\/__________\
So once I've converted from (x,y) to (H,E,X) it is just a matter
of calculating which hex a given (H,E,X) triangle is in. Any
triangle can be described by the following equation:
<triangle> = <base> + n * < 0, 3, 3> + k * < 1, 1, 2>
where I've defined <base> to be one of <0,-1,0>, <0,0,0>,
<0,0,1>, <0,1,1>, <0,1,2>, or <0,2,2>. The hex number is then a
straight-forward function of <base>, n, and k.
III. Functions
I've grouped the functions as follows: utilities (basic math
functions your library should have); (x,y) to <H,E,X>
conversions; <H,E,X> to 0X0Y hex numbers; and the reverse:
0X0Y to the (x,y) point at the center of the hex;
III.1 utilities
Your compiler should have a function like floor(x), that
takes a real number and returns the largest integer less than x.
The correct results to check are:
floor(3.4)=3, floor(-3.2)=-4, and floor(-3.0) = -3.
The last one gets screwed up by rounding sometimes. If you don't
have such a function, here's the code I used:
usage: J = floor(x);
int floor(x)
{ if x >= 0
then return int(x);
else return int(x - 1 + 1E-10);
endif;
};
Where I added the 1E-10 to make float(-3.0) = -3. If you make
this number too small, you won't have enough digits of precision
to make it matter.
III.2 (x,y) to <H,E,X> routines
usage: H = get_H(_xcoord, _ycoord)
int get_H(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
return floor( 2.0 * y);
}
int get_E(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
return floor( sqrt(3.0) * _xcoord - _ycoord);
}
int get_X(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
return floor( sqrt(3.0) * _xcoord + _ycoord);
}
III.3 (x,y) to hexnumber, using above routines
usage: hexnum = getHex( _xcoord, _ycoord);
where hexnum is a 4 digit decimal number, such as 0101 or 2013,
corresponding to the hex map numbering.
int getHex(_xcoord, _ycoord)
float _xcoord, _ycoord;
{
int t,n,ox,oy,h,e,x;
h = get_H(_xcoord, _ycoord);
e = get_E(_xcoord, _ycoord);
x = get_X(_xcoord, _ycoord);
/* t will be the E value of the <base> triangle */
t := e + h - x + ((((x-2*h) mod 3)+3) mod 3);
/* <hex> = <base> + n*<0,3,3> + get_H()*<1,1,2> */
n := floor( (x - 2*h - ((((x-2*h) mod 3)+3) mod 3))/3.0 );
if (t > 0) then
ox = 2 + 2 * n + h;
oy = 1 + floor( ((float)(h-1))/2.0);
else
ox = 1 + 2 * n + h;
oy = 1 + floor( ((float)(h))/2.0 );
endif;
^( 100 * ox + oy);
}
IV. Getting (x,y) from hexnumber
This routine is much easier, since we only need to return the
well-defined center point of the hex.
usage: x = HexToX(hexnumber); y = HexToY(hexnumber);
float HexToX(h)
int h;
{ int tx;
tx = (int) (h/100);
return ( 1/(2*sqrt(3)) + (tx-1)*(sqrt(3)/2));
};
float HexToY(h)
int h;
{ int ty;
int tx;
tx = (int) (h/100);
ty = h mod 100;
return ( ty - 0.5*(tx mod 2);
}
V. Hex counting for range:
This counts the true distance in hexes between two hexnumbers.
usage: range = getRange( h1, h2);
for example, getRange( 0101, 0602) equals 5
See below for getAngle() and nextHex() routines.
/* counts the hexes from here to target. */
int getRange(thisHex, targetHex)
int thisHex, targetHex;
{ int dist, theta; /* theta is an angle in degrees */
int tempHex;
float x,y;
dist=0;
tempHex = thisHex;
while (tempHex <> targetHex)
{
/* limit theta to multiples of 60 degrees */
th:=asInt(getAngle(tempHex, targetHex))/60 * 60 +30;
tempHex = nextHex(tempHex, theta);;
dist=dist+1;
};
return dist;
}
/* returns angle from thisHex to targetHex.
* getAngle(0102,0201) returns +30 deg.
* getAngle(0102,0101) returns +90 deg.
* getAngle(0102,0202) returns +330 deg.
*/
int getAngle(thisHex, targetHex)
int thisHex, targetHex;
{
float t,dx,dy;
dx:= HexToX(targetHex)-HexToX(thisHex);
dy:= HexToY(thisHex)-HexToY(targetHex);
/* flipped because board is upside down. I guess I should change
the code to use the down-is-positive, but then my angles would be
wrong. */
if (dx=0)
{
if dy>=0
{
return 90;
} else {
return 270;
};
} else {
t=radToDeg(arcTan(dy/dx));
if t >= 0
{
if dx>0
then return (int)(t+0.5); /* there are better methods */
/* of rounding, but this */
/* works fine. */
else return (int)(t+0.5+180);
endif;
} else {
if dx>0
{ return (int)(t+360+0.5);
} else {
return (int)(180+t+0.5);
};
};
};
}
/* Returns neighboring hex at the given angle */
Def nextHex(thisHex, theta)
int thisHex;
float(theta);
{
float nx,ny;
nx = HexToX(thisHex) + cos(degToRad(theta));
ny = HexToY(thisHex) - sin(degToRad(theta));
return getHex(nx,ny);
};
VI. Conclusion
In conclusion, I'd like to mention that as I translated the code
from Actor to C, I noticed the C code was much tighter and
faster, and allocated less temporary objects. Of course, it's
not as clear, and a lot more explicit. Over all, I think the C
version of the code is better, and was easier to translate than I
thought. While I'll keep developing my program in Actor, I might
port it to C when I'm done, although I'd loose all my nice MS
Windows dialog boxes and displays.
That's all the files. If you have any questions, I'm
Paul Gyugyi
gyugyi@portia.stanford.edu
--
Paul J. Gyugyi
Grad student, control systems, Stanford University
(and an avid LEGO collector)
gyugyi@isl.Stanford.EDU