¿Cómo obtengo coordenadas de píxel a hexadecimal en un mapa hexadecimal basado en una matriz?

Estoy tratando de hacer un píxel para coordinar la función de un mapa hexadecimal, pero no entiendo las matemáticas correctamente, todo lo que intento parece estar un poco fuera de lugar, y los ejemplos que he encontrado se basan en mapas centrados en círculos.

Por 'basado en matriz' me refiero a la forma en que se ordenan los hexágonos, ver foto.

El resultado más preciso que obtuve fue con el siguiente código, pero aún está apagado y empeora cuanto más aumentan los valores:

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

La pantalla comienza con 0,0 en la parte superior izquierda, cada celda conoce su centro.

Todo lo que necesito es una forma de traducir las coordenadas de la pantalla en coordenadas hexadecimales. ¿Cómo podría hacer eso?

Hay muchos sistemas de coordenadas hexadecimales. Los enfoques de "desplazamiento" son buenos para almacenar un mapa rectangular, pero los algoritmos hexadecimales tienden a ser más complicados.

En mi guía de cuadrícula hexadecimal (que creo que ya has encontrado), tu sistema de coordenadas se llama "par-r", excepto que los estás etiquetando en r,qlugar de q,r. Puede convertir ubicaciones de píxeles en coordenadas hexadecimales con estos pasos:

1. Convierta ubicaciones de píxeles en coordenadas hexadecimales axiales utilizando el algoritmo descrito en esta sección . Esto es lo que hace tu función. Sin embargo, debe dar un paso más.
2. Esas coordenadas axiales son fraccionarias. Deben redondearse al hexágono más cercano. En su código usted usa (int)r, (int)qpero eso solo funciona para cuadrados; para hexágonos necesitamos un enfoque de redondeo más complicado. Convierta las coordenadas r, qa cubo usando las fórmulas axiales a cubo aquí . Entonces use la hex_roundfunción aquí .
3. Ahora tiene un conjunto entero de coordenadas de cubo . Su mapa usa "even-r", no cubo, por lo que debe volver a convertir. Usa el cubo para compensar las fórmulas de r desde aquí .

Necesito reescribir el píxel a la sección de coordenadas hexadecimales para que quede mucho más claro. ¡Lo siento!

Lo sé, esto parece complicado. Utilizo este enfoque porque es el menos propenso a errores (¡no hay casos especiales!) Y permite su reutilización. Esas rutinas de conversión pueden reutilizarse. El redondeo hexadecimal se puede reutilizar. Si alguna vez desea dibujar líneas o rotar alrededor de una coordenada hexadecimal o hacer un campo de visión u otros algoritmos, algunas de estas rutinas también serán útiles allí.

Hay dos formas de manejar este problema, en mi opinión.

1. Utiliza un mejor sistema de coordenadas. Puede hacer que las matemáticas sean mucho más fáciles para usted si es inteligente acerca de cómo numerar los hexes. Amit Patel tiene la referencia definitiva sobre rejillas hexagonales. Querrá buscar coordenadas axiales en esa página.

2. Pedir prestado el código de alguien que ya lo resolvió. Tengo un código que funciona, que saqué de la fuente de Battle for Wesnoth . Tenga en cuenta que mi versión tiene la parte plana de los hexágonos en la parte superior, por lo que tendrá que intercambiar x e y.

Creo que la respuesta de Michael Kristofik es correcta, especialmente por mencionar el sitio web de Amit Patel, pero quería compartir mi enfoque de novato a las redes hexagonales.

Este código fue tomado de un proyecto en el que perdí interés y abandoné escrito en JavaScript, pero la posición del mouse en el mosaico hexadecimal funcionó muy bien. Usé * este artículo de GameDev * para mis referencias. Desde ese sitio web, el autor tenía esta imagen que mostraba cómo representar matemáticamente todos los lados y posiciones del maleficio.

