Vimで検索する6,500個の正規表現で作るBad Apple

 (eieio.games)
1 ポイント 投稿者 GN⁺ 2025-01-13 | 1件のコメント | WhatsAppで共有
  • Vim 内で Bad Apple 動画を再生するため、各フレームを検索クエリに変換し、120x90 の空白グリッド上に検索ハイライトだけで画面を描画
  • 動画は ffmpeg で約 6,500 枚の PNG フレームに分割し、その後 Python で各画像を 0 と 1 の 2D 配列に変換して黒いピクセルを表現
  • Vim の \%l、\%c、\zs、\ze と \| OR パターンを組み合わせ、特定の 行・列範囲の長方形を 1 回の検索でハイライト
  • フレームを長方形の検索パターンへ縮約する過程では、最適解の代わりに上→下マージ、左→右マージ、行ごとの RLE のうち最も短い検索文字列を選ぶ方式を採用
  • マクロが各行の検索パターンを / レジスタに入れて次の行へ移動しながらフレームを送ることで、長いクエリを検索欄に直接貼り付けたときに起きる点滅やフレーム低下を抑制

Vim の検索ハイライトで Bad Apple を再生する

  • 目標は Vim から離れずに Bad Apple 動画を見ること
  • 画面上で実際に変化するのはファイル内容ではなく、Vim の 現在の検索クエリ
  • 出力動画は 120x90 の解像度に制限される
    • 画面サイズの都合でこれ以上大きくするのは難しかった

フレーム抽出と二値化

  • Felixoofed の badapple-frames リポジトリ にある動画と ffmpeg コマンド案を使い、約 6,500 枚の PNG フレームを取得
  • Python コードで各 PNG を 120x90 にリサイズして白黒変換し、ピクセル値が 10 未満なら 1 として扱う
    • 1 は黒いピクセルを意味する
    • 0 は明るいピクセルを意味する
  • 元の動画は 480x360 だったが、ターミナルサイズを測ったうえで 120x90 に縮小
  • text_preview 関数は 0 を ., 1 を # として出力し、変換結果の確認に使われる

ターミナル文字をピクセルのように見せる

  • Vim ファイル内にテキストグリッドを作り、特定の文字を検索すると、検索結果のハイライトが画像のように見える
  • デフォルトの検索ハイライトは青で鮮明ではないため、hi Search cterm=NONE ctermfg=grey ctermbg=grey 設定を使用
    • 検索された文字の前景色と背景色を同じグレーに揃え、ブロックのように見せる
  • 一般的なフォントでは文字が縦長で、ピクセルが長方形に見えてしまう
  • Square フォントを使い、ターミナル文字を正方形に近づけてグリッドをより自然に見せる

長方形を検索パターンで描く

  • Vim の検索は特定の 行番号と列番号を基準にマッチできる
  • 例のパターン \%>5c\%<15c\%>4l\%<9l は、5〜15 列・4〜9 行の長方形にマッチする
  • 複数の長方形は \| で OR 接続し、1 つの検索文字列で同時にマッチ可能
  • この機能により、各フレームの黒いピクセルを複数の 長方形集合へ分解する問題に置き換えられる

フレームを長方形へ縮約するアルゴリズム

  • 90x120 グリッドは約 10,000 ピクセルあるため、ピクセル単位でパターンを作ると検索文字列が数万文字に達することがある
  • 基本テストでは Vim の検索自体は高速だが、検索文字列が長すぎるとフレームレートが低下する
  • 最初に書いた方法は、行単位で 1 の連続区間を見つけ、次の行の区間と重なれば長方形としてマージするもの
    • 最初の行で 1 の連続区間を探す
    • 次の行の区間と前の行の区間の重なりを探す
    • マージした長方形の面積が各行単独の面積より大きければマージする
    • 可能なら既存の長方形に新しい区間を継続してマージする
  • この方法は 1 行先までしか見ないため、最適ではない
    • その時点では悪いマージに見えても、後続の行まで考えれば良いマージになるケースを取りこぼす

