Show HN: Raycasterに閉じ込められて

約1年前（あるいはそれ以上前かもしれない、私の記憶は曖昧なことがある）、私はほとんどのゲーム開発者が経験するであろう、Raycasterの通過儀礼を経験しました。Lodeのチュートリアルを読み、YouTubeの3DSageによる「Make Your Own Raycaster」シリーズ（どちらも強く推奨するリソースです）を見ていたとき、「Entombed」アルゴリズムに出くわしました。これは、Atari 2600のゲーム「Entombed」（1983年）に見られる迷路生成アルゴリズムで、プレイヤーはゾンビに追われながら迷路から脱出しなければなりません。 このアルゴリズムに私が惹かれたのは、迷路が、次に行がどのように生成されるかを指示する古い（今ではほとんど秘術的な）ロジックに基づいて手続き的に生成されていたことです。これはAtari 2600の制約の中で行われました。Atari 2600は128バイト（はい、bです）のRAMしかなく、「Entombed」では、迷路は上方に連続してスクロールし、プレイヤーは下に進んでいきます。つまり、デバイスのメモリ制限を考えると、保存された迷路は事実上不可能です。そのため、迷路は一度に1行ずつ作成し、スクロールして画面外に出たら破棄する必要がありました。ここで疑問が生じます。数行しかメモリに保持できない場合、一度に1行ずつ迷路をどのように構築するのでしょうか？ ここでミステリーテーブルが登場します。「Entombed」ゲームがゲーム考古学者の関心を引いた本当の理由は、迷路生成の背後にあるミステリーテーブルであり、今日に至るまで誰もその仕組みを完全に説明できていないという事実です。長年、それは「酔っ払って頭がおかしくなった誰か」によって書かれたという話がありました。実際の話は、それほど遠くはありませんでした。Paul Allen Newellと数学の大学院生Duncan Muirheadが、バーでビールを数杯飲みながらナプキンにそれをスケッチし、Newellは週末の終わりまでにそれをAtariで動作させました。 Entombedの迷路生成に使用されたミステリーテーブルのマッピング。Aycock, J. and Copplestone, T. 2019. Entombed: An archaeological examination of an Atari 2600 game. The Art, Science, and Engineering of Programming 3(2). doi:10.22152/programming-journal.org/2019/3/4. CC BY 4.0。 ロジックは次のようになります。迷路の各セルは、5つの隣接セルから生成されます。同じ行の左側にある2つのセルと、上の行にある3つのセルです。これらの5つのビットは、0から31までのインデックスを形成し、ルックアップテーブルを参照して、壁（1）、通路（0）、またはコイン投げ（ランダム）を返します。そして、それがすべてです。バックトラッキングも検索もありません。行は一度のスキャンで埋められ、テトロミノのようなウィンドウがセルごとにスライドしていきます。 セルの生成方法。Newell, P.A., Aycock, J. and Biittner, K.M. 2022. Still Entombed After All These Years: The continuing twists and turns of a maze game. Internet Archaeology 59. doi:10.11141/ia.59.3. CC BY 3.0。 このアルゴリズムをセルラーオートマトンと特徴づけることさえできますが、Paul Allen Newell、John Aycock、Katie M. Biittnerによると、「アルゴリズムは容易な分類を拒み、ユニークである可能性があります。局所情報のみに依存しているため、セルラーオートマトンに基づいていると考える誘惑に駆られますが（Sarkar 2000）、並列性の欠如と、Xを取り囲むセルの「近傍」の奇妙な形状は、セルラーオートマトンという考えをこじつけにします。」 これは、迷路アルゴリズムが通常機能する方法とはほぼ反対です。通常、グリッド全体をメモリに保持し、アルゴリズムは実際に解決できる迷路で終わることを保証します。「Entombed」は一度に11行しか見ず、何も保証しません。ただ迷路のように見えるものを生成するだけです。 「Entombed」の場合、保証がないことを考えると、2回の修正パスが導入されます。これらは、行が完了した後、後ろの行を振り返って実行されます。迷路が繰り返し始まったり、セクションを壁で囲んだりしている場合、行全体、またはその半分を空白にします。 参照できるすべての資料を消費した後、すぐにそれをRaycasterに実装する方法を考え始めました！Raycastingの要点と、シンプルなWolfenstein 3Dレンダラーの作成を組み合わせた、非常に楽しいサイドプロジェクトになりました。ただし、マップは、この古い（年齢によっては）Atariゲームから取られたロジックで手続き的に生成される必要がありました！各迷路行の状態をuint32として表現することにしました。各ビットは壁があるかどうかを示します。これにより、プレイヤーが進むにつれて迷路が成長するにつれて、計算が容易になり、メモリ効率が向上します。 Entombedのゲームプレイ、Archive.orgからキャプチャ。対称性に注意してください。プレイフィールドの半分しか生成されず、残りはその鏡像です。 私のバージョンは、オリジナルとはいくつかの点で異なります。鏡像（上記のスクリーンショットに見られる）は削除し、プレイフィールドを30セルに広げ、メモリは今日それほど問題ではない（あるいは問題なのか？）ため、行が生成されたら決して破棄しません。また、プレイヤーと敵に、目の前の壁を破壊する能力を与えました。これは（理論的には）迷路生成にフィードバックされる可能性がありますが、実際には決してそうなりません。生成された行は十分に先行しているため、破壊する頃にはジェネレーターはすでにそれをはるかに過ぎています。面白いのは、最近になって、オリジナルのゲームにもプレイヤーに同じ壁破壊能力が提供されていたことに気づいたことです。行き止まりから進む簡単な方法を提供する必要があることを考えると、理にかなっています...特に、謎の存在に追われている場合は。 C実装は3DSageが提供したものの上に構築し、プレイヤーと敵エンティティがスタックする可能性のあるいくつかのコーナーケースを修正しました。全体として、非常に楽しくユニークな経験でした。一度動作すると、 pretty much それを忘れていました。そして数週間前、「Backrooms」映画を見た後、この短い実験を思い出しました。そこで、それを少し改良し、いくつかのマイナーな問題を解決し、Backrooms風のゲームとしてスキンを適用して（訴えないでくださいねlol）、世界に公開しようと思いました。おまけとして、Claudeにブラウザでプレイ可能なThree.jsバージョンを、さらにいくつかのエフェクト（Diablo風のミニマップを再現しようと最善を尽くしました）とともに書かせました。もし、自分のマシンでCゲームをコンパイルして実行するのが面倒な場合のためです。 Entombed RaycasterのThree.jsバリアント。 閉じ込められるまで、どこまで行けるでしょうか？ Gitlabリポジトリ Three.jsブラウザデモ 参考文献 Entombed Atariゲームに関するWikipedia記事 Archive.orgでプレイ可能な実際のAtari 2600ゲーム「Entombed」 Leon MächlerとDavid Naccacheによる「Entombed Algorithmの説明」 Paul Allen Newell、John Aycock、Katie M. Biittnerによる「Still Entombed After All These Years: The continuing twists and turns of a maze game」 John AycockとTara Copplestoneによる「Entombed: An archaeological examination of an Atari 2600 game」 BBC: 「The mysterious origins of an uncrackable video game」 John Aycockによる「Interview with Steven Boykey Sidley re: Entombed」