Stadt in der Flasche – 256-Byte-Raycasting-System

 (frankforce.com)
3 Punkte von GN⁺ 2024-05-21 | 1 Kommentare | Auf WhatsApp teilen
  • City In A Bottle ist eine JavaScript-Demo, die eine Raycasting-Engine und einen Stadtgenerator in 256 Byte HTML unterbringt
  • Die Ausführung startet nur mit <canvas> und onclick=setInterval(...); die Szene wird in jedem Frame auf einem 99 Pixel breiten Canvas neu gezeichnet
  • Das Rendering erfolgt ohne trigonometrische Funktionen, nur mit einfacher Algebra und Bitoperationen; pro Pixel werden ein Kamerastrahl und ein Strahl in Richtung der Lichtquelle verfolgt, um Schatten zu erzeugen
  • Die Stadtform trennt anhand von X-, Y-, Z-Koordinaten und Bedingungen wie X/9^Z/8, X%99 und Z>32 Gebäudehöhen, Straßen und Freiräume
  • Die endgültige Helligkeit mischt Distanznebel, Schatten und die Textur (X&Y&Z)%3/Z in die Breite von fillRect ein und realisiert mit extrem wenig Code Stadt, Perspektive und Materialwirkung zugleich

Gesamtstruktur in 256 Byte HTML

  • Die Demo funktioniert nicht als JavaScript-Schnipsel, sondern als ein einzelnes gültiges HTML-Programm
<canvas style=width:99% id=c onclick=setInterval('for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a',t=9)>
  • Das Ganze gliedert sich in HTML-Code, Frame-Update-Loop, Rendering-System, Raycasting-Engine und Stadtgenerierungslogik
  • Statt trigonometrischer Funktionen oder höherer Mathematik werden nur einfache Algebra und Bitoperationen verwendet
  • Nach der ursprünglichen Veröffentlichung war es etwa zwei Jahre lang einer der beliebtesten Beiträge in der Twitter-Timeline des Autors

HTML und Ausführungsschleife

  • Das HTML besteht nur aus einem Canvas und einem Click-Event
<canvas style=width:99% id=c onclick=setInterval('',t=9)>
  • Die id des canvas wird auf c gesetzt, um in JavaScript kurz darauf zugreifen zu können
  • style=width:99% ist nicht zwingend erforderlich; es funktioniert auch ohne
  • In onclick wird setInterval aufgerufen, um die Update-Schleife zu starten
    • Das Intervall ist auf 9 Millisekunden gesetzt
    • Die Zeitvariable t wird hier ebenfalls mit 9 initialisiert, um Platz zu sparen
  • Wird das Canvas mehrfach angeklickt, laufen mehrere Intervalle parallel und machen die Demo langsamer – ein kleiner Bug

Lesbar ausgeschriebenes JavaScript

  • Die nach dem Klick ausgeführte JavaScript-Payload ist 199 Byte groß
for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a
  • Mit Leerzeichen und Zeilenumbrüchen lässt sich der Ablauf so lesen
c.width = w = 99
++t
for (i = 6e3; i--;)
{
  a = i%w/50 - 1
  s = b = 1 - i/4e3
  X = t
  Y = Z = d = 1
  for(; ++Z<w &
    (Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46 ||
    d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w));)
  {
    X += a
    Y -= b
  }
  c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)
}
  • c.width = w = 99 löscht das Canvas, setzt die Breite auf 99 Pixel und speichert denselben Wert zur Wiederverwendung in w
  • Die Standardhöhe des Canvas beträgt 150; der Bereich darunter bleibt leer
  • ++t erhöht in jedem Frame den Zeitwert und animiert so die Szene
  • for (i = 6e3; i--;) ist die äußere Schleife, die die Helligkeit jedes Pixels bestimmt

Berechnung der Kamerastrahlen

  • Jedes Pixel wird als ein einzelner Strahl behandelt, der von der Kamera ausgeht
  • Die horizontale Komponente wird in a gespeichert
a = i % w / 50 - 1
  • i % w liefert die horizontale Position des aktuellen Pixels; geteilt durch 50 und minus 1 wird sie grob auf einen Wert zwischen -1 und 1 normalisiert
  • Die vertikale Komponente wird in b gespeichert; derselbe Wert landet auch in s für das Hintergrund-Fading
