Bad Apple in Vim mit 6.500 regulären Ausdrücken für die Suche

 (eieio.games)
1 Punkte von GN⁺ 2025-01-13 | 1 Kommentare | Auf WhatsApp teilen
  • Um das Video Bad Apple innerhalb von Vim abzuspielen, wurde jedes Frame in eine Suchanfrage umgewandelt, und der Bildschirm wurde auf einem 120x90-Leerzeichenraster ausschließlich mit Suchhervorhebungen gezeichnet
  • Das Video wurde mit ffmpeg in etwa 6.500 PNG-Frames zerlegt, danach wandelte Python jedes Bild in ein 2D-Array aus 0 und 1 um, um schwarze Pixel zu markieren
  • Durch die Kombination von Vims \%l, \%c, \zs, \ze und dem OR-Muster \| lassen sich bestimmte Zeilen-/Spaltenbereichs-Rechtecke mit einer einzigen Suche hervorheben
  • Das Reduzieren eines Frames auf rechteckige Suchmuster nutzt keine optimale Lösung, sondern wählt zwischen Zusammenführen von oben nach unten, von links nach rechts und zeilenweisem RLE jeweils den kürzesten Suchstring
  • Ein Makro schreibt das Suchmuster jeder Zeile in das Register / und springt zur nächsten Zeile, um das nächste Frame anzuzeigen; so werden Flackern und Framedrops reduziert, die beim direkten Einfügen langer Queries in die Suchleiste entstehen

Bad Apple mit Vim-Suchhervorhebung abspielen

  • Das Ziel ist, das Video Bad Apple anzuschauen, ohne Vim zu verlassen
  • Was sich auf dem Bildschirm tatsächlich ändert, ist nicht der Dateiinhalt, sondern Vims aktuelle Suchanfrage
  • Das resultierende Video ist auf eine Auflösung von 120x90 begrenzt
    • Wegen der Bildschirmgröße ließ es sich kaum größer machen

Frames extrahieren und binarisieren

  • Mit dem Video aus Felixoofeds badapple-frames-Repository und dem dort vorgeschlagenen ffmpeg-Befehl wurden rund 6.500 PNG-Frames erzeugt
  • Python-Code skaliert jedes PNG auf 120x90, wandelt es in Schwarzweiß um und behandelt Pixelwerte unter 10 als 1
    • 1 steht für ein schwarzes Pixel
    • 0 steht für ein helles Pixel
  • Das Originalvideo hatte 480x360, wurde aber nach dem Messen der Terminalgröße auf 120x90 verkleinert
  • Die Funktion text_preview gibt 0 als ., 1 als # aus, um das Konvertierungsergebnis zu prüfen

Terminalzeichen wie Pixel aussehen lassen

  • Wenn man in einer Vim-Datei ein Textraster anlegt und nach bestimmten Zeichen sucht, kann die Suchhervorhebung wie ein Bild wirken
  • Die Standardsuchhervorhebung ist blau und deshalb nicht klar genug; verwendet wurde stattdessen hi Search cterm=NONE ctermfg=grey ctermbg=grey
    • Vorder- und Hintergrundfarbe der gefundenen Zeichen werden auf dasselbe Grau gesetzt, damit sie wie Blöcke aussehen
  • Normale Schriftarten sind vertikal gestreckt, sodass Pixel rechteckig wirken
  • Mit der Schriftart Square wirken Terminalzeichen eher quadratisch, wodurch das Raster natürlicher aussieht

Rechtecke mit Suchmustern zeichnen

  • Vims Suche kann anhand bestimmter Zeilennummern und Spaltennummern matchen
  • Das Beispielmuster \%>5c\%<15c\%>4l\%<9l matcht ein Rechteck zwischen den Spalten 5–15 und den Zeilen 4–9
  • Mehrere Rechtecke lassen sich mit \| per OR verknüpfen und gleichzeitig in einem einzigen Suchstring matchen
  • Dadurch wird das Problem darauf reduziert, die schwarzen Pixel jedes Frames in eine Menge von Rechtecken zu zerlegen

