¿Cómo generar un nivel aleatorio a partir de una semilla? [cerrado]

46

¿Cómo haría para usar una semilla aleatoria para generar un nivel de juego? La misma semilla siempre debe generar exactamente el mismo nivel.

Para este ejemplo, sería un nivel de estilo Worms . Por lo tanto, cada nivel tendría un tema (praderas, nieve, etc.), terreno base, diferentes objetos como árboles.

Entonces, ¿dónde comenzaría a crear este tipo de generador de niveles? ¿Qué estaría involucrado? ¿Qué conceptos usa?

Puntos de bonificación por cualquier enlace bueno ( puntos de bonificación de bonificación por cualquier cosa relacionada con cómo se hizo en gusanos o similares).

Gracias.

algorithm procedural-generation random Adam Harte
fuente
La generación de nivel aleatorio también se conoce como Generación de contenido procesal (PCG). Y aquí hay una wiki que trata solo eso. ¡pcg.wikidot.com debería darte algunas ideas! : o)
Kaj
1
Chris Crawford tiene un artículo que puede resultar interesante. Fue escrito a principios de los 90 pero aún es relevante. Cómo construir un mundo
Anthony
Si utiliza cualquier forma o algoritmo que utiliza el mismo generador de números aleatorios (excepto uno que de alguna manera se cuela en un invariante como la hora del sistema), la misma semilla va a generar el mismo nivel, en realidad no hay manera de evitarlo.
Kaj
1
Sí, pero creo que el truco es usar una semilla en primer lugar para generar el nivel. He construido generadores de nivel aleatorio antes, pero no usaron una sola semilla. A menudo elegiría puntos aleatorios, luego para cada punto elegiría un activo aleatorio para colocar allí. Haciéndolo de esta manera no hay UNA semilla verdadera que siempre generará el mismo nivel, ya que hay un montón de cosas que generan sus propios números aleatorios.
Adam Harte
10
¿Estás seguro de que sabes lo que significa "semilla"? Este es el "vector inicial" aprobada en a través de, por ejemplo, srand(int). Las llamadas posteriores a rand()devolverán valores secuenciales que siempre se calculan en el mismo orden, en función de esta semilla. Establece la semilla una vez en su programa. Después de eso, si el algoritmo depende solo de los resultados rand, obtendrá el mismo resultado cada vez.
Heath Hunnicutt

Respuestas:

7

La clave para esto es usar su propio generador de números pseudoaleatorio personalizado que inicialice con el valor inicial conocido. El "Mersenne Twister" es un algoritmo popular, aquí está la entrada de Wikipedia y alguna fuente de muestra . Este y otros algoritmos PRNG en realidad producen una serie fija (muy larga) de números para los cuales el valor semilla sirve como punto de partida.

Siempre que siga exactamente el mismo procedimiento para generar su mundo cada vez, cada valor representará un mundo reproducible único.

Jason Morales
fuente
4

Aquí hay un PRNG (generador de números pseudoaleatorios) implementado en ActionScript (disponible en AS2 o AS3). Es ligero y rápido, ideal para juegos: http://lab.polygonal.de/2007/04/21/a-good-pseudo-random-number-generator-prng/

La implementación anterior se basa en el PRNG Park-Miller-Carta . Este sitio le dará más información sobre las matemáticas detrás de todo esto.

Sin embargo, para construir un nivel similar a los gusanos, probablemente usaría una función de ruido Perlin . Si genera una imagen de ruido perlin con la altura de 1px y el ancho de su mundo de juego, básicamente obtendrá un mapa de altura, listo para usar. Las funciones de ruido de Perlin también siempre generan el mismo mapa con la misma semilla.

Luego puede usar el PRNG mencionado anteriormente para determinar dónde colocar objetos aleatorios en el mapa o dónde crear un agujero en el suelo. Para los hoyos, también puede aprovechar el ruido perlin nuevamente. Simplemente cree una imagen de ruido perlin con el tamaño de su mapa (x, y), y luego cree un agujero en su mapa donde el valor de píxel esté por debajo de un umbral determinado (por ejemplo, 0.2).

bummzack
fuente
Usaría el ruido perlin, pero de manera un poco diferente, lo uso para crear un mapa de altura 3D, colocar el mapa en una pendiente y eliminar todos los píxeles por debajo de su umbral. (if pixel.height - (pixel.distanceToBottom * hillFactor) <treshold) pixel = transparent)
Niels
2

Teóricamente, si puede usar un generador de números pseudoaleatorio (como Perlin-Noise o Marsenne Twister) para compartir mapas a través de

números de semillas, entonces también puede crear mapas personalizados y reducirlos a semillas, resolviendo el problema de no poder crear

mapas personalizados cuando se usan PRNG. Sin embargo, esto se basa en algunas presunciones. Es decir, que los generadores de números pseudoaleatorios son

un proceso reversible y que CUALQUIER dato alimentado hacia atrás en un PRNG producirá una semilla válida, ¡mucho menos una semilla!


fuente