senäh

17senäh und so…

HTML/CSS/JS
01. Apr 2012
Kommentare: 0

Was sind Noise Functions?

Kategorien: HTML/CSS/JS | 01. Apr 2012 | Kommentare: 0

Serie: Noise Functions

Hand aufs Herz. Mein letzter Artikel über Perlin Noise als Grundlage für zufällig generierte Landschaften ließ etwas zu wünschen übrig. Ich habe zwar früher bereits mit Perlin Noise gearbeitet, aber das war noch zu meinen Flash-Zeiten und wie ich mittlerweile feststellen musste, unterscheidet sich die Flash-API von Perlin Noise von üblichen Perlin Noise Implementierungen. So musste ich auf eine JavaScript Implementation zurückgreifen, welche zwar gut funktioniert, aber für meine Bedürfnisse nicht so richtig komfortabel war. Herausgekommen ist dabei ein Artikel über Perlin Noise mit dem ich nicht so richtig zufrieden bin. Da mich das Thema ohnehin sehr interessiert (und ich für eines meiner Module in meinen Studium einen bekannten Algorithmus implementieren und untersuchen soll), möchte ich mich noch einmal intensiver mit dem Thema beschäftigen. Mittlerweile habe ich schon einige Zeit in die Recherche gesteckt und komme zu einem ersten Fazit: Das wird gar nicht so leicht!

Motivation

Aber erst einmal langsam mit den jungen Pferden! Ich möchte euch erst noch genau erklären, warum das Thema so spannend ist. Mit Perlin Noise lassen sich viele sehr interessante Dinge anstellen. Es bildet u.a. die Grundlage für viele visuelle Effekte. Außerdem lassen sich mit Perlin Noise „organische“ Dinge erzeugen. Das liegt in dem zufälligen Aussehen der erzeugten Daten. Nehmt eine Landschaft als Beispiel. Die Anordnung von Tälern und Bergen, Seen und Bäumen, Pflanzen und Steigen – das sieht alles relativ zufällig aus. Es gibt keinen Baum auf der Welt, der exakt so aussieht wie ein anderer Baum. Angenommen ihr wollt einen Wald in einem Videospiel anzeigen. Meint ihr, ihr wollt einen Grafiker hunderte oder tausende von Bäumen erstellen lassen? Das dauert viel zu lang und ist unnötig. Man bräuchte also eine Möglichkeit 1x einen Baum zu erstellen und diesem über verschiedene zufällige Parameter „unendlich“ zu variieren. Genau dafür gibt es Perlin Noise (neben anderen ähnlichen Funktionen)!

In diesem Fall sagen Bilder (oder ein Video) mehr als 1000 Worte. Ihr alle kennt sicher Minecraft. In diesem Spiel wurde die komplette Welt mit Perlin Noise generiert. Beeindruckend oder?

Wer denkt, dies wäre nur mit „blockartigen“ Gebilden möglich, irrt sich gewaltig. Auch diese Welt basiert auf Perlin Noise:

Perlin Noise ≠ Perlin Noise

Nun aber zu einem Problem welches mich selbst und viele andere getroffen hatte: Perlin Noise ≠ Perlin Noise! Durch viel Unwissenheit – hauptsächlich ausgelöst durch ein Tutorial von Hugo Elias – besitzen viele ein falsches Verständnis von Perlin Noise. Elias versucht in seinem Tutorial eine Noise Function zu implementieren und bezeichnet diese als Perlin Noise. Das ist aber falsch! Leider ist es dadurch sehr schwer geworden über das Internet vernünftige und vertrauenswürdige Aussagen über Noise zu finden.

Alles was ich euch erzähle basiert auf meinen Rechercheergebnissen, welche aus den oben genannten Gründen falsch sein können! Wenn dies der Fall ist, bitte ich euch mich zu berichtigen, damit wir an dieser Stelle ein gutes ausführliches und fachlich richtiges Dokument über Noise erhalten 🙂
Natürlich versuche ich bereits jetzt schon alles fehlerfrei zu erklären!

An dieser Stelle möchte ich zusätzlich anmerken, dass es durchaus möglich ist, dass ich diesen Artikel in Zukunft noch öfter aktualisieren werde, um neue Erkenntnisse einfließen zu lassen.

Noise Functions

Beginnen wir doch gleich mit etwas mehr Klarheit. Ab sofort spreche ich nicht mehr einfach von Perlin Noise, sondern von Noise Functions. Perlin Noise ist einfach nur die bekannteste Noise Function, weswegen viele beide Begriffe synonym verwenden, obwohl Perlin Noise nur eine spezielle Noise Function ist. Ich bleibe übrigens im Folgenden bei englischem Vokabular, da die meisten Quellen zu diesem Thema in englisch verfasst wurden und dies eure weitere Recherche zum Thema vereinfacht 🙂

