見出し画像

【随時更新】ドル塔迷路生成に挑戦

Hajime Saito

※このエントリは試行錯誤する度に追記されます。

Pythonを憶えるために、何かを題材を探してプログラムを組むことにしたけれど、家で暴れる4歳児の相手をしながらゲームを作るのはシンドイし、短時間で切り上げにくい。

ただ、C++で作っていたゲームライブラリを少しPygameに移植したし、ゲーム関連にしてゲームライブラリは使っていきたい。

そういう考えから1984年にナムコ（現バンダイナムコエンターテインメント）から発売された『ドルアーガの塔』の迷路生成に挑戦することにした。

『ドルアーガの塔』と言えば、迷路状に入り組んだフロア構成が印象的なんだけど、これが1バイトのデータだけを元に自動生成されていることを開発者のEVEZOO遠藤雅伸さん（私は「邪神」と呼んでいる）が開示している。

邪神の話を聞いて驚いたのは、その1バイトのデータというがフロア番号を乱数のシードとして使い回していることで、フロアごとにマップ生成のデータを用意していないという点である。

フロア番号はコンピュータのプログラムらしく0から始まる、いわゆる0オリジンである。

例外がひとつだけある。それはフロア60だ。このフロアのみ専用のデータ値「255」が与えられている。この「255」という値を与えることで次のイメージのようなフロアが生成されるのだ。

画像1

最初の実装

自動生成をするゲームにおいては、疑似乱数のできばえがゲームの面白さを左右する。「ドルアーガの塔」で使われている疑似乱数アルゴリズムはどのようなものだろうかとウェブ検索をかけたら、「せっき～のゲーム屋さん」というブログにある、次のエントリを見つけることができた。

ドルアーガの塔　乱数の工夫の正体

まずはここを足がかりに実装をしていくことにした。

折角ゲームライブラリを移植したのだから、形から入っていこうということで、まずはウェブ検索して「ドルアーガの塔」のマップチップをWindows付属のペイントソフトでポチポチ作成することにした。

柱のデータには上下左右の壁が紐付けることにしたので、上下左右4枚の壁が紐付いた壁であれば、データ値は0x0Fとなる。それを意識しながら柱のデータ16個を並べる。

アーケード版をよく知っている人であれば、壁の長さは20ドットとなっていて、フロアの初期表示を行う前に壁と柱の隙間は綺麗に埋められている。マトックで壁を破壊したときのみ、16ドットのレンガを描き直しているので、柱から2ドットだけ壁が生えている状態となる。

疑似乱数ルーチン

『ドルアーガの塔』に絡む疑似乱数については、ウェブ検索をすると2通りのアルゴリズムを見つけることができる。

ひとつめは「せっき～のゲーム屋さん」で紹介されているアルゴリズムで、LFSR（Linear Feedback Shift Register、線形帰還シフトレジスタ）というものだった。

『ドルアーガの塔』では、ビット7とビット4を取り出し、排他的論理和をかけたものをさらにビットを反転してCとし、元の値を1ビットだけ左シフトして最下位ビット（LSB、Least Significant Bit）へCを入れるというもの。

Pythonのコードで書くとこのようになる。データ長は8ビットみたいなのでマスクをかけている。

bit7 = int(value & (1 << 7) != 0)
bit4 = int(value & (1 << 4) != 0)
c = ~(bit7 ^ bit4)
value = (value << 1) | c & 0xff

これのアルゴリズムであれば、乱数シードが255であれば、Cはかならず1が作成されつづける。乱数値は延々と255となる。

次に見つけたのが、「hayase memo」というブログ。このhayaseさんという方は、ドルアーガクローン「replica of TOD」をFlashベースで作成されている。

次のエントリでは6809ニモニックが書かれているが、「せっき～のゲーム屋さん」のアルゴリズムとはまた随分と違う。

ドルアーガの塔-フロア生成を可視化

Pythonのコードで書くとこのようになる。

work = value
work <<= 1
       work <<= 1
work <<= 1
work ^= value
work = ~work
c = int(work & (1 << 7) != 0)
value = value << 1 | c & 0xff

最後のROL命令はイミディエイト・メモリを指定しなければならないので、おそらくROL WORKの書き間違いではなかろうかと思う。

壁を生やす方向の決め方

疑似乱数で取得される値がどうであれ、基本的な迷路を生成するアルゴリズムは別にある。まずは取得した乱数の値を使って壁を生成する方向を決める。

壁の生える方向は「せっき～のゲーム屋さん」ではパターン1、一般的なゲーム開発で使われている時計回りのパターン2が考えられます。

壁の生える方向

『ドルアーガの塔』がパターン1のような特殊な入力方向データを使っていることについて、「せっき～のゲーム屋さん」ではbit1を上下と左右でわけることで、連続的なジグザグ壁が生成されやすいということらしいです。

ドルアーガの塔では、
線形帰還シフトレジスタ で得た 乱数の1ビットと
前回得た乱数 1ビット
を使って 2ビットを生成しています。

