**Update:** Also see Amit’s guide to hex grids (2013), with visual guides to hex distance and x,y to hex algorithms.

Article: 8616 of rec.games.programmer

>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++;

Article: 8688 of rec.games.programmer

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