Algorithmus zum Reduzieren von Frames auf Rechtecke

  • Das 90x120-Raster hat etwa 10.000 Pixel; erstellt man Muster pro Pixel, kann der Suchstring auf Zehntausende Zeichen anwachsen
  • In Basistests ist Vims Suche selbst schnell, aber zu lange Suchstrings verringern die Framerate
  • Der erste Ansatz suchte zeilenweise zusammenhängende 1-Bereiche und verschmolz sie zu Rechtecken, wenn sie sich mit Bereichen der nächsten Zeile überlappten
    • In der ersten Zeile werden zusammenhängende 1-Bereiche gesucht
    • Überlappungen mit Bereichen der nächsten Zeile werden ermittelt
    • Wenn die Fläche des zusammengeführten Rechtecks größer ist als die Fläche der einzelnen Zeilen für sich, wird zusammengeführt
    • Wenn möglich, werden neue Bereiche weiter an bestehende Rechtecke angehängt
  • Dieser Ansatz ist nicht optimal, weil er nie weiter als eine Zeile im Voraus schaut
    • Er verpasst Fälle, in denen ein zunächst schlechtes Merge unter Einbeziehung späterer Zeilen sinnvoll wäre

Drei Methoden zur Mustergenerierung gegen Engpässe

  • Viele Suchstrings lagen bei 500–2.000 Zeichen, aber für manche Frames wurden Suchstrings mit mehr als 10.000 Zeichen erzeugt
  • Lange Suchstrings ließen die Framerate von etwa 40 FPS auf einstellige Werte fallen
  • Die Suchstringlänge ist kein perfekter Proxy für die Performance, aber in diesem Fall können viele OR-verknüpfte Muster ähnlicher Länge sowohl die Anzahl der Muster als auch die Suchzeit erhöhen
  • Statt nach einem optimalen allgemeinen Algorithmus zu suchen, werden drei einfache Algorithmen ausgeführt und das kürzeste Suchmuster ausgewählt
    • Zusammenführen von oben nach unten
    • Zusammenführen von links nach rechts
    • zeilenweises RLE
  • Die Auswahlhäufigkeiten waren wie folgt
    • ursprüngliche Methode, Zusammenführen von oben nach unten: 1.110-mal
    • Zusammenführen von links nach rechts: 2.239-mal
    • RLE pro Einzelzeile: 3.300-mal
  • RLE wurde am häufigsten gewählt, kann aber im schlechtesten Fall sehr schlecht ausfallen und wird daher nicht allein verwendet

In Vim Frames weiterschalten

  • Im oberen mittleren Vim-Fenster liegt eine Leerdatei mit 90 Zeilen x 120 Spalten
    • Da anhand von Zeilen und Spalten gesucht wird, werden keine tatsächlichen Zeichen benötigt
  • Links und rechts befinden sich leere Buffer, um das Bild mittig zu platzieren
  • Im unteren Fenster stehen rund 6.500 Suchmuster zeilenweise
  • Das Makro liest das Suchmuster der aktuellen Zeile aus, schreibt es ins Suchregister und springt dann zur nächsten Zeile

  • Verwendetes Makro

    • Das Makro hat die Form "ay$:let @/=@a^M+
    • Es arbeitet wie folgt
    • "a: verwendet Register a
    • y$: kopiert bis zum Ende der aktuellen Zeile
    • :let @/=@a: setzt das Suchregister / auf den Inhalt von Register a
    • ^M: führt den Befehl aus
    • +: springt an den Anfang der nächsten Zeile
    • Wenn dieses Makro in Register q gespeichert wurde, kann man mit 1500@q 1.500 Frames so schnell wie möglich abspielen
    • Fügt man eine lange Query wie /^Ra^M direkt in die Suchleiste ein, wächst das Suchfenster auf Tausende Zeichen an, was Flackern und Framedrops verursachen kann
    • Mit let @/=@a wird das Suchregister direkt gesetzt und dieses Problem vermieden

Grenzen und veröffentlichter Code

  • Weil Vims Zeilen-/Spaltensuche verwendet wurde, kann man einwenden, dass dies nicht ausschließlich aus traditionellen regulären Ausdrücken besteht
  • Es gibt keine Logik, um die Framerate stabil zu halten
    • Über das gesamte Video hinweg schwankt die Framerate teilweise
  • Trotzdem wurde ein Ergebnis erreicht, das einer allgemeinen Lösung zum Abspielen von Videos in Vim nur mit Suchanfragen nahekommt
  • Der Code ist nicht aufgeräumt, kann aber im vim-badapple-Repository eingesehen werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-01-13
