Some tile-based map games favor hexagonal grids over rectangular ones, for their
symmetric appeal. In making such games, it is often essential to identify which
hexagon underlies a given screen or mouse point (transforming mouse coordinates to hex
coordinates). Due to the frequency of these queries, it is important to optimize
the transformation as much as possible.
Many internet sources I found presented hackish solutions, involving rectangular approximations with crude corrections.
Below I have outlined the method I used, which I believe is a more elegant constant-time method of resolving screen points to a hexagonal grid. A basic understanding of linear algebra is neccesary.
The hexagon-grid is slightly complicated to deal with directly, but can be
simplified by decomposing each tile into three rhombuses (red, blue, green):
Now the problem of finding which hexagon a screen point is in has been reduced to the problem of finding which parallelogram the point is in. Treating first the blue rhombuses, let us impose some structure on the grid by establishing the X and Y axes, as shown (120 degrees apart). The X-Y axes have effectively reduced the problem to finding the appropriate square, since the axes are aligned with the rhombi sides. Each rhombus can be indexed by its minimum point (with respect to X, Y). Once screen points have been transformed to (X,Y) points, the index can be found be taking the floor of the (X,Y) point. The dark dots are the index points:
Notice, however, that not all indices corrospond to valid blue tiles. Only the valid tiles are labeled; the invalid tiles are dashed. By inspection, we can see that the valid blue tiles are those whose X-Y indices satisfy (X+Y) = 0 (mod 3). Thus we have a method of determining if a point lies within a valid blue rhombus, and the index of the respective blue rhombus.
If the point does not lie within a valid blue tile, we need to check if it is contained by valid red or green tiles. Red tiles are treated in a similar way as blue tiles, except they are indexed with respect to the Y-Z axes as shown. The X, Y, and Z axes are mutually 120 degrees apart.
A similar procedure is executed for green tiles, with respect to the Z-X axes. Below is a diagram of all three tiles (the black dots are the index points). Keep in mind that the axes of their indices differ:
Blue tiles: (X, Y)
Red tiles: (Y, Z)
Green tiles: (Z, X)
Now to make all the tiles in the same hexagon have the same index, we need to express the (Y,Z) and (Z,X) coordinates of the red and green tiles in terms of the (X,Y) coordinates of the blue tiles. This is accomplished by a change of basis (using Z = (-1, -1) in X-Y coordinates)
The resultant X-Y coordinate system:
This system is usable, though not convenient for storage (in an array, for example). To transform into a more convenient, perhaps more intuitive system, change the basis into U-V coordinates (using U = (2,1) and V = (1,2) in X-Y coordinates).
U-V coordinate system:
This indexing is much nicer for array storage and hex-distance calculations.