『DOOM』を“ひとつの巨大文字列”に封じ込める人あらわる。「正規表現」で無理やり動作、1フレームにつき約3分かかる

名作FPS『DOOM』を“文字列の書き換え”のみを用いて動かすユーザーが現れたとして注目を集めている。ただし、1フレームの生成には数分間を要するといい、リアルタイムでプレイするのは難しいようだ。

『DOOM』はid SoftwareがMS-DOS向けに開発し、1993年に発売されたFPS黎明期の代表作だ。現在ソースコードは利用・改変・再配布などを条件付きで認める「GPL-2.0」ライセンスで一般公開されており、数多くのマニアの手によって移植版が作られてきた。なかには一風変わった媒体で動作させる試みもあり、キャプチャ認証や電子タバコの液晶の上で動く『DOOM』なども登場している（関連記事1、関連記事2）。

そんな『DOOM』を「正規表現」を用いて動作させるプロジェクト「doom-regex」が登場した。プログラマーのArtem Lytkin氏によって開発され、7月26日にRedditにて発表。GitHub上では、Windows向けのプレイアブルデモやソースコードが公開されている。

正規表現とは、文字列のパターンを表すための記法だ。検索や置換など、ソフトウェアにおける文字列処理で広く用いられている基本的な仕組みといえる。「doom-regex」では、『DOOM』を動作させるマシンの状態を、96.6MBの巨大な一つの文字列で表現。『DOOM』のプログラムや、マップなどのデータを格納したWADファイルに加えて、仮想CPUのレジスタやメモリ、フレームバッファなどの状態もこの文字列内で管理されている。

そして、544個の正規表現による置換ルールを決まった順番で適用していき、最初に合致したルールに基づく置換1回を1ステップとする。この過程を繰り返すことで処理を進め、フレームを描画していくのだ。ルールの外部にインタプリタや算術演算は一切なく、ドライバ側でひたすらあらかじめ決められたルールにしたがって文字列を置換していくだけで『DOOM』が動いているのである。こうした正規表現による文字列の置換のみで『DOOM』を動作させられるのは、一定のルールにしたがって文字列の置換を繰り返す仕組みそのものが、チューリング完全であるからだという。

RVM1|ST:run|PH:0|CI:02000000fffe|PC:00000000|R0:00000000|R1:00000000|……

では実際にはどのような置換がおこなわれるのか見ていこう。 たとえば上の文字列は、ある時点における巨大文字列の冒頭だ。このうち、命令の実行フェーズにあることを意味する文字列「PH:0」の直後には、現在おこなわれる命令を表す12桁の16進数「CI:02000000fffe」が記されている。最初の2桁が「02」であるこの命令は、特定の値を対象となるレジスタに書き込む「MOVI」命令であり、以下の正規表現のルールにマッチする。

P:\ARVM1\|ST:run\|PH:0\|CI:(?<ci>02(?<d>[0-7]).(?<imm>.{8}))\|PC:(?<pc>.{8})(?<pre>(?:[^|#]*+\|)*?R(?P=d):).{8} R:RVM1|ST:run|PH:1|CI:${ci}|PC:${pc}${pre}${imm}

命令を表す「CI:02000000fffe」のうち、3桁目の「0」が書き込み先のレジスタ番号、そして末尾8桁の「0000fffe」が実際に書き込む値だ。そのためこのルールが適用されると「R0」の値が置き換えられ、フェーズの値は「PH:1」へと切り替わり、巨大文字列は以下のようになる。CPUの基本的な内部動作の一つが、正規表現によって再現されているわけだ。

RVM1|ST:run|PH:1|CI:02000000fffe|PC:00000000|R0:0000fffe|R1:00000000|…

ちなみに、ルールの先頭では「ST」や「PH」の部分をチェックすることで、対象となる状態かどうかを早期に判定している。もしこれらの条件のどれか一つでも一致しなければそのルールは不一致となり、次のルールの判定へと移る。こうした構造によって、544個ものルールを試す際の処理コストを抑えているそうだ。

ただし、1フレームを描画するには膨大な回数のステップを重ねる必要があり、100フレームの生成では約12億5000万回、平均すると1フレームにつき約1250万回の置換が必要になり、時間にして1フレームあたり約3分を要したそうだ。とはいえ、デモではWASDキーによる移動、Ctrlキーでの射撃、Spaceキーでのドア開閉などの操作も可能とのこと。

長年愛される『DOOM』では、時代を経るにつれて、さまざまな技術や発想を用いた“とんでも移植”が登場し続けている。今回のプロジェクトは、文字列の検索や置換に使われる正規表現を強引に活用し、『DOOM』を動かしたという点で、ユニークな試みといえそうだ。