論文に書いてあるとおりに動きました。
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; } |
ループは 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 に固定しているだけで、迷路の性質が変わります。
右のパネルには、参照したコンテキスト、乱数を引いた回数、テーブル32エントリのうちいまどこを見ているかを出しました。Step で1行ずつ進めながらこれを眺めると、5マスの窓が滑っていく様子が追えます。
デモ
デモページで動きます。HTML と CSS と JavaScript を1ファイルにまとめてあるので、ページのソースを保存すればローカルでもそのまま動きます。
- New ── 新しい迷路を作る
- Step ── 1行だけ進める
- Auto ── 連続で進める。もう一度押すと止まる
- Easy / Hard ── 右端の境界を切り替える
- Speed ── Auto のときの間隔
参考
- Entombed: An Archaeological Examination of an Atari 2600 Game ── John Aycock, Tara Copplestone（2018）。付録に Python の再構築コードがあり、この実装はそこを参照しています
- Explaining the Entombed Algorithm ── Léon Mächler, David Naccache（2021）
- Still Entombed After All These Years ── Paul Allen Newell, John Aycock, Katie Bittner（2022）
1982年に4KBのROMに収まっていた処理を、2026年のブラウザで動かすのに書いたのは、200行ほどでした。
コメント