How do I get pixel to hex coordinates on an array based hex map?

by petervaz   Last Updated July 10, 2019 22:13 PM - source

I'm trying to make a pixel to coord function for a hex map but I'm not getting the math correctly, everything I try seems to be a little off, and the examples I've found were based on circled centered maps.

By 'array based' I mean the way the hexes are ordered, see pic.

The most accurate result I got was with the following code, but it is still off, and gets worse the more the values raise:

public HexCell<T> coordsToHexCell(float x, float y){
final float size = this.size; // cell size
float q = (float) ((1f/3f* Math.sqrt(3) * x - 1f/3f * y) / size);
float r = 2f/3f * y / size;
return getHexCell((int) r, (int) q);
} Screen starts with 0,0 on top left, each cell knows its center.

All I need is a way to translate screen coordinates into hex coordinates. How could I do that?

Tags :

There are two ways to handle this problem, in my opinion.

1. Use a better coordinate system. You can make the math much easier on yourself if you're clever about how you number the hexes. Amit Patel has the definitive reference on hexagonal grids. You'll want to look for axial coordinates on that page.

2. Borrow code from someone who has already solved it. I have some code that works, which I lifted from the Battle for Wesnoth source. Keep in mind that my version has the flat part of the hexes on top, so you'll have to swap x and y.

I think Michael Kristofik's answer is correct, especially for mentioning Amit Patel's website, but I wanted to share my novice approach to Hex grids.

This code was taken from a project that I lost interest in and abandoned written in JavaScript, but the mouse position to hex tile worked great. I used * this GameDev article * for my references. From that website the author had this image which showed how to mathematically represent all of the Hex sides and positions.

In my render class I had this defined in a method that allowed me to set any Hex side length that I wanted. Shown here because some of these values were referenced in the pixel to hex coordinate code.

this.s = Side; //Side length
this.h = Math.floor(Math.sin(30 * Math.PI / 180) * this.s);
this.r = Math.floor(Math.cos(30 * Math.PI / 180) * this.s);
this.HEXWIDTH = 2 * this.r;
this.HEXHEIGHT = this.h + this.s;
this.HEXHEIGHT_CENTER = this.h + Math.floor(this.s / 2);

In the mouse input class, I created a method that accepted a screen x and y coordinate, and returned an object with the Hex coordinate that pixel resides within. *Note that i had a fake "camera" so offsets for render position are included as well.

ConvertToHexCoords:function (xpixel, ypixel) {
var xSection = Math.floor(xpixel / ( this.Renderer.HEXWIDTH )),
ySection = Math.floor(ypixel / ( this.Renderer.HEXHEIGHT )),
xSectionPixel = Math.floor(xpixel % ( this.Renderer.HEXWIDTH )),
ySectionPixel = Math.floor(ypixel % ( this.Renderer.HEXHEIGHT )),
m = this.Renderer.h / this.Renderer.r, //slope of Hex points
ArrayX = xSection,
ArrayY = ySection,
SectionType = 'A';
if (ySection % 2 == 0) {
/******************
* http://www.gamedev.net/page/resources/_/technical/game-programming/coordinates-in-hexagon-based-tile-maps-r1800
* Type A Section
*************
*     *     *
*   *   *   *
* *       * *
* *       * *
*************
* If the pixel position in question lies within the big bottom area the array coordinate of the
*      tile is the same as the coordinate of our section.
* If the position lies within the top left edge we have to subtract one from the horizontal (x)
*      and the vertical (y) component of our section coordinate.
* If the position lies within the top right edge we reduce only the vertical component.
******************/
if (ySectionPixel < (this.Renderer.h - xSectionPixel * m)) {// left Edge
ArrayY = ySection - 1;
ArrayX = xSection - 1;
} else if (ySectionPixel < (-this.Renderer.h + xSectionPixel * m)) {// right Edge
ArrayY = ySection - 1;
ArrayX = xSection;
}
} else {
/******************
* Type B section
*********
* *   * *
*   *   *
*   *   *
*********
* If the pixel position in question lies within the right area the array coordinate of the
*      tile is the same as the coordinate of our section.
* If the position lies within the left area we have to subtract one from the horizontal (x) component
*      of our section coordinate.
* If the position lies within the top area we have to subtract one from the vertical (y) component.
******************/
SectionType = 'B';
if (xSectionPixel >= this.Renderer.r) {//Right side
if (ySectionPixel < (2 * this.Renderer.h - xSectionPixel * m)) {
ArrayY = ySection - 1;
ArrayX = xSection;
} else {
ArrayY = ySection;
ArrayX = xSection;
}
} else {//Left side
if (ySectionPixel < ( xSectionPixel * m)) {
ArrayY = ySection - 1;
ArrayX = xSection;
} else {
ArrayY = ySection;
ArrayX = xSection - 1;
}
}
}
return {
x:ArrayX + this.Main.DrawPosition.x, //Draw position is the "camera" offset
y:ArrayY + this.Main.DrawPosition.y
};
},

