Random-Walks

Bevor wir in die Komplexität von Vektoren und auf Physik basierten Bewegungen eingehen, überlegen wir uns, was es bedeutet wenn sich etwas einfach über den Bildschirm bewegt. beginnen wir mit einer der bekanntesten und einfachsten Simulationen von Bewegungen, dem Random-Walk auch Zufallsbewegung oder Irrfahrt genannt.

Stell dir vor, du stehst in der Mitte eines Schwebebalkens in einer Turnhalle. Alle zehn Sekunden, wirfst du eine Münze. Kopf bedeutet einen Schritt nach vorne. Zahl bedeutet einen Schritt zurück. Dies ist ein Random Walk, ein Pfad, der als eine Reihe von zufälligen Schritten definiert ist. Wenn du von diesem Schwebebalken herunter auf den Boden der Turnhalle springst, kannst du einen Zwei-Dimensionalen Random-Walk mit dem zweimaligen Wurf derselben Münze mit folgendem Ergebnis durchführen:

Wurf 1	Wurf 2	Ergebnis
Kopf	Kopf	Schritt vorwärts
Kopf	Zahl	Schritt nach Rechts
Zahl	Kopf	Schritt nach links.
Zahl	Zahl	Schritt rückwärts

Ja, dies mag wie ein besonders naiver Algorithmus aussehen. Dennoch können Random-Walk zur Modellierung von Phänomenen aus dem täglichen Leben verwendet werden, von Bewegungen der Moleküle in einem Gas bis zum Verhalten eines Spielers während eines Tages im Casino. Was uns betrifft, wir beginnen dieses Thema mit dem Studium eines Random-Walk mit drei Zielen.

Das Random Walker-Objekt

Zuerst wollen wir kurz mit der Programmierung eines Walker-Objektes die objektorientierte Programmierung (OOP) wiederholen. Dies wird nur eine sehr oberflächliche Wiederholung. Falls du noch nie mit OOP gearbeitet hast, solltest du dir unser Tutorial zu objektorientiertem JavaScript anschauen.

In JavaScript ist ein Objekt ein Datentyp welchem durch seinen Prototypen sowohl Eigenschaften wie auch Funktionen zugeordnet werden. Wir wollen ein Walker-Objekt designen, welches sowohl seine Daten verwaltet (weiß wo es sich auf dem Bildschirm befindet) als auch gewisse Aktionen ausführen kann (z.B. sich selbst zeichnen oder einen Schritt machen).

Damit wir Instanzen von Walker erstellen können, müssen wir zuerst einen Walker-Prototypen definieren. Wir benützen diesen Prototypen als Keksform und jede neue Instanz von Walker wird ein neuer Keks.

Beginnen wir, indem wir den Objektypen Walker definieren. Der Walker braucht nur zwei Datenwerte, eine Zahl für seine x- und eine für seine y-Koordinate. Wir initialisieren diese der Konstrukor-Funktion so, dass sich der Walker im Zentrum des Canvas befindet.

var Walker = function() {
    this.x = width/2;
    this.y = height/2;
};

Zusätzlich zu seinen Eigenschaften für die x- und y-Koordinaten, hat unser Walker-Objekt auch Methoden welche wir aufrufen können. Die erste Methode wird wird dem Objekt erlauben, sich selbst als schwarzen Punkt darzustellen. Beachte, dass wir in JavaScript Methoden für ein Object definieren, indem wir diese zu seinem Prototypen hinzufügen.

Walker.prototype.display = function() {
    stroke(0, 0, 0);
    point(this.x, this.y);
};

Die zweite Methode wird dem Walker-Objekt erlauben eine Schritt zu machen. Hier wird es nun etwas interessanter. Errinerst du dich an die Turnhalle in welcher wir zufällige Schritte gemacht haben? Nun werden wir die Schritte auf dem Canvas machen. Es gibt vier mögliche Schritte. Für einen Schritt nach rechts zählen wir einfach x eins hoch (x++), bei einem Schritt nach links zählen wir x eins herunter (x--), vorwärts indem wir einen Pixel nach unten gehen (y++), und rückwärts indem wir einen Schritt Pixel nach oben gehen (y--). Und wie wählen wir zwischen diesen vier Möglichkeiten? Wie bereits erklärt, werfen wir einfach zwei Münzen. Da unser Programm keine Münzen werfen kann, benützen wir einfach die Zufallsfunktion random() von ProcessingJS um zufällig zwischen den 4 Möglichkeiten zu wählen.

Walker.prototype.walk = function() {
    var choice = floor(random(4));
};

Die Codezeile oben generiert eine zufällige Gleitkommazahl zwischen 0 und 4 und wandelt diese mit der Funktion floor() in eine ganze Zahl mit dem Resultat 0, 1, 2 oder 3 um. Genau genommen, wird die höchste Zahl nie 4,0, eher 3,999999999 (mit so vielen 9 wie es Dezimalstellen hat) und da floor() immer die nächst kleinere ganze Zahl zurück gibt, wird die höchste Zahl 3. Als nächsten nehmen wir den nächsten Schritt(links, rechts, oben oder unten) gemäß der generierten Zufallszahl.

