Estructura de datos para representar conexiones entre países en un mapa

9

En un juego que estoy desarrollando para un cliente, un concepto clave del juego implica moverse en un mapa. En este caso, los tamaños y formas y demás de los distintos países son irrelevantes: pasar de un país a un país adyacente cuenta como un solo paso.

Estoy tratando de descubrir la mejor estructura de datos para representar internamente las conexiones entre los países. Para un país determinado, el juego necesita saber qué países son adyacentes, tanto para saber de qué manera pueden moverse los jugadores como para permitir que la IA del juego trace rutas, determinando posibles caminos de un país a otro. La IA también necesita evaluar qué tan bien conectado está un país, no solo con sus vecinos adyacentes inmediatos sino con los vecinos de esos países, etc.

He descubierto un par de posibilidades, pero parecen torpes e ineficientes. Debido a que la IA necesitará calcular un montón de rutas posibles para tomar buenas decisiones sobre su movimiento, "ineficiente" es muy problemático.

Sospecho que este es un rompecabezas de CS algo común y que hay una solución común, pero no he podido encontrar mucho buscando. Cualquier sugerencia es bienvenida.

maps efficiency Matthew Frederick
fuente
Si debo preguntar esto en GameDev.StackExchange, házmelo saber. Lo pregunto aquí porque estoy seguro de que este tipo de cosas son necesarias para todo tipo de problemas de desarrollo y no necesito ayuda con el lado del "juego", per se, solo la parte de planificación de rutas.
Matthew Frederick
Necesita un gráfico o una matriz de conectividad (que es útil, porque el cierre es fácil de calcular). Quizás necesites ambos. Búscalos.
2
Eche un vistazo a las estructuras de datos gráficos y algoritmos: en.wikipedia.org/wiki/Graph_%28data_structure%29
1
Esto no me parece sobre el tema. Debería estar en GameDev o Stack Overflow, ya que es un tema demasiado objetivo por aquí.

Respuestas:

6

Definitivamente un gráfico. Compruébalo aquí Teoría de gráficos , básicamente tienes nodos y aristas. Un nodo puede contener 0 o más aristas a otros nodos.

Hay muchos algoritmos para calcular la ruta más corta (saltos o distancia), verificar los ciclos (más de una forma de llegar a uno mismo), etc.

Ahora, para poder implementar soluciones eficientes, eso es un poco más complejo, pero como siempre, hay formas.


fuente
Excelente gracias. ¿Tiene alguna sugerencia sobre dónde encontrar dichos algoritmos? No necesito mucho el camino más corto, pero cosas como buscar círculos, etc. serían muy útiles.
Matthew Frederick
2

Como ya se mencionó, necesitaría un gráfico que represente todas las conexiones posibles entre países. Cada conexión también mantendría la distancia entre dos países.

Luego, se puede usar un algoritmo de búsqueda de ruta como A * para determinar la ruta más corta entre dos países.

También hay algunos buenos libros sobre el juego ai: Game AI, por ejemplo, de Mat Buckland http://www.ai-junkie.com/books/toc_pgaibe.html

o la serie AI Game Programming Wisdom. http://www.aiwisdom.com/ El primer libro tiene varios capítulos sobre la búsqueda de caminos.

Stephen
fuente
Excelente, gracias por los consejos del libro. Parece que hay una tonelada de libros de IA y las recomendaciones personales son mucho mejores que los amplios resultados que he obtenido al buscar.
Matthew Frederick