32バイトのテーブルを JavaScript に移植した｜Entombed の迷路をブラウザで動かす

1982年のアルゴリズムを現代のブラウザで動かすことを表したアイキャッチ Retro Computing
この記事は約12分で読めます。

論文に書いてあるとおりに動きました。

32個の数字を配列に入れて、5マスを見て次の1マスを決める処理を書いて、ブラウザで回す。上から迷路が湧いてきて、左右対称で、Hard 設定にすると時々行き止まりが出る。前の記事で読んだ話が、そのとおりの形で画面に出てきました。

ここまでの2本は、公開されている論文と報道を読んで追いかけただけでした。この記事だけが、自分の手を動かした部分になります。動かしたのは JavaScript の移植版で、実機や ROM は触っていません。下敷きにしたのは、エイコックらの論文の付録に載っている Python の再構築コードです。

デモページにそのまま置いてあります。以下、コードを順に追います。

持っている状態

先に、実行中に保持しているものを並べておきます。ここが少ないことが、このアルゴリズムの性格を決めています。

  • prevRow ── 1つ前の行。8ビット
  • lastrows ── 直近の数行。後処理でだけ使う
  • lasttwo ── いま作っている行で直前に決めた2マス
  • MAGIC ── 32エントリのテーブル。定数

迷路全体を持っていません。生成に必要なのは、前の行1本と、いま埋めている途中の2ビットだけ。画面に出ている部分は Canvas 側が持っていますが、アルゴリズムは参照しません。lastrows だけが例外で、これは後処理のために数行ぶん覚えています。

1982年の実機では、この prevRow が RAM の1バイトでした。128バイトのうちの1バイトです。

32バイトを配列にする

1
2
3
4
5
6
const MAGIC = [
    [1, 1, 1, null, 0, 0, null, null],  // ab=00
    [1, 1, 1, 1, null, 0, 0, 0],        // ab=01
    [1, 1, 1, null, 0, 0, 0, 0],        // ab=10
    [null, 0, 1, null, null, 0, 0, 0]   // ab=11
];

第1の添字が、いま作っている行で直前に決めた2マス（a, b）。第2の添字が、上の行の3マス（c, d, e）。合わせて5マスぶんで、4×8の32通りになります。1 が壁、0 が通路、null が乱数で決める箇所です。

具体的に引いてみます。MAGIC[0][3] は ab=00、cde=011 のケースで、値は null。周囲の状態からは壁でも通路でも成立するので、乱数に投げる。MAGIC[1][5] は ab=01、cde=101 で、値は 0。ここは通路にするしかない。

3種類の出力を、真偽値でも文字列でもなく null 混じりの数値で表すのは、書いていて少し気持ち悪かった。TypeScript に持っていくなら 0 | 1 | null のユニオンで明示することになります。ただ、元が32バイトの ROM 領域で、値が 0 と 1 と 2 と 3 だったことを思うと、型を増やさないほうが元に近い。そのままにしました。

10個ある null の位置を眺めると、どれも「どちらでも成立する」パターンに置かれています。3つのルールが答えを決められる場所では確定値になり、決められない場所だけ乱数に落ちる。表を先に見てからルールを聞くと魔法に見えますが、ルールを先に知って表を見ると、そうとしか書けないという顔をしています。

最終行の右端、MAGIC[3][7] が 0 なのは分かりやすい例です。ab=11 で直前2マスが壁、cde=111 で上の行も壁。ここを壁にすると2×2の壁ブロックが完成してしまうので、通路にするしかない。前の記事で書いた1つ目のルールが、この1マスに出ています。

行の外側を作る

実装で最初に詰まったのは、迷路の端でした。

1行は8ビットです。左端のマスを決めるとき、上の行の、1つ左よりもう1つ外まで見る必要がありますが、そこは行の外側でデータがありません。右端も同じです。

1
2
const leftBit  = getRandomBit();
const rightBit = (mode === 'easy') ? 1 : getRandomBit();

左は常に乱数。右は設定で変えます。ここが Easy と Hard の分かれ目でした。右端を壁で固定すると通路の連結が常に守られ、乱数にすると時々破れる。前の記事で読んだ境界条件の話が、コードでは2行でした。

用意した2ビットを、前の行の左右にくっつけて10ビットにします。

1
2
3
4
5
let lastrowpadded = leftBit;
lastrowpadded <<= 8;
lastrowpadded |= prevRow;
lastrowpadded <<= 1;
lastrowpadded |= rightBit;

言葉だと分かりにくいので、値を追います。prevRow = 0b10110010、leftBit = 1、rightBit = 0 のとき。

