Für eine Karte brauche ich zu jedem Punkt eine Höhe. Die einfachste Idee: pro Pixel eine Zufallszahl. Das Ergebnis ist Fernsehrauschen. Jedes Pixel ist unabhängig vom Nachbarn, also gibt es weder Berge noch Täler, nur Körner. Was man will, sind Zahlen, die sich von Punkt zu Punkt langsam ändern und trotzdem zufällig aussehen.
Links ist Value Noise, rechts Gradient Noise, beide aus denselben Reglern und mit demselben Farbverlauf von Wasser über Wiese bis Schnee. Die Regler setzen Oktaven, Lacunarity, Persistence, Grundfrequenz und Seed, ein Zug an einer Karte verschiebt den Ausschnitt. Darunter liegen die einzelnen Oktaven des Gradient Noise als graue Kacheln. Die Demo startet absichtlich mit linearer Überblendung, damit du das Gitter sofort siehst. Chip 3 schaltet auf die richtige Kurve, dann verschwindet es.
Zufall auf einem Gitter
Value Noise ist die Version, die man sich zuerst ausdenkt. Jeder Gitterpunkt bekommt eine Zufallszahl, dazwischen wird überblendet. Die Zahl kommt aus einem Hash der Gitterkoordinaten und des Seeds, so ist sie überall reproduzierbar und braucht keinen Speicher:
inline double latticeValue(int x, int y, int seed) { return static_cast<double>(latticeHash(x, y, seed) >> 8) / 16777216.0; }
Die oberen 24 Bit des Hashs, geteilt durch 2^24, ergeben eine Zahl in [0, 1). Für einen Punkt in der Zelle nimmt man die vier Eckwerte und mischt sie, erst in x, dann in y:
const Cell c = cellOf(x, y); const double u = applyFade(fade, c.fx); const double v = applyFade(fade, c.fy); const double top = lerp(latticeValue(c.ix, c.iy, seed), latticeValue(c.ix + 1, c.iy, seed), u); const double bottom = lerp(latticeValue(c.ix, c.iy + 1, seed), latticeValue(c.ix + 1, c.iy + 1, seed), u); return lerp(top, bottom, v);
fx und fy sind der Nachkommaanteil innerhalb der Zelle. Das applyFade dazwischen ist der Teil, an dem der Unterschied hängt.
Die Überblendkurve
Mit Chip 1 ist u einfach fx. Dann ändert sich die Steigung an jeder Zellgrenze schlagartig, und das Auge sieht das als Knick. Links in der Demo entstehen Pyramiden und Rauten, rechts bleiben leichte Falten entlang des Gitters. Chip 2 und 3 biegen die Kurve so, dass sie flach in die Zellgrenze hineinläuft:
case Fade::Linear: return t; case Fade::Cubic: return t * t * (3.0 - 2.0 * t); case Fade::Quintic: return t * t * t * (t * (t * 6.0 - 15.0) + 10.0);
Beide haben an den Enden die Steigung 0. Die kubische hat dort noch eine Krümmung (Betrag 6), die quintische (6t^5 - 15t^4 + 10t^3) nicht mehr. Das reicht, damit Zellgrenzen nicht mehr auffallen. Im Test steht das als Vergleich bei t = 0,01: die quintische Kurve liegt da bei etwa einem Dreißigstel der kubischen.
Gradient Noise
Dumm nur: auch mit der guten Kurve bleibt bei Value Noise ein Problem. Die Höhen und Tiefen liegen immer genau auf den Gitterpunkten, denn dort stehen die Zufallswerte, dazwischen wird nur gemittelt. Das Gitter schimmert durch, nur eben weicher.
Gradient Noise speichert an jedem Gitterpunkt einen zufälligen Einheitsvektor, die Höhe ergibt sich erst beim Auswerten. Jede Ecke trägt das Skalarprodukt ihrer Richtung mit dem Vektor von der Ecke zum Punkt bei, und die vier Beiträge werden wie oben überblendet:
const double n00 = g00.x * fx + g00.y * fy; const double n10 = g10.x * (fx - 1.0) + g10.y * fy; const double n01 = g01.x * fx + g01.y * (fy - 1.0); const double n11 = g11.x * (fx - 1.0) + g11.y * (fy - 1.0);
Auf einem Gitterpunkt ist der Abstandsvektor der eigenen Ecke null, die anderen Beiträge haben Gewicht null, also kommt dort genau 0 heraus (im Test für jeden Gitterpunkt geprüft). Die Ausschläge liegen dazwischen, und die Richtungen drehen sich frei, deshalb gibt es kein Raster mehr. Mit Einheitsvektoren bleibt der Rohwert bei höchstens √2/2 (rund 0,71), ich skaliere mit √2 auf [-1, 1] und bilde für die Karte auf [0, 1] ab.
Eine Eigenheit zeigt der Wertebereich über den Karten: bei Seed 7 und fünf Oktaven reicht das Value Noise von 0,20 bis 0,91, das Gradient Noise nur von 0,23 bis 0,73. Mit demselben Farbverlauf bekommt die rechte Karte kaum Schnee, die Werte liegen näher an der Mitte. Wer mehr Berge will, streckt den Bereich vor dem Einfärben.
Oktaven
Eine einzelne Ebene sieht aus wie Wolken. Gelände entsteht erst aus der Summe: dieselbe Funktion noch einmal mit höherer Frequenz und kleinerer Amplitude, und noch einmal. Das ist fbm (fractal Brownian motion):
for (int i = 0; i < clampOctaves(p.octaves); ++i) {
sum += amplitude * noise(x * frequency, y * frequency, i);
frequency *= p.lacunarity;
amplitude *= persistence;
}
return p.normalize ? sum / amplitudeSum(p.octaves, p.persistence) : sum;
Lacunarity ist der Faktor, um den die Frequenz je Oktave wächst (2 heißt: doppelt so fein), Persistence der Faktor für die Amplitude (0,5: halb so hoch). Die Kacheln unter den Karten zeigen jede Oktave mit ihrer Frequenz f und Amplitude a. Erst die dritte oder vierte Kachel bringt das Zerklüftete, und ihre Amplitude ist so klein, dass sie die Gestalt der Landmasse kaum verändert. Wie viel das ausmacht, siehst du am besten, wenn du Persistence hochschiebst.
Stolperfallen
Normalisieren: Fünf Oktaven mit Persistence 0,5 summieren sich auf bis zu 1,94. Teile ich nicht durch diese Summe, verlässt die Höhe den Bereich [0, 1]. Die Demo malt alles darüber orange, mit Chip N siehst du es. Bei vier Oktaven und Frequenz 11 reicht die Summe bis 1,70 (Value Noise) und 1,48 (Gradient Noise), und große Flächen sind orange.
Eigener Seed je Oktave: Würden alle Oktaven denselben Seed benutzen, bekäme derselbe Gitterindex in jeder Oktave denselben Wert, und jede Oktave wäre eine gestauchte Kopie der ersten. Deshalb verschiebt octaveSeed den Seed pro Oktave um 1013.
Negative Koordinaten: static_cast<int>(-0.5) ergibt 0, also die Zelle rechts vom Nullpunkt, und der Nachkommaanteil x - 0 wäre -0,5. Die Überblendung liefe dann über die Zelle hinaus. Darum geht es über std::floor. Weil der Cast danach nur Werte bis ±10^9 sieht, klemmt sane() die Koordinate vorher und macht aus NaN eine 0.
Zu hohe Oktaven: Eine Oktave, die feiner ist als die Auflösung, trägt nichts bei außer Flimmern. Bei Frequenz 11 sind die letzten Kacheln schon fast einfarbig grau, weil jede Kachel mehrere Proben mittelt. Acht Oktaven sind in der Demo die Obergrenze.
Red Blob Games erklärt Rauschen und Gelände ausführlich, in Making maps with noise und in der Einführung ins Rauschen. Flafla2 geht Perlin Noise Schritt für Schritt durch.
Den Code findest du im Repo unter terrain-fbm. Alle Demos der Serie sammelt das Projekt Game Dev Snippets.