Diamant-Square-Algorithmus

Question

Ich versuche, die Diamond-Square algorithm in Java zu schreiben, eine zufällige Karte zu generieren, aber die Umsetzung kann nicht herausfinden ...

Wer mit einigen Java-Code (oder einer anderen Sprache), so kann ich überprüfen wie die Schleife gemacht wird, würde sehr geschätzt werden!

Danke!

Answer 1

Dies ist ein interessanter Algorithmus zum Generieren von Werten. Hier ist eine Implementierung, die ich basierend auf der Erklärung unter this page in the references from the wikipedia article erstellt habe. Es erzeugt "sphärische Werte" (an allen Rändern gewickelt). In den Kommentaren finden Sie Hinweise, wie Sie diese ändern können, um an den Kanten neue Werte zu erzeugen, anstatt sie zu umbrechen (obwohl die Bedeutung des Durchschnitts für die Kanten in diesen Fällen nicht wirklich korrekt ist).

//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

prüfen diese Demo getan heraus mit Processing:

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

Auch hier ist eine andere Seite mit einer rauen algo geschrieben:

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

schließlich eine etwas formellere Papier:

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

Genießen Sie!

Answer 3

Die Antwort von M. Jessup scheint leicht abgegangen zu sein. Wo er hatte:

      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 

Es sollte stattdessen lauten:

      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 

Ansonsten liest sie aus den falschen Stellen (die uninitialised werden kann).

Answer 4

Für jeden, der hier ist, ist hier der von M. Jessup bereitgestellte Algorithmus in einer Klasse enthalten, die einen Seed (um die Ergebnisse zu reproduzieren) einnimmt, einen Wert für n, um Dimensionen anzugeben (Dimensionen sind 2^n + 1) und legt die Ergebnisse als eine normalisierte Anordnung von Schwimmern offen. Es hat auch das Update für den zweiten Teil des Algorithmus angewendet.

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); 
     } 
    } 

} 
}