Minecraftの「Bad Apple!!」
(purplesyringa.moe)- Minecraftの遅いエンジン上で、Bad Apple!! を原作と同じ 512×384解像度、20fps、グレースケールでリアルタイム再生するよう作られた実装
- 核となるのは、
LOADモードの structure block が自分自身を次のフレームの構造物に置き換え、位相差を持たせたクロックで redstone の 10Hz 制限を超える方式 - ブロック1つをピクセル1つとして使うと768チャンクを20Hzで更新する必要があるため、リソースパックの カスタムテクスチャ・モデル・blockstate で1ブロックがより多くの画面情報を表せるようにして削減
- ボトルネックは redstone や照明より
setBlockとイベント処理にあり、デルタ符号化 と頻繁に変わる 4×4 スプライト置換で更新量を削減 - 最終品質は6色グレースケール、ブルーノイズディザリング、非可逆圧縮ノイズ補正で磨き込まれたが、30fpsの原作を20fpsに落とす問題は完全には解決できなかった
原作に近い再生のための条件
- Minecraft内で Bad Apple!! をできる限り原作に近く再生することが目標だった
- 映像は20fpsで再生される
- 解像度は原作アニメーションと同じ 512×384
- 白黒ではなく グレースケール
- 現代的なCPUとGPUでは録画後に速度を上げるのではなく、実際に20fpsで見られる
- コマンドブロックは使わない
- 簡単な抜け道は実装条件から除外した
- MODは実装方式としては使わず、低スペック環境テスト用の最適化MODのみ許可
- コマンドブロック、
/setblock、データパックは使用しない - アニメーションテクスチャも使用しない
- 低スペックな環境では VulkanMod または Sodium が必要な場合がある
- C2ME は自動保存機能のため性能低下を引き起こすので避けるべき
既存実装がぶつかった限界
- 以前の Bad Apple!! 実装の多くは、小さな画面や遅いレンダリングにとどまっていた
- catlord5 の試みは 512×384 と 30fps を達成したが、レンダリングは約40倍遅かった
- 一部の redstone ベースのリアルタイム実装は 5fps や低解像度レベルだった
- Minecraftはシミュレーションエンジンだけでなくレンダリングエンジンも遅く、チャンク数が増えるほど負荷が大きくなる
- 16×16×16チャンクは内容に関係なく再レンダリングのコストが高い
- 画面がまたがるチャンク数を減らすことが重要
- redstone は実用的なクロック生成器が通常 10Hz信号 を出すため、20fps再生にそのまま使うのは難しい
- redstone dust は遅延のない主要構成要素だが、性能面で負担が大きい
データ保存方式の実験
- hopper line 方式は、チェストに保存したアイテムを hopper で取り出し comparator で読む典型的な保存方式
- hopper はアイテム転送間隔が0.4秒なので最大フレームレートは 2.5fps
- 20fpsには複数の hopper を並列に構成する必要があり、タイリングとシミュレーションコストが問題になる
- jukebox と music disc で 1〜15 の値を読み ほぼ4ビット を保存する方法も試した
- ビットを時間軸に展開すれば hopper 2つで 20fps を狙える
- しかしビットシフトに必要な redstone ロジックと dust が遅く、プロトタイプでも性能不足だった
- repeater delay line は、ピクセルごとに repeater ラインを置いて時間に合わせて値を出す単純な方式
- 1×1ピクセルのタイル化は可能
- 目標よりはるかに小さい既存実装でも20倍の高速化が必要だったため、十分ではなかった
structure block でフレームを送る
- 構造ブロック(structure block) は
SAVEで領域を保存し、LOADで別の位置に読み込める- サバイバルで入手はできないが、コマンドブロックのように1コマンドですべてを置き換えるわけではない
- redstone 信号で有効化できる
- 核心は、
LOADstructure block が 自分自身と重なる領域 を読み込める点- 現在の structure block を次の structure block に置き換えると、有効化のたびに次のフレームを読み込む構造になる
- 単純に置き換えると、新しい structure block がすぐ周囲の redstone 信号を検知して再帰的に有効化される
- この再帰は Minecraft のハードリミットに達するまで続く
- redstone dust の電源解除処理も終わる前に止まり、異常な電源状態が残る
- repeater で 1 redstone tick の遅延 を入れて再帰的な有効化を防ぐ
- 構造物は
/tick freeze状態で作成し、repeater がオフの状態で保存する必要がある - 読み込み後、1 redstone tick 後に次の構造へ進む
- 構造物は
20fpsを合わせる tick 処理
- Minecraftには game tick と redstone tick がある
- ゲームエンジンは20Hzで物理を再計算する
- redstone 構成要素は一般に0.1秒単位、つまり10Hzで更新を予約する
- 実際のイベントは0.05秒間隔で処理され、ユーザー入力のタイミングによっては redstone の反応もその位相に合わせてずれることがある
- 20fps を作るために4つの構造を使用する
- 赤・黄の構造が1つの10Hzクロックを形成する
- 青・緑の構造が別の10Hzクロックを形成する
- 2つのクロックを異なる位相で開始すると、同じ位置に4色が 20Hz で交互に表示される
- 2つのクロックを安定して位相差つきで開始するため、ピストンが redstone block を押す際に、直接のユーザー入力では3 game tick かかる古いバグを利用した
チャンク数を減らすリソースパック技法
- ブロック1つをピクセル1つとして使うと、512×384画面は縦24チャンク、横32チャンクになる
- 合計 768チャンク を20Hzで継続更新する必要がある
- vanilla の最大描画距離32チャンクとも噛み合い、現実的ではない
- リソースパックのカスタムテクスチャで複数ブロックのテクスチャを変え、1ブロック内に複数の サブピクセル を入れる
- 16種類のブロック変形は4ビットに相当する
- 256ブロックと追加色を使えば、白黒ではなくグレースケールを表現できる
- この方式でブロック解像度を4分の1にして 256×192ブロック で表現した
- 画面更新チャンク数は192個まで減る
- それでも20Hz更新にはなお大きな負荷が残る
レンダリングキューとデルタ符号化
- Minecraft のレンダリングエンジンはプレイヤー周辺のチャンク更新を優先処理する
- 複数スレッドが同時にチャンクを生成し、更新キューからプレイヤーに近いチャンクを先に取り出す
- 近い N 個のチャンクが20Hzで継続更新されると、そのチャンクだけが処理され、残りは描画されない可能性がある
- Spark で確認したボトルネックは、redstone や照明ではなく一般的な更新処理だった
- 特に
setBlockとイベントハンドラが問題だった
- 特に
- 解決策は 更新数の削減 であり、フレーム間で変化したブロックだけを更新するデルタ符号化を適用した
- 大半のフレームでは変化量が大きくないため、理論上は性能改善の余地がある
- structure block は一度に 48×48×48 ブロックまでしか読み込めないため、画面を 6×4個の48×48サブスクリーン に分割した
- 初期プロトタイプは1回の実行に約7分かかり、
/tick freeze、24個のボタン、/tick unfreezeが必要だったが、動作はした- デルタ符号化だけではまだ十分に速くなかった
モデルと blockstate の最適化
- Minecraft のモデルはブロック形状を cuboid で定義し、座標は
(0,0,0)から(16,16,16)の範囲を超えて -16から32まで 指定できる- 適切に設定すれば、1ブロックが最大3倍大きいようにレンダリングされ、9ブロック領域を置き換えられる
- すべての組み合わせを処理するだけのブロック数は足りないため、完全に黒い 6×6 領域のような頻出ケースでのみ有効
- 約600個の利用可能ブロックのうち256個は基本サブピクセル表現に使い、残りの一部を最適化に活用した
- 最終アプローチは画面を2×2ブロックのセルに分け、各セルの4×4ピクセルスプライトを単一ブロックで置き換える候補にする方式
- 連続する2フレームの差分を計算する
- 変化したセルの前後バージョンにスコアを加える
- 変化の速い場面でより多くのピクセルが変わるセルに高いスコアを与える
- スコアの高いスプライトから利用可能ブロックを割り当てる
- 基本ブロック数の限界を超えるため
blockstatesを調査したoak_logのように属性によって別モデルを選べるgrindstoneのように複数の属性組み合わせをキーにできる
- 標準アセットから blockstate のバリエーションを抽出し、制御不可能な属性を除外した結果、アクセス可能なモデル数は約 600個から1700個 に増えた
- 色数は6色まで増えた
- 最適化済みブロック数は400個まで増えた
オーディオと開始装置
- 音楽はリソースパックで music disc の音を差し替える方式で処理した
- ディスク再生時間は音声を差し替えても固定
- “Bad Apple!!” の長さに最も近い Relic ディスクを使用
assets/minecraft/lang/en_us.jsonを変更し、ゲーム内字幕が “Now Playing: Bad Apple!!” と表示されるようにした
- ボタン、dropper、hopper、jukebox を接続し、ボタン1回でディスクが jukebox に入って再生されるよう構成した
- 再生が終わると hopper がディスクを再び dropper に戻し、次の再生に備える
- quasiconnectivity のため、jukebox が再生中に出す redstone 信号が hopper と dropper の状態を乱していた
- ボタン入力時に dust が dropper を更新するようにした
- 1 redstone tick 後に repeater が再び dropper をオンにしてディスクを挿入するよう処理した
- 観覧位置から画面背面の装置まで信号を送るため、structure block ベースの 即時ワイヤ を作った
- structure block が powered redstone torch を次の区間に読み込み、次の tick に redstone block によってオフになる
- このパルスが次の structure block を有効化して信号を伝える
- structure block は最大48ブロックを扱えるため、48×48サブスクリーンのグリッドに開始信号を送れる
- 観覧者側から画面背面までの約150ブロックは、別のリセット可能な構造で接続した
- structure block と redstone block の組み合わせを連鎖的に生成・削除しながら信号を伝える
- この構造は creative で直接保存しにくいため、Python ライブラリで structure ファイルを生成した
- 最終メカニズムは外側のボタンで動作する 4×2×3ボックス に組み込まれた
フレーム前処理と映像品質
- 残っていた前処理課題は、フルカラー映像を6色に減らすことと、30fps映像を20fpsに変換することだった
- Bad Apple!! は純粋な白黒だけでなく、さまざまな場面でグレースケールを使っている
- モーションブラー
- 明るさの異なるオブジェクト
- シーン切り替えのグラデーション
- 火、太陽、影、水面の揺らぎのような表現
- 単純に最も近い色へ丸めると バンディング が生じる
- ディザリングは表現不可能な中間色を、隣接する表現可能色のパターンに置き換えてこれを緩和する
- 高品質なグローバルディザリングは、フレーム間で結果が大きく変わることがある
- 人の目には不一致が見えやすい
- Minecraft が処理しきれないほど大量の更新が発生する
- Bayer dithering のようなローカルディザリングは安定しているが品質が低く、ブルーノイズベースの ordered dithering が中間解になった
ffmpegはブルーノイズディザリングをサポートしていない- Christoph Peters のブルーノイズテクスチャ を 512×384 に切り出し、Rust スクリプトで適用した
- 元映像は Niconico の投稿 由来の非可逆圧縮素材でノイズがあった
- 黒や白の領域のノイズがディザリング後により目立った
- ほぼ黒は黒に、ほぼ白は白に丸め、中間色は連続性を保つように分散させて補正した
- 30fps を 20fps に落とす問題は完全には解決できなかった
- 3フレームごとに1枚捨てると、動きの間隔が奇数・偶数フレームで変わり、目障りになる
- 更新量もノコギリ状のパターンで変化する
- オンラインの 60fps Bad Apple!! 動画は AI や自動ツールでアップスケールされたものが多く、高速なシーン切り替えでアーティファクトが多かった
結果と後続作業
- 実装は 48×36 解像度と2色から始まり、128×96 と10色、256×192 を経て、最終的に 512×384 と6色 に到達した
- note block で音楽を再生する試みもあったが、良い品質を出すには別プロジェクト級になりそうだったため断念した
- structure block を redstone のように活用する structstone 手法を作り、これを使ったコンピュータのプロトタイプも始めた
- 開発過程では
ffmpeg、mpv、Rust の image crate、Minecraft の逆コンパイルコード、ワールドディレクトリ容量を最小化する技法などが使われた - 全作業には1か月以上かかり、友人たちと協力しながら、一般的なプロジェクトとは違う方法で問題を解く経験になった
1件のコメント
Hacker Newsのコメント
予想以上にコンピュータグラフィックスについて多くを学べたし、投稿者には賛辞を送りたい
ひとつだけ細かな訂正をすると、投稿者が「The sun」と呼んでいる絵は、実際には永琳 [0] が月を見つめている場面だ。そのシーン [1] では、永琳は自分が追放された月へ手を伸ばすもののためらって引っ込め、次の場面では輝夜 [2] も月へ手を伸ばすが、こちらはためらわない。Touhou Wikiによると、月を盗もうとする計画は永琳のものだったらしいので、この象徴が正確に何を意味するのかはよく分からない
[0] https://en.touhouwiki.net/wiki/Eirin_Yagokoro
[1] https://youtu.be/FtutLA63Cp8?t=99
[2] https://en.touhouwiki.net/wiki/Kaguya_Houraisan
永琳は輝夜を守るため、意図的に月とのつながりを断つことを選んだ
Bad Appleがなぜグラフィックレンダリングの事実上のHello Worldになりつつあるのかはあまりよく分からないが、リアルタイムで見るのは面白い
Bad Appleで高フレームレートのハイパーメディアを見せるこのデモも見た: https://data-star.dev/examples/bad_apple
多くの点でTouhouは、それ以前のファンダムとは違って現代インターネットファンダムの原型に近く、同じ音声を使っていてもBad Appleの動画は削除されない
第二に、影絵劇の形式は解像度がどれだけ低くても判別しやすい。3x3グリッドの例も見たことがある。しかも白黒、つまり1/0の2色しかないので、「Hello World」レベルさえ分かっていれば、フレームを想像可能なほぼあらゆる形式に変換するのがとても簡単だ
Redstoneで作られた完全にプログラム可能なCPU上で動作する。IRIS Computerの仕様は、カスタム16ビットCPU、RAM 8 kB、ROM 64 kB、テクスチャROM 1 kB、96x64ピクセル16色画面、浮動小数点ユニット(add/sub/mult/div/sqrt)、173 Redstone tickクロック、3Dグラフィックスのハードウェアアクセラレーションなし、URCLで書かれたプログラムを実行、MCHPRSサーバーのおかげで毎秒100万tickで動作し、クロック速度は5.8 kHzとのことだ
一定の拍子と小節を持つ音楽というより、MS-DOSの起動中に16ビットバスの偶数ビットを楽器につないで聴いていると想像したほうがずっとしっくりくる。Touhouのゲーム開発者が正式な音楽理論教育なしにPC-88/PC-98向けのハードコアシューティングゲームを一人で作りながら作曲した曲なのだから、自然な結果にも見えるし、そのため普通の音楽より組み込みハードウェアエンジニアのほうが親しみを覚えやすいのかもしれない
もうひとつの要因は、2ch/futaba文化の中で発展したnicovideo.jp / nico-techコミュニティだった。報酬や金銭的野心をはるかに超える専門性を持つユーザーたち、当時はSTEMの学生も多く、面白がってリミックスに技術をつぎ込んでいた。正体不明のFPGA魔術師やモータードライバの専門家、映像編集者が突然現れては幻覚的な映像を投げ込んで去っていくことがあり、本当にとんでもなかった。Maker Faire Tokyoが一時期、体裁を整えたいTシャツ姿のWeb開発者たちのために、nico-techのドレスシャツを着ていると思われる人たちを別会場の隔離区画に入れたことさえあった。その件は皮肉なもので、nico-techの集まりの誕生につながったが、繰り返されることはなかった。そうしたとんでもないコンテンツの質と量の密度が、Bad Apple!! PVの勢いを生んだ
最後の重要な要素は、PVがモノクロ、厳密にはグレースケールだったことだ。おそらくそれが、nicovideo.jp黄金期の別の動画ではなくこの動画が選ばれた理由だろう
1: https://www.youtube.com/watch?v=Yw5HTeT_dis
それ自体として見栄えがよく印象的な芸術作品でもあり、特にデモシーンの人たちが好みそうな性質を多く備えていると思う
色付きの別の動画クリップもある: https://youtu.be/mgfwwqwxdxY
「あらゆるものの上でBad Apple!」は、自分の好きなオタク的流行のひとつだ
Genesis/Mega Driveで初めて見たとき、あんな非力なハードウェアで可能だという事実に驚かされた。性能不足のもの向けに新しい移植が作られるのを見るのが好きだ。自分は低レベルプログラミングが得意ではなく、自分で作れるほど賢くもないと思うが、できる人たちは本当に尊敬する
「この再帰は Minecraft がハードの限界に達すると終わり、運が良ければ赤いブロックの代わりに黄色いブロックが生成される」という部分は、昔のアップデート抑制グリッチ(https://mcdf.wiki.gg/wiki/Java_Edition:Update_Suppression)を思い出す
より厄介な population suppression(https://mcdf.wiki.gg/wiki/Java_Edition:Population_Suppressio...)でも、同様にゲームエンジンをグリッチ状態にしてブロックを即座に落下させられる
動画向けでいちばん好きなディザリングアルゴリズムは Yliluoma dithering: https://bisqwit.iki.fi/story/howto/dither/jy/
特にグレースケールのコンテンツに有用で、使えるパレットの中から最適なディザリング行列を探す処理が単なる厳密計算で済み、その結果をルックアップテーブルに入れてリアルタイムレンダリングに使えるから。個人的には、とくにグラデーションでは Bayer やランダムディザリングよりずっとよく見える
「Redstone dust はティック遅延を作らないほぼ唯一の構成要素だが、非常に遅い。Mojang にはグラフアルゴリズムを分かる人がいないようだ」といった言い方は言い過ぎ
原文が情報源としてリンクしている記事以降、かなり遅くなくなっており、直近のものを含めてこの3年で改善が多くあった。Mojang はあらゆる方向からかなり叩かれている。Redstone を遅くしにくくするのに時間がかかったのは、Redstone を少しでも触るとコミュニティが騒ぎ、新機能追加ではない作業をしてもコミュニティが騒ぐので、やる価値が低くなっていたから。ネットで怒りながらグラフアルゴリズムを知らないと言っても助けにはならない。Mojang は Panda4994、Kingbdogz、Gnembon のような Minecraft コミュニティの非常に優秀な人材を何度も採用しており、やりたいことを実現する技術的専門性は持っている。足りないのは無限の時間と予算。15年ものの Java コードベースと巨大なマルチプラットフォーム C++ アプリを同時に維持しながら同期させようとするのは本当に難しいので、もう少し大目に見てほしい。一日中あらゆる方向から降ってくる憎悪にうんざりしていて、ただ Minecraft はすごいと言えたらいいのにと思う
昔はもっと腹が立ったが、後になって、それは尊大さというより「専門的な」経験が少ない16〜21歳くらいの素朴さに近いのだと気づいた
バージョン間の互換性を気にしているようにも見えない
高校を卒業して以降、Minecraft にハマって本格的な Redstone 装置を作ることはなくなった
今では、何かを建てたり探索したりしたい欲求が急に戻ってきたときに、友人たちと月に数回やる程度。今の Redstone 界隈を見ると、完全に変わっていて見分けがつかないほどで、自分がゆっくりシニアソフトウェアエンジニアになっていく中でも同じような感覚を持つのだろうかと思う。年月が過ぎ、数年間実務で触っていないスタックを見て、技術がどれほど速く変わり、その上に人々がどんな新しいものを作るのかに感嘆することになりそうだ
「そして……これで終わり？ 振り返ると結果はほとんど些細なことのように達成できたように見えて、なぜ誰も以前にやらなかったのか不思議に思う」という反応には同意しない
これは素晴らしい開発記録であり、圧倒されるような作業をほとんど不可能だが可能な断片に分解する小さなレッスンでもある。本当に良かった。ちなみにこの実装は、カスタムテクスチャ1つと、より多くのテクスチャを許可するために変更したいくつかのカスタムオブジェクト定義だけで、バニラ Minecraft 上で Bad Apple を 20fps でレンダリングしている。残りは非常にエキゾチックではあるがバニラだ
実際の映像そのものにこれほど多くの労力を注いでいるのが少し面白い
Bad Apple の実装を終えるころには、たいてい疲れ切っていてディザリングやフレームレートを考える余裕はなく、ただ ffmpeg で回して終わりにしてしまうとのこと
Minecraft ワールドで作った Bad Apple も見る価値がある: https://www.youtube.com/watch?v=RN3QW9SVnds