snap to closest hexagon centre in hex based grid

Question

I am attempting to create a grid based game. so far i have a hexagonal tile based grid, with a coordinate scheme as shown below:

col 0
 | col 1
 |   | col 2
 |   |  |
 __  | __    __    __    __   
/00\__/02\__/04\__/06\__/08\__
\__/01\__/03\__/05\__/07\__/09\--- row 0
/10\__/12\__/14\__/16\__/18\__/
\__/11\__/13\__/15\__/17\__/19\--- row 1
/20\__/22\__/24\__/26\__/28\__/
\__/21\__/23\__/25\__/27\__/29\--- row 2
/30\__/32\__/34\__/36\__/38\__/
\__/  \__/  \__/  \__/  \__/   --- row 3

And looks like this in real life just with random colours for each hexagon:

What i am struggling to figure out is, when the user clicks on a hexagon how do i determine what hexagon they have clicked on?

the code i have tried so far is as follows:

private: System::Void MyForm_MouseDown(System::Object^  sender,
    System::Windows::Forms::MouseEventArgs^  e) {

    int CloseI=0,CloseJ=0;
    CloseJ = FindNearesetX(e->X);
    CloseI = FindNearesetY(e->Y);
    //Grid[down(y)][along(x)]
    P1.X = Grid[CloseI][CloseJ].GetX();
    P1.Y = Grid[CloseI][CloseJ].GetY();
} // END MOUSE DOWN EVENT

int FindNearesetX(int ActualX){
    int ClosestJPos;
    ClosestJPos = ((ActualX-Grid[0][0].GetX())/(1.5*HexSideLength));
    return ClosestJPos;
}//END FIND NEAREST X

int FindNearesetY(int ActualY){
    int ClosestIPos;
    ClosestIPos = ((ActualY-Grid[0][0].getY())/(HexHeight));
    return ClosestIPos;
}//END FIND NEAREST Y

private: System::Void MyForm_MouseMove(System::Object^  sender,
    System::Windows::Forms::MouseEventArgs^  e) {
    this->Invalidate();

    P2.X = e->X;
    P2.Y = e->Y; 
} // END MOUSE MOVE EVENT       

This however did not work how i wanted, this is because when the user clicks to the left of the centre point of a hexagon it snaps to the hexagon to the left of the one they clicked, and also if they click above the centre point on all odd columns it snaps to the hexagon above the one they clicked on.

I have been stuck on this one for 2 days now and really want to get it figured out. Thanks

Answer 1

The point clicked will always be closest to the center of hexagon in which the click occurs, unless the point is exactly between two hexagons in which case it will be equidistant from the two centers. The equation for the distance between two points is the SQRT( (x1-x2)^2 + (y1-y2)^2 ).

You do not have to test the distance to every hexagon. By creating x/y thresholds you can limit the test to just nearby hexagons. For example, if hexagons have a width of 10 and the point is at (51, 73) you do not have to test hexagons with x-coordinates of < 40 or > 70.

Answer 2

In fact this can be done quite easily mathematically, without resorting to the irritating, scale-limiting method of iterating through a large quantity of potential values. I came up with the following code in collusion with the excellent information at the following website. The secret is to imagine your hexagonal grid is actually a plane of three-dimensional cubes.

http://www.redblobgames.com/grids/hexagons/

N.B. SS2DCoordinates and SS3DCoordinates are simple structs with two or three integer variables representing coordinates on a 2D and 3D grid respectively (x/y for 2D, x/y/z for 3D) Also note that my hex grid begins at 1/1 rather than 0/0.

SS2DCoordinates coordinatesForHexAtPoint(float a, float b)
{
    // Get basic hex information - pseudocode
    float radius = <radius of one hexagon>

    // Estimate the most likely hex and round to nearest values
    float x = 2.0/3.0*a/radius;
    float z = (1.0/3.0*sqrt(3.0)*b-1.0/3.0*a)/radius;
    float y = -x-z;

    int ix = (int)round((floor(x-y)-floor(z-x))/3.0);
    int iy = (int)round((floor(y-z)-floor(x-y))/3.0);
    int iz = (int)round((floor(z-x)-floor(y-z))/3.0);

    // Adjust to flat coordinates on the offset numbering system
    SS2DCoordinates corrected = hexToFlatCoordinates(SS3DCoordinatesMake(ix, iy, iz));
    corrected.x --;
    return axialToOffsetCoordinates(corrected);
}


