Selbstfahrendes Auto – how to code?

In einem früherem Beitrag habe ich gezeigt, wie wir mit Hilfe von der JavaScript-Library «Kaboom.js» relativ einfach unser eigenes Zelda-Game coden können. Nun wollte ich einen Schritt weiter gehen und ein JavaScript-Projekt realisieren, das komplett ohne Libraries funktioniert. Dazu habe ich anhand von Online-Dokumentationen ein autonom fahrendes Auto gecodet.

Schaut dir die Animation gerne an: Selbstfahrendes Auto mit JavaScript

Die Erläuterung zum Vorgehen und der technischen Umsetzung findet ihr unter Kritik:).

Warnung: Die Erklärungen sind relativ theorielastig ausgefallen …

(mou)

Idee

Ich nahm mir vor in diesem Digezz-Beitrag ein JavaScript-Projekt zu entwickeln, dass komplett ohne Libraries funktioniert, sondern direkt im Code selbst programmiert wird. Dazu suchte ich Inspiration im Internet, um mich auf neue Ideen zu bringen. Schlussendlich entschied ich mich, ein selbstfahrendes Auto anhand der Dokumentationen online zu entwickeln. Das heisst man soll die Strasse sehen, den Verkehr und das von der KI (Künstliche Intelligenz) gesteuerte Auto. Dieses KI-Auto erkennt Hindernisse anhand seiner Sensoren und weicht dementsprechend aus.
In diesem Projekt nutze ich wieder die Plattform Replit, weil ich dort schnell und einfach meine Files erstellen kann und gleich auch im Browser sehe, ob der Code funktioniert.

Umsetzung

Einrichten

Ich logge mich auf Replit.com ein und nutze ein Replit-Template für HTML, CSS und JavaScript. Zu Beginn erstelle ich die leeren Files index.html, main.js und style.css.
Dann erstelle ich im index.html den Titel «Selbstfahrendes Auto mit JavaScript» und verlinke das style.css im head. Im body definiere ich einen canvas namens «meinCanvas» und verlinke auch das main.js.

Als nächstes gebe ich dem ganzen einen Style, damit es nach einer Strasse aussieht;

html, body {
margin: 0;
background: lightblue;
overflow: hidden;
text-align: center;
}

#meinCanvas {
background: darkgrey;
}

Das Ganze soll nur 2D dargestellt werden, deshalb geben wir im main.js «canvas.getContext(«2d»)» ein.

Für das Auto erstellen wir zuerst eine auto.js Datei und verlinken diese im index.html. Dann erstellen wir eine Klasse Auto mit den constructor-Parametern x,y,width und height. Diese Eigenschaften halten fest, wie gross das Auto sein soll und wo es positioniert wird. Darauffolgend zeichnen wir das Auto provisorisch mit der Methode zeichnen(context). In der Methode können wir die Geodaten der Rechtecks festlegen.

Fahrzeugsteuerung

Zu Beginn möchten wir prüfen, wie sich das Fahrzeug steuern lässt. Erst später kommen die Sensoren und damit die Einstellungen der KI dazu. Die Fahrzeugsteuerung halten wir in einem eigenen File namens steuerung.js fest. Als Erstes kommt die Klasse Steuerung mit den Klassenattributen forward, left, right und reverse (rückwärts). Damit das Auto sich entsprechend der Tastaturtasten bewegt, müssen wir sogenannte Keyboard Listeners hinzufügen. In diesem Fall nennen wir die Methode «addTastaturListeners». In der Methode befindet das onkeydown-Event. Hier drin ordnen wir den Tastaturpfeiltasten den Boolean-Wert true zu. Im onkeyup-Event hingegen geben wir den Wert false ein. Somit weiss der Browser, dass die Methode addTastaturListeners nur ausgeführt wird, wenn die Pfeiltasten gedrückt werden (onkeydown).