Finally here is a screenshot of my project with the render's debug turned on. It shows the red lines where the code checks for TypeA vs TypeB cells along with the Hex coordinates and cell outlines Hope this helps some.

Here is the guts of a C# implementation of one of the techniques posted on Amit Patel's web-site (I am sure translating to Java won't be a challenge):

public class Hexgrid : IHexgrid {
/// <summary>Return a new instance of <c>Hexgrid</c>.</summary>
public Hexgrid(IHexgridHost host) { Host = host; }

/// <inheritdoc/>
public virtual Point ScrollPosition { get { return Host.ScrollPosition; } }

/// <inheritdoc/>
public virtual Size  Size           { get { return Size.Ceiling(Host.MapSizePixels.Scale(Host.MapScale)); } }

/// <inheritdoc/>
public virtual HexCoords GetHexCoords(Point point, Size autoScroll) {
if( Host == null ) return HexCoords.EmptyCanon;

// Adjust for origin not as assumed by GetCoordinate().
var grid    = new Size((int)(Host.GridSizeF.Width*2F/3F), (int)Host.GridSizeF.Height);
var margin  = new Size((int)(Host.MapMargin.Width  * Host.MapScale),
(int)(Host.MapMargin.Height * Host.MapScale));
point      -= autoScroll + margin + grid;

return HexCoords.NewCanonCoords( GetCoordinate(matrixX, point),
GetCoordinate(matrixY, point) );
}

/// <inheritdoc/>
public virtual Point   ScrollPositionToCenterOnHex(HexCoords coordsNewCenterHex) {
return HexCenterPoint(HexCoords.NewUserCoords(
coordsNewCenterHex.User - ( new IntVector2D(Host.VisibleRectangle.Size.User) / 2 )
));
}

/// <summary>Scrolling control hosting this HexGrid.</summary>
protected IHexgridHost Host { get; private set; }

/// <summary>Matrix2D for 'picking' the <B>X</B> hex coordinate</summary>
Matrix matrixX {
get { return new Matrix(
(3.0F/2.0F)/Host.GridSizeF.Width,  (3.0F/2.0F)/Host.GridSizeF.Width,
1.0F/Host.GridSizeF.Height,       -1.0F/Host.GridSizeF.Height,  -0.5F,-0.5F); }
}
/// <summary>Matrix2D for 'picking' the <B>Y</B> hex coordinate</summary>
Matrix matrixY {
get { return new Matrix(
0.0F,                        (3.0F/2.0F)/Host.GridSizeF.Width,
2.0F/Host.GridSizeF.Height,         1.0F/Host.GridSizeF.Height,  -0.5F,-0.5F); }
}

/// <summary>Calculates a (canonical X or Y) grid-coordinate for a point, from the supplied 'picking' matrix.</summary>
/// <param name="matrix">The 'picking' matrix</param>
/// <param name="point">The screen point identifying the hex to be 'picked'.</param>
/// <returns>A (canonical X or Y) grid coordinate of the 'picked' hex.</returns>
static int GetCoordinate (Matrix matrix, Point point){
var pts = new Point[] {point};
matrix.TransformPoints(pts);
return (int) Math.Floor( (pts.X + pts.Y + 2F) / 3F );
}

The rest of the project is available here as Open Source, including the MatrixInt2D and VectorInt2D classes referenced above:
http://hexgridutilities.codeplex.com/

Although the implementation above is for flat-topped hexes, the HexgridUtilities library includes the option of transposing the grid.

I actually found a solution without hex math.
As I've mentioned in the question each cell saves it own center coords, by calculating the nearest hex center to the pixel coords I can determine the corresponding hex cell with pixel precision (or very close to it).
I don't think it is the best way to do it since I have to iterate to each cell and I can see how that could be taxing but will leave the code as an alternate solution:

public HexCell<T> coordsToHexCell(float x, float y){
HexCell<T> cell;
HexCell<T> result = null;
float distance = Float.MAX_VALUE;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
cell = getHexCell(r, c);

final float dx = x - cell.getX();
final float dy = y - cell.getY();
final float newdistance = (float) Math.sqrt(dx*dx + dy*dy);

if (newdistance < distance) {
distance = newdistance;
result = cell;
}
}
}
return result;
}

