diamante cuadrado algoritmo

Question

Estoy intentando escribir el Diamond-Square algorithm en Java para generar un mapa al azar, pero no puedo averiguar la ejecución ...

Cualquier persona con un poco de código Java (u otro idioma), así que puede comprobar cómo se hace el lazo sería muy apreciado!

Gracias!

Answer 1

Este es un algoritmo interesante para generar valores. Aquí hay una implementación que he creado según la explicación dada en this page in the references from the wikipedia article. Creará "valores esféricos" (envueltos en todos los bordes). Hay notas en los comentarios sobre cómo cambiarlo para generar nuevos valores en los bordes en lugar de envolver (aunque el significado del promedio para los bordes no es realmente correcto en estos casos).

//size of grid to generate, note this must be a 
//value 2^n+1 
final int DATA_SIZE = 9; 
//an initial seed value for the corners of the data 
final double SEED = 1000.0; 
double[][] data = new double[DATA_SIZE][DATA_SIZE]; 
//seed the data 
data[0][0] = data[0][DATA_SIZE-1] = data[DATA_SIZE-1][0] = 
    data[DATA_SIZE-1][DATA_SIZE-1] = SEED; 

double h = 500.0;//the range (-h -> +h) for the average offset 
Random r = new Random();//for the new value in range of h 
//side length is distance of a single square side 
//or distance of diagonal in diamond 
for(int sideLength = DATA_SIZE-1; 
    //side length must be >= 2 so we always have 
    //a new value (if its 1 we overwrite existing values 
    //on the last iteration) 
    sideLength >= 2; 
    //each iteration we are looking at smaller squares 
    //diamonds, and we decrease the variation of the offset 
    sideLength /=2, h/= 2.0){ 
    //half the length of the side of a square 
    //or distance from diamond center to one corner 
    //(just to make calcs below a little clearer) 
    int halfSide = sideLength/2; 

    //generate the new square values 
    for(int x=0;x<DATA_SIZE-1;x+=sideLength){ 
    for(int y=0;y<DATA_SIZE-1;y+=sideLength){ 
     //x, y is upper left corner of square 
     //calculate average of existing corners 
     double avg = data[x][y] + //top left 
     data[x+sideLength][y] +//top right 
     data[x][y+sideLength] + //lower left 
     data[x+sideLength][y+sideLength];//lower right 
     avg /= 4.0; 

     //center is average plus random offset 
     data[x+halfSide][y+halfSide] = 
    //We calculate random value in range of 2h 
    //and then subtract h so the end value is 
    //in the range (-h, +h) 
    avg + (r.nextDouble()*2*h) - h; 
    } 
    } 

    //generate the diamond values 
    //since the diamonds are staggered we only move x 
    //by half side 
    //NOTE: if the data shouldn't wrap then x < DATA_SIZE 
    //to generate the far edge values 
    for(int x=0;x<DATA_SIZE-1;x+=halfSide){ 
    //and y is x offset by half a side, but moved by 
    //the full side length 
    //NOTE: if the data shouldn't wrap then y < DATA_SIZE 
    //to generate the far edge values 
    for(int y=(x+halfSide)%sideLength;y<DATA_SIZE-1;y+=sideLength){ 
     //x, y is center of diamond 
     //note we must use mod and add DATA_SIZE for subtraction 
     //so that we can wrap around the array to find the corners 
     double avg = 
     data[(x-halfSide+DATA_SIZE)%DATA_SIZE][y] + //left of center 
     data[(x+halfSide)%DATA_SIZE][y] + //right of center 
     data[x][(y+halfSide)%DATA_SIZE] + //below center 
     data[x][(y-halfSide+DATA_SIZE)%DATA_SIZE]; //above center 
     avg /= 4.0; 

     //new value = average plus random offset 
     //We calculate random value in range of 2h 
     //and then subtract h so the end value is 
     //in the range (-h, +h) 
     avg = avg + (r.nextDouble()*2*h) - h; 
     //update value for center of diamond 
     data[x][y] = avg; 

     //wrap values on the edges, remove 
     //this and adjust loop condition above 
     //for non-wrapping values. 
     if(x == 0) data[DATA_SIZE-1][y] = avg; 
     if(y == 0) data[x][DATA_SIZE-1] = avg; 
    } 
    } 
} 

//print out the data 
for(double[] row : data){ 
    for(double d : row){ 
    System.out.printf("%8.3f ", d); 
    } 
    System.out.println(); 
} 

Answer 2

Salida esta demo hecho con Processing:

http://www.intelegance.net/code/diamondsquare.shtml

Además, aquí hay otra página con un algo áspera en escrito:

http://www.javaworld.com/javaworld/jw-08-1998/jw-08-step.html?page=2

Por último, un papel ligeramente más formal:

http://www.student.math.uwaterloo.ca/~pmat370/PROJECTS/2006/Keith_Stanger_Fractal_Landscapes.pdf

¡Disfrútalo!

Answer 3

La respuesta de M. Jessup parece estar ligeramente alterada. Donde tuvo:

      double avg = 
        data[(x-halfSide+DATA_SIZE)%DATA_SIZE][y] + //left of center 
        data[(x+halfSide)%DATA_SIZE][y] + //right of center 
        data[x][(y+halfSide)%DATA_SIZE] + //below center 
        data[x][(y-halfSide+DATA_SIZE)%DATA_SIZE]; //above center 