Im auto.js fügen wir eine update-Methode hinzu. Hier drin findet ein if-Loop statt, dass kontrolliert, wenn steuerung.forward getätigt wird, dann soll das Auto sich an der y-Achse entlang aufwärts bewegen. Im Gegenzug mit steuerung.reverse soll sich das Auto rückwärts, also der y-Achse entlang abwärts bewegen. Zusätzlich braucht das Auto auch eine Geschwindigkeit und eine Beschleunigung. Wenn man es bei diesen beiden Atrributen belassen würde, würde man merken, dass das Auto unendlich in eine Richtung beschleunigt. Um dies zu verhindern, kann man eine maxGeschwindigkeit und Reibung hinzufügen. Als nächstes fügen wir eine if-Schleifen ein. Diese sagen z.B. aus, wenn die Geschwindigkeit die maxGeschwindigkeit überschreiten sollte, wird die Geschwindigkeit automatisch der maxGeschwindigkeit angepasst; if(geschwindigkeit>maxGeschwindigkeit){geschwindigkeit=maxGeschwindigkeit;}. In einer anderen if-Schleife wird der Geschwindigkeit die Reibung subtrahiert, damit es realistischer wirkt; if(geschwindigkeit>0) {geschwindigkeit-=reibung;}.

Damit dem Ganzen Leben eingehaucht wird, braucht es eine Animation. Wir können im main.js eine Funktion «animieren» hinzufügen. In dieser Funktion kann man «requestAnimationFrame(animieren)» einsetzen. requestAnimationFrame ruft die Animations-Funktion wiederholt auf und erzeugt so einen weichen Übergang von Frame zu Frame. Es gibt dem Nutzer die Illusion von Bewegung, die wir brauchen. Nun können wir auch die Bewegungen unseres Autos sehen und testen.

Beim genauen Hinsehen im Browser sehen wir, dass das Auto sich im Stillstand ein klein wenig bewegt. Zurück im auto.js können wir dies mit der folgenden Funktion beheben; if(Math.abs(geschwindigkeit)<reibung){speed=0;}. Diese Funktion fragt ab, ob die Geschwindigkeit des Autos kleiner als die Reibung ist. Wenn sie das ist, wird die Geschwindigkeit gleich Null gesetzt, damit das Auto auch beim genaueren Hinsehen stehen bleibt. Ein weiteres Problem, dass auftretet, ist die Rotation des Autos. Das Fahrzeug soll sich mit den Rädern zusammen lenken lassen und nicht wie einen Panzer an der gleiche Stelle drehen. Deshalb verwenden wir für die beiden Achsen x und y folgende Berechnungen, x-=Math.sin(winkel)*geschwindigkeit; y-=Math.cos(winkel)*geschwindigkeit;

Strasse

Als nächstes widmen wir uns der Strasse. Um die Bearbeitung zu vereinfachen und die Übersicht zu wahren, erstellen wir eine Datei namens strasse.js. Hier erstellen wir eine Klasse mit dem Namen Strasse. Innerhalb der Klasse kreieren wir einen Konstruktor folgenden Attributen; x, width, spurAnzahl, links und rechts. Da die Strasse praktisch unendlich nach oben und nach unten gehen soll, verleihen wir den Attributen oben und unten die provisorischen Werte -1000000 und 1000000.

Im nächsten Schritt gestalten wir die Strassenlinien. Dazu verwenden wir zeichnen(context) mit den Attributen lineWidth, strokeStyle, beginPath, moveTo, lineTo und stroke. Damit die Linien im Browser auch angezeigt werden, müssen wir im main.js die Strasse vor dem Auto einfügen mit strasse.zeichnen(context). Die Strassenlinien werden nun ganz am Rand der Strasse positioniert. Ich möchte eine Pannenstreifen jeweils links und rechts haben, weshalb ich das canvas.width mit 0.9 (90%) multipliziert habe.

Das Auto soll innerhalb einer Spur zentriert werden. Dafür erstelle ich die Funktion holSpurMitte(spurIndex). Der spurIndex geht in unserem Fall von Null bis Zwei, also drei Spuren insgesamt.
Die Kameransicht kann auf die das Fahrzeug fixiert werden, indem man in der Funktion animieren() im main.js folgendes einfügt:

context.save();
context.translate(0,-auto.y+canvas.height*0.5);
context.restore();

Das canvas.height*0.5 gibt an, dass das Auto 50% in der Höhe des Canvas, also in der Mitte des Bildschirms stehen soll.

Sensoren

Für die Sensoren erstellen wir ein sensor.js und verlinken es wieder im index.html. Im Konstruktor der Klasse Sensor kann man die Anzahl Strahlen der Sensoren, ihre Länge und die Breite festlegen. Die Strahlen sollen vom Sensor ausgestrahlt werden und werden benötigt, um Hindernisse zu erkennen. Dazu wird als Anfangspunkt der Mittelpunkte des Autos genommen und als Endpunkt der strahlWinkel * strahlLength verwendet. Am besten heben wir die Sensorstrahlen mit strokeStyle=»yellow» heraus. Wenn die Strahlen während dem Fahren ebenfalls in die Autorichtung zeigen sollen, kann man den Code +auto.winkel anhängen.

