baldosas hexagonales y la búsqueda de sus vecinos adyacentes

Question

Estoy desarrollando un juego de mesa sencillo 2D usando mapas hexagonales baldosas, he leído varios artículos (incluyendo la GameDev de uno, que están vinculados cada vez que hay una pregunta sobre baldosas hexagonales) sobre cómo dibujar hexágonos en la pantalla y la forma de gestionar el movimiento (aunque gran parte de ella ya había hecho antes). Mi problema principal es encontrar las baldosas adyacentes basado en un radio determinado.

Esto es cómo funciona mi sistema de mapas:

(0,0) (0,1) (0,2) (0,3) (0,4)
   (1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
   (3,0) (3,1) (3,2) (3,3) (3,4)

etc ...

Lo que estoy luchando con el hecho de que no puedo acaba de 'seleccionar' las baldosas adyacentes mediante el uso de for(x-range;x+range;x++); for(y-range;y+range;y++); porque selecciona azulejos no deseados (en el ejemplo que he dado, seleccionando el 1,1) baldosas (y dando una serie de 1 sería también me dar el (3,0) baldosa (los que realmente que necesito ser (0,1) (0,2) (1,0) (1,2) (2,1) (2,2)) , que es un poco adyacente a la teja (debido a la forma de la matriz está estructurada), pero no es realmente lo que quiero para seleccionar. acabo de poder de la fuerza bruta, pero eso no sería hermosa y probablemente no cubriría todos los aspectos de 'seleccionar cosa radio'.

Puede alguien me punto aquí en la dirección correcta?

Answer 1

¿Qué es una rejilla hexagonal?

Lo que se ve arriba son los dos rejillas. Todo está en la forma de numerar sus azulejos y la manera de entender lo que es una rejilla hexagonal es. El modo de ver, una rejilla hexagonal es nada más que un uno ortogonal deformado.

Los dos baldosas hexagonales que he encerrado en un círculo de color púrpura, teóricamente, están adyacentes a 0,0. Sin embargo, debido a la deformación que hemos pasado para obtener la rejilla hexagonal de baldosas de la ortogonal, los dos ya no son visualmente adyacente.

Deformación

Lo que tenemos que entender es la deformación ocurrió en una determinada dirección, a lo largo de una línea imaginaria [(-1,1) (1,-1)] en mi ejemplo. Para ser más precisos, es como si la red se ha alargado a lo largo de esa línea, y aplastado lo largo de una línea perpendicular a eso. Así que, naturalmente, los dos azulejos en esa línea consiguieron extienden y ya no son visualmente adyacente. A la inversa, la baldosas (1, 1) y (-1, -1) que eran diagonal a (0, 0) ahora son inusualmente cerca (0, 0), tan cerca en hecho de que son ahora visualmente adyacente a (0, 0). Sin embargo Matemáticamente, todavía son diagonales y ayuda a tratarlos de esa manera en el código.

Selección

La imagen que muestro ilustra un radio de 1. Para un radio de dos, se dará cuenta de (2, -2) y (-2, 2) son los azulejos que no deben ser incluidos en la selección. Y así. Por lo tanto, para cualquier selección de radio r , los puntos de (r, -r) y (-r, r) no debe ser seleccionado. Aparte de eso, el algoritmo de selección debe ser el mismo que una cuadrícula cuadrados de baldosas.

Sólo asegúrese de que ha configurado el eje correctamente en la malla hexagonal, y que usted está de numeración de sus azulejos en consecuencia.

Aplicación

Vamos a ampliar en esto por un poco. Ahora sabemos que el movimiento a lo largo de cualquier dirección en los costes de red nos 1. Y el movimiento a lo largo del estirada nos cuesta dirección 2. Ver (0, 0) a (-1, 1) por ejemplo.

Sabiendo esto, podemos calcular la distancia más corta entre dos baldosas en una cuadrícula tal, por la descomposición de la distancia en dos componentes: un movimiento diagonal y un movimiento recto a lo largo de uno de los ejes. Por ejemplo, para la distancia entre (1, 1) y (-2, 5) en una cuadrícula normales tenemos:

Normal distance = (1, 1) - (-2, 5) = (3, -4)

Ese sería el vector distancia entre las dos baldosas estaban ellos en una rejilla cuadrada. Sin embargo tenemos que compensar la deformación cuadrícula de modo que descompone así:

(3, -4) = (3, -3) + (0, -1)

Como se puede ver, hemos descompuesto el vector en una (3, -3) una diagonal y una recta a lo largo de un eje (0, -1).

Ahora comprobamos para ver si el uno diagonal es a lo largo del eje de deformación que es cualquier (n, -n) punto donde n es un número entero que puede ser positivo o negativo. (3, -3) en efecto, satisfacer esa condición, por lo que este vector diagonal es a lo largo de la deformación. Esto significa que la longitud (o coste) de este vector en lugar de ser 3, será doble, que es 6.

Así que para recapitular. La distancia entre (1, 1) y (-2, 5) es la longitud de (3, -3) más la longitud de (0, -1). Es decir distance = 3 * 2 + 1 = 7.

Implementación en C ++

A continuación se muestra la implementación en C ++ del algoritmo que he explicado anteriormente:

int ComputeDistanceHexGrid(const Point & A, const Point & B)
{
  // compute distance as we would on a normal grid
  Point distance;
  distance.x = A.x - B.x;
  distance.y = A.y - B.y;

  // compensate for grid deformation
  // grid is stretched along (-n, n) line so points along that line have
  // a distance of 2 between them instead of 1

  // to calculate the shortest path, we decompose it into one diagonal movement(shortcut)
  // and one straight movement along an axis
  Point diagonalMovement;
  int lesserCoord = abs(distance.x) < abs(distance.y) ? abs(distance.x) : abs(distance.y);
  diagonalMovement.x = (distance.x < 0) ? -lesserCoord : lesserCoord; // keep the sign 
  diagonalMovement.y = (distance.y < 0) ? -lesserCoord : lesserCoord; // keep the sign

  Point straightMovement;

  // one of x or y should always be 0 because we are calculating a straight
  // line along one of the axis
  straightMovement.x = distance.x - diagonalMovement.x;
  straightMovement.y = distance.y - diagonalMovement.y;

  // calculate distance
  size_t straightDistance = abs(straightMovement.x) + abs(straightMovement.y);
  size_t diagonalDistance = abs(diagonalMovement.x);

  // if we are traveling diagonally along the stretch deformation we double
  // the diagonal distance
  if ( (diagonalMovement.x < 0 && diagonalMovement.y > 0) || 
       (diagonalMovement.x > 0 && diagonalMovement.y < 0) )
  {
    diagonalDistance *= 2;
  }

  return straightDistance + diagonalDistance;
}

Ahora, dada la anterior función ComputeDistanceHexGrid en práctica, ahora se puede tener una implementación ingenua, sin optimizar de un algoritmo de selección que va a ignorar todas las baldosas más allá de la gama de selección especificados:

int _tmain(int argc, _TCHAR* argv[])
{
  // your radius selection now becomes your usual orthogonal algorithm
  // except you eliminate hex tiles too far away from your selection center
  // for(x-range;x+range;x++); for(y-range;y+range;y++);
  Point selectionCenter = {1, 1};
  int range = 1;

  for ( int x = selectionCenter.x - range;
            x <= selectionCenter.x + range;
            ++x )
  {
    for ( int y = selectionCenter.y - range;
              y <= selectionCenter.y + range;
              ++y )
    {
      Point p = {x, y};
      if ( ComputeDistanceHexGrid(selectionCenter, p) <= range )
        cout << "(" << x << ", " << y << ")" << endl;
      else
      {
        // do nothing, skip this tile since it is out of selection range
      }
    }
  }

    return 0;
}

Para una poi selecciónnt (1, 1) y una gama de 1, el código anterior se mostrará el resultado esperado:

(0, 0)
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
(2, 2)

Posible optimización

Para optimizar esto, se puede incluir la lógica de saber hasta qué punto un azulejo es desde el punto de selección (lógica encuentra en ComputeDistanceHexGrid) directamente en su circuito de selección, por lo que puede recorrer la red de una manera que evita de lajas de alcance por completo.

Answer 2

método más simple que puedo pensar ...

minX = x-range; maxX = x+range
select (minX,y) to (maxX, y), excluding (x,y) if that's what you want to do
for each i from 1 to range:
    if y+i is odd then maxX -= 1, otherwise minX += 1
    select (minX, y+i) to (maxX, y+i)
    select (minX, y-i) to (maxX, y-i)

Puede ser un poco apagado; i acabo de trabajar a través de mi cabeza. Pero por lo menos, es una idea de lo que tiene que hacer.

En C'ish:

void select(int x, int y) { /* todo: implement this */ }

void selectRange(int x, int y, int range)
{
    int minX = x - range, maxX = x + range;
    for (int i = minX; i <= maxX; ++i)
        if (i != x) select(i, y);
    for (int yOff = 1; yOff <= range; ++yOff)
    {
        if (y+yOff % 2 == 1) --maxX; else ++minX;
        for (int i=minX; i<=maxX; ++i)
        {
            select(i, y+yOff);  select(i, y-yOff);
        }
    }  
}