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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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;
}

Answer 5

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[0].X + pts[0].Y + 2F) / 3F );
  }

The rest of the Hex Grid Utilities For Games projectis available as Open Source, including the MatrixInt2D and VectorInt2D classes referenced above.

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

Answer 6

I found a simple, alternative approach that uses the same logic as a regular checkerboard. It creates a snap-to-grid effect with points at the center of every tile and at every vertex (by creating a tighter grid and ignoring alternating points).

This approach works well for games like Catan, where players interact with tiles and vertices, but is not suited to games where players only interact with tiles, as it returns which center point or vertex the coordinates are closest to, rather than which hexagonal tile the coordinates are within.

The Geometry

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:

Implementation

With that geometry in mind, you can create a 2D array (just like you would with a square grid), storing the x, y coordinates for each point in the grid (from the first diagram) - something like this:

points = []
for x in numberOfColumns
    points.push([])
    for y in numberOfRows
        points[x].push({x: x * widthOfColumn, y: y * heightOfRow})

Note: As normal, when you are creating a grid around the points (rather than placing dots at the points themselves), you need 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 your 2D array (points) initialized, you can find the nearest point to the mouse just like you would on a square grid, only having to ignore every other point to produce the pattern in the second diagram:

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

That will work, but the coordinates are being rounded to the nearest point (or no point) based on which invisible rectangle the pointer is within. You really want a circular zone around the point (so the snap-range is equal in every direction). Now that you know which point to check, you can easily find the distance (using Pythagoras' Theorem). The implied circle would still have to fit inside the original bounding rectangle, limiting its maximum diameter to the width of a column (quarter the width of a tile), but that is still large enough to work well in practice.