brown water

ゲームやアニメの感想とかプログラムとか

迷路の作成

迷路作成のアルゴリズムを勉強してみました。

ドルアーガの塔の迷路

きっかけですが、ニンテンドースイッチナムコミュージアムに入っているドルアーガの塔を最近遊びました。 懐かしのゲームですが、ヒントもすぐに見られたし何とかクリア出来ました。

f:id:chaz4:20171120220536j:plain

このゲームの迷路作成に関する記事が興味深かったので作って試してみようと思ったのでした。

各柱から ランダムで壁を伸ばします。

f:id:chaz4:20171120221646p:plain

2ビットの乱数 (0~3)を取得し

00: 上に伸びる壁
01: 下に伸びる壁
10: 右に伸びる壁
11: 左に伸びる壁

伸ばした先の柱が、「外壁」 or 「既に壁がある柱」 だった場合
新たに「壁のない柱」から スタート
そうでなければ、伸ばした先の柱 で 同じ処理を行う

f:id:chaz4:20171120221651p:plainf:id:chaz4:20171120221655p:plain

これを繰り返し、全ての柱に 壁があるなら迷路完成

---省略---

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

前回、生まれた乱数が 1だった場合
次の壁は
10: 右に伸びる壁
11: 左に伸びる壁

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

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

迷路作成のアルゴリズムは色々あるようですが、この方法が簡単そうで面白そうだったので作ってみることにしました。

JavaScriptで作成

f:id:chaz4:20171120220522p:plain

準備段階のイメージ(生成用柱が3×2本の場合) 青が柱で、1ブロックごとに間をあけて配置されています。この柱から壁を伸ばしていく。 茶色は外壁。

生成用柱のみの配列を用意、これには柱を伸ばしたかどうかを記録していく。上記の場合だと3×2の配列
他にステージ情報用の配列を用意、壁の位置を記録していく。上記の場合だと9×7の配列。外壁は先に壁情報で埋めておく。

そして迷路生成作業。
ドルアーガの塔での作成方法をそのままプログラムに記述していく。
今回は生成用柱の領域は8×6で作成しました。

f:id:chaz4:20171120220540p:plain

配列「stage」にステージ情報が書き込まれ、最後にその情報を元にCanvasに描画しています。
リロードする度に新しい迷路が作成されます。
何度か試してみましたが、袋小路(進めない箇所)は作成されなかったので、上手くいったのではないかと思います。

壁を細くする

描画の部分を下記に変更。 壁が細くなり、雰囲気が実際のゲーム画面に近づきます。

f:id:chaz4:20171120220546p:plain

実際のゲームでは乱数のseedというものを使い、各フロアの配置は毎回同じ迷路になります。
フロアごとのデータを持たなくても、これを使って生成するので余計なメモリを使わなくて済むというわけです。当時は特にメモリ等の制限が厳しかったと思うし。
ちなみに、JavaScriptには標準では乱数のseedというものは無いようです。

今回使用した迷路生成アルゴリズムは30年前に使われたものですが、今でも使えるし、すぐに試してみたくなるようなシンプルさが素晴らしいです。