钻石广场算法 [英] Diamond square algorithm

问题描述

我试着写钻石广场算法在Java中生成一个随机的地图，可以 W图出实施...

I'm trying to write the Diamond-Square algorithm in Java to generate a random map but can't figure out the implementation...

任何人只要有一些Java code（或其他语言），所以我可以检查回路是如何制造将大大AP preciated！

Anyone with some Java code (or other language) so i can check how the loop is made would be greatly appreciated!

谢谢！

推荐答案

这是一个有趣的算法生成的值。下面是我根据解释创建的在从维基百科的文章引用此页面给予实现。这将创建球形值（包裹在所有的边缘）。目前都在为如何改变它生成的边缘，而不是包装新的价值（虽然平均边缘的意义并不在这些情况下完全正确）的评论说明。

This is an interesting algorithm for generating values. Here is an implementation that I have created based on the explanation give at this page in the references from the wikipedia article. It will create "spherical values" (wrapped at all the edges). There are notes in the comments for how to change it to generate new values on the edges instead of wrapping (though the meaning of average for the edges isn't really correct in these cases).

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

这篇关于钻石广场算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！