procedural generation - métodos - Pregunta matemática: generación de procedimientos de una galaxia

generación procedural videojuegos (19)

Si te sientes valiente, podrías hacer algo peor que mirar cómo lo hizo Ian Bell para la versión original de Elite

Voy a hacer un juego de espacio / comercio / combate que se genera completamente por procedimiento. Pero, sé que almacenar todos los detalles de toda la galaxia en la memoria es inviable. Como resultado, he creído que puedo usar una semilla para generar un sistema solar, y desde ese sistema solar, puedes usar jumpgate para viajar a otros sistemas solares. El problema es que si salto a otro sistema solar desde el que comienza, necesito poder volver al mismo sistema solar de partida exactamente con las mismas características (planetas, asteroides, etc.).

Esencialmente, necesito poder generar una galaxia entera a partir de un número. Y a partir de ese único número, que genera un sistema solar, necesito poder generar todos los otros sistemas solares que se unen desde el primero y todos los sistemas solares que se unen a ellos, y así sucesivamente. Y cada sistema solar tiene que permanecer exactamente de la misma manera, si vuelvo a ellos. Además, la cantidad de enlaces de cada sistema solar puede ser aleatoria o fija, según tu elección. Aleatorio sería mejor sin embargo.

Echa un vistazo al juego original de Worms . Creo que afirmó tener alrededor de 4 mil millones de niveles posibles. Cada nivel se generó en base a una cadena de inicialización corta de quizás 20 caracteres. Esto determinado

el tema del nivel (ártico, bosque, etc.)
la forma del paisaje
el deslizamiento del suelo
la colocación de los detalles del nivel preconstruido (muñecos de nieve, rocas ...)
la colocación de su equipo de gusanos, minas terrestres y cajas de armas.

Si disfrutaste de un nivel, podrías escribir la cadena inicial y usarla para regenerar el mismo nivel en una fecha posterior.

Este es un ejemplo de una función muy compleja, pero determinista, con un único parámetro de entrada. Creo que este es el concepto esencial de lo que necesitas.

Esto es lo que se me ocurrió. No obstante, si será la versión final.

Imagine una cuadrícula hexagonal, y en cada vértice, un sistema solar. Dado que estamos en una cuadrícula hexagonal, solo hay tres líneas que van desde cualquier vértice. Uno es siempre horizontal, y los otros dos son diagonales. Si le damos a la semilla inicial un valor de n, podemos darle al sistema solar que está conectado horizontalmente al punto de partida un valor de n + 1, los otros obtienen valores de n + 2 y n-2.

Oh mierda. No necesariamente obtendremos una grilla. Maldición. Intentemoslo de nuevo.

No creo que haya realmente tanta información en una "galaxia" que no puedas almacenarla en las computadoras de hoy. Supongamos que una galaxia tiene 100 estrellas, y que cada estrella tiene 10 planetas, y que cada planeta tiene 3 lunas. Eso es 100 estrellas + 1,000 planetas + 3,000 lunas de las que tienes que estar pendiente, que son 4,100 cuerpos.

Aquí están las cosas de las que podemos querer hacer un seguimiento de un planeta.

Masa X, Y, posición Z Longitud del día (tiempo para girar en su propio eje) Duración del año Población Cantidad de recursos para 50 recursos diferentes

Suponiendo que cada valor requiere un doble para almacenarlo, y tenemos 57 valores para almacenar (vamos a redondearlo y decir 100), entonces tenemos 100 valores * 8 bytes * 4100 cuerpos = 3,280,000 bytes. Ahora, eso es 3 megas de datos. Eso puede parecer mucho, pero en realidad no es mucho. Además, no creo que realmente quieras tener tantas estrellas en una sola galaxia. El juego sería realmente demasiado grande para explorar, y probablemente sería demasiado grande para tratar de simular realmente todo lo que sucede en una galaxia determinada.

Míralo de esta manera. Si toma un juego como SimCity, y mira cada casilla en la cuadrícula de la ciudad como un planeta potencial, y luego se da cuenta de cuánta información se puede almacenar en un archivo pequeño, para que no tenga que generar nada al azar.

Podría construir un número pseudo aleatorio de N dígitos de una determinada semilla (el "número madre"). Luego, divide los dígitos en grupos y los utiliza para responder sus preguntas.

Ejemplo: N = 20

-> un dígito: ¿cuántas puertas de salto adicionales?
-> tres dígitos: semilla para generar las longitudes respectivas de cada salto disponible
-> seis dígitos: semilla para generar este sistema solar
-> diez dígitos: semilla para generar una nueva semilla de 20 dígitos para cada sistema solar vinculado

Luego recurse. Cada sistema (con órbitas estables, etc.) se genera en el tiempo 0, y tendrá que calcular cómo se ve ahora .

