Article: 迷路生成アルゴリズム
迷路を用いたものはゲームに限らず色々ありますが、どのように作られているか考えた事はないでしょうか。実はこのロジック、とても単純なものになっていて、知っているだけで楽に作れるようになります。何種類か方法がありますが、ここでは一番楽な「棒倒し法」を紹介していきます。
- 棒倒し法による迷路生成アルゴリズム。 |
壁の用意
まずはこのように、四角の外壁の中に、さらに等間隔に内壁を配置します。色分けされているのは便宜上のもので実際はどうでも良く、0(壁がある)と1(壁がない)の情報でも構成する事ができます。この壁を用意するのに気を付けなければならない事は、外壁を大きめに取っておく事です。多くのゲームではこの全体像が見える事はなく、スクロールという概念を用いたりして一部しか見えないようになっています。その際、スクロールで見える限界点が、外壁の外に到達してしまうと「情報を用意していない」、具体的には配列外の情報を呼んだ為にエラーを起こしてしまいます。この説明で理解できなかった人も、多分プログラムの段階で分かると思います
(^^; |
左端内壁の棒倒し
ではいよいよ迷路を制作しましょう。図1の黄色く描いた内壁のそれぞれを基点として、四方向の任意の方角に壁を作ります。その例が図2の通りです。黄色の内壁が9ブロックあるので、置いた壁も9つある事を確認してください。なお、置こうとした方角に既に壁があった場合は、
a) 別な、壁を置ける方角に必ず配置する。 このどちらかを選んでください。a) を選んだ場合は常に一通りしかない迷路ができあがります。言いかえると「右手法で必ず解ける迷路」となります。一方 b) を選んだ場合は、少しばかりの空間が生まれます。ダンジョンRPGのような3D系はこちらにしないと自由性がなくなってしまいます。 |
残りの迷路生成
残った暗橙色の部分の内壁それぞれを基点として、先程と同様に壁を伸ばしていきます。但し「左側には伸ばしてはいけません」。つまり伸ばせるのは上、右、下の3方角ということです。既に壁が置いてあった場合は、先に決めた通り対処します。全てにおいてこの施行を行なえば、図3のように完成します(a による構築)。パターンとしては左上隅がスターと、右下隅がゴールですが、どこに設定しても構いません。20円の当たりつきガムで見た絵だなぁと思うかもしれませんが、あれとは違い、常にゴールに辿りつける手順が存在しています(笑)。 |
2Dでも色々な拡張方法はあります。ディアブロがその良い例で、この迷路マップをあくまで「縮小図」的に扱い、その中に様々なオブジェを配置する手法です。こうすると、一見迷路と思えないようなフィールドで、それでいて迷路になっていることが分かるわけです。そういった拡張手段は各自考えてみてください。なお、先の b) パターンを用いた迷路プログラムを、VBScript で作成してあります。IE4、IE5 を使っている方は、ぜひ遊んでみてください。ソースを見れば、先のアルゴリズムをどうコードにすれば良いか判ると思います。→「子供だまし迷路 Ver0.1」を遊ぶ - 鷹月ぐみな |