Я пытаюсь написать алгоритм Алмаз-Квадрат на Java для создания случайной карты, но не может понять реализацию..
Приветствуется любой человек с некоторым кодом Java (или другим языком), поэтому я могу проверить, как делается цикл.
Спасибо!
Алмазный квадрат
Ответ 1
Это интересный алгоритм генерации значений. Вот реализация, которую я создал на основе объяснения, дайте на эту страницу в ссылках из статьи wikipedia. Он создаст "сферические значения" (обернут на всех краях). В комментариях есть замечания о том, как изменить его, чтобы генерировать новые значения на ребрах вместо обертывания (хотя значение среднего для ребер в этих случаях не совсем корректно).
//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();
}
Ответ 2
М. Ответ 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
В противном случае он читается из неправильных местоположений (которые могут быть неинициализированы).
Ответ 3
Для любого, кто ищет, вот алгоритм, предоставленный М. Джессопом, завернутый в класс, который принимает семя (чтобы воспроизвести результаты), значение для 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);
}
}
}
}
Ответ 4
Проверьте это демо, сделанное с помощью 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
Наслаждайтесь!