Por supuesto, este enfoque, a partir de un sistema madre, significaría que cuanto más lejos esté el sistema actual del sistema madre, más tardará en generar sus datos. Además, de esta manera se forma un árbol, no una red (lo que yo esperaría).

Creo que sería mejor generar coordenadas: use coordenadas polares en el plano y tal vez un elipsoide en tres dimensiones.

Puedo recordar vagamente esto hecho antes. A principios de los 90, los fractales causaron furor y recuerdo una compañía que ofrecía mundos a los programadores de juegos. El había creado un universo infinito lleno de galaxias con soles y planetas, un evento hasta los valles y texturas de lugares en los planetas. Ofrecían encontrar bienes raíces virtuales adecuados para los desarrolladores de juegos. Los desarrolladores del juego obtendrían el software para representar y usar esto, junto con las coordenadas exactas para su propiedad en este universo fractal.

Busqué en Google durante unos minutos "universo de planeta de juego fractal" y demás, pero no los encontré. Pudo haber sido Pandromeda , pero no recuerdo bien.

Deberías estudiar fractales para esta idea. Todo lo que necesita es un campo continuo de números que puede recrear desde una semilla y luego presentar esos números como estrellas, planetas y satélites con diferentes propiedades.

Si realmente desea volver a un estado fijo, no creo que la generación de procedimientos a partir de un único valor sea el camino correcto.

Supongamos que tiene una grilla fija de 256x256 sistemas en cada plano y 16 planos en el universo. Cada avión tiene hasta 512 estaciones comerciales y hasta 8 enlaces a otros aviones. Todas las estaciones comerciales y enlaces están en una posición fija. El valor inicial de semilla debe ser al menos 2 ^ 76 para codificar todos los universos posibles. Agregue algunos objetos más (planetas, barcos, ...) y el número crece exponencialmente.

Editar: es un poco menos si no permite más de una estación comercial o enlace en cada sistema. Usaría un almacenamiento permanente, tal vez una base de datos incrustada como Firebird o sqlite. Por cierto, actualmente estoy desarrollando un juego de este tipo.

Si usa un generador de números pseudoaleatorios, puede garantizar que cada número aleatorio que genere aparecerá en el mismo orden de una semilla determinada. El código para generar un sistema sembrado por un número dado aparecerá igual cada vez que lo genere.

Use el primer número de la secuencia numérica pseudo aleatoria para generar el número de "puertas". Pase por cada puerta y obtenga un valor de la secuencia numérica para asignar e inicializar cada sistema objetivo.

Genera las características de cada sistema basado en esa semilla.

Hay varios algoritmos conocidos para generar semillas aleatorias.

Dale una traba al tornado de Mersenne

Una semilla aleatoria para cada sistema solar es una solución viable, pero tengo la sensación de que estás ladrando el árbol equivocado aquí.

¿Puede el jugador hacer algo para cambiar lo que hay allí? (Decir, construir algo, extraer un recurso agotador, etc.) Si es así, deberá guardar el estado de todos modos.

¿Puede el jugador buscar cómo era el lugar sin tener que volver allí? (Y si él no puede, ¿por qué no ?!) ¿Lo va a buscar o va a regenerar todo el sistema solar solo para descubrir una información sobre él? (La solución PRNG no le permite obtener solo una parte del sistema solar, tiene que hacer todo el proceso).

¿Cuantos detalles hay de todos modos que necesitas guardar?

Esta es la idea básica tal como lo entiendo. Digamos que ha llegado al sistema estelar n. ° 42 y necesita saber qué hay en él. Tiene planetas nplanets , un número entre 0 y 10, por ejemplo:

>>> star_system = 42 >>> nplanets = hash(''nplanets%d'' % star_system) % (10 + 1) >>> nplanets 4

OK, entonces, sobre el planeta # 2, ¿cuántas estaciones espaciales están en órbita allí al comienzo del juego? Encuentra un número entre 0 y 3:

>>> planet = 2 >>> nstations = hash(''nstations%d/%d'' % (star_system, planet)) % (3 + 1) >>> nstations 1

Y así. Los números son cada uno una función hash de los índices (sistema estelar n. ° 42, planeta n. ° 2, en este caso), reducidos al rango apropiado. Dado que las funciones hash son deterministas pero ''aleatorias'', es lo mismo cada vez, pero al azar para el jugador.

Por supuesto, las cadenas de hashing con largas secuencias como ''nstations'' en ellas no son la forma más rápida de hacerlo, pero muestran la idea.

