BashでのRaycaster実装

 (github.com/izabera)
2 ポイント 投稿者 GN⁺ 2024-12-22 | 1件のコメント | WhatsAppで共有
  • Bashで実装された raycasterで、矢印キーで回転・移動し、qで終了するターミナルベースの pseudo-3D デモ
  • 実装は主に Lode Vandevenne の raycasting チュートリアルを移植したもので、すべての数学計算を浮動小数点なし・64K スケールの整数演算で処理
  • 最大の制約は Bash の性能で、ピクセルごとにコマンドを実行したり、画面状態を配列・文字列で保持したりすると、フレーム時間内に描画するのが難しい
  • ターミナル表示では Unicode の half block と前景色/背景色の 24 ビットカラーを使って縦方向の解像度を実質 2 倍にしているが、隣接ピクセルの色も同時に把握しておく必要がある
  • 現在のロードマップでは fluid movement、decent framerate、parallel rendering、kitty keyboard protocol、sound の初期プロトタイプなどが完了しており、textures、sprites、enemies、particles、multiplayer などは未完了

Bashで作られたターミナル raycaster

  • このプロジェクトは Bash で動作する raycasterで、ターミナル内に pseudo-3D 画面をレンダリングする
  • 操作は矢印キーで回転と移動を行い、qで終了する
  • さらに多くのスクリーンショットと動画は Imgur アルバム にある
  • 実装は主に Lode Vandevenne の raycasting チュートリアル を移植したもの

実装を難しくした制約

  • 最大の問題は Bash が遅いこと
    • ピクセルごとにたった 1 つのコマンドを実行するだけでも、acceptable frame rate を得るのは難しいとしている
    • 画面状態を色の配列として保持しても、任意の配列要素へのアクセスが線形時間なので問題になる
    • 画面状態を長い 1 本の文字列として保持しても、LANG=C でも n 番目の文字へのアクセスが線形時間のため、画面にダンプするために読むだけで 1 フレームより長くかかることがある
  • Bash には 浮動小数点のサポートや数学関数ライブラリへのアクセスがない
    • すべての数学は整数で処理する
    • 整数値は 64K スケールに拡大して計算する
  • ターミナルで 1 文字を 1 ピクセルのように使うと見栄えが良くないため、Unicode の half block を使う
    • 前景色と背景色を別々に指定し、縦方向の解像度を実質 2 倍にする
    • 1 つのセルで 2 色のうち片方だけを更新する方法はない
    • 現在のセルの色を問い合わせる方法もなく、Bash ではそのような問い合わせ自体も遅すぎる
    • そのため、ピクセルを書き込むたびに隣接ピクセルの色を把握しておく必要がある

ターミナルと入出力の問題

  • 低速な言語である Bash でターミナル全体を一度に更新するのは簡単ではない
  • ほとんどのターミナルはビデオゲーム向けに設計されておらず、現在押されているキーの状態を確認できない
    • 通常は押し続けている単一キーの入力しか取得できない
    • 入力リピートは遅くデバウンスされ、連続入力の上限も低いため、1 秒あたり 5〜6 文字程度しか得られない状況が生じる
    • modifier 以外の複数キー同時入力も取得しにくい
    • kitty keyboard protocol がこの問題を解決するとしている
  • 色でターミナルを埋めるには大量のデータが必要
    • 作者の通常のフォントサイズでは毎秒約 10MB I/O が発生する
  • Bash は複数の改行を含む文字列を出力する際に単一の syscall を使わない
    • このプロジェクトでは \n を出力せず、別の方法でカーソルを移動している

FAQと実行条件

  • ウィンドウサイズを変えると表示が崩れる、点滅が激しい、特定のターミナルで見栄えが悪い場合は issue を開いてほしいとしている
  • CPU が極端に熱くなったり、古いコンピューターが遅くなったりする場合は、解像度を下げるか FPS 環境変数を 30 未満に設定するよう案内している
    • Microsoft Defender が性能を大きく低下させることが知られており、無効化を提案している
  • Bash 5.2 未満では動作しない
  • 純粋な Bash だけで書かれたコードではない
    • 起動時に stty を 1 回呼び出して echo を無効化する
    • 終了時に stty を 1 回呼び出して echo を再び有効化する
    • 終了後の一部統計は別のツールで収集する

