たった96KBの実行ファイルで動作するFPS「.kkrieger」を作ったエンジニアが当時を振り返る

かつて容量が96KBしかないFPSゲーム「.kkrieger」を作成したときの思い出について、制作グループの一員であるファビアン・ギーセンさんがブログに書き残しています。

Metaprogramming for madmen | The ryg blog
https://fgiesen.wordpress.com/2012/04/08/metaprogramming-for-madmen/

.theprodukkt
https://web.archive.org/web/20120204065621/http://www.theprodukkt.com/kkrieger

2003年～2010年までの間、Breakpointというデモシーンパーティが開催されており、「.kkrieger」は2004年の96KBゲームコンペティション用の作品として作成されました。

リリース予定の2週間ほど前の段階で、.kkriegerの容量は70KB～80KB程度でした。ただし、完成までにまだコンテンツを入れなければならず、ギーセンさんたちは「全てのコンテンツを入れてゲームを完成させる」「容量を96KBに抑える」という2つの作業を同時にこなす必要があったとのこと。ギーセンさんによると、コードを小さく抑える方法は下記の通り。

◆1：アーキテクチャ
モジュール化を維持したり、適切なアルゴリズムを使用したり、データを正しい方法で保存したりするなど、コードを小さくできる設計を行う必要があります。なお、こうした作業は時間がかかるためリリースの2週間以上前までに終わらせるべきとのこと。

◆2：「重し」の除去
コードの中で、使用していない部分を削除します。円環体を使っていない場合は円環体生成のためのコードは当然不要です。円環体を1個しか使っていない場合は生成のためのコードを別の内容に置き換えてコードの量を減らせる可能性があります。コンテンツに関する基本的な統計情報があればこのステップは非常に簡単で、1時間以内という短時間の作業で数キロバイト程度の大きな成果を得られるとのこと。

◆3：細かい作業
コード内の全ての関数に関するデータをまとめ、必要以上に大きかったり小さくできそうだったりする関数を見つける厄介な作業です。コンパイラが大きなコードを生成している場所と理由を見つけるために逆アセンブリリストを眺めたり、特定のイントロを小さくするための近道が無いかを探したりして1日あたり300～400バイトというゆっくりなスピードで改善を重ねたと述べられています。

.kkriegerが遊べるようになった時点で実行ファイルの容量は120KBでした。アーキテクチャの修正と重しを除去した時点で102KBまで減ったものの、96KBにはまだ遠い上、一部のコンテンツがまだ入っていないなどの問題もありました。リリースの1週間前時点で100KBになりましたが、ギーセンさんたちは「このままではうまくいかない」と感じていたとのこと。

ギーセンさんたちは別のアプローチを試みました。実行ファイル内では、全てのコンテンツが1つのデータファイルから手続き的に生成されているので、データファイルを編集したり差し替えたりしないのであれば、そのデータファイルを使ったときに使用しないコードを丸々削除しても問題ありません。この解析を手動でやるのは退屈である上にミスも発生しやすいため、ギーセンさんたちは「lekktor」という解析ツールを作成することにしました。

lekktorはコードの使用状況を追跡して使われなかったコードを削除するというツールで、ギーセンさんたちのアイデアは「一度コンテンツの生成プロセスを実行し、使用されなかったコードをlekktorで検知して削除する」というもの。このlekktor作成においてはC++コードの解析が必要という点が問題でした。

C++コードの解析といっても、構文全体を解析する必要はなく、プログラムの流れに関わる「if」「else」「for」「while」「do」「&&」「||」「?:」だけを検出すればOKです。ギーセンさんたちはさまざまな解析ライブラリを確認したものの適したライブラリが見つからず、仕方なく自分たちでパーサーを作成することになりました。

パーサーの作成には3日かかったものの、幸いにもうまく動作しました。コードの各場所に一意のIDを割り当て、プログラムがその場所を通過するたびにカウントすることで不要な部分を除去したり、IF文の評価が「true」「false」の一方にしかならない場所を発見したりできたとのこと。その後も最適化を重ね、コンテスト開始の2時間前に96KB以内におさまるイントロ無しバージョンが完成。30分後にはイントロを含めても96KB以内におさまるようにできました。

こうして完成した.kkriegerはコンペティションで1位を獲得しました。実際のゲームプレイの様子は下記のムービーで確認できます。

.KKRIEGER - A Truly Remarkable Game that Squeezes a Fully Functional Sci-Fi FPS Into Just 96kb! - YouTube

.kkrieger - The FPS Game in 96KB (Full Gameplay) - YouTube

また、.kkriegerのソースコードはGitHubで他のプロダクトと一緒に公開されているので、気になった人は確認してみてください。