Haciendo infinito el algoritmo cuadrado de diamante.

Estoy tratando de generar un mapa infinito, como tal. Estoy haciendo esto en Python, y no puedo hacer que las bibliotecas de ruido funcionen correctamente (parece que nunca encuentran mi VS2010, y hacerlo en Python en bruto sería demasiado lento). Como tal, estoy tratando de usar el algoritmo cuadrado de diamante .

¿Sería posible, de alguna manera, hacer esto técnicamente infinito?

Si no, ¿debería volver a intentar que funcione uno de los enlaces de ruido de Python?

Esto puede hacerse. Divida su paisaje en “mosaicos” y aplique el algoritmo de desplazamiento de punto medio (como prefiero llamarlo) dentro de cada mosaico.

Cada baldosa debe ser lo suficientemente grande como para que la altura en una esquina no dependa significativamente de la altura en otra. De esa manera, puede crear y destruir mosaicos sobre la marcha, estableciendo la altura en las esquinas que aparecen de nuevo en un valor aleatorio independiente.

Ese valor (y la aleatoriedad dentro de la baldosa también) se debe sembrar desde la posición de la baldosa, para que obtenga la misma baldosa cada vez.

La última versión del módulo de ruido (en http://pypi.python.org/pypi/noise/1.0b3 ) menciona que “se solucionaron los problemas de comstackción con Visual C ++ en Windows”; es posible que desee intentarlo de nuevo. Se instala y funciona correctamente para mí (Python 2.7.1, MinGW, Windows 7).

Si organiza sus mosaicos en una cuadrícula x, y y siembra el generador de números aleatorios para cada mosaico como random.seed ((x, y)), entonces cada vez que regrese al mismo parche de mundo, se volverá a crear el mismo terreno.

Con el algoritmo de diamante cuadrado, dos lados de cada mosaico dependen de los mosaicos contiguos; sin embargo, la dependencia no se propaga a lo largo del mosaico. Si deja que cada mosaico dependa de los mosaicos que lo preceden (es decir, arriba y a la izquierda) y escribe una función create_fake_tile que asume que todos los valores del mosaico precedente son 0, obtendrá un mosaico “malo” en el que la columna derecha y la parte inferior row son los valores correctos de los que depende el siguiente mosaico. Si dibuja cada pantalla comenzando con la fila y la columna de mosaico que preceden a la primera fila y columna en la pantalla, entonces la parte visible de su mundo será correcta.

Resolví el algoritmo Diamante Cuadrado para paisajes infinitos. Y en realidad encontré esta pregunta haciendo mi debida diligencia. Sí. Aunque las respuestas proporcionadas aquí son en su mayoría erróneas, se puede hacer totalmente. Conceptualmente, lo que debe hacer es ver cada iteración del algoritmo como un campo infinito y el caso base como un campo infinito de números perfectamente aleatorios. Así que cada iteración es una versión de diamante cuadrado de la anterior.

Y para resolver un rango de cuadrícula [100-200] [100-200] en la iteración 7, lo que necesita es la mitad del bloque completo (aproximadamente una cuarta parte del tamaño h * w) en la iteración 6 más un borde adicional en cada lado. Entonces, si tienes una función que se resuelve para un mosaico dado:

getTerrain (x0, y0, x1, y1, iteración) … puede resolver esto para esa baldosa si tiene [49,101] [49,101] en la iteración 6. Luego, simplemente aplique el diamante al cuadrado en cualquier lugar que no funcione. los bordes, pero funcionarán en cualquier otro lugar, y le proporcionarán datos suficientes para resolver el mosaico [100-200] [100-200] en la iteración 7.

Para obtener ese mosaico en la iteración 6, solicitará [23-52] [23-52] de la iteración 5. Y esto continuará hasta que la iteración 0 simplemente le dé [-1,3] [- 1,3] que será 16 Valores perfectamente aleatorios. Si solicitó una baldosa tan grande que la iteración 0 aún no alcanzó ese tamaño y posición, solo necesitará una astilla diferente, lo que está bien porque de todos modos las está inventando.

De esta manera, deshacerse completamente del paso de sembrado, simplificar el algoritmo, hacerlo infinito, hacer que tome una huella de memoria razonable. El uso de un número pseudoaleatorio determinista con hash de las coords le permitirá generar y regenerar los mosaicos idénticos sobre la marcha, ya que en realidad generó las iteraciones inferiores superiores y lo hizo de manera enfocada.

Mi blog tiene más información al respecto, http://godsnotwheregodsnot.blogspot.com/2013/11/field-diamond-squared-fractal-terrain.html

En realidad, la mayor parte de la complicación del algoritmo se debe a que el caso base tiene cuatro puntos en un bucle, ya que no es el caso más simple. Y aparentemente se le ha escapado a la mayoría de la gente que incluso podría haberlo simplificado al hacer 1 punto en un bucle (aunque esto todavía es inútilmente complejo). O cualquier cosa que haga que el algoritmo parezca tener al menos 4×4 puntos. Incluso podría comenzar con una iteración de 4×4 puntos, eliminar cualquier fila o columna con un valor desconocido (todos los bordes), luego tener un bloque 5×5, luego un bloque 7×7 y luego un bloque 11×11 … (2n-3) x (2n -3).

En resumen, si tienes un campo infinito para tu caso base, puedes tener un campo infinito, las iteraciones simplemente determinan cómo se mezclan tus cosas. Y si usa algo determinista para el desplazamiento inyectado pseudoaleatorio, tiene un generador de paisaje infinito muy rápido.

y aquí hay una demostración de ello en javascript, http://tatarize.nfshost.com/FieldDiamondSquare.htm

Aquí hay una implementación en javascript. Simplemente le da una vista del campo correcto en esa iteración, posición y tamaño. El ejemplo vinculado anterior utiliza este código en un canvas móvil. No almacena datos y recalcula cada cuadro.

function diamondSquaredMap(x, y, width, height, iterations) { var map = fieldDiamondSquared(x, y, x+width, y+height, iterations); var maxdeviation = getMaxDeviation(iterations); for (var j = 0; j < width; j++) { for (var k = 0; k < height; k++) { map[j][k] = map[j][k] / maxdeviation; } } return map; function create2DArray(d1, d2) { var x = new Array(d1), i = 0, j = 0; for (i = 0; i < d1; i += 1) { x[i] = new Array(d2); } return x; } function fieldDiamondSquared(x0, y0, x1, y1, iterations) { if (x1 < x0) { return null; } if (y1 < y0) { return null; } var finalwidth = x1 - x0; var finalheight = y1 - y0; var finalmap = create2DArray(finalwidth, finalheight); if (iterations === 0) { for (var j = 0; j < finalwidth; j++) { for (var k = 0; k < finalheight; k++) { finalmap[j][k] = displace(iterations,x0+j,y0+k) ; } } return finalmap; } var ux0 = Math.floor(x0 / 2) - 1; var uy0 = Math.floor(y0 / 2) - 1; var ux1 = Math.ceil(x1 / 2) + 1; var uy1 = Math.ceil(y1 / 2) + 1; var uppermap = fieldDiamondSquared(ux0, uy0, ux1, uy1, iterations-1); var uw = ux1 - ux0; var uh = uy1 - uy0; var cx0 = ux0 * 2; var cy0 = uy0 * 2; var cw = uw*2-1; var ch = uh*2-1; var currentmap = create2DArray(cw,ch); for (var j = 0; j < uw; j++) { for (var k = 0; k < uh; k++) { currentmap[j*2][k*2] = uppermap[j][k]; } } var xoff = x0 - cx0; var yoff = y0 - cy0; for (var j = 1; j < cw-1; j += 2) { for (var k = 1; k < ch-1; k += 2) { currentmap[j][k] = ((currentmap[j - 1][k - 1] + currentmap[j - 1][k + 1] + currentmap[j + 1][k - 1] + currentmap[j + 1][k + 1]) / 4) + displace(iterations,cx0+j,cy0+k); } } for (var j = 1; j < cw-1; j += 2) { for (var k = 2; k < ch-1; k += 2) { currentmap[j][k] = ((currentmap[j - 1][k] + currentmap[j + 1][k] + currentmap[j][k - 1] + currentmap[j][k + 1]) / 4) + displace(iterations,cx0+j,cy0+k); } } for (var j = 2; j < cw-1; j += 2) { for (var k = 1; k < ch-1; k += 2) { currentmap[j][k] = ((currentmap[j - 1][k] + currentmap[j + 1][k] + currentmap[j][k - 1] + currentmap[j][k + 1]) / 4) + displace(iterations,cx0+j,cy0+k); } } for (var j = 0; j < finalwidth; j++) { for (var k = 0; k < finalheight; k++) { finalmap[j][k] = currentmap[j+xoff][k+yoff]; } } return finalmap; } // Random function to offset function displace(iterations, x, y) { return (((PRH(iterations,x,y) - 0.5)*2)) / (iterations+1); } function getMaxDeviation(iterations) { var dev = 0.5 / (iterations+1); if (iterations <= 0) return dev; return getMaxDeviation(iterations-1) + dev; } //This function returns the same result for given values but should be somewhat random. function PRH(iterations,x,y) { var hash; x &= 0xFFF; y &= 0xFFF; iterations &= 0xFF; hash = (iterations << 24); hash |= (y << 12); hash |= x; var rem = hash & 3; var h = hash; switch (rem) { case 3: hash += h; hash ^= hash << 32; hash ^= h << 36; hash += hash >> 22; break; case 2: hash += h; hash ^= hash << 22; hash += hash >> 34; break; case 1: hash += h; hash ^= hash << 20; hash += hash >> 2; } hash ^= hash << 6; hash += hash >> 10; hash ^= hash << 8; hash += hash >> 34; hash ^= hash << 50; hash += hash >> 12; return (hash & 0xFFFF) / 0xFFFF; } }; 

Actualizado para agregar, continué con esto, e hice mi propio algoritmo de ruido basado en el mismo algoritmo de campo de ámbito aquí. Aquí está el Jsfiddle para ello.

https://jsfiddle.net/rkdzau7o/

Puede hacer clic y arrastrar el ruido alrededor.

¿Se puede aplicar el desplazamiento del punto medio de abajo hacia arriba? Digamos que está trabajando en una cuadrícula discreta y desea generar una región MxN. Consígase una función de ponderación w (i). Comience aplicando un desplazamiento aleatorio con peso w (0) a cada punto. Luego aplique un desplazamiento aleatorio con peso w (1) a cada otro punto, y propague el desplazamiento a los puntos intermedios. Luego haz cada cuarto punto con w (2), nuevamente propagando. Ahora puede generar una cuadrícula de cualquier tamaño, sin tener una suposición inicial sobre el tamaño.

Si hay algo de N para el que w (i> N) = 0, entonces puedes dejar de generar cuando lo golpeas, ¡lo cual es bastante importante si quieres que la generación termine! Probablemente desee una función aw que comience en 1, aumente a algún valor y luego caiga a cero; los modelos en bits aumentan la rugosidad de la ley de potencia del terreno de hasta 100 km más o menos, y los modelos en bits disminuyen el hecho de que planetas enteros son más o menos esféricos. Si estuvieras haciendo Marte en lugar de la Tierra, querrías que w (i) fuera más lejos, debido a la protuberancia de Tharsis.

Ahora reemplace la función aleatoria con una función de observación aleatoria pero determinista de las coordenadas del punto (por ejemplo, introduzca las coordenadas en un hash SHA1). Ahora, cada vez que genere una parte particular de la cuadrícula, se verá igual.

Deberías poder hacer un cuadrado de diamante de la misma manera que esto; Solo necesitas alternar la forma de los desplazamientos.