b = s = 1 - i / 4e3
  • Statt eines exakten vertikalen Seitenverhältnisses wird mit i / 4e3 vereinfacht, um Codegröße zu sparen
  • Diese Vereinfachung erzeugt eine kaum wahrnehmbare Schrägstellung, spart aber Bytes
  • 4e3 wurde gewählt, um den Horizont unter die Bildmitte zu verschieben
  • Die Startposition der Kamera nutzt den Zeitwert und erzeugt eine Szene, die sich nach rechts bewegt
X = t
Y = Z = d = 1
  • Y, Z und das für Distanznebel verwendete d werden alle mit 1 initialisiert

Stadtgenerierung und Kollisionsprüfung

  • Die innere Schleife ist der Kern des Raycasting-Systems und bewegt Z vorwärts, bis etwas getroffen wird
for(; ++Z<w &
  • Z wird erhöht, solange es kleiner als w, also 99, ist
  • Gebäude, Gassen und Freiräume zur Meerseite hin entstehen durch die folgende Bedingung
Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46
  • Es wird geprüft, ob der Strahl unterhalb der Höhe an dieser Position liegt, um die Kollision zu bestimmen
  • 6 - verschiebt das Höhenergebnis nach unten in Richtung Mitte und kehrt es um, sodass der Boden unten liegt
  • Die Bedingung in Klammern bestimmt die Form der Stadt
    • 32<Z lässt Platz zwischen Kamera und der ersten Gebäudereihe
    • 27<X%w erzeugt periodische Freiräume und teilt die Stadtblöcke wie Straßen auf
    • Bei negativen Werten ist es immer false, wodurch leere Bereiche wie Meer entstehen
    • X/9^Z/8 nutzt bitweises XOR, um eine zufällig wirkende Verteilung der Gebäudehöhen zu erzeugen
    • Die Divisoren 9 und 8 steuern Gebäudebreite und -tiefe
    • X/9 ist zusammen mit den Zahlen für die Straßenbreite durch 9 teilbar und verhindert so, dass an den Rändern extrem dünne Gebäude entstehen
  • Das Klammerergebnis wird mit 8 multipliziert und per Modulo 46 begrenzt, um den maximalen Höhenbereich zu erzeugen
  • 8 und 46 wurden experimentell gewählt, um unterschiedliche Gebäudehöhen zu erzeugen

Schatten, Textur und Distanznebel

  • Bei einer Kollision übernimmt dieselbe innere Schleife eine zweite Aufgabe und führt eine Prüfung in Richtung der Lichtquelle aus
d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w)
  • d | unterscheidet, ob der aktuelle Strahl von der Kamera ausgeht oder als Strahl in Lichtrichtung auf Schatten prüft
  • Anfangs ist d = 1, daher arbeitet er als Kamerastrahl
  • Nach einer Kollision wird d = Z/w, also kleiner als 1; dadurch ändert sich das Ergebnis der bitweisen OR-Auswertung, die Schleife läuft erneut, und die Schattenprüfung beginnt
  • Kommt es während der Schattenprüfung erneut zu einer Kollision, wird die Schleife verlassen und das betreffende Pixel als Schatten gezeichnet
  • Der Texturwert s wird mit folgendem Ausdruck erzeugt
s = (X&Y&Z)%3/Z
  • Durch bitweises AND auf X, Y und Z sowie den Rest bei Division durch 3 entsteht eine grau wirkende Textur, die an Fenster erinnert
  • Die anschließende Division durch Z lässt weit entfernte Texturen verblassen
  • Um den Strahl in Richtung einer sonnenähnlichen gerichteten Lichtquelle zu schicken, werden a und b beide auf 1 gesetzt
  • d = Z/w ist der Distanznebelwert und wird verwendet, um weit entfernte Gebäude heller zu machen

Pixel zeichnen und Helligkeit darstellen

  • Jedes Pixel wird mit fillRect gezeichnet
c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)
  • i%w ergibt die x-Koordinate, i/w|0 die y-Koordinate
  • Die Helligkeit wird durch Verkleinern der Pixelbreite dargestellt; das ist die zentrale Technik, um mit wenig Code ein Graustufenbild zu erzeugen
  • 1 entspricht einem schwarzen Pixel, daher erzeugt der endgültige Ausdruck die Bildhelligkeit, indem er einen Wert von 1 abzieht
  • d * Z/w kombiniert Schatten- und Distanzeffekte
    • Ohne Schatten bewegt sich der Strahl bis zur maximalen Distanz w, sodass Z/w den Wert 1 annimmt
    • Im Schatten ist Z kleiner als w, wodurch das Ergebnis dunkler erscheint
    • Je näher das lichtblockierende Objekt ist, desto dunkler wird der Schatten, was einen Effekt ähnlich Ambient Occlusion hinterlässt
  • Am Ende wird s addiert, um die Gebäudetextur in die endgültige Helligkeit einzumischen