ボトルネックを避けるための 3 つのパターン生成方式

  • 多くの検索文字列は 500〜2,000 文字程度だったが、一部のフレームでは 10,000 文字を超える検索文字列が生成された
  • 長い検索文字列はフレームレートを約 40 FPS から一桁台まで落とした
  • 検索文字列の長さは性能の完全な代理指標ではないが、このケースでは似た長さのパターンを OR で多数つなぐことで、パターン数と検索時間がともに増える可能性がある
  • 最適な一般アルゴリズムを探す代わりに、3 つの単純なアルゴリズムをすべて実行し、最も短い検索パターンを選択
    • 上→下マージ方式
    • 左→右マージ方式
    • 行ごとの RLE 方式
  • 選択回数は次の通り
    • 元の方式である上→下マージ: 1,110 回
    • 左→右マージ: 2,239 回
    • 単一行 RLE: 3,300 回
  • RLE が最も頻繁に選ばれたが、悪いケースでは極端に不利になるため単独使用は避けた

Vim 内でフレームを送る

  • Vim 上部中央のウィンドウには、90 行 x 120 列の 空白ファイルを置く
    • 行・列基準で検索するため、実際の文字は不要
  • 左右には画像を中央に置くための空バッファを配置
  • 下部ウィンドウには約 6,500 個の検索パターンを行単位で置く
  • マクロは現在行の検索パターンを読み取り、検索レジスタに入れて次の行へ移動する

  • 使用したマクロ

    • マクロは "ay$:let @/=@a^M+ の形
    • 動作は次の通り
    • "a: レジスタ a を対象に使う
    • y$: 現在行の末尾までコピー
    • :let @/=@a: 検索レジスタ / をレジスタ a の内容に設定
    • ^M: コマンド実行
    • +: 次の行頭へ移動
    • このマクロをレジスタ q に記録しておけば、1500@q で 1,500 フレームを可能な限り高速に送れる
    • /^Ra^M のように検索欄へ長いクエリを直接貼り付けると、検索欄が数千文字のクエリに合わせて広がり、点滅やフレーム低下が起きることがある
    • let @/=@a で検索レジスタを直接設定すれば、この問題を回避できる

制限と公開コード

  • Vim の行・列検索機能を使っているため、伝統的な正規表現だけで構成されているとは言い切れないという反論はありうる
  • フレームレートを安定的に維持するための処理はない
    • 動画全体ではフレームレートに多少の揺れがある
  • それでも、検索クエリだけで Vim 内で動画を再生する汎用的な解法に近い結果になった
  • コードは整理されていないが、vim-badapple リポジトリ で確認できる

関連記事