En mi clase de renderizado, tenía esto definido en un método que me permitía establecer cualquier longitud del lado Hex que quisiera. Aquí se muestra porque algunos de estos valores fueron referenciados en el código de coordenadas píxel a hexadecimal.

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

En la clase de entrada del mouse, creé un método que aceptaba una coordenada x e y de pantalla, y devolvía un objeto con la coordenada Hex dentro de la cual reside el píxel. * Tenga en cuenta que tenía una "cámara" falsa, por lo que también se incluyen las compensaciones para la posición de renderizado.

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

Finalmente, aquí hay una captura de pantalla de mi proyecto con la depuración del render activada. Muestra las líneas rojas donde el código verifica las celdas Tipo A frente a Tipo B junto con las coordenadas Hex y los contornos de las celdas.
Espero que esto ayude un poco.

En realidad encontré una solución sin matemática hexadecimal.
Como mencioné en la pregunta, cada celda guarda sus propias coordenadas centrales, calculando el centro hexadecimal más cercano a las coordenadas de píxel puedo determinar la correspondiente celda hexadecimal con precisión de píxel (o muy cerca de ella).
No creo que sea la mejor manera de hacerlo, ya que tengo que iterar en cada celda y puedo ver cómo eso podría ser gravoso, pero dejaré el código como una solución alternativa:

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

Aquí están las agallas de una implementación en C # de una de las técnicas publicadas en el sitio web de Amit Patel (estoy seguro de que traducir a Java no será un desafío):

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

El resto del proyecto está disponible aquí como Open Source, incluidas las clases MatrixInt2D y VectorInt2D mencionadas anteriormente:
http://hexgridutilities.codeplex.com/

Aunque la implementación anterior es para hexes de superficie plana, la biblioteca HexgridUtilities incluye la opción de transponer la cuadrícula.

Encontré un enfoque simple y alternativo que usa la misma lógica que un tablero de ajedrez regular. Crea un efecto de ajuste a la cuadrícula con puntos en el centro de cada mosaico y en cada vértice (al crear una cuadrícula más ajustada e ignorar los puntos alternos).

Este enfoque funciona bien para juegos como Catan, donde los jugadores interactúan con fichas y vértices, pero no es adecuado para juegos donde los jugadores solo interactúan con fichas, ya que devuelve qué punto central o vértice a las coordenadas están más cerca, en lugar de qué ficha hexagonal Las coordenadas están dentro.

La geometría

Si coloca puntos en una cuadrícula con columnas que son un cuarto del ancho de un mosaico y filas que son la mitad de la altura de un mosaico, obtendrá este patrón:

Si luego modifica el código para omitir cada segundo punto en un patrón de tablero de ajedrez (omitir if column % 2 + row % 2 == 1), terminará con este patrón:

Implementación

Con esa geometría en mente, puede crear una matriz 2D (tal como lo haría con una cuadrícula cuadrada), almacenando las x, ycoordenadas para cada punto en la cuadrícula (desde el primer diagrama), algo como esto:

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

Nota: Como es normal, cuando crea una cuadrícula alrededor de los puntos (en lugar de colocar puntos en los puntos mismos), debe compensar el origen (restando la mitad del ancho de una columna xy la mitad de la altura de una fila y).

Ahora que tiene su matriz 2D ( points) inicializada, puede encontrar el punto más cercano al mouse tal como lo haría en una cuadrícula cuadrada, solo teniendo que ignorar cualquier otro punto para producir el patrón en el segundo diagrama:

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

Eso funcionará, pero las coordenadas se están redondeando al punto más cercano (o sin punto) en función del rectángulo invisible dentro del puntero. Realmente desea una zona circular alrededor del punto (por lo que el rango de ajuste es igual en todas las direcciones). Ahora que sabe qué punto verificar, puede encontrar fácilmente la distancia (usando el Teorema de Pitágoras). El círculo implícito aún tendría que caber dentro del rectángulo delimitador original, limitando su diámetro máximo al ancho de una columna (un cuarto del ancho de un mosaico), pero aún es lo suficientemente grande como para funcionar bien en la práctica.