Rétro-D: Terrain fractal avec Diamond-Square

Télécharger le projet
Commenter

Description

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 ...
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (William VOIROL)