In writing my Settlers of Catan computer version, I came upon the following conundrum: how do I perform coordinate hit tests on a hexagonal grid? Dealing with cartesian, square grid is very simple and well understood. A hex grid, in reality is not very much more complex, but does throw a few curve balls (i.e. there are angles to consider, cells overlap, etc). I did a little online research and my search wasn't too fruitful, but what I did find confirmed some ideas I already had which I'll outline here.
A few points of interest with respect to hex grids:
- There are two ways of rendering the grid (flat-side up and point up). Each of these presents a different algorithm and a solution to the point hit test problem.
- If the flat-side-up orientation is chosen, you will actually end up with fewer hexes visible on the screen at a time.
Here is the scenario I ended up with:
- I chose the point-up orientation of the hexes.
- Each successive column/row of hexes overlaps by one pixel on its neighboring hex to provide a seamless edge - this greatly simplified the creating of hexagonal tiles.
- My hex-grid (map) is rendered graphically offset from the upper-left corner of the image so we must take that offset into consideration during our hit test.
In solving the problem, I made the following assumptions and assertions on my code:
- My hex tiles are a fixed size: 153 x 177 pixels
- The origin (0, 0) of the map is offset to the upper right of (1, 0)
- In order to provide graphical symmetry in my maps, every other row starting with 0 (continuing with 2, 4, 6, etc) has one fewer column than the odd rows (1, 3, 5, etc).
- We have to take the 'missing' column as well as points that fall off of the grid into consideration while performing our hit test or we might return invalid coordinates.
Now to the solution:
In order to perform the hit test, I decided to treat the entire map in a traditional, grid-based manner, dissecting the map into a grid where each square was 153 x 133 (or MAPTILE_WIDTH x MAPTILE_HEIGHT * .75). Each square then contains points that belong to up to three hexes.
If my y coordinate falls on an 'odd' row, then the lower 66% of the square belongs to two adjacent hexes. The upper 1/3rd belongs to three hexes. If the y coordinate falls on an 'even' row, the lower 2/3rds of the square belong entirely to a hex and the upper 1/3rd belongs to two other hexes as per the diagram.
The other issue to resolve is that of calculating points in relation to a given slope (very easy using the point-slope equations that I learned back in junior high-school). If you observe the code you'll see that I cheat a little...I preresolve the slopes (since they are constant and I don't want to have to reevaluate a known value repetitively).
I'm not going to give a play-by-play of my code, but if you have any questions, feel free to let me know; I've commented that which I felt was important to comment and have included it below.
Just a few points of interest about my code because it does target my game and isn't entirely generic, though breaking it out to be completely generic would be a no-brainer, I don't have the immediate need to do so:
- Map.Current is a singleton instance of a Map object (defined elsewhere) that represents the map in question.
- Several of the constants that I use in the code are defined in a Constants class.
- InvalidPoint is a point object (defined as private readonly Point InvalidPoint = new Point(-1, -1)) and represents any coordinate position on the map that doesn't correlate to a coordinate on the grid.
Undoubtedly, there are better algorithms for detecting hit tests against a hexagon and I'd love to see them...this merely represents a first-go at the problem and I think it addresses it well. This function is intended to return a Point object containing the map x-y coordinate pair as resolved against a pixel x-y coordinate pair (e.g. from the current mouse position).
Ok, here's the code:
private Point getHex(Point pt) {
if ( null == Map.Current ) return InvalidPoint;
// precalculate the 'hotspot' regions
const float MAPTILE_HEIGHT_HOT = Constants.MAPTILE_HEIGHT * .75F;
const float MAPTILE_UPPERTHIRD = MAPTILE_HEIGHT_HOT * .33F;
const float ANGLE = 0.589F;
const float ANGLE2 = 1.8095F;
const int MAPTILE_LEFTHALF = Constants.MAPTILE_WIDTH >> 1;
// subdivide the map up into squares.
// each square contains 1/2 of two opposing hexes horizontally and a portion
// of one or two hexes vertically
// for ease of calculation, offset the point by the map margins
pt.Offset(-MAP_MARGIN, -MAP_MARGIN);
int row = (int)( (pt.Y + ( pt.Y / MAPTILE_HEIGHT_HOT )) / MAPTILE_HEIGHT_HOT );
int col = (int)( (pt.X + ( pt.X / Constants.MAPTILE_WIDTH )) / Constants.MAPTILE_WIDTH );
// convert the point (mouse coord) to coordinates relative to the current square
pt.X -= ( col * Constants.MAPTILE_WIDTH ) - col;
pt.Y -= (int)( row * MAPTILE_HEIGHT_HOT ) - row;
if ( pt.Y < MAPTILE_UPPERTHIRD ) {
if ( row % 2 == 0 ) {
if ( pt.X < MAPTILE_LEFTHALF && pt.X * ANGLE > pt.Y )
row--;
else if ( pt.X >= MAPTILE_LEFTHALF && ( pt.X - MAPTILE_LEFTHALF ) / ANGLE2 < ( MAPTILE_UPPERTHIRD - pt.Y ) )
row--;
else if ( pt.X < MAPTILE_LEFTHALF )
col--;
}
else {
if ( pt.X >= MAPTILE_LEFTHALF && ( pt.X - MAPTILE_LEFTHALF ) * ANGLE > pt.Y )
row--;
else if ( pt.X < MAPTILE_LEFTHALF && ( pt.X / ANGLE2 < ( MAPTILE_UPPERTHIRD - pt.Y ) ) ) {
row--;
col--;
}
}
}
else if ( row % 2 == 0 && pt.X < MAPTILE_LEFTHALF ) {
// if the point of interest is within the lower 2/3 of the hex, then there are
// two possibilities - even rows (0, 2, 4, ...) contain two hexes, whereas odd
// rows (1, 3, 5, ...) have only one hex.
col--;
}
if ( col < 0 || row < 0 || row >= Map.Current.Rows || col >= ( ( row % 2 == 0 ) ? Map.Current.Columns - 1 : Map.Current.Columns ) || pt.X < 0 )
return InvalidPoint;
else
return new Point(col, row);
}