Mouse hits on a Hex grid?
Dave Mitton
Does anyone have an insights and/or algorithms for resolving x,y mouse
hits on a hex grid?
ie: I will get the mouse click events with an x,y coord, which I then
want to quickly figure out which hex it's in.
Dave.
Warwick Allison
/*
Given a hex grid oriented this way (for other obvious orientation,
simply swap x for y, w for h):
__ __ __
/03\__/23\__/43\
\__/12\__/32\__/
/02\__/22\__/42\
\__/11\__/31\__/
/01\__/21\__/41\
\__/10\__/30\__/
/00\__/20\__/40\
.__/ \__/ \__/ . = (0,0 mouse position)
(mx,my) = mouse coordinate
h = height of hexagon
tw = width of hexagon horizontal side
cw = width of side corner
ie.
-- = cw
____
/ \ |
/ \ | = h
\ / |
\____/ |
---- = tw
Then, only acknowledge clicks in this region:
____
/####\
/ #### \
\ #### /
\####/
As others are likely to be misses by the user.
(of course, you need a feedback (eg. click, cursor flash)
as the user picks a correct position)
You can extend the algorithm later to account for the side corners, if
you think it's necessary.
*/
int XYtoHex(int mx, int my, int h, int tw, int cw, int *hx, int *hy)
/* Returns 0 if not valid (too close to side corners),
* else returns hex for (mx,my) in (*hx,*hy).
*/
{
*hx = (mx/(tw+cw));
if (mx%(tw+cw) < cw) return 0;
/* *hy depends on whether *hx is odd or even */
*hy = (my - ((*hx&1) ? h/2 : 0))/h;
return 1;
}
--
Warwick
--
_-_|\ war...@cs.uq.oz.au /Disclaimer:
/ * <-- Computer Science Department, /
\_.-._/ University of Queensland, / C references are NULL && void*
v Brisbane, Australia. /
Greg Kuperberg
>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++;
Marty Lamb
(Greg Kuperberg) writes:
>>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\
> \__/ \__/ \__/
>
>
the first idea that comes to mind may be a little slow, but it's
(conceptually) the simplest one i could think of: if you could arrange your
grid so that no hexagon touches two hexagons of the same color (if they have to
be the same, you could sacrifice a few palette numbers to fool the computer),
you could separate the screen into a bunch of SQUARES, each with a single
hexagon inscribed. Then you could get the color of the selected pixel & figger
out which hexagon in that square is this color. BIG BIG BIG downfall for this:
you'll probably need at least 5 colors. Hope this helps a little (maybe
inspiring a much better solution?) :)
Marty
--
___________________________________________________________________________
/-------------------------------------------------------------------------/|
| Be like the 22nd elephant with | Marty Lamb (215)758-1402 ||
| heated value in space. Bark! | Box 0151 ||
|-------------------------------------- Lehigh University ||
| ma...@lehigh.edu | 29 Trembley Dr. ||
Greg Alt
>In article <1992Dec4.0...@midway.uchicago.edu>, gr...@marvin.uchicago.edu
> (Greg Kuperberg) writes:
>>>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\
>> \__/ \__/ \__/
How about this idea... Imagine having sort of rows and columns that
align themselves with the edges of the hexes.
Sort of like this:
>> /\/\/\/\/\/\/\/\
>> \/\/\/\/\/\/\/\/
>> /\/\/\/\/\/\/\/\
>> \/\/\/\/\/\/\/\/
>> /\/\/\/\/\/\/\/\
>> \/\/\/\/\/\/\/\/
>> /\/\/\/\/\/\/\/\
>> \/\/\/\/\/\/\/\/
(overlay thison the hex grid)
So, now each hex has 2 diamonds and 2 half diamonds. First determine
the diamond the point is in, then check the horizontal row (each hex
is in two horizontal rows). Then you should be able to get the hex
that it is in.
----
"Dwayne Dibly?!" - The Cat (I've seen 5th season. Have you?)
----
neil.a.kirby
>>In article <1992Dec4.0...@midway.uchicago.edu>, gr...@marvin.uchicago.edu
>> (Greg Kuperberg) writes:
>>>>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\
>>> \__/ \__/ \__/
>
I was hoping someone else would save me from replying to this...
C'mon, it's not that hard. I don't have my code easily accessible, and
copyright worries keep me from posting it, but math is free (if the
algorithms aren't patented).
The geometry of a 30-60-90 triangle gives us side lengths of 1, 2, root 3.
That means that a hex is 4 wide at it's widest point, 2 wide on the flat
parts. A hex grid has an incremental width of 3; add another column and it
grows three units wider. A hex is 2*root(3) tall.
Take all of those numbers, some of which are floats, and multiply by a
scaling factor to map them into how many pixels a hex is in any given
dimension. You do this one time, when the scale of the map is determined.
Store them as ints, since pixels are int, not float. Yes, it means that
small hexes distort, but small hexes are so small you expect it and can't
see it anyway.
To make life a bit easier, chop off the left unit of the grid so that the
visible part starts with the flat tops and not the jagged edge.
Divide x by 3*scale. If you are lucky, it gives you the column number
directly. (As others have posted). To find out if you are in the painful
zone, compute x % scale. If it's zero or one, fine, you have the cloumn
number. If not, life gets hard - more on that later.
The row number depends on the column number, since every other row is
offset by root(3)*scale vertically. If the column has no offset, divide y
by 2*root(3)*scale to get the row number directly. THe statement "has no
offset" can be quite complex if you let users scroll the map around at
will. If the colum has an offset, subtract root(3)*scale from y before
dividing.
The hard case.... FIrst some bad ascii graphics...
case one:
_________
\ |
\ |
\ |
\ |
\ |
\ |
\ |
\ |
________\|
Case two looks the same except the diagonal runs the other way.
What you
need to do is isolate which case you have. THis involves things like (1) is
the expected colum an offset column or not, (2) a lot of use of the %
operator with the numbers computed earlier. Note: if you let your user scroll
your map around a lot, this is non-trivial.
Once you have which case you have, the prblem comes down to: which side of
the line is the point on. Using the % operator you convert to the local
space of the box with the line running through it. We know the sizes of
this box (scale wide by root(3)*scale tall). Y = mX + b is the equation
of a line. If the point is left of the line, the original column number
(the first thing we computed way back up there) is correct. If the point
is right of the line, add one to the column number and recompute the row
number (it could change due to the offset).
THis works out to a page of visual basic code. I humbly suggest that yuou
test the living daylights out of it, especially if you let users scroll
your map. Scrolling the map so that an ODD numbered column is leftmost on
the display might change some assumptions that are easy to fall into when
you write the code.
Neil Kirby
Paul Gyugyi
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
gyu...@portia.stanford.edu
--
Paul J. Gyugyi
Grad student, control systems, Stanford University
(and an avid LEGO collector)
gyu...@isl.Stanford.EDU
Chris Phillips
Here's a simple method if you have a little extra memory.
Use a background buffer to draw a mirror image of the displayed
hex grid only use one color per hex. Then when the mouse is clicked
pick up the color on the background buffer thats at the same x,y as your
mouse and thats your hex location. You could also use variations on this
to just fine tune aproximations. eg narrow it down to 5 hexes and then use
the back buffer to get the exact hex..