HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Show HN: Entombed in a Raycaster (stelabouras.com)

34 pointsby stelabouras6 コメント

要約

この記事は、Atari 2600のゲーム「Entombed」に登場する、メモリ制約下で迷路を生成するユニークなアルゴリズムに焦点を当てています。著者はこのアルゴリズムの謎めいた仕組みと、それを現代のRaycaster実装に応用した自身のプロジェクトについて解説しています。このアルゴリズムは、限られた情報から迷路を逐次生成するという、従来の迷路生成法とは異なるアプローチを取っています。

全文翻訳

Raycasterに閉じ込められて

2026年9月25日 金曜日

[画像: 記事の冒頭の画像]

約1年前(もっと経っているかもしれない、私の記憶は曖昧なことがある)、私はほとんどのゲーム開発者が経験するであろう、レイキャスターの通過儀礼を経験しました。Lodeのチュートリアルや、YouTubeの「Make Your Own Raycaster」シリーズ(どちらも強く推奨するリソースです)を読んでいたとき、「Entombed」というAtari 2600のゲーム(1983年)で見つかった迷路生成アルゴリズム、「Entombedアルゴリズム」に出会いました。このゲームでは、プレイヤーはゾンビに追われながら迷路からの脱出を目指します。

このアルゴリズムに私が惹かれたのは、Atari 2600の制約の中で次の行がどのように生成されるかを指示する、古(今ではほとんど秘術的)なロジックに基づいて迷路が手続き的に生成されていた点です。

Atari 2600は128バイト(はい、bです)のRAMしか持たず、「Entombed」では、プレイヤーが下に進むにつれて迷路は上方に連続してスクロールします。これは、デバイスのメモリ制限を考えると、保存された迷路は事実上不可能であることを意味します。そのため、迷路は一度に1行ずつ作成され、スクロールして画面外に出ると破棄される必要があります。ここで疑問が生じます:数行しかメモリに保持できない場合、どのようにして一度に1行ずつ迷路を構築するのでしょうか?そこで登場するのがミステリーテーブルです。

「Entombed」ゲームがゲーム考古学者の関心を引いた本当の理由は、迷路生成の背後にあるミステリーテーブルと、今日に至るまで誰もその仕組みを完全に説明できていないという事実です。長年、それは「酔っ払って頭がおかしくなった誰か」によって書かれたという話がありました。実際のところ、その話はそれほど的外れではありませんでした:Paul Allen Newellと数学の大学院生Duncan Muirheadが、バーでビールを数杯飲みながらナプキンにそれをスケッチし、Newellは週末の終わりまでにはそれをAtariで動作させていました。

[画像: Entombedの迷路生成に使用されたミステリーテーブルのマッピング]

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)、またはコイン投げ(random)を返します。そして、それがすべてです。バックトラッキングも検索もありません。行は一度のスキャンで、テトロミノのようなウィンドウがセルごとにスライドしながら埋められていきます。

[画像: セルの生成方法を示すウィンドウ、スライド方向、ルックアップ、書き込まれる値]

セルの生成方法。
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回の修正パスが導入されています。これらは、行が完了した後、後続の行を参照して実行されます。迷路が繰り返しパターンに入ったり、セクションを壁で囲ったりし始めた場合、行全体または半分を空白にします。

見つけられるすべての参考文献を消費した後、すぐにそれをレイキャスターに実装する方法を考え始めました!それは、レイキャスターの仕組みを学び、この古代(年齢によるが)のAtariゲームから取られたロジックで手続き的に生成されるマップを除いて、シンプルなWolfenstein 3Dレンダラーを作成するという、非常に楽しいサイドプロジェクトになりました。

各迷路行の状態をuint32で表現することにしました。各ビットが壁かそうでないかを示すようにします。これにより、プレイヤーがさらに遠くまで移動するにつれて、計算が容易になり、メモリ効率も向上します。

[画像: Atari 2600のEntombed、中央で鏡映されたプレイフィールド]

Entombedのゲームプレイ。Archive.orgからキャプチャ。
対称性に注意:プレイフィールドの半分しか生成されておらず、残りはその鏡像です。

私のバージョンはオリジナルといくつか異なります。ミラーリング(上記のスクリーンショット参照)を削除し、プレイフィールドを30セルに広げ、メモリは今日問題ではない(あるいはそうなのか?)ので、生成された行は決して破棄しません。

また、プレイヤーと敵に前方の壁を破壊する能力を与えました。これは(理論上は)迷路生成にフィードバックされる可能性がありますが、実際には決してそうなりません。生成される行は十分に先行しているため、プレイヤーが何かを破壊する頃には、ジェネレーターははるか先に進んでいます。

面白いのは、最近になってオリジナルのゲームもプレイヤーに同じ壁破壊能力を提供していたことに気づいたことです。行き止まりから進む簡単な方法を提供する必要があることを考えると、それは理にかなっています…特に謎の存在に追われている場合はなおさらです。

C言語での実装は3DSageが提供したものの上に構築し、プレイヤーと敵エンティティがスタックする可能性のあるいくつかのコーナーケースを修正しました。全体として、非常に楽しくユニークな経験でした。

それが機能するようになると、ほとんど忘れていました。そして数週間前、「Backrooms」の映画を見た後、この短い実験を思い出しました。そこで、それを少し改善し、いくつかのマイナーな問題を解決し、Backrooms風のゲームとしてスキン(訴えないでくださいね lol)して、世界に公開しようと思いました。

さらに、Claudeにブラウザでプレイ可能なThree.js版を作成させ、さらにいくつかのエフェクト(Diablo風のミニマップを再現しようと最善を尽くしました)を追加しました。C言語のゲームをコンパイルして実行するのが面倒な場合のためです。

[画像: Three.js版 Entombed]

EntombedレイキャスターのThree.jsバリアント。

どこまで行けば閉じ込められてしまうのでしょうか?

参考文献