Estructura de datos para un mundo aleatorio

Question

Por lo tanto, estaba pensando en hacer un generador mundial aleatorio simple. Este generador crearía una "célula" inicial que tendría entre una y cuatro salidas al azar (en los puntos cardinales, algo así como un laberinto). Después de decidir esas salidas, generaría una nueva "celda" aleatoria en cada una de esas salidas, y repetiría cada vez que un jugador se acercara a una parte del mundo que aún no se había generado. Este concepto permitiría un tipo de mundo "infinito", todo generado al azar; sin embargo, no estoy seguro de cómo representar mejor esto internamente.

Estoy usando C++ (lo que realmente no importa, podría implementar cualquier tipo de estructura de datos necesaria). Al principio pensé en usar una especie de gráfico dirigido en el que cada nodo tendría bordes dirigidos a cada celda que lo rodea, pero esto probablemente no funcionará bien si un usuario encuentra un lugar en el mundo, retrocede, y vuelve a eso lugar desde otra dirección. El mundo podría hacer cosas raras, como generar dos celdas en una ubicación.

¿Alguna idea sobre qué tipo de estructura de datos podría ser la más efectiva para tal situación? ¿O estoy haciendo algo realmente tonto con mi generación mundial aleatoria?

Cualquier ayuda sería muy apreciada. Gracias, Chris

Answer 1

A map< pair<int,int>, cell> probablemente funcionaría bien; el par representaría las coordenadas x, y. Si no hay una celda en el mapa en esas coordenadas, crea una nueva celda. Si quisiera hacerlo realmente infinito, podría reemplazar las entradas con una clase entera de longitud arbitraria que tendría que proporcionar (como un bigint)

Answer 2

¿No podría tener un hash (o conjunto de STL) almacenado? una colección de todas las coordenadas de cuadrícula que contienen celdas ocupadas?

Luego, cuando esté buscando crear una nueva celda, puede verificar rápidamente si la ubicación de la celda candidata ya está ocupada.

(si tuviera espacio limitado, podría usar una matriz 2d - Creo que vi esto en un artículo de la revista Byte en ~ 1980-ish, pero si lo entiendo correctamente, quiere un mundo que podría extenderse indefinidamente)

Answer 3

Si las celdas del mundo están dispuestas en una cuadrícula, puede darles fácilmente coordenadas cartesianas. Si mantiene una gran lista de celdas existentes, antes de determinar las salidas de una celda determinada, puede verificar esa lista para ver si ya existe alguno de sus vecinos. Si lo hacen, y usted no quiere tener puertas de 1 vía (¿gráfico dirigido?), Entonces tendrá que tener en cuenta sus salidas. Si no te importa tener rampas en tu juego, aún puedes elegir salidas al azar, solo asegúrate de vincularlas a las existentes si están allí.

Nota de optimización: comprobar una tabla hash para ver si contiene una clave en particular es O (1).

Answer 4

Te recomiendo que leas sobre los gráficos. Esta es exactamente una aplicación de generación de gráficos aleatorios. En lugar de 'celda' y 'salida', está describiendo 'nodo' y 'borde'.

Además, entonces puede hacer cosas como el análisis de ruta más corta, la detección de ciclos y todo tipo de otras aplicaciones de teoría de gráficos útiles.

This le ayudará a entender acerca de los nodos y los bordes:

y here es una aplicación terminada de estos conceptos. Implementé esto de una manera OOP: cada nodo conocía sus bordes a otros nodos. Una alternativa popular es implementar esto usando un adjacency list.Creo que el concepto de lista de adyacencia es básicamente lo que user470379 describió con su respuesta. Sin embargo, su solución de mapa permite gráficos infinitos, mientras que una lista de adyacencia tradicional no lo hace. Me encanta la teoría de grafos, y esta es una aplicación perfecta de ella.

¡Buena suerte!

-Brian J. Stianr-