Update: See Amit’s guide to hex grids[1] (2013) for a more visual and comprehensive explanation.
From: amitp@Xenon.Stanford.EDU (Amit Patel) Newsgroups: rec.games.programmer Subject: Re: Hexagon playfield query Date: 24 May 1996 18:22:11 GMT Organization: Computer Science Department, Stanford University.
I’ll post the routines I use to calculate which hex the mouse is in. First, I should explain the hexagon size and layout.
___ ___ / \___/ \ \___/ \___/ / \___/ \ \___/ \___/
Each hexagon is 28 x 24 pixels, but since the columns overlap, the distance from the center of one hex to the center of the next column’s hex is 21.
My coordinate system is offset-grid with no gaps. The lower left is (1,1); as you go up, the N coordinate increases. (I call them (M,N) instead of (X,Y) to distinguish between the hex and square coordinates.) Every other column is pushed up half a hexagon height.
First, this is the approach based on a rec.games.programmer article saved on my web pages[3]. It is based on the view that hexagons are a projection of three dimensional cubes onto a plane. (See that web page for an explanation.)
// Note: HexCoord is a struct that just stores hex coordinates HexCoord PointToHex( int xp, int yp ) { // NOTE: HexCoord(0,0)'s x() and y() just define the origin // for the coordinate system; replace with your own // constants. (HexCoord(0,0) is the origin in the hex // coordinate system, but it may be offset in the x/y // system; that's why I subtract.) double x = 1.0 * ( xp - HexCoord(0,0).x() ) / HexXSpacing; double y = 1.0 * ( yp - HexCoord(0,0).y() ) / HexYSpacing; double z = -0.5 * x - y; y = -0.5 * x + y; int ix = floor(x+0.5); int iy = floor(y+0.5); int iz = floor(z+0.5); int s = ix+iy+iz; if( s ) { double abs_dx = fabs(ix-x); double abs_dy = fabs(iy-y); double abs_dz = fabs(iz-z); if( abs_dx >= abs_dy && abs_dx >= abs_dz ) ix -= s; else if( abs_dy >= abs_dx && abs_dy >= abs_dz ) iy -= s; else iz -= s; } return HexCoord( ix, ( iy - iz + (1-ix%2) ) / 2 ); }
Now, here’s another approach that I’m now using. It’s not as general, but it’s faster.
HexCoord PointToHex( int xp, int yp ) { // NOTE: First we subtract the origin of the coordinate // system; replace with your own values xp -= X_ORIGIN; yp -= Y_ORIGIN; int row = 1 + yp / 12; int col = 1 + xp / 21; int diagonal[2][12] = { {7,6,6,5,4,4,3,3,2,1,1,0}, {0,1,1,2,3,3,4,4,5,6,6,7} }; if( diagonal[(row+col)%2][yp%12] >= xp%21 ) col--; return HexCoord( col, (row-(col%2))/2 ); }
In this approach, I first figure out which “half row” the (x,y) lies in, and put that in `row’. Each hexagon occupies two half rows, but every other column chooses different half rows to start with.
Then I figure out which column I’m in, approximately, and put that in `col’. (Each approximate column is 21 pixels wide.)
| ____| | / \ |/ |\ |\ |/| | \____/ 28 = hex width | | 0 21
The vertical lines marks the approximate column boundary. The half row and the column number tells me whether I need to look at the /
diagonal or the \
diagonal.
I then look at the pixel locations of the diagonal. I can use the y coordinate (modulo the half row height) as an index into the diagonal. If the x coordinate (modulo the column width) is less than the diagonal value, then I need to move the coordinate to the left.
- Amit[4]
September 1999: Jason W. Goodwin writes to me with a fix for negative coordinates (which I don’t use in my code, but may affect my readers):
From: Jason W Goodwin To: amitp@CS.Stanford.EDU I'm using one of the algorithms listed on your game programming information web page (BTW, I haven't gone through it thoroughly yet, but it looks like a great resource) for transforming screen coordinates into hexagonal coordinates. Specifically the first one listed at: http://www-cs-students.stanford.edu/~amitp/Articles/GridToHex.html Have you noticed a problem with it giving the wrong coordinates once it should start going into the negatives? Specifically, it gives N+1 when N < 0 and also errs whenever M is < 0 and odd. I made the following small change to the last line, and it works fine for me now (I've only tested this against -100 <= m <= 100, -100 <= n <= 100, so there might be an error at 101, I don't know) // Note that for ix = -1, -3, -5, ... : 1 - (ix % 2) = 2. // Original Line: // return HexCoord( ix, ( iy - iz + (1-ix%2) ) / 2 ); // Added Lines: if ((s = iy - iz) < 0) iy = s - 1 + ((ix+1) & 1); // this should be !(ix&1), but I else // haven't checked it, and it might iy = s + 1 - (ix & 1); // be compiler dependant. return HexCoord( ix, iy / 2 ); -- Jason Goodwin "O Theos mou! Echo ten labrida en te mou kephale!"