【C#】棒倒し法で作る迷路

C#

 

最近Unityで迷路を作ったのでその時に使った迷路を作るアルゴリズムを紹介します。実際には、上のサムネにあるようなものを作ります。

棒倒し法で迷路を作るアルゴリズム

 

簡単な作成法を説明します。

まず、迷路は縦横奇数マスで作ります。

そして□を壁として下のような配置で初期化します。これらは配列を使って作ります。例えば壁を0、壁じゃない部分(穴と呼ぶ)は-1として、実際に表示する際に「0なら”□”と表示」、「-1なら” ”と表示」と設定します。

 

そこから外周の壁とその内部の壁で、内部の1つ1つの壁から上下左右にランダムに壁を発生させます。つまり□から右に壁を発生させると□□となります。

 

これが棒倒し法と呼ばれる所以で、一つの壁□からその上下左右のいづれかに壁□ができる様が、最初の壁□を倒したようだからです。

 

この時、上下左右ランダムに倒すなら何でもいいというわけではなく、ほかの壁□とかぶってはいけません。つまり、□ □ があるとして、右側の壁が右に倒れて、左側の壁が左に倒れるち壁になる部分がかぶってしまうが、そうなってはいけないと言うことです。

 

なのでランダムに倒すとき、「他の壁がすでに倒れて□になっていないか」を確認する作業を加える必要があります。

 

また、一番最初の□の行は上下左右に倒れることが出来ますが、それ以降の行の□は上に倒れることはできません。もしこれが出来てしまうと、ある壁□の上下左右にある壁□が自分に向かって壁□を伸ばした際に自分自身の上下左右が壁□で埋められてしまい、結果自分は倒れることが出来なくなります。

 

以上のルールをまとめると

  • 迷路のマス目は奇数×奇数
  • 最初の行の壁□は上下左右に倒れることができるが、2行目以降は下左右にしか倒れられない
  • 倒れる場所がすでに壁□になっている場所に倒れてはいけない

多分このくらいです。

 

実際のソースコードを貼ります。

迷路自動生成(棒倒し法)のソースコード

 

 

上のコードでは大まかに

  • 迷路を作るMazeByRodメソッド(迷路の初期化と迷路作成)
  • 迷路を表示するPrintメソッド(迷路配列の値に基づいて迷路を表示)
  • Mainメソッド(上の2つのメソッドを呼び出す)

です。MazeByRodは(棒による迷路)の意味です。

 

コメントがわちゃわちゃしてるかもしれませんが、なるだけわかりやすいようにしたかったので邪魔だったら消してください。

 

また、コード内のランダムな値を設定するときのシード値はユーザーが自由に設定できるようにすれば、よりランダムな迷路を作ることが出来ます。

 

このプログラムはどこかからコピペしたのではなく、私が独自に考えたものなので、要領が悪い部分が目立つかもしれませんが、そういう所は、改善された方を採用してください。

 

おまけ

 

Unityで作った迷路です。

ただこちらは棒倒し法ではなく、穴掘り法というアルゴリズムで作った確か99×99の迷路です。

 

 

かなりキモイですねw

左下のほうから実際に迷路を探索してみましたが、さすがにゴールにたどり着けませんでした。というか、あきらめました。

 

コメント