How can I implement hexagonal tilemap picking in XNA?

I have a hexagon tiled map in which I need to check when a hexagon is clicked. The hexagons aren't actually touching, rather they have a slight gap in between each of them.

Does anyone know how could I go about checking whether a hexagon is clicked without over complicating the whole thing?

Take a look to this picture As you can see there is a relatively intuitive way to map x,y rectangular coordinate system to the hexagonal one.

We may talk about "rect" irregular hexagons ie hexagons inscribed in ellipses or hexagons obtained from regular hexagons scaled in both directions disproportionately (no rotations-shearings).

A rect hexagon can be defined by the height and width of the circumscribing rectangle plus the width of the inscribing one. (W,w,h) The easiest way to find out the hexagonal index is to partitionate the space as follow: The rectangle width is w + (W - w)/2 = (w + W)/2, its height is h/2; the width of the green rectangle is (W-w)/2. Is easy to find out where in which rectangle the point falls: u and v are the reminder coordinates that indicates where the point is whithin the i,j rectangle: Using w we can say if we are in the green area (u < (W-w)/2) or not.

if it is the case we are in the green area we need to know if we are in the upper or lower half of the hexagon: we are in the upper half if i and j are both even or both odd; we are in the lower half otherwise.

In both cases it is usefull to trasform u and v so they vary between 0 and 1: if we are in the lower half and v < u

or

if we are in the upper half and (1-v) > u

then we decrement i by one

Now we simply have to decrement j by one if i is odd to see that i is the horizontal hexagon index (column) and the integer part of j/2 is the vertical hexagon index (row) • Thanks! Really helpful, had a few troubles arising with the splitting of the green section (should i subtract 1 from i or not), but i think that was due to the orientation of my hexagons. All working, thanks! – Joel Dec 10 '11 at 9:16

Regular hexagons have six axes of symmetry, but I will assume your hexagons only have two axes of symmetry (ie. all angles are not exactly 60-degrees). Not necessarily because yours don't have the full symmetry, but because it may be useful to someone else.

Here are the parameters of one hexagon. Its centre is in O, the largest width is 2a, the height is 2b, and the length of the top edge is 2c.

Y ^
|
____|____
/  b |   |\
/     |   | \
/      |   |  \
---(-------+---+---)------>
\     O|   c  / a      X
\     |     /
\____|____/
|

This is the row/column layout, with the origin at the centre of the lower left hexagon. If your setup is different, translate your (x,y) coordinates to fall back on this case, or use -y instead of y for instance:

col 0
| col 1
|   | col 2
|   |  |
__  | __    __    __    __
/  \__/  \__/  \__/  \__/  \__
\__/  \__/  \__/  \__/  \__/  \
/  \__/  \__/  \__/  \__/  \__/
\__/  \__/  \__/  \__/  \__/  \
/  \__/  \__/  \__/  \__/  \__/_ _ line 2
\__/  \__/  \__/  \__/  \__/  \ _ _ _ line 1
/ .\__/  \__/  \__/  \__/  \__/_ _ line 0
\__/  \__/  \__/  \__/  \__/

The following code will then give you the row and column of the hexagon containing point (x,y):

static void GetHex(float x, float y, out int row, out int column)
{
// Find out which major row and column we are on:
row = (int)(y / b);
column = (int)(x / (a + c));

// Compute the offset into these row and column:
float dy = y - (float)row * b;
float dx = x - (float)column * (a + c);

// Are we on the left of the hexagon edge, or on the right?
if (((row ^ column) & 1) == 0)
dy = b - dy;
int right = dy * (a - c) < b * (dx - c) ? 1 : 0;

// Now we have all the information we need, just fine-tune row and column.
row += (column ^ row ^ right) & 1;
column += right;
}

You can check that the above code draws perfect hexagons on this IdeOne run.

• First time I've heard about ideOne, but it seems really useful! – David Gouveia Dec 8 '11 at 14:52
• @davidluzgouveia: yes, it is awesome. I am not fond of web or cloud services but this one is helpful. – sam hocevar Dec 8 '11 at 15:06

You could fit 3 rotated rectangles inside the area of the hexagon, and if done properly it would fill the area exactly. Then it would be simply a matter of checking for collision on the three rectangles.

You probably don't need to de-register clicks between the tiles. That is to say, it won't hurt and might even help the player if you allow the spaces between tiles to be click-able as well unless you are talking about a large space between them that is filled with something that logically shouldn't be clicked. (Say, the hexes are cities on a large map where in-between them are other click-able things like people)

To do the above, you can simply plot the centers of all the hexes, and then find the nearest one to the mouse when clicked on the plane of all the hexes. The nearest center on a plane of tessellated hexagons will always be the same one you are hovering over.

I've already answered a similar question, with identical goals, over on Stack Overflow I'll repost it here for convinience: (NB - all code is written and tested in Java) This image shows the top left corner of a hexagonal grid and overlaid is a blue square grid. It is easy to find which of the squares a point is inside and this would give a rough approximation of which hexagon too. The white portions of the hexagons show where the square and hexagonal grid share the same coordinates and the grey portions of the hexagons show where they do not.