ロードマップの状態

  • 完了した項目

    • semi-accurate pseudo 3d

      • fluid movement
      • decent framerate
      • parallel rendering
      • 24 bit colours
      • kitty keyboard protocol
      • framerate-independent speed
      • sound、ただし非常に初期のプロトタイプ
      • dynamic wall colours
      • dynamic map、現時点ではイベントで変化しないが、技術的には動的とのこと
      • basic animations effects for walls
      • basic on-screen minimap
      • 未完了の項目

    • mouse support

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

関連記事

1件のコメント

 
GN⁺ 2024-12-22
Hacker News のコメント
  • これは本当にいい。ピクセルごとに一回ずつ echo せずにどうやって描画しているのか気になっていたが、そのやり方がとても賢い。
    ゲームが「本物の」3Dではないので、列ごとに一回だけレイトレーシングを走らせ、空・芝生・実際の物体に相当する数行だけ描けばよい。
    必要な回数だけ「このピクセルを描いて一つ下へ移動する」文字列を文字列の繰り返しで端末に出力するという方式。
    Bash向けではないが、計算資源が限られた別の環境でボクセルレンダリングエンジンを作ってみようかと思っていたので、ここで確実に使えそうなものが見つかりそうだ。
  • MS Batchで書かれたレイキャスターがあるのか気になっていたなら、これもある: https://github.com/nTh0rn/batch-raycaster
  • stty がフォークを必要とするのが惜しい。次のプロジェクトは Bash と rowhammer で必要な ioctl を呼び出し、フォークなしで処理するものになるかもしれない。
  • Bashでこんなことが可能だとは思わなかった。かなり上級レベルで Bash を使いこなせると思ったこともあったが、これは本当に驚きだ。
    実装を理解できるほどの数学力はないが、見ているだけでも楽しい。
  • 私の Bash スクリプトは各種コマンドラインオプションのパースだけで300行も使っているのに、実はその代わりにこんなゲームを見せることもできたんだな :-P
  • いまだにこんな途方もなく遅いシェルに縛られているのが、ずっと理解できない。純粋な狂気のように思える。
    一部のアプリが vt100 のありとあらゆる特殊な挙動を必要とするのは理解できるが、おそらくアプリの90%は単に標準出力と標準エラーに書き込むだけだ。
    テキストを画面にもっと速く表示し、残りの10%は互換モードに入れられるべきではないかと思う。
    • シェルは遅いし、特に Bash はそうだが、その後の話がどうつながるのかはよく分からない。シェルはターミナルエスケープシーケンスの解釈にはまったく関与しておらず、現代のターミナルはかなり速い。
      350列のターミナルでもアニメーションをレンダリングできるし、制約を考えれば非常になめらかに表示される。
      しかもこの記事の前提自体が、Bash はレイキャスティングに向いていない言語だということだ。CSSでバブルソートを書くようなもの。
      「残りの10%を互換モードに入れよう」というのを妨げるものはない。文字列が通常の文字だけを含むか検査して高速パスを使えばよい。
      問題は、ソフトウェアのテキストレンダリングには実際には高速パスがないことだ。依然としてリガチャのような処理をしなければならない。
  • 「bashは遅い。」
    だからスクリプティングに Bash を使わない理由の一つだ。対話的にも使っていない。
    一部の人気 Linux ディストリビューションも Bash をスクリプティングシェルとして避けている。
  • これを作者のフォークなし ps 実装と組み合わせて、ほぼフォークなしの psDoom 実装を作れたらいい。
    冗談はさておき、本当にすばらしい。
  • もちろん、9年前の awk レイキャスターにも名誉ある言及をしておくべきだ: https://github.com/TheMozg/awk-raycaster/tree/master