There are many hex coordinate systems. The “offset” approaches are nice for storing a rectangular map but the hex algorithms tend to be trickier.

In my hex grid guide (which I believe you've already found), your coordinate system is called “even-r”, except you're labeling them r,q instead of q,r. You can convert pixel locations to hex coordinates with these steps:

1. Convert pixel locations to axial hex coordinates using the algorithm described in this section. This is what your function does. However, you need to take one more step.
2. Those axial coordinates are fractional. They need to be rounded off to the nearest hex. In your code you use (int)r, (int)q but that only works for squares; for hexes we need a more complicated rounding approach. Convert the r, q to cube coordinates using the axial to cube formulas here. Then use the hex_round function here.
3. Now you have an integer set of cube coordinates. Your map uses “even-r”, not cube, so you need to convert back. Use the cube to even-r offset formulas from here.

I need to rewrite the pixel to hex coordinate section to make it much more clear. Sorry!

I know, this seems convoluted. I use this approach because it's the least error prone (no special cases!) and allows for reuse. Those conversion routines can be reused. The hex rounding can be reused. If you ever want to draw lines or rotate around a hex coordinate or do field of view or other algorithms, some of these routines will be useful there too.

I found a very simple approach that supports pointing to tiles and vertices, and works just like a grid.

If you place points in a grid with columns that are quarter the width of a tile, and rows that are half the height of a tile, you get this pattern: If you then modify the code to skip over every second dot in a checkerboard pattern (skip if column % 2 + row % 2 == 1), you end up with this pattern: Instead of drawing yellow dots at each point, create a 2D array (just like with a square grid), storing the x, y coordinates for each point - something like this:

points = []

for x in range(numberOfColumns) {

points.push([])

for y in range(numberOfRows) {

point = {x: x * widthOfColumn, y: y * heightOfRow}
points[x].push(point)
}
}

Note: When creating a grid around the points (rather than placing dots at the points themselves), you'll want to offset the origin, subtracting half the width of a column from x and half the height of a row from y).

Now that you have points initialized, you can then find the nearest point just like you would on a square grid, though remembering to ignore every second point:

column, row = floor(mouse.x / columnWidth), floor(mouse.y / rowHeight)
point = null if column % 2 + row % 2 != 1 else points[column/2][row/2]

Strictly speaking, this approach does not allow you to map the mouse to the nearest point, as it returns null when the mouse is far away from any point. However, whenever the mouse is close to one of the points, it will find which.

Another issue with this approach is that the mouse is being rounded to the nearest point (or no point) based on which invisible rectangle the mouse is within. If you wanted a circle around the point instead, you could use Pythagoras' Theorem at the end to check the distance, but the circle would have to fit inside the rectangle, limiting its maximum diameter to the width of a column (quarter the width of a tile).

Note: All of this assumes the hexagons are oriented as shown in the diagrams (stacked in columns), but it can be adapted to the other orientation (with the tiles arrayed in rows).

Storing a hex grid

Updated June 28, 2018 07:13 AM

Get ring of tiles in hexagon grid

Updated June 18, 2018 10:13 AM

hexagonal grid Mouse over

Updated May 05, 2018 15:13 PM