Noise Functions besitzen bestimmte Eigenschaften. Wer Rauschen aus der Physik und der Technik kennt, weiß, dass Rauschen eine zufällige Störgröße ist. Das mit einer Noise Function erzeugte Rauschen ist jedoch nur „scheinbar“ zufällig. Es sieht zufällig aus, ist es aber nicht. Das liegt zum einen an technischen Beschränkungen (Computer arbeiten deterministisch, also immer vorherbestimmt), zum anderen wollen wir es auch nicht anders. Wir wollen mit Noise Functions Daten erzeugen, welche zufällig aussehen, aber jederzeit reproduzierbar sind. Es wäre doch doof, wenn wir eine tolle Landschaft in einem Spiel generieren und sie beim nächsten Start des Spiels verloren wäre. Wenn etwas nur scheinbar zufällig ist, dann nennt man dies Pseudo Random. Es bezeichnet die Tatsache, dass eine bestimmte Eingangsgröße eine bestimmte Ausgangsgröße erzeugt. Unsere Ausgangsgröße wäre in diesem Fall unsere Landschaft und die Eingangsgröße kann alles mögliche sein – üblicherweise eine Zahl. Man nennt die Eingangsgröße Seed.
Anders formuliert: Ein und derselbe Seed erzeugt immer wieder die gleiche Landschaft. Wird ein anderer Seed verwendet, erhalten wir eine andere Landschaft.
Fun Fact: Die Zufälligkeitsfunktion in vielen Programmiersprachen (bei JavaScript Math.random())  ist ebenfalls nur scheinbar zufällig. Als Seed wird hier die Uhrzeit mit Datum verwendet, wenn das Script startet. Da die aktuelle Uhrzeit und das Datum jedes Mal anders ist, wird nie der gleiche Seed verwendet, man erhält also immer andere Ergebnisse. Dennoch sind die Ergebnisse nur scheinbar zufällig.

Die Ausgangsgrößen, also das erzeugte Rauschen/die erzeugten Daten, sind häufig normiert. (Jede „Stelle“ im Rauschen besitzt meist einen Wert von -1 bis 1 oder von 0 bis 1 oder von 0 bis 255.) Außerdem besitzt jede Stelle eine Koordinate mit n-Dimensionen. Angenommen wir haben ein 2dimensionales Rauschen, so könnten wir mit der (x/y)-Koordinate genau überprüfen, welchen Wert das Rauschen an einer bestimmten Stelle hat.
Für eine typische Minecraft-ähnliche Landschaft benötigen wir bspw. ein 3dimensionales Rauschen, um eine Welt mit Bergen/Tälern und Höhlen zu erzeugen.

Inhalte, welche mit den erzeugten Daten einer Noise Function erstellt wurden (z.B. eine Landschaft), werden als Procedural Content bezeichnet. Procedural heißt, dass der erzeugte Inhalt automatisch von einem Algorithmus (z.B. eine Noise Function) erstellt wurde und nicht von manuell von einem Menschen (z.B. ein Grafiker).

Je nachdem wie das Rauschen erzeugt wird, kann man die Noise Function in diverse Kategorien unterteilen:

  • Value Noise
  • Gradient Noise
  • Simplex Noise
  • Wavelet Noise

Value Noise wurde u.a. von Hugo Elias in seinem Tutorial implementiert und fälschlicherweise als Perlin Noise bezeichnet. Ein Beispiel für Gradient Noise wäre Perlins erste Noise Function, welche auch als „Classic Perlin Noise“ bezeichnet wird, und ein Beispiel für Simplex Noise wäre Perlins zweite Noise Function, welche häufig auch als „Improved Perlin Noise“ bezeichnet wird. Zu Wavelet Noise konnte ich bisher leider keine Implementation finden. 🙁 Eine theoretische Erklärung gibt es hier.

Möglicherweise gibt es noch mehr Arten von Noise, die ich noch nicht kenne. Wenn dem so ist, dann schreibt bitte einen Kommentar! 🙂

Mein Ziel ist es in den folgenden Artikeln dieser Serie jeweils eine Noise Function Kategorie vorzustellen und in JavaScript zu implementieren. Alle Noise Functions sollen am Ende eine ähnliche API besitzen. Anschließend kann ich sie auf ihre Geschwindigkeit hin vergleichen. Alle Implemenationen landen dann in folgendes Framework:

Noizy

Am Ende dieser Serie entsteht hoffentlich ein kleines JavaScript Framework, welches ich Noizy getauft habe. Es wird alle Noise Function Implementationen enthalten, die ich auftreiben kann. Die API soll dabei vereinheitlicht werden. Mein Plan ist es jede Noise Function mindestens für 3 Dimensionen zu implementieren. Als Konstrukt verwende ich meine kleine OOP-Vorlage.

Na dann! Ich freue mich schon darauf, bald die erste Funktion zu implementieren 🙂

 

Autor: Pipo

...kommt ursprünglich aus der Designerecke, ist aber im Laufe seines Studiums in die Webentwicklung gestolpert. Kann sich seit dem nicht so richtig entscheiden wo er hingehört und wagt deswegen vielleicht die Flucht nach vorne in ein komplett neues Gebiet. Vielleicht Management? Niemand weiß es. Auch er nicht.