SS2DCoordinates hexToFlatCoordinates(SS3DCoordinates hex)
{
    SS2DCoordinates coordinates;
    coordinates.x = hex.x;
    coordinates.y = hex.z;
    return coordinates;
}


SS2DCoordinates axialToOffsetCoordinates(SS2DCoordinates axial)
{
    SS2DCoordinates offset;
    offset.x = axial.x;
    offset.y = axial.y + (NSInteger)ceilf((float)axial.x/2.0);
    return offset;
}

Answer 3

One should be able to find the closest hexagon with O(1) complexity:

    odd     even    odd    even
 0 +----+  |    |  +----+  |
   | 00 |\ |    |  | 02 |  |
   |    | \+----+  |    |  +
   |    | /| 01 |  |    |  |
 H +----+/ |    |  +----+  |
   | 10 |\ |    |  | 12 |  |
   |    | \+----+  |    |  +
   |    | /| 11 |  |    |  |
2H +----+/ |    |  +----+  |
   0....X..W.......2W......3W

The corners '+' are also the corners of the hexagons. 'x' DIV 2*W and y DIV H determine the correct square when 'x' mod W < X. When W <= x mod 2W <= W+X, the point is located on even columns. On odd columns, the row number is y DIV H, on even columns, it's (y + H / 2) DIV H.

The gray area poorly illustrated with the zig-zag pattern requires solving two linear equations (or a dot product) to determine on which side of the diagonal the point falls to. In any case there are a maximum of two candidates to select from.

Answer 4

Actually, due to the regular shape of hexagons (all sides are the same length), this is as easy as cycling through your list of hexagonal tiles and figuring out which tile's center is closest to the mouse click.

C++ pseudocode:

//assuming "map" is an array of "Tile" pointers

Tile *closest = nullptr;
int fromClosestCenterToClick = INT_MAX;

for (int row = 0; row < map.numRows(); row++)
{
   for (int col = 0; col < map.numCols(); col++)
   {
      int distance = std::sqrt(std::pow(map[row][column]->center.x - mouseClickX, 2) + std::pow(map[row][column]->center.y - mouseClickY, 2) < fromClosestCenterToClick);
      if (distance < fromClosestCenterToClick)
      {
         closest = map[row][column];
         fromClosestCenterToClick = distance;
      }
   }
}
//closest now holds the correct tile

Answer 5

I do believe this answer is correct, except for me, I didn't need the corrected.x --; But I needed JavaScript for AfterEffects, so here, let me provide the JavaScript version.

function coordinatesForHexAtPoint(r, a, b)
{
    // Get basic hex information - pseudocode
    var radius = r;

    // Estimate the most likely hex and round to nearest values
    var x = 2.0/3.0*a/radius;
    var z = (1.0/3.0*Math.sqrt(3.0)*b-1.0/3.0*a)/radius;
    var y = -x-z;

    var ix = Math.round((Math.floor(x-y)-Math.floor(z-x))/3.0);
    var iy = Math.round((Math.floor(y-z)-Math.floor(x-y))/3.0);
    var iz = Math.round((Math.floor(z-x)-Math.floor(y-z))/3.0);

    // Adjust to flat coordinates on the offset numbering system
    var corrected = hexToFlatCoordinates(ix, iy, iz);
    //corrected.x--;
    
    return axialToOffsetCoordinates(corrected);
}


function hexToFlatCoordinates(ix, iy, iz)
{
    var coordinates = [];
    coordinates.x = ix;
    coordinates.y = iz;
    
    return coordinates;
}

function axialToOffsetCoordinates(axial)
{
    var offset = [];
    offset.x = axial.x;
    offset.y = axial.y + Math.ceil(axial.x/2.0);
    
    return offset;
}

var point = coordinatesForHexAtPoint(100, 100, 100);
var x = point.x;
var y = point.y;

This code above gave me extremely accurate results.