Nachfolgende Demos und Experimentierwerkzeuge

  • Die Demo wurde bei der Revision 2022 demo party eingereicht und ist auf Pouet zu sehen
  • Damals wurde sie in der falschen Kategorie eingereicht und erreichte deshalb keine hohe Platzierung
  • Später erstellten Xor und andere Coder auf Shadertoy 256-Byte-Shader, die die JavaScript-Version nachbildeten
  • Daniel Darabos erstellte ein Observable-Werkzeug, mit dem sich verschiedene Elemente des Programms in Echtzeit manipulieren lassen
  • Der Code kann auf Dwitter remixt werden; auch in CapJS lässt sich damit experimentieren

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-21
Hacker-News-Meinungen
  • Als verwandtes Material gibt es die Art, wie die Welt von Pitfall für den Atari 2600 aufgebaut ist: https://evoniuk.github.io/posts/pitfall.html
    Prozedurale Generierung im frühen 8-Bit-Spiel Elite: https://procedural-generation.tumblr.com/post/112509130817/e...
    Allgemeiner Artikel zu prozeduraler Generierung: https://en.wikipedia.org/wiki/Procedural_generation
    Ein etwas verwandtes Konzept ist auch die Lazy Evaluation in funktionalen Programmiersprachen: https://en.wikipedia.org/wiki/Lazy_evaluation
    Wenn ein Raytracing-Algorithmus beim Erzeugen eines 2D-Bildes aus 3D-Daten nur die sichtbaren Punkte auswertet, wirkt das ähnlich wie das Konzept der Lazy Evaluation, also „die Auswertung eines Ausdrucks aufzuschieben, bis sein Wert benötigt wird“: https://en.wikipedia.org/wiki/Ray_tracing_(graphics)
    Darüber hinaus fühlt es sich oberflächlich auch grob mit „Beobachtung lässt die Wellenfunktion kollabieren“ verbunden an: https://en.wikipedia.org/wiki/Wave_function_collapse
  • Vom selben Autor gibt es auch 1K Pinball Game in JavaScript: https://frankforce.com/lu1ky-pinball-code-deep-dive/
  • Alcatraz’ Remnants ist ebenfalls eine ähnliche 256-Byte-MS-DOS-Demo und enthält einen YouTube-Link: https://www.pouet.net/prod.php
    Allerdings ist dieses Werk noch beeindruckender, weil es in JavaScript gebaut wurde. JavaScript hat nämlich oft eine schlechtere Codedichte als 16-Bit-x86-Maschinencode
  • Wirklich beeindruckend. Die Informationsdichte, die wir aus so wenig Code wahrnehmen, ist absurd hoch
    Deshalb kommt mir der Gedanke, dass große Sprachmodelle vielleicht nicht die beste Methode sind, die Welt zu modellieren
    • Obfuskierter Code voller Abkürzungen ist wahrscheinlich ebenfalls nicht die beste Methode, die Welt zu modellieren. Trotzdem ist das zweifellos eine beeindruckende Leistung
      Ich wäre schon zufrieden, wenn ich so etwas in etwa 256 Zeilen hinbekäme, und in Wirklichkeit würde ich wahrscheinlich deutlich mehr brauchen
      Visuelle Dinge, ob künstlich oder natürlich, folgen in vielen Fällen Mustern. Sonst wären sie von vornherein schwer zu erkennen. Deshalb lässt sich mathematisch viel damit anfangen. Für Höhentexturen kann man verschiedene Arten von Rauschen oder Mustern verwenden, Fraktale lassen sich ebenfalls interessant einsetzen, für Vegetation und Bäume Fibonacci/Goldener Schnitt, zwischen Skelett-Elementen und Knochen Größenverhältnisse und Ähnliches. Dafür braucht man keine magische Vermutungsmaschine
    • Warum sollte man glauben, dass große Sprachmodelle das Optimum sind?
  • Sehr cool, aber etwas schade ist, dass beim Lesen des Artikels die Schleife ununterbrochen weiterläuft und mein Laptop überhitzt
    • Deshalb war mein Handy in den letzten Minuten also ungewöhnlich warm!
  • Wenn dir so etwas gefällt, wird dir auch #tweetcart auf Twitter gefallen
    Das sind tweetgroße Programme für die virtuelle Konsole Pico-8