¿Las cuadrículas cuadradas o hexagonales son mejores para encontrar caminos?

17

¿Hay alguna diferencia significativa entre usar una cuadrícula cuadrada o hexagonal para el área buscada por un algoritmo de búsqueda de ruta? En otras palabras, es cuadrado o hexagonal mejor, y si es así, ¿por qué?

Edwin Earl Ross
fuente
44
Creo que deberías usar lo que se adapte a tu juego;)
Andrew Russell

Respuestas:

19

La consideración principal para decidir si usar cuadrículas cuadradas o hexagonales no debería ser la facilidad de implementación de la inteligencia artificial: los algoritmos de búsqueda de amplitud y profundidad primero son prácticamente los mismos, sin importar qué tipo de gráfico tenga.

Más bien, este es un problema de juego que los diseñadores de juegos deberían considerar. Las cuadrículas cuadradas son más accesibles para el mercado de masas (los paneles hexagonales tienden a parecer "geek"), y en un mundo de controles arriba / abajo / izquierda / derecha es mucho más intuitivo navegar por cuadrados que hexágonos desde el punto de vista de la interfaz de usuario. Las cuadrículas cuadradas también tienden a restringir un poco más el movimiento; suponiendo un movimiento ortogonal (y no diagonal), se requieren 4 movimientos para caminar alrededor de un obstáculo de un cuadrado, en comparación con 3 movimientos en una cuadrícula hexagonal. Desde el punto de vista de la programación, los hexágonos también son un poco más fáciles de implementar, pero no se trata tanto de algoritmos de búsqueda como de que una cuadrícula cuadrada sea igual a una matriz bidimensional, sino que una cuadrícula hexadecimal realmente no se asigna a una estructura de datos estándar.

La desventaja de las cuadrículas cuadradas es que el movimiento nunca se siente bien. Moverse en diagonal debería tomar puntos de movimiento sqrt (2), pero en la práctica es 1 movimiento (lo que hace que parezca que caminar sobre diagonales es rápido y rara vez hay una razón para caminar ortogonalmente) o son 2 movimientos (lo que hace que el movimiento diagonal se sienta demasiado lento ) Con las cuadrículas hexagonales, la distancia de movimiento es mucho más intuitiva, ya que siempre es la misma distancia de un hexágono a otro sin importar el camino que tome.

Ian Schreiber
fuente
44
+1. Esta es una decisión de diseño, no una decisión de IA. Si quieres cuadrículas hexagonales, una cuadrícula de desplazamiento cuadrado como www-cs-students.stanford.edu/~amitp/game-programming/grids/… puede ser menos intimidante para los jugadores casuales, y es matemáticamente equivalente a los hexágonos. Además, también es una representación conveniente en memoria.
2
+1 para la frase "Las cuadrículas cuadradas son más accesibles para el mercado de masas (las tablas hexagonales tienden a parecer" geek ")": D
Kornel Kisielewicz
Edwin no pregunta qué es mejor en un juego basado en cuadrícula. Pregunta qué es mejor para que la IA use cuadrados o hexágonos. El mundo y el juego en sí no tienen que limitarse a ellos, solo a los nodos en los que la IA está buscando.
AttackingHobo
He implementado juegos de estrategia por turnos con cuadrículas hexagonales y cuadradas, y no hay absolutamente ninguna diferencia necesaria en términos de complejidad para encontrar caminos. Incluso cambié un juego de un mapa hexadecimal a un mapa cuadrado, y (aparte del renderizado) el único cambio que tuve que hacer fue un método MapLocation :: GetDistance () que calculaba la distancia entre dos sectores. Simplemente tuve que ajustar los cálculos para lidiar con cada otra fila que se compensa ligeramente. En ambos casos, puede usar la misma representación en memoria. Entonces, como han dicho los demás, es realmente un problema de diseño.
Mike Strobel
44
Solo un lado, los hexágonos se pueden asignar a una matriz bidimensional. Imagine una cuadrícula cuadrada, luego desplace cada columna pareja medio paso hacia abajo. Ahora tienes una cuadrícula cuadrada desplazada, que es isomorfa a una cuadrícula hexadecimal.
Asmor
3

No soy un experto en IA de ninguna manera, pero la diferencia debería ser insignificante. Las cuadrículas cuadradas son un poco más rápidas (4 conexiones por nodo en lugar de 6), pero ese no es realmente el factor limitante en el tiempo de ejecución algorítmico. Dependiendo del algoritmo que esté planeando usar, el código puede ser un poco más complejo para una cuadrícula hexadecimal, ya que es un poco más complicado calcular las coordenadas y es más difícil usar el tipo de atajos de árbol / octree que creo que son A menudo se utiliza en la búsqueda de caminos.

Pero para un mundo simple como un nivel de juego de estrategia por turnos, la diferencia entre los dos diseños no debería importar mucho; una cuadrícula cuadrada será un poco más simple y rápida.

Gregory Avery-Weir
fuente
55
"Las cuadrículas cuadradas son un poco más rápidas (4 conexiones por nodo en lugar de 6)", a menos que pueda viajar a lo largo de diagonales, en cuyo caso son 8 conexiones frente a 6.
Ian Schreiber
Touche Tienes toda la razón; por supuesto, las conexiones diagonales serían probables.
Gregory Avery-Weir
3

Hay una diferencia práctica que puedo pensar con respecto a la planificación de rutas. Recorrer desde el centro de una celda hexadecimal hasta la de sus vecinos es siempre la misma distancia, mientras que, si permite un desplazamiento diagonal, esto no es cierto para los cuadrados.

Clodéric
fuente
0

Esta guía sobre hexágonos es asombrosa. La parte sobre la búsqueda de rutas tiene un ejemplo interactivo y algo de información sobre cómo adaptar la búsqueda de rutas cuadradas.

Si está utilizando trazado de ruta basado en gráficos, como A * o el algoritmo de Dijkstra o Floyd-Warshall, el trazado de ruta en cuadrículas hexagonales no es diferente del trazado de ruta en cuadrículas cuadradas.

  • Vecinos El código de muestra que proporciono en el tutorial de búsqueda de rutas llama a graph.neighs para obtener los vecinos de una ubicación. Use la función en la sección de vecinos para esto. Filtrar a los vecinos que son intransitables.
  • Heurístico. El código de muestra para A * utiliza una función heurística que proporciona una distancia entre dos ubicaciones. Use la fórmula de distancia, escalada para que coincida con los costos de movimiento. Por ejemplo, si su costo de movimiento es 5 por hexágono, entonces multiplique la distancia por 5.
marca
fuente