Zufall & RauschenRND-02
Perlin Noise
Aus rohem Zufall wird weiches Rauschen, aus dem sich Landschaften, Wolken und Texturen bauen lassen.
- Laufzeit
- O(n · o)
- Zusatzspeicher
- O(n)
- Wertebereich
- 0 … 1
- Steuerung
- Oktaven, Persistenz
01Worum es geht
Reiner Zufall sieht aus wie Fernsehrauschen: Jeder Punkt ist von seinen Nachbarn völlig unabhängig. Die Natur sieht anders aus. Berge, Wolken und Wellen sind zufällig, aber benachbarte Stellen ähneln sich.
Genau das erzeugt Perlin Noise. Es glättet Zufallswerte und legt dann mehrere Detailstufen übereinander, bis grobe Formen und feine Struktur zusammenkommen. Ken Perlin entwickelte das Verfahren 1983 für den Film Tron und bekam dafür einen Oscar für technische Verdienste.
02So funktioniert es
Die Grundlage ist ein Feld aus Zufallswerten. Darüber legt der Algorithmus mehrere Oktaven.
Eine Oktave tastet das Zufallsfeld in einem festen Raster ab, zum Beispiel nur alle 32 Punkte. Alles dazwischen wird zwischen den vier umliegenden Rasterpunkten interpoliert. Das Ergebnis ist ein weicher Verlauf statt harter Sprünge.
Mehrere Oktaven verwenden dasselbe Zufallsfeld mit immer feinerem Raster: erst das ganze Bild, dann die Hälfte, dann ein Viertel. Jede weitere Oktave bringt feinere Details, wird aber über die Persistenz schwächer gewichtet.
Am Ende werden alle Oktaven addiert und durch die Summe ihrer Gewichte geteilt, damit das Ergebnis wieder zwischen 0 und 1 liegt. Wenige Oktaven ergeben sanfte Hügel, viele Oktaven zerklüftete Felsen.
03Ausprobieren
04Implementierung
public static class PerlinNoise
{
// Legt dieselben Zufallswerte in mehreren Zoomstufen ("Oktaven") übereinander.
// seed enthält width * height Zufallswerte in [0, 1); das Ergebnis ist genauso groß.
// Funktioniert am besten mit quadratischen Größen, die Zweierpotenzen sind.
public static float[] Generate(float[] seed, int width, int height, int octaves, float persistence)
{
var noise = new float[width * height];
for (var y = 0; y < height; y++)
{
for (var x = 0; x < width; x++)
{
var value = 0f;
var amplitude = 1f;
var amplitudeSum = 0f;
for (var octave = 0; octave < octaves; octave++)
{
// Jede Oktave tastet die Zufallswerte feiner ab: ganzes Bild, Hälfte, Viertel, ...
var step = Math.Max(width >> octave, 1);
value += Sample(seed, width, height, x, y, step) * amplitude;
amplitudeSum += amplitude;
// Spätere Oktaven ergänzen feinere Details mit immer weniger Gewicht.
amplitude *= persistence;
}
// Das Teilen durch die Summe aller Amplituden hält das Ergebnis in [0, 1).
noise[y * width + x] = value / amplitudeSum;
}
}
return noise;
}
// Nimmt die vier Rasterecken um (x, y) herum und blendet zwischen ihnen über.
private static float Sample(float[] seed, int width, int height, int x, int y, int step)
{
// Auf das Raster dieser Oktave abrunden; das Modulo lässt das Rauschen nahtlos umlaufen.
var left = x / step * step;
var top = y / step * step;
var right = (left + step) % width;
var bottom = (top + step) % height;
// Wie weit der Punkt zwischen den Ecken liegt, als Wert von 0 bis 1.
var blendX = (float)(x - left) / step;
var blendY = (float)(y - top) / step;
var topValue = Lerp(seed[top * width + left], seed[top * width + right], blendX);
var bottomValue = Lerp(seed[bottom * width + left], seed[bottom * width + right], blendX);
return Lerp(topValue, bottomValue, blendY);
}
// Lineare Interpolation: liefert a bei t = 0, b bei t = 1 und die Werte dazwischen.
private static float Lerp(float a, float b, float t) => a + (b - a) * t;
}
05Beispiel: Rauschen als Bild
const int size = 32;
// Perlin Noise erfindet den Zufall nicht, es glättet nur vorhandene Zufallswerte.
var random = new Pcg(seed: 2024);
var seed = new float[size * size];
for (var i = 0; i < seed.Length; i++)
seed[i] = (float)random.NextDouble();
var noise = PerlinNoise.Generate(seed, size, size, octaves: 5, persistence: 0.6f);
// Das Mitteln der Oktaven zieht alle Werte zur Mitte, deshalb wird der Bereich
// wieder auf 0 .. 1 gestreckt, damit die Struktur deutlich sichtbar wird.
var darkest = noise.Min();
var range = noise.Max() - darkest;
// Das Ergebnis als ASCII-Art zeichnen: dunkle Werte werden Leerzeichen, helle werden @.
const string ramp = " .:-=+*#%@";
for (var y = 0; y < size; y++)
{
for (var x = 0; x < size; x++)
{
var brightness = (noise[y * size + x] - darkest) / range;
var index = Math.Clamp((int)(brightness * ramp.Length), 0, ramp.Length - 1);
// Jedes Pixel wird zweimal ausgegeben, weil Zeichen höher als breit sind.
Console.Write(new string(ramp[index], 2));
}
Console.WriteLine();
}
********++++========------::::.. ..::----::--------==++++++**
++********++++++++====----::::........::------------====++++**++
++++******++++++**++==----::::::::::::::----==------====++****++
**++++++****++****++====--------------------------====++++******
****++++**********++==============--------------====++++++++****
++++++++++********++++======--------------------======++++++++++
++++**++++++****++****++====--::::::----::------================
++++++++************++++====--::..::--::::::----================
++++++******######**++++++==--::..::::::::::----========--======
======++++******##****++++==----::----------============--======
==========++********##**++====------========++======----------==
==========++****####******++++==--==++++++++++++====----------==
========--==****####**####****++==++++******++++++==----------==
----------==++**##**************++++++++**++====------------::--
..::::----==++**************######**++++++++==--::----------::::
....::----====++**********####%%%%##****++==----::::------::::..
..::::----==++********####%%@@@@%%##**++==--::..::------::....
....::----====++**********####%%@@%%##**++==----::----------::::
::::::--======++************####%%##****++==----==------------::
::::::--======++**++++++++******##****++============----------::
--------====++++++++++++++++++++****++==--======++==------------
========================++++++++++++====----====++==------------
========--==================++++++======------==++==============
++++====----==----------========----------================++++++
**++==----------::::::----------::::::----==============++++++**
**++++==--------::::----------::::::::--========--========++++++
++++++++====----::----------::::::::::--========--==++====++++++
++++++++====----::--------::::::..::::--======----========++++++
++++====++==----::------::::::::..::::--====--------====++++++++
++++++++++====------------::::....::----==----------====++++++++
********++++====----------::::....::----==--------====++++++==++
********++++======--------::::.. ..::------::------====++++++++
06Beispiel: eine Insel als Höhenkarte
const int size = 64;
// Jeder Bereich von Höhenwerten bekommt seine eigene Bedeutung. Das ist der ganze
// Trick einer Höhenkarte: Aus einer Zahl pro Punkt wird eine Landschaft.
static char Terrain(float height) => height switch
{
< 0.20f => '~', // tiefes Wasser
< 0.34f => '-', // flaches Wasser
< 0.40f => '.', // Strand
< 0.54f => ',', // Wiese
< 0.66f => '#', // Wald
< 0.70f => '^', // Fels
_ => '*', // Schnee
};
var random = new Pcg(seed: 7);
var seed = new float[size * size];
for (var i = 0; i < seed.Length; i++)
seed[i] = (float)random.NextDouble();
var noise = PerlinNoise.Generate(seed, size, size, octaves: 6, persistence: 0.5f);
// Die Oktaven ziehen alles zur Mitte, deshalb wird der Bereich wieder gestreckt.
var lowest = noise.Min();
var range = noise.Max() - lowest;
// Zeichen sind etwa doppelt so hoch wie breit, deshalb genügt jede zweite Zeile
// für eine Karte, die nicht in die Länge gezogen wirkt.
for (var y = 0; y < size; y += 2)
{
for (var x = 0; x < size; x++)
{
var height = (noise[y * size + x] - lowest) / range;
// Eine Insel statt einer endlosen Landschaft: Je weiter ein Punkt von der
// Mitte entfernt ist, desto mehr Höhe wird abgezogen, der Rand versinkt im Meer.
var offsetX = (x - size / 2f) / (size / 2f);
var offsetY = (y - size / 2f) / (size / 2f);
height -= 0.5f * (offsetX * offsetX + offsetY * offsetY);
Console.Write(Terrain(height));
}
Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine("~ water - shallow . beach , grass # forest ^ rock * snow");
~~~~~~~~~~~~~~~----~~~~~~~~~~~~~~~~~~~~~~~~~~---.---~~~~~~~~~~~~
~~~~~~~~~~~~~~~---~~~~~~~~~~~~~~~~~~~~~~~~~~----.----~~~~~~~~~~~
~~~~~~~~---------------~~~~~~~~~~~~~~~~~~~~---------~~--~~~~~~~~
~~~~~~~~~--------------------~~~~~~~~~~~~~~-----...-----~~~~~~~~
~~~~~~~-----~---------..,.-----~~~~~~~~~~~----..,,...---~~~~~~~~
~~~~~~~~~~~~-~~~--------..------~~~~~~-----...,,,,,..---~~~~~~~~
~~~~~~~~~~~~~~~~~~--------------~~--~---...,,,,,.,,,.---~----~~~
~~~~~~~~~~~~-~~~~~~-----------~~~~----.,,,,,,,,,,,,,..-------~~~
~~~~~~~~~~~~~~~~~~~~-----------~~----.,,,,,,,,,,,,,......---~~~~
~~~~~~~~~~---~~~~~~------------------.,,,,,,,,,,,,,,......---~~~
~~~~~~~-------------------------------.,,,,,,,,,,,,,....,.------
~~~~~~--------------------------~~---..,,,,,,,,##,,,...------~~~
~~~~~~~----...----------~~~---~~~~---.,,,,,,######,,----~~~~~~~~
~~~~~---..,,,,.,,......--------~~-----..,,,,,,,,,,,..-----~~~~~~
~~~~~--.,,,,,,,,,,,,,,,,,,,.----~~-------.,,,,,,,,,.----------~~
~~~--.,,,,,,,,,####,,####,..---~~~~--------.....-------------~~~
~~---,,#############^^###,,.--~~~~~~------------~-------------~~
~~----.,,##,,############,,..--~~~~---.....,,...--..--.---.---~~
~~~~---.,,,,,,##^#####,,,,,,,..----.,,...,,,,,,,,,,..........--~
~~~---.,,,,,,,#####,,,,,,,,,,,,.....,,,,,,,,,,,,,,,,,,,,,.----~~
~~~-...,,,,,###,,,,,,,###,,,,,,,,,,,,,,,,,,,,##########,,,.-~~~~
~~~----...,,,,,,,,##,,#,,,,,,,,,,,,,,,,,,,,,,#########,,,,.---~~
~~~-------.--.,,,#########,,,,,,#,,,,,,,########^#####,,,,...--~
~~~~~-------..,,,,,,,,,,,,,,,,,,,,,,,,,,,,######^^####,,,,,.--~~
~~~~-~~~~~---..,,,,..,,,,,,,,,,,#####,,,.,,##^^**^^######,.--~~~
~~~~~~~~~---...,,,,..,,,,,,,...,,,,,,,,..,,,,#######,,,,,,.--~~~
~~~~~~~~~---...,,,...,,,,,,....------.,,,,,,,,,,,,###,,,.---~~~~
~~~~~~~~~~------....-.,,,,..----~---....,,,,,,,,,,,,,,,.--~~~~~~
~~~~~~~~~~~~~---------..,..---~~~~~---..,,,,,,,,,..-------~~~~~~
~~~~~~~~~~~~~~--------------~~~~~~~~~---....,,,,,,...----~~~~~~~
~~~~~~~~~~~~~-------~~~~~~~~~~~~~~~~~~~~~--.,...,....----~~~~~~~
~~~~~~~~~~~~~~~-----~~~~~~~~~~~~~~~~~~~~~~----...------~~~~~~~~~
~ water - shallow . beach , grass # forest ^ rock * snow
~~~~~~~~~~~~~~~----~~~~~~~~~~~~~~~~~~~~~~~~~~---.---~~~~~~~~~~~~ ~~~~~~~~~~~~~~~---~~~~~~~~~~~~~~~~~~~~~~~~~~----.----~~~~~~~~~~~ ~~~~~~~~---------------~~~~~~~~~~~~~~~~~~~~---------~~--~~~~~~~~ ~~~~~~~~~--------------------~~~~~~~~~~~~~~-----...-----~~~~~~~~ ~~~~~~~-----~---------..,.-----~~~~~~~~~~~----..,,...---~~~~~~~~ ~~~~~~~~~~~~-~~~--------..------~~~~~~-----...,,,,,..---~~~~~~~~ ~~~~~~~~~~~~~~~~~~--------------~~--~---...,,,,,.,,,.---~----~~~ ~~~~~~~~~~~~-~~~~~~-----------~~~~----.,,,,,,,,,,,,,..-------~~~ ~~~~~~~~~~~~~~~~~~~~-----------~~----.,,,,,,,,,,,,,......---~~~~ ~~~~~~~~~~---~~~~~~------------------.,,,,,,,,,,,,,,......---~~~ ~~~~~~~-------------------------------.,,,,,,,,,,,,,....,.------ ~~~~~~--------------------------~~---..,,,,,,,,##,,,...------~~~ ~~~~~~~----...----------~~~---~~~~---.,,,,,,######,,----~~~~~~~~ ~~~~~---..,,,,.,,......--------~~-----..,,,,,,,,,,,..-----~~~~~~ ~~~~~--.,,,,,,,,,,,,,,,,,,,.----~~-------.,,,,,,,,,.----------~~ ~~~--.,,,,,,,,,####,,####,..---~~~~--------.....-------------~~~ ~~---,,#############^^###,,.--~~~~~~------------~-------------~~ ~~----.,,##,,############,,..--~~~~---.....,,...--..--.---.---~~ ~~~~---.,,,,,,##^#####,,,,,,,..----.,,...,,,,,,,,,,..........--~ ~~~---.,,,,,,,#####,,,,,,,,,,,,.....,,,,,,,,,,,,,,,,,,,,,.----~~ ~~~-...,,,,,###,,,,,,,###,,,,,,,,,,,,,,,,,,,,##########,,,.-~~~~ ~~~----...,,,,,,,,##,,#,,,,,,,,,,,,,,,,,,,,,,#########,,,,.---~~ ~~~-------.--.,,,#########,,,,,,#,,,,,,,########^#####,,,,...--~ ~~~~~-------..,,,,,,,,,,,,,,,,,,,,,,,,,,,,######^^####,,,,,.--~~ ~~~~-~~~~~---..,,,,..,,,,,,,,,,,#####,,,.,,##^^**^^######,.--~~~ ~~~~~~~~~---...,,,,..,,,,,,,...,,,,,,,,..,,,,#######,,,,,,.--~~~ ~~~~~~~~~---...,,,...,,,,,,....------.,,,,,,,,,,,,###,,,.---~~~~ ~~~~~~~~~~------....-.,,,,..----~---....,,,,,,,,,,,,,,,.--~~~~~~ ~~~~~~~~~~~~~---------..,..---~~~~~---..,,,,,,,,,..-------~~~~~~ ~~~~~~~~~~~~~~--------------~~~~~~~~~---....,,,,,,...----~~~~~~~ ~~~~~~~~~~~~~-------~~~~~~~~~~~~~~~~~~~~~--.,...,....----~~~~~~~ ~~~~~~~~~~~~~~~-----~~~~~~~~~~~~~~~~~~~~~~----...------~~~~~~~~~
- tiefes Wasser
- flaches Wasser
- Strand
- Wiese
- Wald
- Fels
- Schnee
07Gut zu wissen
- Der Modulo beim Abtasten sorgt dafür, dass das Rauschen an den Rändern nahtlos weiterläuft. Damit lassen sich Texturen kachelnd wiederholen.
- Das Verfahren ist auf jede Dimension übertragbar: eindimensional für Kurven, zweidimensional für Höhenkarten, dreidimensional für animierte Wolken.
- Der häufigste Einsatz ist die Höhenkarte: Man deutet jeden Wert als Höhe und teilt den Wertebereich in Zonen ein. Unter einer Grenze ist Wasser, darüber Strand, dann Wiese, Wald, Fels und Schnee. Weil benachbarte Werte ähnlich sind, entstehen zusammenhängende Küsten und Gebirge statt einzelner Pixel. Das zweite Beispiel zeigt genau das.
- Multipliziert man die Höhe zusätzlich mit einer Maske, lässt sich die Form der Karte steuern. Eine Maske, die zum Rand hin abfällt, ergibt eine Insel. Ein waagerechter Verlauf ergibt eine Küstenlinie.
- Weil alle Oktaven aufsummiert werden, drängen sich die Werte zur Mitte hin. Für ein kontrastreiches Bild streckt man den Wertebereich nachträglich, so wie im Beispiel unten.