¿Función semilla aleatoria para la generación de mapas?

28

Estoy buscando una función para generar un mapa aleatorio basado en mosaicos a medida que cambian los límites visuales del mapa (al pasar por el mapa). Quiero que el mapa sea infinitamente grande y tenga una estructura tipo laberinto.

Sin embargo, si el mundo es infinito, volver a donde un jugador ya estuvo antes plantea un problema. El juego debe recordar cómo se veía todo allí.

Entonces, estaba pensando: "¿Cómo resuelve Minecraft este problema?" y pensé para mí mismo que debían estar usando algún tipo de función de número aleatorio con una semilla, que puede avanzar pero también retroceder, y de esa manera, volver a generar mosaicos antiguos exactamente como eran, pero en casos nuevos.

¿Qué piensas sobre esto?

Mathias Lykkegaard Lorenzen
fuente
¿Cómo es que mi respuesta está en +5 pero la pregunta solo está en +2? Esta es una de las mejores preguntas en la portada en este momento.
2
¿Minecraft no almacena simplemente los fragmentos que ya visitó / modificó?
FxIII
@FxIII: Minecraft debe, porque puedes modificar el paisaje. Si no puede hacer eso, almacenar los fragmentos es probablemente un desperdicio, o al menos una complicación excesiva.
@ Joe Wreschnig: Ok, Ok ... ¡Tenía miedo de perder algo realmente grande!
FxIII

Respuestas:

20

Lo que has notado es la diferencia entre un generador de números aleatorios y una función de ruido . Un generador de números aleatorios escupe un número diferente cada vez que lo llama. Una función de ruido toma algunos argumentos, por ejemplo, un mapa x e y, y escupe números con propiedades estadísticas similares al azar , pero el mismo valor para los mismos argumentos cada vez , es decir, es una función matemática adecuada.

Los dos están muy relacionados. Una función de ruido puede simular un generador de números aleatorios, haciendo pasar en un valor diferente cada vez - por ejemplo noise(1), noise(2)y así sucesivamente. Y un generador de números aleatorios, arrojado a una mesa gigante, puede actuar como una función de ruido. Sin embargo, en ambos casos, está utilizando la herramienta incorrecta para el trabajo.

Minecraft en particular usos Perlin ruido , un tipo de ruido que es barato para calcular, y tiene una propiedad deseable de ser continua en tantas dimensiones como sea necesario - si se hace un gráfico f(x)que f(x + 1), no habrá ningún saltos bruscos. Esto lo hace muy útil para muchas cosas como la modulación de textura, nubes y gases volumétricos y la generación de terreno.

Si estás buscando una implementación para comenzar a jugar, el generador de ruido Perlin mejorado de Ken Perlin es una de las implementaciones más simples.


fuente
3
Tenga en cuenta que muchos generadores de números aleatorios usan una semilla, y generarán el mismo conjunto de números dados la misma semilla.
thedaian
3
@thedaian: que no es particularmente útil en este caso, a menos que desee regenerar cada número; una función de ruido le permite obtener el número 500 sin tener que generar 499 antes de eso.
Dado el algoritmo de ruido Perlin, ¿es posible calibrarlo? Considere que quiero que el algoritmo sea más propenso a generar un paquete de mosaicos y luego un paquete de mosaicos espaciales.
Mathias Lykkegaard Lorenzen
3
No has leído ni entendido los enlaces que di en seis minutos.
1
Esta respuesta se habría completado con la publicación del blog de Notch: notch.tumblr.com/post/3746989361/terrain-generation-part-1
deceleratedcaviar
3

La forma en que Minecraft controla su generación es creando una semilla de nivel que se usa para sembrar toda la generación de números aleatorios para el juego. Si no existe un fragmento en el disco cuando se solicita, se generará utilizando la función de generación de Notch basada en la semilla del nivel; luego se guarda en el disco para más tarde.

Parece que está buscando lograr un comportamiento similar, por lo que es una forma segura de hacerlo.

Keeblebrox
fuente
2

Como Joe señaló, estás buscando una función hash. En general, las funciones aleatorias son solo funciones hash sembradas con el último número devuelto. Entonces, si se Random()devuelve Hash(seed)=1234, una segunda llamadaRandom() volvería Hash(1234), etc.

Si está buscando una función de hash simple para números pseudoaleatorios, consulte MurMurHash . Lo he implementado en C # y puedo publicarlo en algún lugar si estás interesado. Aquí se puede encontrar información más detallada de Perlin Noise, que utiliza una función de hash de este tipo , y su implementación en C # es aquí .

Toda esta información proviene de una pregunta que hice hace un año aquí en Stack Overflow. Lo que estás buscando se llama generación de contenido procesal, así que si necesitas más información, haz una búsqueda. ¡Feliz generación de terreno!

dlras2
fuente
-1. El hash del ruido de Perlin, tal como está, no se parece en nada a las técnicas utilizadas en MMH u otras rutinas criptográficas de hashing; ese código C # es basura que parece hacer interpolación lineal entre valores aleatorios; requiere mucha más memoria que el ruido de Perlin adecuado y es probable que funcione más lento.
1
@ Joe - Lamento que te sientas tan fuertemente acerca de tu implementación de Perlin Noise. Perlin Noise es en sí mismo un concepto de convertir una función hash en una función de ruido continuo. He estado generando mucho ruido Perlin de manera muy efectiva con MurMurHash. En cuanto al código C #, es un ejemplo de cómo determinar mediante programación el valor de un solo punto en 2D Perlin Noise. Nunca lo usaría en producción, pero es, en mi opinión, más fácil de recorrer que el código que publicaste.
dlras2
1
El OP no tenía conocimiento del ruido o el hash, por lo que simplemente intenté proporcionar referencias con la esperanza de que investigaran más y decidieran por sí mismos cómo implementar lo que sea que necesiten hacer.
dlras2
"Perlin Noise es en sí mismo un concepto de convertir una función hash en una función de ruido continuo". No, el ruido Perlin es una de las funciones de ruido continuo inventadas por Ken Perlin (y no la que él llamó "ruido simplex"). No todas las funciones de ruido continuo son ruido de Perlin; no todas las funciones de ruido continuo son incluso ruido de gradiente, de las cuales el ruido de Perlin es un ejemplo particular; lo que vinculaste no es el ruido de gradiente, sino el ruido de valor.
El código en su enlace es "más fácil de recorrer" porque no es ruido de Perlin; no es tan suave; utiliza muchos más recursos; en resumen, es más fácil caminar porque es más tonto.