Dann gehen wir wieder ins auto.js um die Sensoren zu instanzieren; sensor=new Sensor(); und fügen bei update() auch sensor.update() hinzu sowie bei zeichnen(context) den Code sensor.zeichnen(context). Die Sensoren werden ausgestrahlt, das ist super. Nun sollten sie aber auch Strassenränder und andere Fahrzeuge erkennen. Dafür braucht es zum einen Strassenränder und zum anderen Messungen. In der update()- und der sensor.update()-Funktion fügen wir den Parameter strasseBorders ein.

Daraufhin ist es möglich auch im sensor.js den Parameter strasseBorders im update() einzufügen. Jetzt können wir mit den Sensoren erkennen, ob die Strassenränder in der Nähe sind. Im sensor.js kann man einen leeren Array namens «messungen» erstellen. In der for-Schleife der Strahlen-Messung wird kontrolliert, ob der Strahl den Strassenrand berührt (touch) und automatisch in den Array touches eingefügt mit touches.push(touch). In einer if-Schleife kann man festlegen, wenn es keine Berührungen gibt, ergbit es return null. Und wenn es Berührungen gibt, soll die nächstgelegene Berührungen (kleinster Offset) ausgespielt werden.

Die Strahlen sollten sich verändern, sobald sie mit etwas in Berührung kommen. In der zeichnen(context)-Methode kann man folgendes schreiben;

let end=this.strahlen[i][1];
if(this.messungen[i]){
end=this.messungen[i];
}

Mit diesem Code verleiht man der Variable end einen Punkt mit x- und y-Attributen. Diesen «end»-Punkt kann man im context.lineTo anpassen. Als nächstes kopieren wir den Code von den gelben Sensorstrahlen und fügen ihn nochmals ein. Diesmal ist die strokeStyle-Farbe schwarz und die Strahlen fangen dort an, wo sich das Hindernis befindet. Leider scheint bei mir die Anzeige der schwarzen Sensorstrahlen nicht zu funktionieren.

Kollisionen

Das Fahrzeug soll mit anderen Autos und dem Strassenrand kollidieren können. Dazu kreieren wir eine neue Methode im auto.js namens «erstellPolygon». Momentan fehlen uns die Angaben der vier Ecken des Fahrzeuges. Dafür spielen wir mit den trigonometrischen Funktionen. Zum einen können wir die halbe Diagonale des Fahrzeugvierecks, also die Hypothenuse berechnen. Zum anderen können wir den Winkel «alpha» über die von JavaScript integrierte Math-library herausfinden;

const radius=Math.hypot(this.width,this.height)/2;
const alpha=Math.atan2(this.width,this.height);

Mit Hilfe dieser Konstanten können wir die vier Eckpunkte unseres Autos definieren. Die erstellen Polygon-Punkte fügen wir nun in zeichnen(context) ein. Ich möchte dass es anzeigt, wenn das Fahrzeug gegen ein Hindernis, in diesem Fall der Strassenrand, fährt. Im Konstruktor des Autos können wir die Attribute damaged=false definieren. Desweiteren fehlt uns noch eine Funktion die herausfindet, wenn sich Polygone (Fahrzeug und Hindernis) schneiden. Diese Funktion fügen wir im tools.js ein;

function polysSchnittpunkt(poly1, poly2){
for(let i=0;i<poly1.length;i++){
for(let j=0;j<poly2.length;j++){
const touch=holSchnittpunkt(
poly1[i],
poly1[(i+1)%poly1.length],
poly2[j],
poly2[(j+1)%poly2.length]
);
if(touch){
return true;
}
}
}
return false;
}

Es geht darum die Berührungs- bzw. Schnittpunkte herauszufinden und so einen Boolean auszugeben. Wenn das Fahrzeug eine Kollision hat, soll es nicht mehr fahren können «if(!this.damaged)» und die Farbe ändern;

if(this.damaged){
context.fillStyle=»gray»;
}else{
context.fillStyle=»black»;
}

Verkehr