The solution is now as simple as finding which box a point is in, then checking to see if the point is in either of the triangles, and correcting the answer if necessary.

private final Hexagon getSelectedHexagon(int x, int y)
{
// Find the row and column of the box that the point falls in.
int row = (int) (y / gridHeight);
int column;

boolean rowIsOdd = row % 2 == 1;

// Is the row an odd number?
if (rowIsOdd)// Yes: Offset x to match the indent of the row
column = (int) ((x - halfWidth) / gridWidth);
else// No: Calculate normally
column = (int) (x / gridWidth);

At this point we have the row and column of the box our point is in, next we need to test our point against the two top edges of the hexagon to see if our point lies in either of the hexagons above:

// Work out the position of the point relative to the box it is in
double relY = y - (row * gridHeight);
double relX;

if (rowIsOdd)
relX = (x - (column * gridWidth)) - halfWidth;
else
relX = x - (column * gridWidth);

Having relative coordinates makes the next step easier. Like in the image above, if the y of our point is > mx + c we know our point lies above the line, and in our case, the hexagon above and to the left of the current row and column. Note that the coordinate system in java has y starting at 0 in the top left of the screen and not the bottom left as is usual in mathematics, hence the negative gradient used for the left edge and the positive gradient used for the right.

// Work out if the point is above either of the hexagon's top edges
if (relY < (-m * relX) + c) // LEFT edge
{
row--;
if (!rowIsOdd)
column--;
}
else if (relY < (m * relX) - c) // RIGHT edge
{
row--;
if (rowIsOdd)
column++;
}

return hexagons[column][row];
}

A quick explanation of the variables used in the above example:  m is the gradient, so m = c / halfWidth

NeoShamam's addition to the above

This is an addendum to SebastianTroy's answer. I would leave it as a comment but I don't enough reputation yet.

If you want to implement an axial coordinate system as described here: http://www.redblobgames.com/grids/hexagons/

You can make a slight modification to the code.

// Is the row an odd number?
if (rowIsOdd)// Yes: Offset x to match the indent of the row
column = (int) ((x - halfWidth) / gridWidth);
else// No: Calculate normally
column = (int) (x / gridWidth);

use this

float columnOffset = row * halfWidth;
column = (int)(x + columnOffset)/gridWidth; //switch + to - to align the grid the other way

This will make the coordinate (0, 2) be on the same diagonal column as (0, 0) and (0, 1) instead of being directly below (0, 0).

• I realise that this doesn't take into account the gaps between the hexagons but it should help narrow your problem down considerably. – Troyseph Apr 14 '15 at 15:49

If all your hexagons are made using the same proportions and placing, you could use some sort of overlay asset for the collisions, something along the lines of: Then, all you have to do is place the collision image where your hexagon is, get the mouse position relative to the left corner, and see if the pixel of the relative position is NOT white (which means there is a collision).

Code (not tested):

bool IsMouseTouchingHexagon(Vector2 mousePosition, Vector2 hexagonPosition,
Rectangle hexagonRectangle, Texture2D hexagonImage)
{
Vector2 mousePositionToTopLeft = mousePosition - hexagonPosition;

// We make sure that the mouse is over the hexagon's rectangle.
if (mousePositionToTopLeft.X >= 0 && mousePositionToTopLeft.X < hexagonRectangle.Width &&
mousePositionToTopLeft.Y >= 0 && mousePositionToTopLeft.Y < hexagonRectangle.Height)
{
// Where "PixelColorAt" returns the color of a pixel of an image at a certain position.
if (PixelColorAt(hexagonImage, mousePositionToTopLeft) == Color.White)
{
// If the color is not white, we are colliding with the hexagon
return true;
}
}

// if we get here, it means that we did not find a collision.
return false;
}

You could obviously perform a rectangle collision check beforehand (of your whole hexagon image) to improve performance of the whole process.

The concept is quite simple to understand and implement, but only works if your hexagons are all the same. It could also work if you only have a set of possible hexagon dimensions, which would then mean that you would need more than one collision overlay.

If find it to be a very simplistic solution to what could be a lot more complete and reusable (using maths to really find the collision) but it's definitely worth a try in my opinion.

• With your way, you could use any set of irregular shapes and give them all an overlay with a unique colour, then map the colours to the object they are overlaying so you pick a colour from your overlay buffer and then use your map to get the object under the mouse. Not that I'm particularly endorsing this technique, sounds a little over-complicated and an attempt at premature optimisation IMHO. – Troyseph Apr 14 '15 at 15:45

There's an article on Game Programming Gems 7 called For Bees and Gamers: How to Handle Hexagonal Tiles which would be exactly what you need.

Unfortunately I don't have my copy of the book with me at the moment, otherwise I could have described it a little.