Algorithme carré de diamant
J'essaie d'écrire l'algorithme Diamond-Square en Java pour générer une carte aléatoire mais je n'arrive pas à comprendre l'implémentation...
Toute personne ayant du code Java (ou un autre langage) afin que je puisse vérifier comment la boucle est faite serait grandement appréciée!
Merci!
4 réponses
C'est un algorithme intéressant pour générer des valeurs. Voici une implémentation que j'ai créée sur la base de l'explication donnée à cette page dans les références de l'article wikipedia . Il va créer des "valeurs sphériques" (enveloppées à tous les bords). Il y a des notes dans les commentaires sur la façon de le changer pour générer de nouvelles valeurs sur les bords au lieu d'envelopper (bien que la signification de moyenne pour les bords ne soit pas vraiment correcte dans ces cas).
//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();
}
La réponse de M. Jessup semble être légèrement sur écoute. Où il avait:
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
Il devrait plutôt se lire:
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
Sinon, il lit à partir des mauvais emplacements (qui peuvent être non initialisés).
Pour ceux qui cherchent, voici l'algorithme fourni par M. Jessup enveloppé dans une classe qui prend une graine (pour permettre de reproduire les résultats), une valeur pour n pour spécifier les dimensions (les dimensions sont 2^N + 1), et expose les résultats comme un tableau normalisé de flotteurs. Il a également le correctif pour la deuxième partie de l'algorithme appliqué.
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);
}
}
}
}
Découvrez la démo fait avec Traitement:
Http://www.intelegance.net/code/diamondsquare.shtml
Aussi, Voici une autre page avec un algo rugueux écrit:
Http://www.javaworld.com/javaworld/jw-08-1998/jw-08-step.html?page=2
Enfin, un papier un peu plus formel:
Http://www.student.math.uwaterloo.ca/~pmat370/PROJECTS/2006/Keith_Stanger_Fractal_Landscapes.pdf
Profitez!