钻石广场算法

Question

我试图用Java编写的Diamond-Square algorithm生成一个随机地图，但不能找出执行...

任何人只要有一些Java代码（或其他语言），所以我可以检查如何制作循环将不胜感激！

谢谢！

Answer 1

这是一个有趣的生成值的算法。下面是我根据this page in the references from the wikipedia article给出的解释创建的实现。它会创建“球形值”（包裹在所有边缘）。注释中有注释，说明如何将其更改为在边缘生成新值而不是缠绕（尽管在这些情况下边缘平均值的含义并不真正）。

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

看看这个演示与Processing完成：

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

而且，这里有一个粗略的算法中另一个页面写出：

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

最后，稍微正式的文件：

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

享受！

Answer 3

M. Jessup的答案似乎略有误差。他在那里：

      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 

它应改为阅读：

      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 

否则，从错误的地点（可未初始化）读取。

Answer 4

对于任何人来说，这里是由M. Jessup提供的算法，包含在一个接受种子的类中（以允许重现结果），一个用于指定维数的n值（维度为2^n + 1） ，并将结果作为标准化的浮点数组公开。它也适用于算法的第二部分应用。

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

} 
}