1
2
3
4
5
1. lastrowpadded = 1         → 0b1
2. lastrowpadded <<= 8       → 0b1_0000_0000
3. lastrowpadded |= prevRow  → 0b1_1011_0010
4. lastrowpadded <<= 1       → 0b11_0110_0100
5. lastrowpadded |= rightBit → 0b11_0110_0100

左端の1ビットを置いてから8ビットぶん左へずらして前の行を流し込み、もう1ビットずらして右端を足す。結果が10ビット。この上を3ビットの窓が滑っていきます。

シフトの回数を1つ間違えると、窓が半マスずれて迷路がまるごと崩れます。ここは何度か行ったり来たりしました。toString(2).padStart(10, '0') でログに出しながら合わせています。

1行を左から埋める

本体はこれだけです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (let i = 7; i >= 0; i--) {
    const threeabove = (lastrowpadded >> i) & 0b111;
    const tableVal   = MAGIC[lasttwo][threeabove];
 
    let newbit;
    if (tableVal === null) {
        newbit = getRandomBit();
    } else {
        newbit = tableVal;
    }
 
    newrow  = (newrow << 1) | newbit;
    lasttwo = ((lasttwo << 1) | newbit) & 0b11;
}

10ビットの上を3ビットの窓が右へ滑っていく様子。iが7、6、5と減るごとに参照位置が1マスずつ移動することを示した図

ループは 7 から 0 へ降ります。i は、いま決めているマスの位置。7 が左端で 0 が右端です。

(lastrowpadded >> i) & 0b111 で、10ビットの中から3ビットを切り出します。i = 7 なら上位3ビット、i = 0 なら下位3ビット。i が1ずつ減るたびに、窓が1マスぶん右へ動く。10ビットから3ビットの窓で8回取ると、ちょうど端まで届きます。

newrow は左シフトして OR で積むので、最上位ビット側から順に埋まります。i の降順と向きが揃っている。

最後の行の & 0b11 が地味に効いています。左に1ビットずらして新しいビットを足し、下位2ビットだけ残す。これで「さっきの b が新しい a、いま決めたのが新しい b」になる。lasttwo という2ビットの窓が、行の上を左から右へ這っていく形です。

分岐は「テーブルの値が null かどうか」の1つだけ。再帰も探索もバックトラックもありません。1マスあたりシフト2回、マスク2回、配列参照1回、分岐1回。6507 のアセンブリなら10数サイクルで、1行8マスなら100サイクル台に収まる計算になります。走査線1本あたり76サイクルという制約に対して、水平帰線期間を足せば足りる範囲です。

行の最初の一手だけ、まだ何も決めていないので初期値が要ります。

1
let lasttwo = (mode === 'easy') ? 0b11 : 0b01;

Easy では行の左外に壁が2つあることにする。Hard では 01 で、オリジナルの挙動を再現します。左端の leftBit と合わせて、境界の与え方が2箇所あることになります。

テーブルだけでは足りなかった

ここが、書く前に想像していなかった部分でした。論文の実装には後処理があります。

1
2
3
4
5
6
7
8
9
10
11
12
// 左半分の閉塞を潰す
let history = lastrows.map(b => b & 0xF0);
if (!history.includes(0)) {
    let sumLeft = 0;
    for (let b of lastrows) {
        sumLeft += (b >> 7) & 1;
    }
    if (sumLeft === 0) {
        lastrows[lastrows.length - 1] = 0;
        newrow = 0;
    }
}

b & 0xF0 で各行の上位4ビット、つまり左半分を取り出します。それが直近の行すべてで非ゼロ、言い換えると左半分のどこかに必ず壁がある状態が続いている。そのうえで (b >> 7) & 1、最左端の列を全行ぶん足して 0、つまり左端はずっと通路のまま。この2つが同時に成立したら、いまの行を丸ごと 0 にします。

右半分にも同じ形の処理があります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 右半分の閉塞を潰す
if (lastrows.length >= 7) {
    const recent7 = lastrows.slice(-7);
    history = recent7.map(b => b & 0x0F);
    if (!history.includes(0)) {
        let comparator = 0;
        if (lastrows.length >= 9) {
            comparator = lastrows[lastrows.length - 9];
        }
        let sumRight = 0;
        for (let b of recent7) {
            sumRight += b & 1;
        }
        if (sumRight === (comparator & 1) * 7) {
            lastrows[lastrows.length - 1] &= 0xF0;
            newrow = lastrows[lastrows.length - 1];
        }
    }
}