Esta es mi segunda solución mejorada. El jugador comenzará en un sistema solar generado al azar. Cada sistema está conectado a entre 1 y 4 otros sistemas. Piense en ellos como sistemas norte, sur, este y oeste. Si un jugador se moviera a través del jumpgate norte, será llevado a un sistema cuya semilla es una más que el sistema anterior. Si va hacia el sur, la semilla para ese sistema será una menos. 2+ y 2- para el este y el oeste respectivamente. Las distancias a esos sistemas (en parsecs o años luz o lo que sea) se calculan con la semilla del sistema y la dirección desde la que está llegando. De esta forma, el tamaño de la galaxia está limitado solo por el máximo y el mínimo del número utilizado para contener las semillas.

Los agujeros de deformación para ir a otras galaxias se colocarán a cierta distancia del sistema de inicio. La próxima galaxia será como una continuación de esta galaxia en que los números de las semillas se incrementarán de la misma manera y que el sistema que está en el otro extremo del agujero de la disformidad galáctica será simplemente un "este" o un "norte" "conexión desde el sistema de arranque.

Por cierto, este uso de semillas en aumento lleva a una web, a diferencia de la solución anterior. Además, puedes ver que este método usa cuadriláteros mientras que la solución anterior usaba hexágonos, lo que hacía imposible crear una web.

Por supuesto, todo esto se basa en la suposición de que todas las semillas generarán una secuencia aleatoria de números que es diferente de cualquier otra secuencia. Esto hace que cada sistema sea único.

Siempre que llame a srandom () con la misma semilla, obtendrá los mismos valores de forma aleatoria (). Entonces, basar todo en un sistema estelar a partir de una sola llamada a srandom () ... Entonces, solo necesitará almacenar 1 entero (la semilla) para un sistema de estrella completa. ¡Ahora eso es compresión!

Sospecho que el mayor problema al que te enfrentarás es tener un sistema de nombres para nombrar todos estos objetos de una manera consistente y significativa para el jugador, aunque tenemos esquemas para nombrar objetos reales sistemáticamente. Olvidé si la convención de nombres de Elite se rompió después de cierto punto ...

Yo uso el Mersenne Twister. Es PRNG que acepta como su matriz de semillas de cualquier longitud.
Por ejemplo, quiero generar galaxia en las coordenadas x = 25, y = 72. Reinicio twister con semillas [25,72].
Si quiero generar el 1138º planeta en esta galaxia, uso [25,72,1138].
¿País? [25,72,1138,10]
¿Ciudad? [25,72,1138,10,32]
y así.
Con este método, puede generar miles de millones de trillones de trillones de objetos utilizando un solo número (el que está antes de la coordenada x, en nuestro caso antes del 25).
Hay algunos proyectos ahora que lo usan.
Noctis: anynowherehere
Infiniverse: http://www.infiniverse-game.com/

¿No puedes simplemente SHA1 la ID de la galaxia, EG:

Galaxy 1

Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab

Galaxy 2

Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0

Galaxy 3

Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb

A continuación, puede segmentar el código, es decir:

First 4 Chars = Número de planetas

356a da4b 77de

Necesitarías algún tipo de algoritmo de cadena a número, uno simple sería tomar el código ASCII de cada carácter no numérico, y luego multiplicarlos todos juntos o algo así.

Entonces, ahora sabemos cuántos planetas hay en nuestra galaxia, ¿qué hay de las dimensiones de galaxias x, y, z?

Siguiente 9 caracteres = Dimensiones de la galaxia (x, y, z)

Mismo principio que el anterior, convierta el código en un número grande. Ten también algunos controles de sensibilidad, no quieres una galaxia que sea 10milesx10milesx10miles con 20 millones de planetas en ella. Tenga algún tipo de algoritmo ponderado, como el tamaño mínimo es # de planetas * 10000. Tendrá que jugar con los números para asegurarse de que los rangos sean todos compatibles y los caracteres seleccionados del hash realmente le den un rango razonable.

O, en lugar de esto, puedes hacer que un número aleatorio elija un número entre el tamaño mínimo y el máximo de la galaxia, pero usa una semilla RNG constante, como la ID de la galaxia. De esta forma, los tamaños de galaxias son esencialmente "aleatorios" para el observador, pero serán los mismos siempre.

¡Etcétera etcétera!

Esa es una forma de obtener propiedades de tu Universo, pero ¿y las propiedades del planeta? Al igual que la población y otras cosas?

Si tienes Galaxy 1 con 20,000 planetas, puedes hacer:

Sha1(''1:340'') = bc02ab36f163baee2a04cebaed8b141505cc26b5

Es decir, galaxy one, planet 340. Luego puedes unir ese código como quieras. El beneficio de usar un hash es que cada planeta debe tener un código totalmente único.

