Encontrar el camino más corto en una cuadrícula hexagonal

14

Estoy escribiendo un juego por turnos que tiene algunos elementos de simulación. Una tarea en la que estoy colgado actualmente es encontrar el camino. Lo que quiero hacer es mover cada turno un aventurero de IA una ficha más cerca de su objetivo usando su x, y actual y su objetivo x, y.

Al tratar de resolver esto por mí mismo, puedo determinar 4 direcciones sin problema usando

dx = currentX - targetY
dy = currentY - targetY

pero no estoy seguro de cómo determinar cuál de las 6 direcciones es en realidad la ruta "mejor" o "más corta".

Por ejemplo, en la forma en que está configurada actualmente, uso East, West, NE, NW, SE, SW pero para llegar a la casilla NE me muevo hacia el este y luego hacia el NW en lugar de solo mover hacia el NW.

Espero que esto no haya sido todo divagado. Incluso un enlace o dos para comenzar sería bueno. La mayor parte de la información que he encontrado está en dibujar las cuadrículas y asimilar el extraño sistema de coordenadas necesario.

Timothy Mayes
fuente
55
A * le brinda la ruta más corta independientemente de la forma de su gráfico (cuadrícula, hexadecimal, forma libre ...)
Jari Komppa

Respuestas:

21

Algunas respuestas!

El sistema de coordenadas que he visto con mayor frecuencia para el recorrido basado en hexágono es uno en el que el jugador puede moverse en todas las direcciones normales de NSEW, así como NW y SE. Luego, solo representa cada fila con un desplazamiento de medio cuadrado. Como ejemplo, la ubicación (2,7) se considera adyacente a (1,7), (3,7), (2,6), (2,8), y las extrañas: (1,6) y (3,8). Mientras tanto, si suponemos que (2,7) se representa en el centro de la pantalla, (2,6) se representará hacia arriba y hacia la derecha, (2,8) se representará hacia abajo y hacia abajo -la izquierda, (1,7) y (3,7) lo colocarán a la izquierda y derecha respectivamente, y (1,6) y (3,8) se colocarán arriba a la izquierda y abajo a la derecha respectivamente.

Un diagrama de lo que quiero decir:

ingrese la descripción de la imagen aquí

Si lo está haciendo de esta manera, encontrar el camino directo más corto no es difícil: recorra la distancia máxima NW / SE que pueda sin sobrepasar su objetivo a lo largo de un eje cardinal, luego viaje directamente a lo largo de ese eje hasta el objetivo.

Pero, por supuesto, eso te llevará directamente a través de montañas u otro terreno intransitable. Para responder una pregunta que aún no ha formulado: El algoritmo de búsqueda A * es un enfoque común y razonablemente bueno para encontrar rutas. Manejará no solo diseños extraños que no sean de cuadrícula, sino que felizmente se enfrentará a obstáculos e incluso a terrenos obstruidos / lentos.

ZorbaTHut
fuente
Gracias por el enlace al algoritmo de búsqueda A *. La única forma en que puedo imaginar poder atravesar nsew y nw / se es un hex inclinado. Lo que se ve raro en mi cabeza. ¿Me puede vincular a un ejemplo de eso?
Timothy Mayes
44
Estoy diciendo que su imagen renderizada no tiene que tener mucho parecido con la estructura interna. Sugiero que internamente use NSEW y NW / SE, pero se lo muestre al usuario como si fuera una cuadrícula. Adjuntando un diagrama explicativo a la respuesta original :)
ZorbaTHut
2
Representación interesante para una cuadrícula hexadecimal. Por lo general, hago un patrón irregular, por lo que la adyacencia es diferente para las filas pares e impares. Esto introduce una complejidad mínima adicional en la búsqueda de ruta, pero usa una matriz bidimensional de manera más eficiente (suponiendo que toda el área de juego sea un rectángulo.
Panda Pajama
2
@PandaPajama: dentado funciona mejor para almacenar eficientemente mapas rectangulares; puedes hacer que las coordenadas no irregulares funcionen bien con este truco
amitp
2
@PandaPajama, hay otro truco interesante que puedes usar: puedes usar la representación no irregular para las coordenadas, luego abstraer el respaldo para el almacenamiento de datos detrás de algo que usa el método "irregular". He descubierto que el sistema de coordenadas de no irregular es mucho más fácil de manejar, pero, por supuesto, una vez que se abstrae, el backend puede hacer lo que quiera para que las cosas sean eficientes :)
ZorbaTHut
5

Acabo de publicar una biblioteca de utilidades de cuadrícula hexadecimal en CodePlex.com aquí: https://hexgridutilities.codeplex.com/ La biblioteca incluye la búsqueda de rutas (usando A- * a la Eric Lippert) e incluye utilidades para la conversión automática entre cordones irregulares (denominados Usuario) y coordenadas no irregulares (denominados canónicos). El algoritmo de búsqueda de ruta permite que el costo del paso para cada nodo varíe tanto con el hexágono de entrada como con el lado hexagonal atravesado (aunque el ejemplo proporcionado es más simple). Además, se proporciona un campo de visión elevado mediante la proyección de sombras, [editar: palabras eliminadas].