こちらは直近7行の下位4ビットを見ます。7行すべてで右半分に壁があり、なおかつ右端の列7つが、9行前の右端と同じ値で揃っている。そのときだけ下位4ビットをクリアする。(comparator & 1) * 7 は、7行ぶんの合計が全部 0 か全部 1 かを見ているだけで、実質は「揃っているか」の判定です。

7 と 9 という数字に、いまのところ説明を見つけられていません。3つのルールから導けるものではなく、動かしながら決めた値に見えます。

テーブルが見ているのは5マスだけです。局所的には全部正しくても、何行も積み重なると閉塞したパターンが育つことがある。それを潰すための安全弁でした。

3つのルールで32個の数字が全部説明できる、という前の記事の話は美しいのですが、実際の ROM には表の外側にこういう処理が入っています。理論で説明できる部分と、動かすために足された部分が、同じプログラムの中に同居している。ここを読んだとき、自分のプラグインのことを思い出しました。設計として説明できる箇所と、動かなかったから足した箇所が、区別なく並んでいる。

画面に出す

1
2
3
4
5
6
7
8
9
10
11
12
function rowToPlayfield(row) {
    let pf = [];
    pf.push(1, 1);                  // 左の外壁
 
    for (let i = 7; i >= 0; i--) {
        const bit = (row >> i) & 1;
        pf.push(bit, bit);          // 1ビットを2ピクセルに
    }
 
    const mirror = pf.slice().reverse();
    return pf.concat(mirror);       // 左右対称にする
}

8ビットを2ピクセルずつに引き伸ばして、左に外壁を2つ足す。ここまでで18ピクセル。それを反転コピーして右半分にすると36ピクセルになります。

slice() を挟んでいるのは、reverse() が破壊的だからです。ここは1回踏みました。pf.reverse() と書くと pf 自身がひっくり返るので、concat した結果が左右とも反転した迷路になります。画面を見て気づくまで少しかかりました。

この反転は、オリジナルでは TIA というチップのプレイフィールド反転モードが担っていた部分だそうです。ハードウェアが持っていた機能を、こちらは1行の reverse() で書いている。40年前は配線でやっていたことを、いまは配列操作でやっている。

2ピクセルへの拡大も、実機側の都合をなぞったものです。Atari 2600 のプレイフィールドは横方向の解像度が粗いので、1マスを1ドットで描くと迷路が細くなりすぎる。左右対称なのも、指定するビット数が半分で済むからでした。第1部で書いた128バイトの制約が、迷路の見た目そのものを決めていることになります。

動かして見えたこと

デモには Auto と Step を付けました。Step のほうが面白い。1行ずつ進めながら、いま参照しているコンテキストと、テーブルのどのマスを引いたかを右側に出しています。

Hard で回していると、行き止まりが本当に出てきます。ゲームではここで壁を壊すアイテムを使うことになる。Easy に切り替えると出なくなる。rightBit を 1 に固定しているだけで、迷路の性質が変わります。

右端の境界を乱数にした Hard では行き止まりが出るが、1に固定した Easy では上から下まで通路がつながることを比較した図

右のパネルには、参照したコンテキスト、乱数を引いた回数、テーブル32エントリのうちいまどこを見ているかを出しました。Step で1行ずつ進めながらこれを眺めると、5マスの窓が滑っていく様子が追えます。

デモ

Entombed 迷路ジェネレーターのデモ画面。左に生成された迷路、右に参照中のコンテキストと32エントリのテーブルが表示されている

デモページで動きます。HTML と CSS と JavaScript を1ファイルにまとめてあるので、ページのソースを保存すればローカルでもそのまま動きます。

  • New ── 新しい迷路を作る
  • Step ── 1行だけ進める
  • Auto ── 連続で進める。もう一度押すと止まる
  • Easy / Hard ── 右端の境界を切り替える
  • Speed ── Auto のときの間隔

参考

1982年に4KBのROMに収まっていた処理を、2026年のブラウザで動かすのに書いたのは、200行ほどでした。

Retro Computing
この記事を書いた人
rapls
rapls

WordPressのプラグインを作っているフリーランスエンジニアです。Web開発はもう6年以上。WordPress.orgで Rapls AI Chatbot、Thanks Mail for Stripe、Rapls PDF Image Creator、Prime Cache の4本を公開し、保守を続けながら、日本語ロケールの翻訳エディター(PTE)も務めています。このブログに書くのは、現場で自分が実際にハマって、調べて、直した話です。

raplsをフォローする
raplsをフォローする

フォローする

同じ文面を流し込むのではなく、媒体ごとに書き分けています。

rapls

コメント

タイトルとURLをコピーしました