- Adaptive Tile Refresh（ATR） は、Commander Keen 1〜3がEGAの低速な全画面更新を避けるため、画面全体ではなく 変化したタイルだけを再描画する ようにしたスクロール技法
- EGA mode
Dh は 320x200・16色 の画面を4つのプレーン（C0〜C3）に分けて保存し、全画面32KiBを毎フレームISAバス経由で書き込むと約 5fps にとどまり、60Hz更新は難しい
- ATRは
CRTC_START、OFFSET、PEL レジスタで仮想画面内の縦横移動を処理し、端に達すると jolt によって画面基準を戻したうえで、必要なタイルだけをVRAMに上書きする
- joltのコストは再描画するタイル数に左右され、Commander Keen 1の例では250個中 40個のタイル だけが変化し、全画面の16%だけを再描画した。繰り返しタイルの多いマップ設計が性能を左右した
- Commander Keen 4〜6はATRの代わりに64KiB VRAM apertureのwraparoundを利用してパンし続け、新たに現れる端のストリップ だけを描画する方式に変わったが、一部のSuper VGAカードでは未初期化メモリに入ってしまう互換性問題が起きた
EGAで突き当たった帯域幅の限界
- Commander Keenは EGA（Enhanced Graphics Adapter） を搭載したPCで最もよく動作し、グラフィックスプログラミングは設定用レジスタと、VRAMにマップされた 64KiBのメモリウィンドウ を通じて行われた
- EGAは内部データを4つのプレーン
C0、C1、C2、C3 に保存する
C0 は各4ビットピクセル値の最下位ビット（LSB）を保存するC3 は最上位ビット（MSB）を保存する- 各プレーンは200ライン、1ラインあたり40バイトで構成される
- 4バンク構造はCRT画面に追従する帯域幅を確保するための設計で、CRTCは4バイトを並列に読み出す
- Commander Keenが使うEGA mode
Dh は 320x200解像度と16色 を提供する
- mode
10h のように64色値の中からインクを再構成する方式は使わない
- mode
Dh でも基本16色の中でパレット色を変更でき、Commander Keenのシンプルなフェードイン／フェードアウト効果に使われる
Adaptive Tile Refreshが避けた全画面再描画
- ATRが解決した中核のボトルネックは 帯域幅
- 320x200ピクセルの4ビット値、約 32KiB を毎フレーム書き込む処理はISAバスにとって負荷が大きすぎる
- 全画面を毎回更新する単純なループでは約 毎秒5フレーム 程度にとどまる
- EGAには4バンクへ同時書き込みする方法もあるが、画面消去やWolfenstein 3Dのカラム複製には役立っても、Commander Keenのスクロール問題には適していない
レジスタで実現した滑らかなスクロール
- ATRではまず、画面より大きい 仮想画面 をVRAM内に作り、CRTCがどこから読み出すかを決める
CRTC_START の値を変えて表示領域を動かす
- 縦スクロールは比較的単純
- 表示画面の上下にそれぞれ16ラインを追加すると、プレーンごとに
40 x 232 = 9,280 バイトを使う
- 画面を1ライン上へ動かすときは
CRTC_START を40バイト増やす
- 1ライン下へ動かすときは
CRTC_START を40バイト減らす
- 横スクロールは
OFFSET レジスタと PEL レジスタを組み合わせて使う
OFFSET を2に設定するとライン間に16バイトのパディングが追加され、仮想画面の左右にそれぞれ16ピクセルの余白ができるCRTC_START を1増やすとプレーン構造のため画面が 8ピクセル単位 で動いてしまい、粗すぎるHorizontal Pel Panning、つまり PEL レジスタは CRTC_START の後に最大7ビットをスキップさせ、ピクセル単位の横スクロール を可能にする
- 実際の左右移動は、座標を8で割った値で
CRTC_START を調整し、座標の余り（% 8）で PEL を合わせる方式
joltとタイル単位の部分更新
- 仮想画面の端に達すると、ATRは jolt を行って仮想画面を再び中央に合わせる
- 全画面を再描画すると約 200ms かかって5fpsまで落ちるため、joltは全体再描画ではなく、変化したタイルだけを上書きする方式で動作する
- Commander Keenのレベルは 16x16タイル で作られている
- アーティストがタイルを描くと、ビルドシステムが各タイルに固有IDを割り当てる
- レベルデザイナーは2DエディタでタイルIDを配置してマップを作る
- エンジンは仮想画面内にどのタイルIDがあるかを追跡する
- joltの時点では、現在の仮想画面状態と、再び中央に合わせた目標状態の タイルID を比較する
- 同じタイルはスキップする
- 異なるタイルだけをVRAMに上書きする
- joltの効率は再描画するタイル数に反比例するため、ゲームデザイナーは 繰り返しタイル が多く現れるようタイルマップを構成する必要があった
- Commander Keen 1の例では、右へ滑らかに移動して仮想画面の端に達し、16ピクセル左へのjoltが発生したとき、250個中 40個のタイル だけが変化した
- 背景の上にはスプライトレイヤーが描かれる
- エンジンはスプライトが上書きしたダーティタイル座標の一覧を保持する
- 新しいフレームごとにダーティ一覧を巡回して背景タイルを復元し、その後スプライトを再描画する
ダブルバッファと第2三部作のdrifting
- 視覚的アーティファクトを避けるため、システム全体は 2つのフレームバッファ に複製されている
- 一方をCRTCが読み出している間、もう一方へVRAMの別の位置に書き込める
- 各バッファは
(320 + 32) * (200 + 32) * 4 / 8 = 40,832 バイトを使う
- ダブルバッファ全体では
40,832 * 2 = 81,664 バイトとなり、IBM純正EGAカードの64KiBを超える
- VileRによれば、64KiBを搭載していたのは元のIBM EGAボードだけで、1986〜1987年ごろに登場したEGAクローンの大半は 256K を搭載しており、Commander Keen発売時には256K未満のEGAカードはほとんどなかった
- Commander Keen 1〜3ではATRが求める反復パターンが画面にはっきり現れるが、Commander Keen 4〜6では同じ特徴はそれほど目立たない
- 第2のKeen三部作は、
CRTC_START が64KiBブロックの終端に達すると再び先頭へ戻る wraparound 動作を利用する
- 画面を継続的にパンし、新たに見える端のタイル列 だけを描画する
- joltがなくなり、似た色の反復フィールドを作る必要性が減る
- この方式は新機能追加というより、joltをなくした改善に近い
- 2つのダブルバッファ要素が同じ速度でVRAM空間をdriftするため、互いに重ならない
- ほとんどの場合は問題なく動作する
- 一部の Super VGA カードでは問題が発生した
- 標準と異なる実装やより大きなメモリを持つカードでは、終端から先頭へwraparoundせず、実際に存在する未初期化メモリへ入ってしまうことがあった
- Carmackは多数の非標準カードごとに個別対応する代わりに、画面端に達したら一時的な引っかかりを受け入れて全画面を上へコピーする簡単な解決策を選んだ
- このdrifting技法は、タイルやスプライトをVRAMに保存して高速なVRAM-to-VRAMコピーを使う方式を妨げた可能性はあるが、毎フレーム描く量が非常に少ないため大きな問題にはならなかった可能性がある
1件のコメント
Hacker News のコメント
Commander Keen 4〜6 のスクロールの滑らかさは、PCでは何年ものあいだ追随できるゲームがなく、ゲームが256色グラフィックスへ移行した後もそうだった。
John Carmack の驚異的な技術仕事と Adrian Carmack の16色パレットアートのおかげで、id は1990年代のしばらくの間、PCで最も見栄えのするプラットフォームゲームを作っていたと言える。
Adrian Carmack は、より有名な Carmack とは親戚ではないが、16色パレットの隠れた名手だと思う。
グラフィックスとゲームプレイの進歩の速さは本当にすさまじかった。
最初のゲームからの変化: https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
最後のゲームまでの変化: https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
当時、子どもとして実際に遊んでいたが、物事がそんなに速く進んでいたことを忘れていた。
Commander Keen をけなすつもりはないが、PoP のビジュアルとゲームメカニクスは当時の基準では群を抜いていたと感じる。
7歳くらいで初めて遊んだとき魔法のような印象を受け、今でも一番好きなプラットフォームゲームなので偏りはある。
もちろん PoP にはスクロールがまったくなく、そこは Commander Keen の黒魔術だ。
「メモリが遅いなら、変わった部分だけ描き直そう」というのは、今ではほとんど当たり前の発想だ。
それでも4〜6作目の最適化は面白い。1〜3作目ではバッファがラップしないという前提で全体の処理をしていたのに、実際にはラップしていて、その作業が無駄になっていたという点も興味深い。
Windows 98 で DirectX 5 を使って タイルベースのゲーム を作ったことがあり、最初はこの記事で説明されているものに似た方式を実装していた。
画面はスクロールしなかったが、多くのタイルを描き直す必要があり得たので、状況は少し単純だった。
結局そのコードは全部取り除いた。RIVA TnT カードで画面全体を描くコストをプロファイルしてみると、時間があまりに小さくて測定すらできなかったからだ。
PC開発で EGA 時代を逃していてよかった。あの時代だったら何も完成させられなかった気がする。
乗算の代わりにビットシフトで最適化し、核心部分のコードはアセンブリで書き、プロセッサが進歩するにつれて一度に16ビットや32ビットずつ書き込む、といった具合だった。
手元の資料が少なかったので、地元の図書館の本と txt ファイルの入ったフロッピーディスクで学び続けた。
若すぎて経験も足りず、完成させたものはなかったが、滑らかな垂直スクロールは作れたし、水平スクロールもほぼ動くところまで行った。さらに、回転する3Dキューブのダブルバッファリングも実装した。深度バッファリング、数学、ライン単位のポリゴン描画まで含まれていた。
ところが DirectX が登場すると、機械との接点が消え、回転する3Dキューブは簡単すぎて面白くなくなった。
バスは8ビットから16/32ビットへ広がり、グラフィックスカードがポステッドライト（posted writes）をサポートして CPU の待ち時間が減り、CPU も速くなったことで、高速なシステムでは 640x480x256 の画面を毎秒300フレーム以上書き込めた。
この場合は、キャッシュされたシステムメモリバッファと DMA コピーだったか、あるいはブリッターが描画を処理していたのかもしれない。だが Windows 98 の頃でも、低価格帯の3Dカードの中には CPU アクセスが非常に遅く、古い ISA バスカードよりかろうじてましな程度のものもあった。
画面解像度が高くなりすぎたことで、今では少し逆戻りしている面もある。4K の全画面を毎秒60フレームで描き直せるとしても、効率的とは言いにくい。
ゲームは通常いまだに全部描き直すが、デスクトップコンポジタは描き直す領域を減らすため、レイヤーをハードウェアプレーンへ動的に割り当てるなど、かなり最適化している。
同じ時期に別のゲーム会社で働いていて、2つ目のアプローチと同じような スクロール手法 を自分で考案した。
それほど驚くようなことだとは思わない。当時同じ問題を解いていたなら、おそらく似た結論に達したはずだ。
PCスピーカーでサンプル音を再生するために独自の PWM オーディオドライバも作ったが、他の人たちもみんなそうしていたように思う。
私たちが皆コンソールへ移る前、PCは十分に愛されていなかった。Hornet の 8088 MPH のようなデモを見ると、今でも興奮する。
面白いゲームの必須条件ではないが、特に 10MHz 未満のような低スペックのハードウェアで Keen が見せた滑らかさは、当時としては目を見張るものだった。
何千年もの間知られないままだった偉大な発明は、数え切れないほどあったはずだ。
私も LinkedIn が出る10年前に似たものを「発明」したが、うまく商業化できなかった。ほとんどの発明は広く知られないままだと思う。
だから多くのスタートアップは2人で始まる。専門家が1人、ビジネス担当が1人だ。
だから間違いではない。この発明はそれ自体は特別ではないものかもしれないが、新規性・有用性・成功した商業化 が組み合わさることで特別になった。
すばらしい本 Masters of Doom では、Keen は Mario 系、つまり横スクロールゲームだったと説明されている
id は Mario を PC に移植する選択肢としてこの技術を Nintendo に提案したが、Nintendo が断ったため Keen が生まれた
PC ゲームにとっては巨大な飛躍であり、新しい PC ゲーム時代を切り開いた
ただ、今でもよく理解できないのは、NES と PC の技術の何がそれほど違っていたから、Nintendo は PC より数年早く横スクロールを実現できたのかという点だ
EGA のグラフィックモードでは、線、円、個別ピクセルなど、望む任意のものを描けるし、そう使うように作られていた
しかしスクロールはタダではない。メモリを直接コピーする必要があり、リンク先の記事が示すように力任せにやると ISA バス帯域の制限のせいで毎秒 5 フレーム程度しか出ない
NES や他の 8/16 ビットゲーム機は、任意のものを描くようには作られていなかった。タイルをレンダリングするように作られていた
背景タイルのグリッドを定義し、スクロールオフセットを与えればよい。スプライトも似たように動作するが、独立して動かせる。これらすべてが毎秒 60 フレームでタダで提供される
欠点は、任意のものを簡単にはレンダリングできないことだ。たとえばどこかに個別ピクセルを 1 つ塗るには、かなりひどい回避策が必要になる
Nintendo が IBM より先に「見つけた」問題というより、IBM は汎用コンピュータと静的グラフィックに合わせた汎用グラフィックシステムを作り、すべてのピクセルに対する細かな制御を提供していた。EGA カードを見ると、シリコンがたくさん載ったかなり巨大な装置だ
一方 Nintendo は、タイルを押し動かすことに合わせた、はるかに単純な 専用グラフィックシステム を作ったということだ
Nintendo が受け入れなかったため、新しいアセットを作り、それが後の Keen になった
移植版の映像はここにある: https://youtu.be/1YWD6Y9FUuw
NES 側については https://www.nesdev.org/wiki/PPU がよい出発点に見える
核心的な課題は「横スクロールのやり方を見つけること」そのものではなく、まったく別のシステムのメモリ空間と帯域幅の制約の中で、横スクロールゲームエンジンが見栄えよく動くように調整することだ
レイヤーを持つスプライトベースでゲームを作っていたのだから、2D を「アクセラレート」する方法としてはかなり理にかなっていた
Lex Fridman の John Carmack インタビュー では、各ゲームの主な革新をすべて一通り取り上げている
本当に興味深いエピソードなので、時間があるなら強くおすすめする。だいたい 5 時間ほどある
彼の他のインタビュー 2 本もおすすめする
Todd Howard: https://www.youtube.com/watch?v=H9AAnV59ddE
Guido van Rossum: https://www.youtube.com/watch?v=-DVyjdw4t9I
Commander Keen Goodbye Galaxy のほぼすべての 隠し要素 を知っていると信じていた頃を今でも覚えている
学校の友人たちは、放課後に学校のコンピュータで遊んでいたレベルの秘密を教えてくれとよく聞いてきた
fabiensanglard.net を見かけると、すぐに推薦したくなる
技術的に深みのある他の古典ゲームブログを知っている人がいれば共有してほしい
https://nicole.express/ と https://sudden-desu.net/ も私のお気に入りだ
フレームバッファの開始位置をスキャンライン単位で調整すれば 垂直スクロール がどうなるかは理解できたが、水平スクロールがフレームバッファをひどくねじ曲げずにどう可能なのかは、最初は明確ではなかった
もう少し考えてみると、円筒の側面に絵を描くのに似ていることに気づいた。画像の左端をどこに描いても、円筒を回して CRTC_START と PEL レジスタを設定すれば、常に画像全体をくっきり見られる方法がある
「画面端に到達すると、簡単な解決策としてカクつきを受け入れて画面全体を上にコピーした」という部分も興味深い
Keen を起動すると、たいてい “VGA compatibility mode enabled” のようなメッセージが出ていた記憶があるが、それがどういう意味なのか、いつも気になっていた
Commander Keen は本当に愛らしい小さなゲームだった
もう一度起動する方法を探してみないと
ところで、これはどうやって実行するのがいいのだろう？ 「大人」になってから Windows を使わなくなって20年くらい経つのだけど、Debian ではどうやってプレイできるのだろうか？
当時のコンピューターはコンソールより10倍くらい高かったので、たいていは大人たちが子どもが何をすべきかについて強い考えを持っていたからだ
NES や Genesis のゲームと比べると、魂が足りない。当時は好きだったけれど、最近 DosBox でやり直してみたら、明らかに比べものにならないと感じた
数年前に2つ目の方法を実装したけれど、前側の端だけを描画しても非常に遅かった
ただし C で書いたもので、アセンブリプログラミングをきちんと学んだことはない
https://github.com/geon/kate/blob/master/src/platform/dos/eg...