Hacker-News-Kommentare

  • Von nolen hatte ich erwartet, dass er so etwas um den Faktor 1000 größer macht :))) Ich habe früher ähnliche Techniken ausprobiert, aber jeweils separat – und ganz sicher nicht an nur einem Tag. Falls es interessiert:
    Bad Matrix (Blöcke mit tput ins Terminal ausgeben): https://www.evalapply.org/posts/bad-matrix/
    Animating Text Art in Javascript (Text in ein festes Raster ausgeben und wie ein Daumenkino animieren): https://www.evalapply.org/posts/animate-text-art-javascript/...
    oxo (ein Tic-Tac-Toe-Brett formatiert im Terminal ausgeben und Sieg/Niederlage/Unentschieden per Regex abgleichen): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
    Trotzdem ist dieses Bad Apple das Beste

  • Die Tech-Demo, die mich wirklich zu Bad Apple gebracht hat, war die Version, die auf dem NES läuft
    https://somethingnerdy.com/downloads/
    Hier ist ein Video davon auf meinem Everdrive
    https://inversethought.com/jordi/video/badapple.mp4
    Sogar der Ton ist vollständig dabei. Die Daten sind etwa 1 GB groß, und das auf einem System, bei dem normale Spiele nicht über ein paar Hundert KB hinausgehen und die CPU nur drei 8-Bit-Register für Berechnungen hat

    • Cool. Als jemand, der ein wenig NES-Entwicklung gemacht hat, stelle ich mir vor, dass es nicht leicht war, die Grafikleistung hinzubekommen. Normalerweise fängt das NES schon bei ein paar Sprites pro Zeile an, Sprites „wegzuschmelzen“ – den genauen Begriff kenne ich nicht
      Ich frage mich, ob statt Sprites die Background-Tilemap verwendet wurde. Auch das wäre in puncto Grafikbandbreite ziemlich beeindruckend
      Dort steht „volle Audio-Abtastrate (44,2 kHz)“, und es ist erstaunlich, dass der Klang so klar ist. Ich frage mich, ob das eine Funktion ist, die die Cartridge erweitert. Soweit ich mich erinnere, kommt der PCM-Kanal des NES bei Weitem nicht an diese Bitrate heran, und die Sample-Größe war wohl auch 8 Bit
    • Je nachdem, welcher Teil dich fasziniert hat, könnte dir auch ein ähnliches Bad Apple auf dem NES gefallen. Als zusätzliche Schwierigkeit läuft es über ACE in Super Mario Bros., und sämtliche Daten werden über den Controller gestreamt
      https://www.youtube.com/watch?v=lfG8DbxFibY
      Es gibt auch ein begleitendes Erklärvideo
      https://www.youtube.com/watch?v=Wa0u1CjGtEQ
    • Wirklich cool; falls es dazu irgendwo eine schriftliche Zusammenfassung gibt, würde ich sie gern lesen

  • Den Teil am Ende, der zur nächsten Zeile springt, damit man das Vim-Makro „erneut abspielen“ kann, könnte man auch mit folgendem Befehl erledigen, der das Makro einmal pro Zeile ausführt
    :%norm @q

    • Wow, heute gelernt. Ich bin ziemlich überrascht, dass ich diesen Trick nicht kannte
      Früher beim Vim-Golfen habe ich Makros meistens rekursiv gebaut. Man zeichnet ein Makro auf und beendet es mit +@q. Also erst zur nächsten Zeile springen und dann das Makro erneut ausführen. Wenn man das Makro dann einmal startet, läuft es über alle Zeilen
      In Bezug auf die Anzahl der Tastendrücke ist das sehr effizient, aber praktisch ist es schwer zu durchdenken und geht nicht gut in die Finger, daher nutzt man es nicht oft. Für Golf ist es aber eine lustige Technik

  • Letzten Monat waren diese Govee Curtain Lights im Angebot
    https://us.govee.com/products/govee-curtain-lights
    Soweit ich weiß, kann man dort animierte GIFs hochladen. Also habe ich das Erstellen eines „Bad Apple“-GIFs auf mein Kanban-Board gesetzt, weiß aber noch nicht, wie viel Speicher das Gerät hat und wie gut es laufen wird
    Die Szene, in der Remmy Scarlet ihre Flügel ausbreitet, jagt mir manchmal immer noch einen Schauer über den Rücken

    • Ich habe das mit Twinkly-Leuchten ausprobiert, aber leider reichte der Speicher auf der Lichtseite nicht, um es länger als ein paar Sekunden laufen zu lassen
    • Ich habe ein Bad-Apple-GIF mit 64x32 Auflösung, es ist knapp unter 1 MB groß
      https://ezgif.com/ war dabei eine große Hilfe

  • Bad Apple wird nie langweilig. Es ist das Beste im Internet. Und fast jedes Mal, wenn ich es sehe, bin ich ein bisschen neidisch, dass ich nicht zuerst auf diese Idee gekommen bin
    Auch die Fußnoten-Implementierung in diesem Blog gefällt mir wirklich gut. Die werde ich mir wohl ausleihen

    • Diese Fußnoten stammen von der Website meines talentierten Freundes Jake (https://jakelazaroff.com/). Vielleicht hast du seine Arbeit hier früher schon einmal gesehen
      Auf großen Bildschirmen erscheinen sie als Randnotizen, auf kleinen Bildschirmen werden sie zu Inline-Fußnoten, die sich per Klick aufklappen. Nimm sie dir ruhig

  • Beim Problem der Rechteckminimierung scheint das Problem hier ein anderes zu sein als das, das auf StackOverflow diskutiert wurde. Der SO-Thread behandelt eine nicht überlappende Rechteckzerlegung, während dieses Vim-Projekt Überlappungen erlaubt
    Daher könnte es gut sein, dass das Finden der optimalen Lösung deutlich einfacher ist

    • Aus algorithmischer Sicht ist es tatsächlich umgekehrt. Das Minimum-Cover-Problem mit erlaubten Überlappungen ist NP-schwer, während das minimale Zerlegungsproblem ohne Überlappungen einen polynomiellen Algorithmus hat. Siehe das Paper von Franzblau und Kleitman aus dem Jahr 1984, „An Algorithm for Covering Polygons with Rectangles“: https://core.ac.uk/download/pdf/82333912.pdf
      Natürlich ist das nur eine akademische Randbemerkung und heißt nicht unbedingt, dass die eine Seite in der Praxis wirklich einfacher ist, wenn man bei einem Nachmittagsprojekt einfach etwas zum Laufen bringen will
    • Guter Punkt. Stimmt, ich hatte völlig übersehen, dass die Rechtecke überlappen dürfen. Dieses Projekt werde ich wahrscheinlich dabei belassen, und mit der aktuellen Lösung bin ich ziemlich zufrieden, aber ja, ich denke, das vereinfacht das Problem erheblich

  • Ein paralleler Generator für Kandidatenlösungen ist eine wirklich gute Idee, aber ich brauche jedes Mal lange, um zu begreifen, dass man nicht unbedingt den stärksten Algorithmus bauen muss. Denn man denkt immer, mit nur ein bisschen mehr Feinschliff könnte man eine Lösung bauen, die in allen Fällen funktioniert

    • Das ist wahrscheinlich mein liebster Trick, um Prototypen schnell genug zu machen. Es macht jedes Mal Spaß, wenn es funktioniert
      Ich stimme aber zu: Es ist wirklich schwer zu erkennen, dass man einen Schritt zurücktreten und diesen Ansatz verwenden kann, statt die „perfekte“ Lösung zu bauen

  • Ziemlich cool. Schöne Kreativität. Die Spiele, auf denen das basiert, sind auch ziemlich ordentlich, und Bullet Hell ist hypnotisch

  • Leute, die Doom oder Bad Apple auf völlig unerwartete Weise ausführen, sind wirklich großartig
    Es gibt auch interessante Beispiele wie Doom auf einem Schwangerschaftstest

    • Da kann ich nur schwer zustimmen. Im Grunde war das eher so, dass man einen beliebigen Mikrocontroller in das Gehäuse eines Schwangerschaftstests gesteckt und darauf Doom laufen ließ

  • Das erinnert mich daran, wie ich die Fußball-WM 2006 bei der Arbeit geschaut habe. Ich konnte mich per ssh auf meinem Heimserver einloggen und das Spiel im Terminal ansehen
    Für jede andere Art des Schauens reichte die Bandbreite nicht