Walker.prototype.walk = function() {
    var choice = floor(random(4));
    if (choice === 0) {
        this.x++;
    } else if (choice === 1) {
        this.x--;
    } else if (choice === 2) {
        this.y++;
    } else {
        this.y--;
    } 
};

Nun, da wir die Klasse geschrieben haben, wird es Zeit in unserem Programm ein Walker-Objekt zu instanzieren. Wenn wir einen einzelnen Random-Walk modellieren wollen, deklarieren und initialisieren wir eine globale Variable vom Typ Walker, indem wir seinen Konstruktor mit dem Operator new aufrufen.

var w = new Walker();

Und nun wollen wir, dass der Walker tatsächlich etwas tut. Dazu definieren wir die Funktion draw() und bringen dem Walker bei, bei jedem Aufruf einen Schritt zu machen und sich danach selbst auf dem Canvas darzustellen.

draw = function() {
    w.walk();
    w.display();
};

Da wir in der Funktion draw background() nicht aufrufen, können wir den Pfad des Random Walks auf unserem Canvas sehen. Und nun verstehst du auch weshalb dies auf deutsch auch Irrfahrt genannt wird.

Den Random Walker verbessern

Es gibt ein paar Verbesserungen, welche wir an dem Random Walker machen können. Auf der einen Seite, sind die möglichen Schritte für diesen Walker auf nur vier Richtungen (oben, unten, links, rechts) limitiert. Jedes Pixel auf dem Canvas hat aber acht mögliche Nachbarn und eine neunte Möglichkeit wäre es an der gleichen Stelle zu bleiben.

Um ein Walker-Objekt welches einen Schritt zu allen acht Nachbarpixels (oder gar keinen) machen kann zu implementieren, wählen wir eine Zahl zwischen 0 und 8 (9 Möglichkeiten). Der Code wäre aber einfacher zu schreiben, wenn wir einfach zwischen drei möglichen Bewegungen auf der x-Achse (-1, 0 oder 1) und drei möglichen Bewegungen auf de y-Achse wählen würden.

Walker.prototype.walk = function() {
  var stepx = floor(random(3))-1;
  var stepy = floor(random(3))-1;
  this.x += stepx;
  this.y += stepy;
};

Wenn wir diese Idee weiterentwickeln, könnten wir auch einfach eine Dezimalzahl für x und y wählen und die Bewegung anhand einer Zufallszahl zwischen -1 und 1 machen, wenn unsere Umgebung den Unterschied zwischen "2,2" und "2,4" richtig darstellt.

Walker.prototype.walk = function() {
  var stepx = random(-1, 1);
  var stepy = random(-1, 1);
  this.x += stepx;
  this.y += stepy;
};

All diese Variationen des “traditionellen” Random Walk haben eines gemeinsam: die Wahrscheinlichkeit, dass der Walker wählt einen Schritt die eine Richtung zu machen( oder sich gar nicht zu bewegen) ist jederzeit gleich groß, wie die Wahrscheinlichkeit, dass der Walker jede andere Entscheidung trifft. In anderen Worten, wenn es vier mögliche Schritte gibt, ist die Wahrscheinlichkeit für jeden Schritt des Walker 1 von 4 (oder 25%). Mit neun möglichen Schritten ist die Wahrscheinlichkeit 1 von 9 (oder 11.1%).

Praktischerweise funktioniert die Funktion random() genau gleich. Der Zufallszahlengenerator erzeugt Zahlen nach einer sogenannten "Gleichverteilung". Wir können diese Verteilung mit einem Programm testen, welche jedes Mal zählt, wenn eine Zufallszahl gewählt wird und das Resultat als die Höhe eines Rechtecks darstellt:

Sind nach ein paar Minunten Laufzeit die Balken alle gleich hoch? Wahrscheinlich nicht. Unsere Stichprobe (d.h. die Anzahl von Zufallszahlen, die wir gewählt haben) ist eher klein und es gibt gelegentliche Abweichungen, da mache Zahlen öfters ausgewählt werden als andere. Mit einem guten Zufallszahlen-Generator, wird sich dies mit der Zeit aber ausgleichen.

Die Zufallszahlen welche Die Funktion random() generiert sind aber nicht wirklich zufällig. Daher werden sie auch “pseudo-zufälligen.” genannt, da sie das Ergebnis einer mathematischen Funktion sind, welche die Zufälligkeit simuliert. Nach einer gewissen Zeit würde diese Funktion ein Muster von sich wiederholenden Zahlen generieren. Diese Zeitspanne wäre aber so lange, das sie für uns so gut wie eine reine Zufallsfunktion ist!

Im nächsten Abschnitt betrachten wir verschiedene Möglichkeiten, wir wir Walker mit der "Tendenz" in eine bestimmte Richtung zu gehen erstellen können. Bevor du aber darin eintauchst, wartet nun eine Challenge auf dich!

Der Kurs "Natürliche Simulationen" ist eine Bearbeitung von "The Nature of Code" von Daniel Shiffman, und wird unter der Creative Commons Attribution-NonCommercial 3,0 Unported Lizenz verwendet.

Willst du an der Diskussion teilnehmen?

Anmelden

Sortiere nach:

Noch keine Beiträge.

Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.