Debe vez leído:

      double avg = 
        data[(x-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)][y] + //left of center 
        data[(x+halfSide)%(DATA_SIZE-1)][y] + //right of center 
        data[x][(y+halfSide)%(DATA_SIZE-1)] + //below center 
        data[x][(y-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)]; //above center 

De lo contrario, se lee desde los lugares equivocados (que pueden no inicializado).

Answer 4

Para cualquiera que esté buscando, aquí está el algoritmo proporcionado por M. Jessup envuelto en una clase que toma una semilla (para permitir la reproducción de los resultados), un valor para n para especificar dimensiones (las dimensiones son 2^n + 1) y expone los resultados como una matriz normalizada de flotadores. También tiene la solución para la segunda parte del algoritmo aplicado.

import java.util.Random; 

public class DiamondSquare { 

public float[][] data; 
public int width; 
public int height; 

public DiamondSquare(long mseed, int n) { 
    //size of grid to generate, note this must be a 
    //value 2^n+1 
    int DATA_SIZE = (1 << n) + 1; 
    width = DATA_SIZE; 
    height = DATA_SIZE; 
    //an initial seed value for the corners of the data 
    final float SEED = 1000.0f; 
    data = new float[DATA_SIZE][DATA_SIZE]; 
    //seed the data 
    data[0][0] = data[0][DATA_SIZE-1] = data[DATA_SIZE-1][0] = 
      data[DATA_SIZE-1][DATA_SIZE-1] = SEED; 

    float valmin = Float.MAX_VALUE; 
    float valmax = Float.MIN_VALUE; 

    float h = 500.0f;//the range (-h -> +h) for the average offset 
    Random r = new Random(mseed);//for the new value in range of h 
    //side length is distance of a single square side 
    //or distance of diagonal in diamond 
    for(int sideLength = DATA_SIZE-1; 
      //side length must be >= 2 so we always have 
      //a new value (if its 1 we overwrite existing values 
      //on the last iteration) 
      sideLength >= 2; 
      //each iteration we are looking at smaller squares 
      //diamonds, and we decrease the variation of the offset 
      sideLength /=2, h/= 2.0){ 
     //half the length of the side of a square 
     //or distance from diamond center to one corner 
     //(just to make calcs below a little clearer) 
     int halfSide = sideLength/2; 

     //generate the new square values 
     for(int x=0;x<DATA_SIZE-1;x+=sideLength){ 
      for(int y=0;y<DATA_SIZE-1;y+=sideLength){ 
       //x, y is upper left corner of square 
       //calculate average of existing corners 
       float avg = data[x][y] + //top left 
         data[x+sideLength][y] +//top right 
         data[x][y+sideLength] + //lower left 
         data[x+sideLength][y+sideLength];//lower right 
       avg /= 4.0; 

       //center is average plus random offset 
       data[x+halfSide][y+halfSide] = 
         //We calculate random value in range of 2h 
         //and then subtract h so the end value is 
         //in the range (-h, +h) 
         avg + (r.nextFloat()*2*h) - h; 

       valmax = Math.max(valmax, data[x+halfSide][y+halfSide]); 
       valmin = Math.min(valmin, data[x+halfSide][y+halfSide]); 
      } 
     } 

     //generate the diamond values 
     //since the diamonds are staggered we only move x 
     //by half side 
     //NOTE: if the data shouldn't wrap then x < DATA_SIZE 
     //to generate the far edge values 
     for(int x=0;x<DATA_SIZE-1;x+=halfSide){ 
      //and y is x offset by half a side, but moved by 
      //the full side length 
      //NOTE: if the data shouldn't wrap then y < DATA_SIZE 
      //to generate the far edge values 
      for(int y=(x+halfSide)%sideLength;y<DATA_SIZE-1;y+=sideLength){ 
       //x, y is center of diamond 
       //note we must use mod and add DATA_SIZE for subtraction 
       //so that we can wrap around the array to find the corners 
       float avg = 
         data[(x-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)][y] + //left of center 
         data[(x+halfSide)%(DATA_SIZE-1)][y] + //right of center 
         data[x][(y+halfSide)%(DATA_SIZE-1)] + //below center 
         data[x][(y-halfSide+DATA_SIZE-1)%(DATA_SIZE-1)]; //above center 
       avg /= 4.0; 

       //new value = average plus random offset 
       //We calculate random value in range of 2h 
       //and then subtract h so the end value is 
       //in the range (-h, +h) 
       avg = avg + (r.nextFloat()*2*h) - h; 
       //update value for center of diamond 
       data[x][y] = avg; 

       valmax = Math.max(valmax, avg); 
       valmin = Math.min(valmin, avg); 


       //wrap values on the edges, remove 
       //this and adjust loop condition above 
       //for non-wrapping values. 
       if(x == 0) data[DATA_SIZE-1][y] = avg; 
       if(y == 0) data[x][DATA_SIZE-1] = avg; 
      } 
     } 
    } 


    for(int i=0; i<width; i++) { 
     for(int j=0; j<height; j++) { 
      data[i][j] = (data[i][j] - valmin)/(valmax - valmin); 
     } 
    } 

} 
}