Supongamos que comienzas con una semilla para la galaxia, es decir, 1234, tomas esta semilla y generas 10000 números aleatorios, cada uno representa un sistema estelar. Cuando te acercas a la estrella, tomas el número aleatorio de la estrella, y lo haces como una semilla para una nueva función aleatoria. Genere un número aleatorio para la cantidad de cuerpos celestes que orbitan alrededor de la estrella, y genere un número para cada cuerpo (siempre usando la segunda función aleatoria) y así sucesivamente. No sé si esto te ayuda, pero debes recordar que las funciones aleatorias son internamente caóticas, para una condición inicial, toda la función cambia.

La semilla para las estrellas en la galaxia debe producir siempre las mismas estrellas, la semilla de las estrellas debe producir los mismos cuerpos, etc.

Siempre puede hacer las cosas más interesantes usando estadísticas, cálculos de densidad, mejorando los resultados. Compruebe siempre que las funciones producirán el mismo resultado para la misma entrada.

Lo siento si mi inglés apesta, soy de Argentina, y el inglés no es una de mis cualidades entrenadas: p

PD: estoy haciendo el mismo tipo de juego;)

Creo que vale la pena señalar que

un generador que produce la misma salida de aspecto aleatorio para la misma entrada se llama generador de números pseudoaleatorios, "PRNG". Normalmente le das un número de entrada de "semilla" al principio y luego simplemente extraes números aleatorios, llamándolo sin más información. Nota: no puede "volver" a un número anterior, al menos no sin comenzar desde el principio.
una función tipo PRNG que se llama con coordenadas como entrada de cada llamada es típicamente una función de "ruido". Aquí NO tiene el problema de "no puedo regresar": simplemente vuelva a llamar con la entrada "anterior". Una función de ruido utiliza un PRNG (como un backend, o al menos podría) que todavía se puede sembrar desde el principio, por lo que no se pierde la función "universo de un solo número".
Si bien puedes usar un PRNG y combinar las coordenadas de la galaxia en una "semilla" cada vez, solo obtendrás "ruido blanco" en el mejor de los casos, sin más atributos. Una función de ruido es mucho más adecuada para el trabajo, ya que puede elegirse o incluso ajustarse para darle un aspecto enlosable / suavizado / similar a una espiral / etc. resultados. Por ejemplo, busca imágenes de textura que se hicieron usando ruido perlin. Espero que veas que con la misma función de ruido puedes crear, por ejemplo, miles de nubes aleatorias, pero ajustando la función de ruido a tus necesidades (no solo la semilla o las coordenadas), puedes obtener lava o galaxias. Sin embargo, ajustarlo puede no ser trivial.
El número de coordenadas de entrada para cada llamada determina el número de dimensiones de la función de ruido, por lo que para un mapa bidimensional (o textura, etc.) puede utilizar una función de ruido bidimensional. Entonces lo llamas como noise2d (x, y) cada vez.

En su situación, probaría una función de ruido simple tridimensional (símplex es del autor del ruido perlin, recomendado como mejor).

Cada sistema estelar coordinado triplete le da un número de resultado. La siguiente decisión sería: ¿qué representa el número? Para aprovechar mejor la función de suavizado del ruido símplex, asignaría números más bajos a sistemas solares más vacíos y números más altos a sistemas con más masa. O, mejor aún, para cada sistema, llame al ruido simplex varias veces con subcoordenadas. Los números de resultados medianos son planetas, los números pequeños son vacío o asteroides. Números grandes estrellas, etc.

El tema no está activo y es antiguo, pero las búsquedas pueden terminar aquí, como lo hizo la mía.

Mira esta serie en Gamasutra:

Un universo de procedimiento en tiempo real, los primeros cuatro enlaces

Además, esto: Algoritmos para un universo infinito

Matemáticamente, desea generar al azar / pseudoaleatoriamente un Gráfico Conectado, No Dirigido. En este gráfico, cada nodo sería un sistema solar y cada borde sería una puerta de salto.

1) Cree N nodos y asigne aleatoriamente cada una de las coordenadas espaciales. Estos nodos eventualmente se convertirán en sus sistemas solares.

2) Generar bordes usando el algoritmo de triangulación Deluanay. Sugiero la triangulación de Deluanay porque creará un mapa bastante atractivo sin puertas que se crucen entre sí, pero puede usar cualquier algoritmo que desee. Realmente no sé lo que estás buscando.

3) Si utilizó la triangulación Deluanay, le sugiero que elimine una cierta cantidad de bordes para crear "dispersión". Esto hará que el mapa sea más interesante ya que ciertas ubicaciones se convertirán en centros de transporte, mientras que otras son simplemente paradas en boxes.

4) Guarde este gráfico. Este es tu universo. No extravíe ni arroje su universo. Guárdelo de la manera más eficiente que desee, pero no elimine ninguna información.

5) Asigne a cada nodo una semilla, y use esta semilla para generar cada sistema solar.

6) Felicidades, ahora tienes un universo con una cantidad arbitraria de sistemas solares y puertas de salto.