前回、生まれた乱数が 1だった場合

次の壁は
10： 右に伸びる壁
11： 左に伸びる壁

右に伸びる壁（10） の後は、
必ず 上に伸びる壁（00）か、下に伸びる壁（01） になります。

となると、
右下へのジグザグ壁 というのが生まれやすい
（10 → 01 → 10 → 01 → 10 → 01 → )

せっき～のゲーム屋さん
「ドルアーガの塔　乱数の工夫の正体」より引用

これに対し「『ドルアーガの塔』研究室」では、邪神が迷路生成のアルゴリズムに答えている。これはかつて邪神が『2ちゃんねる』で質疑応答していた際の記録である。

これは画期的なことかも知れないんだけれど、TODは１フロアにつきマップのデータを１バイトしか持っていません。つまり、プログラム的にはマップという概念がないんですね。ちょっと難しいのですが、説明します。
　TODの迷路は、まず全ての柱を想定します。そして、最初の１本を選び、そこから面数を根とした乱数によって、０～３の数を導き出し、それに相当する方向（ex.０:上、１:右、２:下、３:左）に壁を作ります。それが外壁か別の壁に接触しなければ、新しい根より０～２の乱数をもとめ、そちら方向（ex.０:進行方向左、１:まっすぐ、２:進行方向右）へ壁を伸ばします。これを外壁か別の壁に接触するまで続けます。
　もし外壁か別の壁に接触した場合、最初に選んだ柱から順番に、まだ壁の通過していない柱を選んで同じ処理を繰り返します。壁の通過していない柱がなくなると迷路の完成、結果として、迷路のある地点Ａから別の地点Ｂまで１通りしかルートのない、狭義の意味での迷路ができるのです。
　このフロアを元にした乱数の根を255にすると、なぜか整然とした迷路になってしまったので、これを特別に最上階60階の迷路用の根として、残りはフロア数がそのまま迷路のデータとなっているのです。
　あのフロア全てをデータで持つと大変なのですが、このような方式で作成しているため、全く同じ方法を取ったとしても、迷路のサイズが異なれば構造が違ってしまうわけです。遠藤としては、最上階以外のフロアの形状に関しては、まったく関心がなかったので、移植が同じ方法で迷路を生成しているのは、かえって新鮮で良いのでは？と思いました。

『ドルアーガの塔』研究室
「邪神の啓示『ドルアーガの塔』編」より引用

さらに邪神の説明するアルゴリズムでは、連続的に迷路を生成する場合には乱数の扱い方を変更している旨、情報開示されている。

パターン2は時計回りのアルゴリズムなので、現在の進行方向へ0を足せば進行方法は変わらず、-1するか+3をして下位2ビットを取得すれば左周りに方向が変わり、+1して同じく下位2ビットを取得すれば右周りに方向が変わる。

このパターンの違いは何か。neko800さんによれば、どうやらパターン1はファミコン版の生成パターンということらしい。

neko800さんの解説によれば、パターン1の方向は左右が逆とのこと。実際に再現されているのでこちらが正しいのだろう。

壁の伸ばし方

壁を生成する方向を決めたら、その方向へ壁を伸ばし、次の柱でまた乱数を振って壁を生成する方向を決める。この壁の伸ばし方は「柱倒し法」と呼ばれるアルゴリズムである。

邪神の解説によれば、2枚目以降の壁については乱数を使って転換する方向を決めるということだったが、実際には乱数では壁を伸ばす方向のみを決めており、方向転換を行うということはしていない。

これは古い記憶を頼りに解説しているための誤解説だと思われる。もしかしたら試行錯誤していた際に扱っていたアルゴリズムだった可能性も否定できない。

どんどん壁を伸ばしていくと、まるでTRONゲームのように、すでに生成した壁、あるいは現在伸ばしている壁にぶち当たるという事態に見舞われる。

この場合、壁を生やす方向を決め直す必要がある。

すでに生成した壁に当たった、あるいは外壁に当たった場合は、そこで壁を伸ばすことを止め、次の柱に処理を移せばよいらしい。

現在伸ばしている壁にぶち当たった場合はどうか。

牧野雅人さんの解説によれば、2つのパターンに分けられるそうである。

ひとつは方向転換すれば壁の生成を続けられるもの、もうひとつは方向転換できず、もう一度、現在作っている最中の壁を作り直したほうがいいものである。

現在進行中の壁を管理するためには、パンくずリスト（breadcrumb list）を利用すればよい。自身の壁に4方向囲まれている場合は作り直し、囲まれていないがぶち当たってしまった場合は乱数を振り直すという実装方法になる。

意外な盲点

私が再現したかったのはアーケード版だが、すでに自身で実装されている高岡義晴さんから貴重なアドバイスをいただいた。

なんと左上からではなく、右上の柱から壁の生成を行っているとのことだった。私自身も再現してわかったが、さらにY座標優先なのである。一筋縄ではいかないところが、さすが邪神の実装である。

つづく

この記事が気に入ったらサポートをしてみませんか？