1件のコメント

 
GN⁺ 2025-01-13
Hacker Newsのコメント

  • nolenなら何かを1000倍にスケールさせると思ってた :))) 以前に似たような手法を試したことはあるけど、全部バラバラだったし、1日でやったなんてことは絶対になかった。興味があれば:
    Bad Matrix(tputでターミナルにブロックを出力): https://www.evalapply.org/posts/bad-matrix/
    Animating Text Art in Javascript(固定グリッドにテキストを描いてパラパラ漫画のようにアニメーション): https://www.evalapply.org/posts/animate-text-art-javascript/...
    oxo(三目並べの盤面をターミナル向けに整形して出力し、勝ち/負け/引き分けの結果を正規表現でマッチ): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
    それでもあのBad Appleが最高

  • Bad Appleに本当にハマるきっかけになった技術デモは、NESで動作するバージョンだった
    https://somethingnerdy.com/downloads/
    自分のEverdriveで動かした動画はこちら
    https://inversethought.com/jordi/video/badapple.mp4
    音声まで完全に再生される。データは約1GBで、普通のゲームが数百KBを超えず、CPUには計算用の8ビットレジスタが3つしかないシステムでこれをやっている

    • すごい。少しだけNES開発をやったことがある立場からすると、グラフィックス性能を合わせ込むのは簡単じゃなかったはず。普通は1ラインにスプライトが数個あるだけでNESがスプライトを「溶かし」始めるけど、正確な用語はわからない
      スプライトの代わりに背景タイルマップを使ったのか気になる。それでもグラフィックス帯域という意味ではかなり印象的。
      「完全なオーディオ再生レート(44.2kHz)」とあるけど、音がそこまでクリアなのも驚き。カートリッジの拡張機能なのだろうか。記憶ではNESのPCMチャンネルはそのビットレートにまったく届かず、サンプルサイズも8ビットだった気がする
    • どの部分を面白いと思ったか次第では、NESで実装した似たようなBad Appleも気に入るかもしれない。追加の難所として、Super Mario Bros.のACE経由で実行し、すべてのデータをコントローラーからストリーミングしている
      https://www.youtube.com/watch?v=lfG8DbxFibY
      一緒に作られた解説動画もある
      https://www.youtube.com/watch?v=Wa0u1CjGtEQ
    • 本当にすごいが、もしこの制作について記事にまとめたものがあるなら読んでみたい

  • Vimマクロを「再生可能」にするために最後で次の行へ移動させる代わりに、次のコマンドで各行ごとにマクロを1回ずつ実行することもできる
    :%norm @q

    • うわ、今日学んだ。これを知らなかったのはかなり意外だ
      昔Vimゴルフをやっていたころは、たいていマクロを再帰的に作っていた。マクロを録画して、最後を+@qで終える。つまり次の行に移動してからマクロを再実行する形。そうするとマクロを1回実行するだけで全行を走査できる
      キー入力数の面ではとても効率的だけど、実際には考えにくいし手にもなじまないので、あまり多用することはない。それでもゴルフ用としては面白いテクニック

  • 先月このGovee Curtain Lightsがセール中だった
    https://us.govee.com/products/govee-curtain-lights
    ここにアニメーションGIFをアップロードできるはず。なので「Bad Apple」のGIFを作る作業をカンバンボードに追加したけど、デバイスのメモリがどれくらいあるのか、どの程度うまく動くのかはまだわからない
    ときどきRemmy Scarletが翼を広げる場面は今でも鳥肌が立つ

    • Twinklyの照明でこれを試したことがあるが、残念ながら照明側のメモリが足りず、数秒以上は再生できなかった
    • 64x32解像度のBad Apple GIFがあるが、サイズは1MB弱
      https://ezgif.com/ にはかなり助けられた

  • Bad Appleは飽きない。インターネット最高の作品だ。そしてほとんど毎回、どうして自分があのアイデアを先に思いつかなかったのかと少し嫉妬する
    このブログの脚注の実装も本当に気に入った。たぶん拝借することになりそう

    • その脚注は才能ある友人Jakeのサイト(https://jakelazaroff.com/)から持ってきたもの。以前ここで彼の作品を見たことがあるかもしれない
      大きい画面ではサイドノートとして表示され、小さい画面ではクリックすると展開するインライン脚注に切り替わる。どうぞ自由に使ってほしい

  • 長方形最小化問題について言うと、ここの問題はStackOverflowで議論されていたものとは違って見える。SOのスレッドは重ならない長方形分割を扱っているが、このVimプロジェクトは重なりを許している
    なので最適解を見つける問題はずっと簡単である可能性もありそう

    • アルゴリズムの観点では実は逆。重なりを許す最小被覆問題はNP困難で、重なりを許さない最小分割問題には多項式時間アルゴリズムがある。FranzblauとKleitmanによる1984年の論文「An Algorithm for Covering Polygons with Rectangles」を参照: https://core.ac.uk/download/pdf/82333912.pdf
      もちろんこれは学術的な余談にすぎず、午後のプロジェクトとして何かを動かすという状況で片方が実際により簡単という意味ではないかもしれない
    • いい指摘だ。そう、長方形が重なれるという事実を完全に見落としていた。このプロジェクトはたぶんここで終わりにすると思うし、今の解法にもかなり満足しているが、この点が問題をかなり単純化しているのは確かだと思う

  • 並列な候補解ジェネレーターは本当にいいアイデアで、必ずしも最強のアルゴリズムを作る必要はないと気づくまで毎回かなり時間がかかる。もう少し手を入れればどんなケースにも通用する解法を作れそうだと思ってしまうからだ

    • プロトタイプを十分速く作るコツとしては、たぶんいちばん好きなやり方だ。動くたびに楽しい
      ただ、「完璧な」ものを使う代わりに一歩引いてこの方法を使えると気づくのが本当に難しい、という点には同意する

  • かなりいい。発想が素晴らしい。元になったゲーム群もなかなか良いし、弾幕は催眠的だ

  • DoomやBad Appleを思いもよらない方法で動かす人たちは本当にすごい
    妊娠検査薬でDoomを動かしたような興味深い例もある

    • それにはあまり強く同意できない。実際には妊娠検査薬の筐体の中に任意のマイクロコントローラーを入れてDoomを動かした、というのに近かった

  • 2006年のサッカーワールドカップを職場で見ていたのを思い出す。自宅サーバーにsshでログインして、ターミナルで試合を見られた
    ほかの方法で見るには帯域が足りなかった