この記事はUnityゲームプログラミングバイブルの内容を解説しています
https://www.amazon.co.jp/Unity%E3%82%B2%E3%83%BC%E3%83%A0-%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%83%BB%E3%83%90%E3%82%A4%E3%83%96%E3%83%AB-%E5%90%89%E8%B0%B7-%E5%B9%B9%E4%BA%BA/dp/4862464130

迷路自動生成アルゴリズム

今回は迷路などを入る度ランダムに生成するアルゴリズムについて話します
これによりゲームの繰り返しを避け飽きさせなくします

アルゴリズム

今回紹介するやり方は壁を作り部屋を作るというよりは
一面壁のフィールドに穴を掘っていくことで迷路を作ります

今回用いるアルゴリズムはマップの広さを奇数×奇数としたときのみ可能です
まずはランダムに奇数番目×奇数番目のマスを選択します（配列上では偶数×偶数番目）
今回は3×3番目の真ん中のマスを使おうと思います

1-1　スタート地点

まずはスタート地点の壁を掘り白くします
ここから穴を掘るルールを決めます

掘った穴から上下左右に2マス先を判定し壁があれば黒い矢印
2マス先に壁がなければ青い矢印にします

1-2　掘る

黒い矢印の中から1つをランダムに選びその方向の壁を2マス掘る

1-3　掘り進める

掘り進めた先のマス今回であれば上から1番目横に3番目のマスから
再び矢印をだし黒い矢印が出なくなるまで繰り返します

上にもう進むマスがない、下方向には2マス先に壁がないので青い矢印になり左右だけ
黒い矢印がでます

右方向をランダムに選んだとしたとき上のような図になります

1-4　最終形態

進んだマスから出る矢印がすべて青になった時終了し、その結果

自動でこのようなマップができました
ここまではイメージ図なので実際にゲームにマップを作る時を考えましょう

1-5　ゲームに適応

まずはこのマップのマス目に数字をつけましょう

スタート地点を２、ゴールを３、壁を０、掘った後は１にしましょう

この数字を配列に直し数字に対応したオブジェクトを置いていくことで迷路となります

2　不思議のダンジョンのような部屋のあるダンジョン制作

先ほど紹介したものはあくまで迷路でありただ進むだけです
そこで先ほどのアルゴリズムに工夫を加えてダンジョンっぽくしていきたいと思います

2-1　壁の用意

さきほど同様ップの広さを奇数×奇数としスタートの場所の選び方も同様にし
真ん中からスタートします
今回は壁を掘る際のルールを変更し

黒い矢印をそれぞれランダムにtrueとfalseにわけ
trueなら赤い矢印で壁を掘りfalseなら青い矢印で１マス横を黒く塗りつぶします
黒い矢印の条件は1マス先に壁があり壁が黒でないこととする

2-2　掘る

今回は上と右側をtrue、下と左をfalseとすると

このように掘り進めることができまた黒いマスもできます

2-3　掘り進める

そして先ほど同様掘った先のマスを基準に同じことを繰り返します

壁のない場所は矢印が青くなりもともとfalseになります
3×1のマスの左右の矢印がfalse
5×3のマスの上下の矢印がtrueになったとすると

このように掘り進めることができます

2-4　最終形態

この動作を繰り返した結果以下のようになります（なったと仮定）

2-5　ゲームに適応

スタート地点を２、ゴールを５、壁を０

ここまでは同じですがダンジョン風にするために
通路と部屋で分けます
矢印の判定をし、赤い矢印で壁を掘った時に2マス先を３、1マス先を１として

３を部屋、１を通路、黒い壁を４とする

数字に適応させマップにつけたのが

となる
この数字を配列に直し数字に対応したオブジェクトを置いていくことで迷路となります

０と４を壁、１を通路、２をスタート地点、３を部屋、５をゴールとする

2-6　補足説明

黒い壁を増やした理由

一度判定した道を再度判定し直さないようにするため

迷路自動生成アルゴリズム

アルゴリズム

1-1 スタート地点

1-2 掘る

1-3 掘り進める

1-4 最終形態

1-5 ゲームに適応

2 不思議のダンジョンのような部屋のあるダンジョン制作

2-1 壁の用意

2-2 掘る

2-3 掘り進める

2-4 最終形態

2-5 ゲームに適応

2-6 補足説明