L'algorithme du carré de diamant est un algorithme de génération de terrain fractal (carte de hauteur). Vous pouvez trouver une belle description de son fonctionnement ici:
http://www.gameprogrammer.com/fractal.html (utilisé comme référence.)
http://www.playfuljs.com/realistic-terrain-in-130-lines/ (Excellente implémentation JS, vous voudrez peut-être voler son moteur de rendu. Jetez un œil ici ce que cet algorithme est capable de http: // démos. playfuljs.com/terrain/ .)
L'idée générale est que vous avez 4 coins comme graines (a), et calculez la hauteur du point central en faisant la moyenne de ces quatre coins et en ajoutant une valeur aléatoire, par exemple entre -0,5 et 0,5 (b). Si vous appliquez cela à la grille, vous obtenez à nouveau une grille de diamants (carrés tournant 45 °) et vous répétez la même chose (c, d), mais la plage aléatoire devient plus petite, par exemple -0,125 à 0,125, etc.
Votre programme doit accepter un certain nombre d'entrées:
- Un entier
l=1,2,3,...
qui détermine la taille de la grille carrée avec la longueur du côté2^l+1
. Àl=10
vous devrez stocker environ un million de numéros. - Quatre graines (virgule flottante) pour chaque coin
- Un paramètre
0<h<1
qui détermine la rugosité (H
dans le lien) qui signifie la taille initiale de la plage aléatoire - Paramètres
a,b
qui représentent les limites inférieures et supérieures initiales de la plage aléatoire et sont multipliés parh
à chaque étape de raffinement. (Le nombre aléatoire est uniformément choisi entrea
etb
.
La sortie doit être constituée de la grille 2D finie.
Donc, l'algorithme approximatif ressemblerait à ceci:
Create a square grid with sidelength 2^l+1
Place seed values in the corners
Repeat:
| Perform square steps
| Refine Range: a = a*h; b=b*h;
| Perform diamond steps
| Refine Range
Il y a un détail dont vous devez être conscient: à la limite de la grille, vous n'aurez que trois sommets du diamant , vous devez donc également calculer uniquement la moyenne de ces trois points.
Une visualisation de quelques exemples (veuillez nous dire quels paramètres vous avez utilisés) est facultative mais appréciée, et n'ajoute bien sûr pas au nombre d'octets.
Une implémentation légèrement variée de cet algorithme peut être trouvée ici: Générateur de terrain de voxels projetés parallèlement
J'ai créé une petite fonction de dessin en javascript pour afficher les cartes de hauteur en 2D comme image en niveaux de gris. http://jsfiddle.net/flawr/oy9kxpsx/
Si quelqu'un d'entre vous aime la 3D fantaisie et peut créer un script pour visualiser des cartes en 3D, faites le moi savoir! =)