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.
Summary of Procedure:
- Transform screen coordinates to (X,Y), (Y,Z) and (Z,X) coordinates. (change of basis)
- Floor all coordinates to find the three indices.
- Find in which third of the hexagon the point resides, by checking if (X+Y)%3 = 0 or (Y+Z)%3 = 0 or (Z+X)%3 = 0.
- Whichever modulo check passed, use the coordinates of that system. Transform these coordinates to X-Y. (change of basis)
- Transform the X-Y coordinate indices to U-V. (change of basis)