Алмазный квадрат алгоритм

Question

Я пытаюсь написать Diamond-Square algorithm в Java, чтобы генерировать случайные карты, но не могу понять реализацию ...

Любой с некоторым 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

Ответ М. Джессапа кажется слегка искаженным. Где он был:

      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

Для всех, кто ищет, вот алгоритм, предоставленный М. Джессопом, обернутый в класс, который принимает семя (чтобы воспроизвести результаты), значение для 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); 
     } 
    } 

} 
}