¿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é?
ai
path-finding
Edwin Earl Ross
fuente
fuente
Respuestas:
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.
fuente
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.
fuente
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.
fuente
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.
fuente