Aquí hay una muestra de código que se convierte fácilmente entre tres sistemas de coordenadas de cuadrícula hexadecimal:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2,1, 0,2, 0,0, 2);
IntVector2D VectorCanon {
  get { return !isCanonNull ? vectorCanon : VectorUser * MatrixUserToCanon / 2; }
  set { vectorCanon = value;  isUserNull = isCustomNull = true; }
} IntVector2D vectorCanon;
bool isCanonNull;

static readonly IntMatrix2D MatrixCanonToUser  = new IntMatrix2D(2,-1, 0,2, 0,1, 2);    
IntVector2D VectorUser {
  get { return !isUserNull  ? vectorUser 
             : !isCanonNull ? VectorCanon  * MatrixCanonToUser / 2
                            : VectorCustom * MatrixCustomToUser / 2; }
  set { vectorUser  = value;  isCustomNull = isCanonNull = true; }
} IntVector2D vectorUser;
bool isUserNull;

static IntMatrix2D MatrixCustomToUser = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
static IntMatrix2D MatrixUserToCustom = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
IntVector2D VectorCustom {
  get { return !isCustomNull ? vectorCustom : VectorUser * MatrixUserToCustom / 2; }
  set { vectorCustom  = value;  isCanonNull = isUserNull = true; }
} IntVector2D vectorCustom;
bool isCustomNull;

IntMatrix2D e IntVector2D son implementaciones enteras [editar: homogéneas] de affine2D Graphics Vector y Matrix. La división final por 2 en las aplicaciones de vector es volver a normalizar los vectores; esto podría estar oculto en la implementación de IntMatrix2D, pero la razón del séptimo argumento para los constructores de IntMatrix2D es menos obvia. Tenga en cuenta el almacenamiento en caché combinado y la evaluación diferida de las formulaciones no actuales.

Estas matrices son para el caso:

  • Hexagonal de grano vertical;
  • Origen en la esquina superior izquierda para coordenadas canónicas y de usuario, en la esquina inferior izquierda para coordenadas personalizadas;
  • Eje Y verticalmente hacia abajo;
  • Eje X rectangular horizontalmente a través; y
  • Eje X canónico hacia el noreste (es decir, hacia arriba y hacia la derecha, a 120 grados CCW desde el eje Y).

La biblioteca de códigos mencionada anteriormente proporciona un mecanismo igualmente elegante para la selección hexadecimal (es decir, identificar el hexadecimal seleccionado con un clic del mouse).

En coordenadas canónicas, los 6 vectores de dirección cardinales son (1,0), (0,1), (1,1) y sus inversas para todos los hexágonos, sin la asimetría de las coordenadas irregulares.

Pieter Geerkens
fuente
¡Guauu! Net un voto negativo para publicar una biblioteca de código de trabajo, con ejemplos y documentación, que responda a la pregunta / problema planteado por el OP.
Pieter Geerkens
55
Si bien no fui el votante negativo (y la etiqueta generalmente sugiere dejar un comentario explicando un voto negativo), sospecho que el voto negativo se debió a que (a) la publicación suena como publicidad y (b) pone la mayor parte de una respuesta en el otro el lado de un enlace generalmente está mal visto porque los enlaces tienden a pudrirse y los sitios SE intentan ser autónomos. La información que se proporciona aquí es interesante, pero no responde la pregunta del usuario , y la única información que podría responder la pregunta está en el otro lado del enlace.
Steven Stadnicki
Buenos puntos; gracias. He ampliado la publicación con extractos que abordan la cuestión de cómo mantener eficientemente múltiples coordenadas de cuadrícula hexadecimal. La biblioteca de códigos publicados es freeware
Pieter Geerkens
¡Uy! La división por 2 solo funciona para enteros positivos. (Gracias de nuevo, K&R.) Debería ser reemplazado por una llamada al método Normalize () en IntVector2D:
Pieter Geerkens
public IntVector2D Normalize() { if (Z==1) return this; else { var x = (X >= 0) ? X : X - Z; var y = (Y >= 0) ? Y : Y - Z; return new IntVector2D(x/Z, y/Z); } }
Pieter Geerkens
0

Este es un problema resuelto, con mucha literatura para respaldarlo. El mejor recurso que conozco es en Red Blob Games: https://www.redblobgames.com/grids/hexagons/ .

En resumen, la razón más probable es que comenzó con un sistema de coordenadas incorrecto. Usar un sistema de coordenadas Cube que implementa el algoritmo A * es bastante simple. Ver demostración en vivo en el enlace de arriba.

Si realmente desea utilizar algún otro sistema, realice la conversión ay desde cuando sea necesario.

david.pfx
fuente