Damit die Fahrt nicht zu eintönig wird und unserem Fahrzeug eine Challenge geboten wird, fügen wir zusätzliche Fahrzeuge ein. Im main.js erstellen wir eine neue Konstante «verkehr», in dem ein Dummy-Fahrzeug erzeugt wird. Beim Ausprobieren merkt man, dass die Steuerung der Pfeiltasten nun auf das Dummy-Fahrzeug übertragen wurde. Um dies zu berichtigen, legen wir verschiedene Steuerungstypen fest. Zum einen haben wir das von uns gesteuerte Auto mit der Attribute «ADMIN» und unserem Dummy-Fahrzeug mit «DUMMY». In der steuerung.js fügen wir folgenden Code ein;

switch(typ){
case «ADMIN»:
this.#addTastaturListeners();
break;
case «DUMMY»:
this.forward=true;
break;
}

Dieser Code legt fest, dass nur der Admin über die Pfeiltasten Zugriff auf das erste Fahrzeug hat. Das Dummy-Fahrzeug fährt standardmässig vorwärts. Damit es uns nicht davon fährt, können wir dem Dummy-Fahrzeug eine niedrigere Geschwindigkeit geben. Momentan haben beide Fahrzeuge Sensortstrahlen. Mit if(steuerungTyp!=»DUMMY»){this.sensor=new Sensor(this);} können wir den Dummy von den Sensoren ausschliessen.

Künstliche Intelligenz

In diesem Schritt kommen wir zur künstlichen Intelligenz bzw. zur Implementierung eines neuronalen Netzwerks. Unser Gehirn besteht aus über 100 Milliarden Nervenzellen und jede Nervenzelle ist über Tausende von Kontakten mit anderen Zellen verbunden. In diesem Beispiel wollte ich das neuronale Netzwerk im kleinen Rahmen versuchen darzustellen. Dazu teile ich die Neuronen in Ebenen auf, um eine Ordnung zu haben. Wir erstellen ein ki.js und verlinken es im index.html. Dann werden in der neu erstellte Klasse «Ebene» Arrays erstellt. Zum einen braucht es input- und output-Zahlen, da jede Nervenzelle einen Wert hat und ausgibt. Hinzu kommt, dass jeder in Inputzahl eine Gewichtung und eine Neigung gegeben wird. Die Inputs erhaltet man von den Sensoren.

Challenges

Es war für mich sehr schwierig zu verstehen, wie genau ich z.B. die trigonometrischen Funktionen aufbauen kann und wie ich sie umsetzen kann. Mein persönlichen JavaScript-Skills sind mittelwertig und deshalb gab es einige Situationen, in denen ich eine Pause brauchte, um wieder einen klaren Kopf zu kriegen und nochmals drüber schauen musste. Zum Beispiel bei den Berechnungen mit der Beschleunigung und der Reibung oder beim diagonal Fahren, bei den Kollisionen oder beim Nachbauen des neuronalen Netzes. Ein anderes Problem war, dass ich manchmal ein Durcheinander hatte, wo ich welche Bezeichnungen geführt hatte und sie mit Englisch gemischt habe, beispielsweise addTastaturListeners, steuerung.forward oder borders statt ränder. Die Bezeichnungen mögen etwas wirr erscheinen, jedoch habe ich mich bewusst für so entschieden, damit die deutschen ä, ö oder ü nicht im Code vorkommen. Gegen Ende des Projektes hin schlich sich ein gröberer Fehler ein, den ich nicht zu beheben wusste. So ersetzte ich die ältere Version mit der neuen. Ich bin sehr froh darüber, dass die neuste Version bis zu einem gewissen Grad funktioniert.

Fazit

Es war eine spannende und aufschlussreiche Übung. Ich konnte meine JavaScript-Kenntnisse nutzen und erweitern. Und ich musste viel grübeln, denn es kamen (zumindest mir) neue Funktionen wie canvas.getContext, zeichnen(context), Math.abs(), Math.sin(), Math.cos() usw. dazu. Das Programmieren war sehr anspruchsvoll, dadurch dass ich keine Libraries nutzen wollte, die die Arbeit um einiges erleichtert hätten. Ich habe versucht den Prozess so gut es geht zu erläutern, damit auch für andere verständlich ist, wie ich vorgegangen bin. Ich hoffe, es ist mir gelungen, auch wenn dabei auf viel Code zur Erklärung miteinbegriffen habe. Ich hätte noch viel genauer mich mit dem neuronalen Netz oder maschinellem Lernen beschäftigen können, jedoch hätte das den Arbeitsrahmen gesprengt. Ich habe bereits zahlreiche Stunden in das bestehende Werk investiert. Alles in allem bin ich mit dem Ergebnis zufrieden und freue mich, dass ich das Projekt erfolgreich abschliessen konnte.