Java 菱形平方算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2755750/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Diamond square algorithm
提问by Gabriel A. Zorrilla
I'm trying to write the Diamond-Square algorithmin Java to generate a random map but can't figure out the implementation...
我正在尝试用 Java编写Diamond-Square 算法来生成随机地图，但无法弄清楚实现...
Anyone with some Java code (or other language) so i can check how the loop is made would be greatly appreciated!
任何有一些 Java 代码（或其他语言）的人，我都可以检查循环是如何制作的，将不胜感激！
Thanks!
谢谢！
采纳答案by M. Jessup
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();
}
回答by Xavier Ho
Check out this demo done with Processing:
看看这个用Processing完成的演示：
http://www.intelegance.net/code/diamondsquare.shtml
http://www.intelegance.net/code/diamondsquare.shtml
Also, here's another page with a rough algo written out:
此外，这是另一个写出粗略算法的页面：
http://www.javaworld.com/javaworld/jw-08-1998/jw-08-step.html?page=2
http://www.javaworld.com/javaworld/jw-08-1998/jw-08-step.html?page=2
Finally, a slightly more formal paper:
最后，稍微正式一点的论文：
http://www.student.math.uwaterloo.ca/~pmat370/PROJECTS/2006/Keith_Stanger_Fractal_Landscapes.pdf
http://www.student.math.uwaterloo.ca/~pmat370/PROJECTS/2006/Keith_Stanger_Fractal_Landscapes.pdf
Enjoy!
享受！
回答by Chris Handley
M. Jessup's answer seems to be slightly bugged. Where he had:
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
It should instead read:
它应该改为：
? ? ? 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
Otherwise it reads from the wrong locations (which can be uninitialised).
否则，它会从错误的位置读取（可能未初始化）。
回答by Bergasms
For anyone looking, here is the algorithm provided by M. Jessup wrapped in a class that takes in a seed (to allow reproducing the results), a value for n to specify dimensions (dimensions are 2^n + 1), and exposes the results as a normalised array of floats. It also has the fix for the second part of the algorithm applied.
对于任何人来说，这里是 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);
}
}
}
}
