gordon@osiris.cso.uiuc.edu (John Gordon) (11/23/90)
I've had several requests to post this, so here it is:
-----------------------------------------------------------------
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.
In article <3540001@hpfcda.HP.COM> dlc@hpfcda.HP.COM (Dennis Clark) writes:
>
> Does anyone have an algorythm to figure ranges on a hex grid? What I want to
>use is a 2 dimensional array to store what is in the hex grid that looks
>basically like the Metagaming grids eg. 0102, 0103, etc. I need a translator
>from grid to array and array to grid and range (distance) checking. This isn't
>as easy as it sounds...
Took me a while to do this one. Store the hex grid as an array where the
first two digits (column) are a subscript as are the last two digits (row).
This doesn't solve the range problem, but it does solve the storage
problem. It gives a 100x100 grid. It sounds like you already have a
handle on this.
One of the keys to the game I'm currently working on is what I call
"rational" numbering as opposed to "hex" numbering. In rational numbering,
even numbered columns have even numbered rows, odd numbered columns have odd
numbered rows. Diagram follows (10x10 grid, first digit is col, second is
row):
Rational Hex
/00\__/20\__/40\ /00\__/20\__/40\
\__/11\__/31\__/ \__/10\__/30\__/
/02\__/22\__/42\ /01\__/21\__/41\
\__/13\__/33\__/ \__/11\__/31\__/
/04\__/24\__/44\ /02\__/22\__/42\
\__/15\__/35\__/ \__/12\__/33\__/
To convert:
Column numbers stay the same.
r to h: new row is old row over 2, round down (integer divide)
h to r: new row is 2* old row (even columns),
new row is 2* old row +1 (odd columns).
Range:
Let cd be the absolute value of the column difference (c1 - c2)
Let rd be the absoulte value of the row difference (r1 - r2)
if( cd >= rd)range = cd;
else range = cd + (rd -cd)/2;
There are boatloads of problems that get easier to do with rational
numbering. This includes LOS path tracing, bearing, and a bunch of others.
In particular, this allows you to completely avoid floating point and trig
functions (which is why I'm doing it).
Display in hex (it's what your users are used to seeing), compute in
rational (easier), and store the array in hex (subscripts).
Neil Kirby
...att!archie!nak