2017年、カナダ人のJohn AycockとBritish Tara Copplestoneの2人の科学者が、Atari 2600ビデオゲームコンソール向けの古典的なゲームEntombedの分析を公開しました。 1982年にリリースされたこのゲームのメカニズムは非常にシンプルです。プレイヤーが操作する考古学者は、スクロールカタコンベを下から上に向かって進み、ゾンビを避けなければなりません。 Atari 2600には128バイトのRAMしかありませんでした。それにもかかわらず、一見無限に見える迷路は、起動するたびに新しくなりました。メモリに生成されます。プログラマはそれをどのように管理しましたか？これは、38年前にこのゲームを作成したプログラマであるStephen Sidleyによるコメントです。
- . , , . , , , , , .
ウィキペディアには、迷路を生成するためのさまざまなアルゴリズムがリストされています。ゲーム機で最も興味深いのは、同じ1982年にMicrosoftのMartin Ellerによって作成された「Ellerアルゴリズム」です。エラーのアルゴリズムを使用すると、ループのない行ごとに接続された迷路を作成し、無制限の高さの迷路を生成できます。メモリに保存できるのは、最後の数行だけです。これはまさにEntombedが必要とするもののようです！しかし、悲しいかな、Ellerのアルゴリズムは垂直スクローラーのゲームメカニクスと互換性がありません。結果として生じる迷路では、上から定期的に障害物を回避しなければならないためです。これを実証するために、Ellerのアルゴリズムを少し変更して、Entombedのように「壁」と「通路」のマトリックスで迷路が作成されるようにしました。
再帰などを使用したより高度なアルゴリズムは、128バイトのRAMには収まりません。したがって、Entombedのアルゴリズムの要件は次のとおりです。
- 高さが無制限の迷路を行ごとに生成。
- 作成された迷路は、切断されたセクションをできるだけ少なくする必要があります。（プレイヤーは「壁を突破する」能力が限られているため、まれな干渉が問題になることはありません）
- 作成された迷路は、主に分岐と接続の垂直通路で構成する必要があります。これにより、迷路の通路が上方向に移動する必要がなくなります。
- 迷路の新しい行を生成するために、生成された最後の数行のみを使用する必要があります。（Atari 2600にはビデオバッファーがないため、画面に表示される迷路のすべての行を128バイトのメインメモリに何らかの形式で格納する必要があります）。
誰がどのようにしてこのアルゴリズムを作成したのですか？
「ビデオゲームの考古学者」と名乗る2人の科学者は、迷路の中で考古学者についてのゲームであるEntombedで研究を始めることにしました。調査中、彼らはスティーブンシドリーを追跡し、迷路を生成するのに使用したアルゴリズムを尋ねました。すでに述べたように、Sidleyは彼らに、アルゴリズムの作者でさえ彼のアルゴリズムが何であったかを覚えておらず、Sidley自身さえも覚えていないと語った。その後、研究者たちはこのアルゴリズムを作成した「ジャンキー」を見つけようとしました。ストーリーの後半は、2008年に公開されたインタビューで見つかりました。
Entombed [Duncan Muirhead] [Paul Allen Newell]. - , , , . , . , VCS [Atari 2600], . , . , , . , Towering Inferno、そこでアルゴリズムの一部を使用して終了します。私が去った後、会社はスティーブン・シドリーを雇い、迷路発生器を彼に手渡しました。ゲームメカニックの余地を作るために、彼は私のコードのかなりの部分を削除しなければなりませんでした。[Atari 2600では、RAMとROMの量に対する厳しい制限に加えて、ピクセルの各行の生成に正確に76サイクルの作者の注意が必要です。
Sidleyは、迷路ジェネレータコードはコメントなしで6502アセンブリで記述されていると述べました。これは、それ自体が偉業のようになりますように注意します キム、「コマンドのセットは非常に制限されていて曲がっているので、プログラムを作成するときに主な質問が発生します。この奇跡についてどのように書くことができますか？」それにもかかわらず、研究者たちはゲームコードを掘り下げ、迷路が次のように生成されていることを発見しました：生成された行の8つのセルのそれぞれについて、すでに生成された5つのセルが考慮され（上部に3つ、左側に2つ）、「マジックテーブル」に従って新しいセルの状態が選択されます。 （通路、壁、またはランダムな選択）。左端の2つのセルは常にいっぱいで、メモリには保存されません。迷路の右半分は、左の鏡像です。
未解決のアルゴリズムの中心にある謎のテーブル
生成された迷路のプロパティは、以前に生成された5つの各セルの新しいセルセットの状態によって異なります。 Entombedに縫い付けられたテーブル、多くの困惑した研究者：「カルノー地図の形で提示するいくつかの方法があっても、法律に気づかなかった」シドリーは同じように言った：「私にとってそれは謎のままである：私はそれを解明することができず、それをブラックボックスとして使用した。」ただし、表に規則性がないことは少々誇張されています。たとえば、Karnotマップでは、c = 1（現在のセルの左上の壁）の場合、X = 1（現在のセルの壁）は生成されないことがわかります。
その報告におけるBBC「デジタル考古学」について、彼女はさらに劇的な誇張に訴えました。「テーブルは本当に独創的です。ゲームを開始するたびに、最初から最後まで進むことができる新しい迷路が作成されます。この表の値が少しでも異なっていれば、おそらく迷路は通行できないことが判明します。不可解だ」と語った。 hackaday.comへの再投稿はさらに自信をもって定式化されています。「神秘的なテーブルは常に通過可能な迷路を作成しますが、そのビットを変更すると、パズルは不溶になります。」実際、ゲームのビデオで見ることができるように、迷路は必ずしも一貫していませんでした。テーブルの小さな変更は、結果の迷路に顕著な影響を与えません。JavaScript バージョンを作成しました、自分で「神秘的なテーブル」で遊ぶことができます。「外出先で」それを正しく変更し、結果として迷路がどのように変化するかを確認してください。おそらく、Paul Newellがインタビューで述べた迷路の接続性の保証は、コードの削除された部分とともに失われました。
ビデオゲームの考古学
ジョンエイコックは、Entombedがどのように研究の対象になったかについてコメントしました。彼は、生徒のためにリバースエンジニアリングタスクを準備し、比較的知られていないゲームを選択しました。ランダムに選択されたゲームでそのような優れた発見があった場合、それは当時のほぼすべてのゲームで素晴らしいプログラミングソリューションが存在することを意味しますか？ Stephen Sidleyは、貧弱な命令セット、128バイトのRAM、ピクセルラインあたり76クロックのAtari 2600の設計を、「酸素タンクなしでエベレスト山を登る」と比較しました。プラットフォームの非常に制限により、プログラマーは独創的なアルゴリズムを発明する必要がありました。
より深く掘り下げることは単なる比喩ではありません。古典的なビデオゲームの研究は、それらが記録されたメディアの脆弱性と、古いゲームを興味のないゴミとして扱うことの両方によって複雑になっています。 1983年に、Atari は 47トンのAtari 2600カートリッジを埋め立て地に投棄しました。アスファルトローラーで押しつぶされ、コンクリートが注がれたこれらのカートリッジは、2014年に「デジタル考古学者」が残っているカートリッジを発掘して取り出す許可を得るまで30年間置かれていました。掘ったカートリッジはどれも機能しませんでしたが、少なくとも1つはコンポーネントをはんだ付けすることによって復元されました。
「泥棒」から保護するためにカートリッジにコンクリートを注いだアタリの行動は、知的財産が無料で誰かに与えられるという事実から「失われた利益」を被るよりも、作品を永遠の忘却に委ねる著作権者にとって非常に典型的です。しかし、商業的価値を長く失ったプログラムを無料で複製できるようにすることで、20世紀の「仮想文化層」を保護するのに遅すぎるのではないでしょうか。
