Implementierung eines Raycasters in Bash

 (github.com/izabera)
2 Punkte von GN⁺ 2024-12-22 | 1 Kommentare | Auf WhatsApp teilen
  • Ein in Bash implementierter Raycaster, ein terminalbasiertes Pseudo-3D-Demo, das sich mit den Pfeiltasten drehen und bewegen lässt und mit q beendet wird
  • Die Implementierung ist größtenteils ein Port von Lode Vandevennes Raycasting-Tutorial; die gesamte Mathematik wird ohne Fließkommazahlen mit Ganzzahlarithmetik im Maßstab 64K ausgeführt
  • Die größte Einschränkung ist die Performance von Bash: Wenn pro Pixel Befehle ausgeführt werden oder der Bildschirmzustand in Arrays/Strings gehalten wird, ist eine Ausgabe innerhalb der Frame-Zeit schwer zu erreichen
  • Für die Terminaldarstellung werden Unicode-Half Blocks sowie 24-Bit-Vordergrund-/Hintergrundfarben verwendet, wodurch die vertikale Auflösung effektiv verdoppelt wird; dabei besteht jedoch die Einschränkung, dass die Farben benachbarter Pixel gemeinsam bekannt sein müssen
  • In der aktuellen Roadmap sind fluid movement, decent framerate, parallel rendering, kitty keyboard protocol und ein erster Sound-Prototyp bereits abgeschlossen; textures, sprites, enemies, particles und multiplayer sind noch unvollständig

Terminal-Raycaster in Bash

  • Dieses Projekt ist ein Raycaster, der in Bash läuft, und rendert ein Pseudo-3D-Bildschirmbild im Terminal
  • Gesteuert wird mit den Pfeiltasten zum Drehen und Bewegen; mit q wird beendet
  • Mehr Screenshots und Videos gibt es im Imgur-Album
  • Die Implementierung ist größtenteils ein Port von Lode Vandevennes Raycasting-Tutorial

Einschränkungen, die die Implementierung schwierig machten

  • Das größte Problem ist, dass Bash langsam ist
    • Schon wenn pro Pixel nur ein einziger Befehl ausgeführt werden muss, ist es laut Autor schwer, eine akzeptable Framerate zu erreichen
    • Selbst wenn der Bildschirmzustand in Farb-Arrays gehalten wird, bleibt der Zugriff auf beliebige Array-Elemente problematisch, da er linearer Zeitkomplexität unterliegt
    • Selbst wenn der Bildschirmzustand in einem einzigen langen String gehalten wird, ist auch bei LANG=C der Zugriff auf das n-te Zeichen linear, sodass allein das Auslesen zum Dumpen auf den Bildschirm länger als ein Frame dauern kann
  • Bash hat keine Unterstützung für Fließkommazahlen und keinen Zugriff auf eine Mathematik-Funktionsbibliothek
    • Die gesamte Mathematik wird mit Ganzzahlen verarbeitet
    • Ganzzahlwerte werden für die Berechnung um den Faktor 64K skaliert
  • Wenn im Terminal ein Zeichen wie ein Pixel verwendet wird, sieht das nicht besonders gut aus, daher werden Unicode-Half Blocks verwendet
    • Durch unterschiedliche Vorder- und Hintergrundfarben wird die vertikale Auflösung effektiv verdoppelt
    • Es gibt keine Möglichkeit, in einer Zelle nur eine der beiden Farben zu aktualisieren
    • Auch die aktuelle Zellenfarbe kann nicht abgefragt werden, und in Bash wären schon solche Abfragen selbst zu langsam
    • Deshalb muss beim Schreiben eines Pixels immer auch die Farbe benachbarter Pixel bekannt sein

Terminal- und Ein/Ausgabeprobleme

  • In einer langsamen Sprache wie Bash ist es nicht trivial, das gesamte Terminal auf einmal zu aktualisieren
  • Die meisten Terminals sind nicht für Videospiele ausgelegt, daher kann der aktuell gedrückte Tastenstatus nicht geprüft werden
    • Normalerweise lässt sich nur die Eingabe einer einzelnen gedrückten Taste erfassen
    • Die Eingabewiederholung wird langsam entprellt, und die Grenze für fortlaufende Eingaben ist niedrig, sodass Situationen auftreten, in denen nur etwa 5–6 Zeichen pro Sekunde ankommen
    • Auch mehrere gleichzeitig gedrückte Tasten außer Modifiern sind schwer zu erfassen
    • Das kitty keyboard protocol löst dieses Problem laut Autor
  • Wenn das Terminal mit Farben gefüllt wird, ist viel Datenmenge nötig
    • Bei der üblichen Schriftgröße des Autors fallen etwa 10 MB I/O pro Sekunde an
  • Bash verwendet beim Ausgeben eines Strings mit mehreren Zeilenumbrüchen keinen einzelnen Syscall
    • Dieses Projekt gibt \n nicht aus und bewegt den Cursor stattdessen auf andere Weise

