Bonjour,
Voici des codes strictement personnels de l'algorithme diamant-carré (en: diamond-square algorithm) qui est souvent utilisé pour la réalisation de terrains fractals.
Le nombre d'instructions utilisées est très réduit, comparativement à ce qu'on trouve habituellement.
Les boucles intérieures y sont particulièrement soignées (et optimisées).
C'est uniquement la partie génération du tableau des hauteurs (heightmap) qui est traitée ici.
La représentation graphique est rudimentaire et sert simplement à visualiser les résultats.
Nous utiliserons le dessin au trait de la scène 3D "Rétro":
CodeS-SourceS: Rétro-C. Surfaces h = f(x,y) au trait.
Le graphisme sera amélioré dans un de mes prochains articles de la série "Rétro".
Hunter Loftis: Realistic terrain in 130 lines
Pour "situer" le présent article, je prends comme référence le code de Hunter Loftis
Realistic terrain in 130 lines, qui semble avoir le vent en poupe.
Hunter Loftis: Realistic terrain in 130 lines,
code source HTML/Javascript.
Ce code source de Hunter Loftis définit le tableau des hauteurs avec l'instruction:
this.map = new Float32Array(this.size * this.size);
Dans le but d'estimer l'efficacité de la
création du heightmap, j'y ai (provisoirement) remplacé la ligne
terrain.generate(0.7);
par les 3 lignes
var t0=new Date().getTime();
for (i=0; i<100; ++i) terrain.generate(0.7);
alert('100 times [513*513]: '+((new Date().getTime())-t0)+' ms');,
Ainsi, on mesure le temps de 100 executions.
Diamond-Square-A
La fonction
DiamondSquare(K,H) est le cœur de la génération du tableau des hauteurs.
On divise le temps d'exécution quasiment par deux en utilisant
H = new Float32Array(...); pour définir le tableau des hauteurs (au lieu de H = [];).
function DiamondSquareA(K,H) {
var N=1<<K,N1=N+1; // dimensions: H.length >= N1*N1
H[0]=Math.random()-0.5; H[N]=Math.random()-0.5; // 4 corners
H[N*N1]=Math.random()-0.5; H[N1*N1-1]=Math.random()-0.5;
var A,D,d,dd,d0,d1,d2,d3;
for (D=N,A=1; D>1; D=d,A*=0.70710678) {
d=D/2; dd=d*N1; d0=-d-dd; d1=d-dd; d2=-d+dd; d3=d+dd;
for (var y=d; y<N; y+=D)
for (var x=d; x<N; x+=D) Square(x,y);
A*=0.70710678;
for (var y=0; y<=N; y+=D)
for (var x=d; x<N; x+=D) DiamondDef(x,y);
for (var y=d; y<=N; y+=D)
for (var x=0; x<=N; x+=D) DiamondCal(x,y);
}
function Square(x,y) {
var a=x+N1*y;
H[a]=A*(Math.random()-0.5)+(H[a+d0]+H[a+d1]+H[a+d2]+H[a+d3])/4;
}
function DiamondDef(x,y) { // first elem of line is defined
var a=x+N1*y,r=A*(Math.random()-0.5);
if (y==0) H[a]=r+(H[a-d]+H[a+d]+H[a+dd])/3;
else if (y==N) H[a]=r+(H[a-dd]+H[a-d]+H[a+d])/3;
else H[a]=r+(H[a-dd]+H[a-d]+H[a+d]+H[a+dd])/4;
}
function DiamondCal(x,y) { // first elem of line must be calculated
var a=x+N1*y,r=A*(Math.random()-0.5);
if (x==0) H[a]=r+(H[a-dd]+H[a+d]+H[a+dd])/3;
else if (x==N) H[a]=r+(H[a-dd]+H[a-d]+H[a+dd])/3;
else H[a]=r+(H[a-dd]+H[a-d]+H[a+d]+H[a+dd])/4;
}
} // Feb 2016, William VOIROL, Switzerland
J'espérais obtenir une amélioration d'une dizaine de % par rapport au temps d'exécution de
Realistic terrain.
A ma grande surprise, ce temps est divisé par 6 !
Essayons de faire encore d'autres améliorations.
Diamond-Square-B
La fonction
Square(x,y) me plait pas mal, à part le calcul explicite de l'adresse a.
Par contre, les fonctions
DiamondDef(x,y) et
DiamondCal(x,y) font des tests que l'on doit pouvoir supprimer !
Pour cela, il faut traiter séparément la première et la dernière ligne pour
DiamondDef(x,y), et le premier et le dernier élément des lignes pour
DiamondCal(x,y).
Ceci nous amène à quasiment réécrire le code de la fonction:
function DiamondSquareB(K,H) {
var N=1<<K,N1=N+1,Y=N*N1; // dimensions: H.length >= N1*N1
H[0]=Math.random()-0.5; H[N]=Math.random()-0.5; // 4 corners
H[Y]=Math.random()-0.5; H[N1*N1-1]=Math.random()-0.5;
for (var D=N,A=1; D>1; D=d,A*=0.70710678) {
var x,X,y,d=D/2,Dy=N1*D,dy=Dy/2,dd=D+Dy,dp=dd/2,dm=(Dy-D)/2;
for (y=0; y<Y; y+=Dy) // ######## Square: ########
for (x=y,X=y+N; x<X; x+=D)
H[x+dp]=A*(Math.random()-0.5)+(H[x]+H[x+D]+H[x+Dy]+H[x+dd])/4;
A*=0.70710678; // ######## Diamond: odd lines ########
for (x=0; x<N; x+=D) // first line
H[x+d]=A*(Math.random()-0.5)+(H[x]+H[x+D]+H[x+dp])/3;
for (y=Dy; y<Y; y+=Dy) // internal lines
for (x=y,X=y+N; x<X; x+=D)
H[x+d]=A*(Math.random()-0.5)+(H[x-dm]+H[x]+H[x+D]+H[x+dp])/4;
for (x=Y; x<Y+N; x+=D) // last line
H[x+d]=A*(Math.random()-0.5)+(H[x-dm]+H[x]+H[x+D])/3;
for (y=dy; y<Y; y+=Dy) { // ######## Diamond: even lines ########
H[y]=A*(Math.random()-0.5)+(H[y-dy]+H[y+d]+H[y+dy])/3; // first elem
for (x=y+D,X=y+N; x<X; x+=D) // internal elems
H[x]=A*(Math.random()-0.5)+(H[x-dy]+H[x-d]+H[x+d]+H[x+dy])/4;
H[X]=A*(Math.random()-0.5)+(H[X-dy]+H[X-d]+H[X+dy])/3; // last elem
}
}
} // Feb 2016, William VOIROL, Switzerland
L'amélioration du temps d'exécution est de quelques %.
Diamond-Square-R
Javascript ne semble par être pourvu d'une fonction
seed() qui permet d'obtenir des séquences identiques de nombres aléatoires.
Pour y remédier, nous allons calculer à l'avance quelques milliers (ici 4177 qui est premier) de nombres aléatoires pour y accéder "circulairement" à laide de l'index n%4177:
for (var i=0; i<4177; ++i) this.R[i]=Math.random()-0.5; // dans TerrainFractalR.SetRand()
Adaptons la fonction
DiamondSquare:
function DiamondSquareR(K,H,R) {
var N=1<<K,N1=N+1,Y=N*N1; // H.length >= N1*N1, R.length = 4177
H[0]=R[0]; H[N]=R[N%4177]; // 4 corners
H[N*N1]=R[(N*N1)%4177]; H[N1*N1-1]=R[(N1*N1-1)%4177];
for (var D=N,A=2; D>1; D=d,A*=0.70710678) {
var x,X,y,d=D/2,Dy=N1*D,dy=Dy/2,dd=D+Dy,dp=dd/2,dm=(Dy-D)/2;
for (y=0; y<Y; y+=Dy) // ######## Square: ########
for (x=y,X=y+N; x<X; x+=D)
H[x+dp]=A*R[(x+dp)%4177]+(H[x]+H[x+D]+H[x+Dy]+H[x+dd])/4;
A*=0.70710678; // ######## Diamond: odd lines ########
for (x=0; x<N; x+=D) // first line
H[x+d]=A*R[(x+d)%4177]+(H[x]+H[x+D]+H[x+dp])/3;
for (y=Dy; y<Y; y+=Dy) // internal lines
for (x=y,X=y+N; x<X; x+=D)
H[x+d]=A*R[(x+d)%4177]+(H[x-dm]+H[x]+H[x+D]+H[x+dp])/4;
for (x=Y; x<Y+N; x+=D) // last line
H[x+d]=A*R[(x+d)%4177]+(H[x-dm]+H[x]+H[x+D])/3;
for (y=dy; y<Y; y+=Dy) { // ######## Diamond: even lines ########
H[y]=A*R[y%4177]+(H[y-dy]+H[y+d]+H[y+dy])/3; // first elem
for (x=y+D,X=y+N; x<X; x+=D) // internal elems
H[x]=A*R[x%4177]+(H[x-dy]+H[x-d]+H[x+d]+H[x+dy])/4;
H[X]=A*R[X%4177]+(H[X-dy]+H[X-d]+H[X+dy])/3; // last elem
}
}
} // Feb 2016, William VOIROL, Switzerland
Le temps d'exécution s'améliore encore bien.
De plus, cette méthode nous permettra d'utiliser d'autres lois de probabilité sans ralentissement.
Comme le présent article a pris des dimensions nettement plus grandes de ce que j'avais initialement prévu, cela sera fait dans un autre exposé.
J'y traiterai également la notion de
rugosité de la surface.
Temps d'exécution mesurés
Voici quelques mesures de temps d'exécution pour générer
100 HeightMaps 513×513:
RealisticTerrain: 2214 ms
Diamond-Square-A: 715 ms (sans utilisation de Float32Array)
Diamond-Square-A: 356 ms
Diamond-Square-B: 339 ms
Diamond-Square-R: 232 ms (astuce random)
Quelques autres liens:
Wikipédia: Algorithme Diamant-Carré
Wikipedia: Diamond-square algorithm (plus complet)
Geeklabs: Algorithme Diamants-Carrés : Génération de heightmaps
Le Martelot: Synthèse Aléatoire de Terrains 3D
CodeS-SourceS: Créateur de surfaces de terrains
Merci d'avance pour vos éventuelles suggestions, critiques ou corrections.
Bonne lecture ...
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.