FAQ und Ausführungsbedingungen

  • Wenn das Bild nach dem Ändern der Fenstergröße kaputtgeht, stark flackert oder in bestimmten Terminals nicht gut aussieht, bittet der Autor darum, ein Issue zu eröffnen
  • Wenn die CPU sehr heiß wird oder ein älterer Rechner langsamer wird, soll die Auflösung reduziert oder die Umgebungsvariable FPS auf unter 30 gesetzt werden
    • Es ist bekannt, dass Microsoft Defender die Performance stark verschlechtert, daher wird vorgeschlagen, ihn zu deaktivieren
  • Auf Bash-Versionen vor 5.2 läuft es laut FAQ nicht
  • Der Code besteht nicht ausschließlich aus reinem Bash
    • Beim Start wird stty einmal aufgerufen, um Echo auszuschalten
    • Beim Beenden wird stty einmal aufgerufen, um Echo wieder einzuschalten
    • Einige Statistiken nach dem Beenden werden mit anderen Tools gesammelt

Status der Roadmap

  • Abgeschlossene Punkte

    • semi-accurate pseudo 3d

      • fluid movement
      • decent framerate
      • parallel rendering
      • 24 bit colours
      • kitty keyboard protocol
      • framerate-independent speed
      • sound, allerdings nur ein sehr früher Prototyp
      • dynamic wall colours
      • dynamic map, derzeit nicht durch Ereignisse verändert, aber technisch dynamisch
      • basic animations effects for walls
      • basic on-screen minimap
      • Unvollständige Punkte

    • mouse support

      • textures
      • sprites
      • objects/enemies
      • particles
      • better perf
      • multiplayer

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-12-22
Hacker-News-Kommentare
  • Das ist wirklich großartig. Ich habe mich gefragt, wie hier gezeichnet wird, ohne für jedes Pixel einmal echo auszuführen, und der Ansatz ist sehr clever
    Da das Spiel kein „echtes“ 3D ist, wird das Raycasting nur einmal pro Spalte ausgeführt, und es müssen nur ein paar Zeilen gezeichnet werden, die Himmel, Gras und die eigentlichen Objekte entsprechen
    Für die nötige Anzahl an Wiederholungen wird dann die Zeichenkette „dieses Pixel zeichnen und eine Zeile nach unten gehen“ per String-Wiederholung im Terminal ausgegeben
    Nicht für Bash, aber ich hatte überlegt, eine Voxel-Rendering-Engine in einer anderen Umgebung mit begrenzten Rechenressourcen zu bauen, und ich glaube, dass sich hier definitiv etwas Brauchbares finden lässt
  • Falls sich jemand gefragt hat, ob es auch einen in MS Batch geschriebenen Raycaster gibt: den gibt es ebenfalls: https://github.com/nTh0rn/batch-raycaster
  • Schade, dass stty einen Fork benötigt. Vielleicht besteht das nächste Projekt darin, mit Bash und rowhammer das nötige ioctl direkt aufzurufen und so ohne Fork auszukommen
  • Ich hätte nicht gedacht, dass so etwas in Bash möglich ist. Ich dachte eigentlich, ich könne ziemlich gut mit Bash auf fortgeschrittenem Niveau umgehen, aber das hier ist wirklich erstaunlich
    Ich verstehe die Implementierung mathematisch nicht gut genug, um ihr im Detail zu folgen, aber allein das Anschauen macht Spaß
  • Meine Bash-Skripte brauchen 300 Zeilen nur fürs Parsen von Kommandozeilenoptionen, dabei hätte ich stattdessen offenbar auch so ein Spiel zeigen können :-P
  • Ich verstehe immer noch nicht, warum wir weiterhin an so eine absurd langsame Shell gebunden sind. Das wirkt wie reine Verrücktheit
    Ich verstehe, dass manche Apps alle möglichen Sonderheiten von vt100 brauchen, aber vermutlich schreiben 90 % der Apps einfach nur auf Standardausgabe und Standardfehler
    Man sollte Text doch schneller auf den Bildschirm bringen können und die übrigen 10 % dann in einen Kompatibilitätsmodus packen
    • Die Shell ist langsam, insbesondere Bash, aber ich verstehe nicht ganz, wie sich der Rest des Arguments daraus ergibt. Die Shell ist an der Interpretation von Terminal-Escape-Sequenzen überhaupt nicht beteiligt, und moderne Terminals sind ziemlich schnell
      Selbst in einem Terminal mit 350 Spalten lässt sich eine Animation rendern, und unter den gegebenen Einschränkungen wirkt sie sehr flüssig
      Außerdem ist die Prämisse dieses Beitrags gerade, dass Bash keine für Raycasting geeignete Sprache ist. Das ist ähnlich, als würde man Bubble Sort in CSS schreiben
      Gegen die Idee, „die übrigen 10 % in einen Kompatibilitätsmodus zu packen“, spricht nichts. Man kann prüfen, ob ein String nur normale Zeichen enthält, und dann einen schnellen Pfad verwenden
      Das Problem ist, dass es für Software-Text-Rendering in Wirklichkeit keinen schnellen Pfad gibt. Man muss immer noch Dinge wie Ligaturen verarbeiten
  • „bash is slow.“
    Das ist einer der Gründe, warum ich Bash nicht fürs Skripting verwende. Interaktiv nutze ich es ebenfalls nicht
    Einige populäre Linux-Distributionen meiden Bash auch als Scripting-Shell
  • Es wäre schön, das mit der Fork-losen ps-Implementierung des Autors zu kombinieren und daraus fast eine fork-lose psDoom-Implementierung zu machen
    Scherz beiseite, das ist wirklich cool
  • Natürlich sollte auch der neun Jahre alte awk-Raycaster ehrenvoll erwähnt werden: https://github.com/TheMozg/awk-raycaster/tree/master