書くことがぴんちなので、以前作ってみていた迷路の自動生成アルゴリズム各種とか。
インラインインデントですっきりさせました☆
壁伸ばし法を追加しています。
発端
迷路は人気があるのか、なでしこ貯蔵庫にも一時、迷路のプログラムが続けざまに上がりました。
でも、この記事のプログラムを流用して、自作のCSV迷路を解いてもらうというものが多かったです。
迷路データ自体は表計算ソフトの機能を使って作成したCSVで、二次元配列の扱い方やキーボードのイベントが学べる内容です。
そりゃねー、ダンジョンは自分で作った方が楽しいよね～。
冒険者をどうやって陥れてやろうか、ウヒヒ……なんてね！ｗ
ところで、マイナビの連載にはもう一つ迷路の記事があって、
こちらはプログラムで迷路を自動生成するというものです。
なんかかっこいいよね～。しゅごい！
が！！！
冒頭に掲げられた画像ですでに、アレ？
ってなるんですけど、どうでしょうか？
まず、島が多すぎ！ ってかほぼ島。よく見ると部屋もある。
ちなみに島とは、どこともつながっていない、周囲をぐるっと回れちゃう壁のことで、部屋とは壁に囲われて入ることの出来ない空間のことです。
ゲームのダンジョンならば同じところぐるぐる回らされるのもアリだし、入れない部屋があって、中にお宝があったりして、取るためには壁を壊すアイテムとかテレポートの魔法とかが必要みたいなことも大ありだから別にいいんですけれど、迷路というパズルとして考えた時には、入れない部屋はなく、正解ルートは一本しかない、というのが望ましい。
ぷろぐらむ、このていどか……（んなわけない💧）
あなおそろしや。コレは、おそらく罠ですよ。
ワタクシのようなド素人が、アレ？ ってなって迷路沼にはまらされるとゆう実に巧妙な……
そのために、わざとああなってるんです！ タブンそうです！！ 絶対にそうです！！！
迷路の自動生成
クラスタリング法
色々検索して、クラスタリング法とやらが名前からしてカッコよさげなのでやってみます。
詳しい説明などできませんからそれはご本家のページを見て頂くとして、ワタシの理解によれば、
- 最初に格子状に壁と部屋を作る。
- 各部屋に連番の部屋番号をつける。
- ランダムに壁を選んで、接する二部屋の部屋番号を比較。
・ 部屋番号が同じだったら、何もしない。
・ 部屋番号が違っていたら、
1. 壁を壊す。
2. 部屋番号を小さい方のに揃える。
3を全ての壁に対して行う。
こんな感じ？
[15,9]のクラスタリング法迷路作成して、それを表CSV変換して表示。
●(サイズの)クラスタリング法迷路作成とは:
変数 [道,壁]＝[0,1]。
変数 [迷路幅,迷路高]＝サイズ。
変数 迷路＝空配列。
変数 壁データ＝空配列。
変数 部屋番号＝空配列。
# 最初に全てを壁にする。
行を0から(迷路高-1)まで繰り返す。:
迷路[行]＝空配列
列を0から(迷路幅-1)まで繰り返す。:
迷路[行][列]＝壁。
変数 部屋数x＝迷路幅/2を整数変換。
変数 部屋数y＝迷路高/2を整数変換。
行を0から(部屋数y-1)まで繰り返す。:
列を0から(部屋数x-1)まで繰り返す。:
# 部屋を作る
迷路[行*2+1][列*2+1]＝道。
# 壊す壁のデータを作る
もし、行＝部屋数y-1でなければ、:
壁データに[行,列,行+1,列]を配列追加。# 部屋行,列とその下隣との間の壁。
もし、列＝部屋数x-1でなければ、:
壁データに[行,列,行,列+1]を配列追加。# 部屋行,列とその右隣との間の壁。
# 部屋に通し番号を付ける
部屋番号＝0から(部屋数x*部屋数y)までの配列連番作成。
# ランダムに壁を壊していく
壁データを配列シャッフル。
壁データを反復。:
変数 [Y1,X1,Y2,X2]＝対象。
変数 部屋番1＝部屋番号[Y1＋X1*部屋数y]。
変数 部屋番2＝部屋番号[Y2＋X2*部屋数y]。
もし、部屋番1＝部屋番2ならば、続ける。# 部屋番号が同じなら壊さない。
もし、X1＝X2ならば、:
迷路[Y1*2+2][X1*2+1]＝道。# 同じ列なら下の壁を壊す。
違えば、:
迷路[Y1*2+1][X1*2+2]＝道。# 同じ行なら右の壁を壊す。
# 部屋繋げる(クラスタリング)
変数 [統合先,統合元]＝[部屋番1,部屋番2]。
もし、部屋番1＞部屋番2ならば、:
統合先＝部屋番2。統合元＝部屋番1。
# 部屋番号が大きい方(統合元)を小さい方(統合先)の番号に全て変更する。
部屋番号の要素数回:
もし、部屋番号[回数-1]＝統合元ならば、部屋番号[回数-1]＝統合先。
迷路で戻る。
できました！
ループ（島）を作らない保証だとか死に領域（部屋）が出来ない保証だとかは、ワタクシの知恵では証明出来ませんが、見た感じ良さそげです（大雑把💧）
棒倒し法
検索してみると、棒倒し法の評判はイマイチ芳しくない。
そりゃそうだよね、っと愚かなワタシは当初思っていたのであるが、どうもそうゆうコトでは無いらしい。
迷路迷路で暮らしているうち次第に賢くなって、修正すべき点が発覚したのでやってみる。
棒倒し法についての解説は、さっきのマイナビの記事を見て頂くこととして、とりあえずこんな感じ。
- 最初に外周を壁、それ以外を道とする。
- 行も列も偶数なら柱を立てる（壁にする）。
- 上下左右のいずれかに向かって棒を倒す（壁にする）。
※ ただし2段目以降は上には倒さない。
※ 既に壁がある方向へは倒さない。
※の2点が追加した条項で、2段目以降で上に向かって倒すことを許すと、部屋が出来てしまうのねん。そして、最重要が、すでに壁がある方向へは倒さないことで、コレを許すと迷路がスカスカになって島が多発してしまうのでした。
[15,9]の棒倒し法迷路作成して、それを表CSV変換して表示。
●(サイズの)棒倒し法迷路作成とは:
変数 [道,壁]＝[0,1]。
変数 [迷路幅,迷路高]＝サイズ。
変数 迷路＝空配列。
# 外周を壁、それ以外を道とする。
行を0から(迷路高-1)まで繰り返す。:
迷路[行]＝空配列。
列を0から(迷路幅-1)まで繰り返す。:
# 最初に全部を道にする。
迷路[行][列]＝道。
# それから外周を壁にする。
もし、(列＝0)または(行＝0)または(列＝迷路幅-1)または(行＝迷路高-1)ならば、:
迷路[行][列]＝壁。
# 行も列も偶数なら柱を立てる（壁にする）
行を2から(迷路高-3)まで繰り返す。:
列を2から(迷路幅-3)まで繰り返す。:
もし(列%2=1)または(行%2=1)ならば続ける。
# まず柱を立てる。
迷路[行][列]＝壁。
# 上下左右のいずれかに向かって棒を倒す（壁にする）。
上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]。
# ただし2段目以降は上には倒さない。
もし、行>2ならば、上下左右の０を配列削除。
方向＝上下左右を配列シャッフル。
方向の要素数回:
ｘ,ｙ＝方向[回数-1]。
# 既に壁がある方向へは倒さない
もし、迷路[行+ｙ][列+ｘ]＝壁でなければ、:
迷路[行+ｙ][列+ｘ]＝壁。
抜ける。
迷路で戻る。
できました！
こうしてみるとぱっと見は、クラスタリング法で作った迷路と変わりません。
でも、1段目だけが上にも倒せる、とゆうルールのため、上の2行だけ柱が少ないとゆう弱点があるラシイ。ふーん、そうなんだー。
穴掘り法
棒倒し法に並ぶ、有名なヤツですよねー。
もっと真面目にやれば良かったけど、ほぼコレ。
- 最初に全て壁にする。
- 起点から穴掘り開始
※起点をまず掘るの忘れず！- 迷路掘削処理
・ 2マス先を調べて壁でなければ中止
・ 違えば、穴掘る。
3を再帰で掘り進める。
変更点は、掘り始めに起点をまず掘ること。でないとスタート地点が壁のままなので、スタート地点付近で変な地形が出ちゃう。
それと、他も全てそうなのですが、迷路の縦横の長さは違うく出来るようにしています。
実用のためのほかに縦横同じ長さで作り始めてしまうと、行？列？ タテ？ヨコ？ x？y？ ・・・と、なんかよく分かんなくなって間違えていてもなんとなく出来た感になってしまい、後になって発覚するから良くないのねん（ワタシ的に
）
[15,9]の穴掘り法迷路作成して、それを表CSV変換して表示。
●(サイズの)穴掘り法迷路作成とは:
変数 [道,壁]＝[0,1]。
変数 [迷路幅,迷路高]＝サイズ。
変数 迷路＝空配列。
# 最初に全部を壁にする。
行を0から(迷路高-1)まで繰り返す。:
迷路[行]＝空配列。
列を0から(迷路幅-1)まで繰り返す。:
迷路[行][列]＝壁。
# 左上を起点として穴掘りをはじめる
迷路[1][1]＝道。# 起点をまず掘る。
[1,1]から迷路の迷路掘削処理。
●(起点から迷路の)迷路掘削処理とは:
変数 [道,壁]＝[0,1]。
変数 [列,行]＝起点。# 起点は[x,y]の配列。
変数 [迷路幅,迷路高さ]＝[迷路[0]の要素数,迷路の要素数]。
変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]
変数 方向＝上下左右の配列シャッフル。
方向を反復:
変数 [RX,RY]＝対象。# ランダムに選択された方向。
変数 [X1,Y1]＝[RX+列,RY+行]。# 1マス先。
変数 [X2,Y2]＝[RX*2＋列,RY*2+行]。# 2マス先。
# 2マス先を調べて壁でなければ中止
もし、(X2≦0)または(X2≧迷路幅-1)ならば続ける。# 迷路の外
もし、(Y2≦0)または(Y2≧迷路高-1)ならば続ける。
もし、迷路[Y2][X2]=道ならば続ける。
# 穴を掘る
迷路[Y1][X1]＝道。
迷路[Y2][X2]＝道。
# 再帰的に掘削する
[X2,Y2]から迷路の迷路掘削処理。
迷路で戻る。
他とは見た目のマッタク異なる、ぐるぐるした感じの迷路になる。
櫛形（短い行き止まりが連なる形）はほぼ出ず、ぱっと見はキレイな迷路っぽくなるのですが、分岐少なくひたすら長い道のりを歩かされるような形も出る。
本当は、再帰じゃなく、行き止まったら次の掘削開始点をランダムに選択するような方がイイみたいなのねん。へー。
壁伸ばし法
コレも有名なヤツだと思うんですが、どうも棒倒し法と穴掘り法に比べて解説が少なかったり、名前だけではしょられてたりと扱いが悪い気がするんですが、気のせいですか？
わたしもスルーしてたんですが、前作ったヤツのせておわりってのもねと、追加で作ってみたら思ったよりも時間かかってしもうた
いちおう、ここを参考にしました。
棒倒しや穴掘り法についても書かれています。
- 最初に外周を壁、それ以外を道とする。
- 行も列もともに偶数なら壁建設開始候補地として記録する。
- 壁建設開始候補地の中からランダムに起点を選択。
- 壁建設処理。
1. 起点がすでに壁になっていたら中止。
2. 2マス先を調べる。
・建設中なら中止 。
・道なら建設中として続ける。
1. 起点と1マス先を建設中とする。
2. 2マス先を起点として再帰で建設を続ける。
・壁なら接続して建設終了。
1. 起点と1マス先を建設中とする。
2. 建設中を全て壁にして戻る。
3. 全ての方向が建設中の壁だったら建設失敗。
・全て道に戻して戻る。
なんか、他と比べて結構フクザツ？
[15,9]の壁伸ばし法迷路作成して、それを表CSV変換して表示。
●(サイズの)壁伸ばし法迷路作成とは:
変数 [道,壁]＝[0,1]。
変数 [迷路幅,迷路高]＝サイズ。
変数 迷路＝空配列。
変数 壁建設開始候補地＝空配列。
# 外周を壁、それ以外を道とする。
行を0から(迷路高-1)まで繰り返す。:
迷路[行]＝空配列。
列を0から(迷路幅-1)まで繰り返す。:
# 外周を壁にする。
もし、(列＝0)または(行＝0)または(列＝迷路幅-1)または(行＝迷路高-1)ならば、:
迷路[行][列]＝壁。
# 残りを全部を道にする。
違えば、:
迷路[行][列]＝道。
# 行も列もともに偶数なら壁建設開始候補地として記録する
もし(列%2=0)かつ(行%2=0)ならば、壁建設開始候補地に[列,行]を配列追加。
((壁建設開始候補地の要素数)＞０)の間:
壁建設開始候補地を配列シャッフル。
変数 [列,行]＝壁建設開始候補地[0]。
壁建設開始候補地から０を配列削除。
もし、迷路[行][列]＝道ならば、[列,行]から迷路に壁建設処理。
迷路で戻る。
●(起点から迷路に)壁建設処理とは:
変数 [道,壁,建設中]＝[0,1,9]。
変数 [列,行]＝起点。# 起点は[x,y]の配列。
変数 [迷路幅,迷路高さ]＝[迷路[0]の要素数,迷路の要素数]。
変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]
変数 方向＝上下左右の配列シャッフル。
方向を反復:
もし、迷路[行][列]＝道でなければ、戻る。
変数 [RX,RY]＝対象。
変数 [X1,Y1]＝[RX+列,RY+行]。
変数 [X2,Y2]＝[RX*2＋列,RY*2+行]。
迷路[Y2][X2]で条件分岐:
建設中ならば、:
続ける。
道ならば、:
迷路[行][列]＝建設中。
迷路[Y1][X1]＝建設中。
# 再帰的に建設する
[X2,Y2]から迷路に壁建設処理。
壁ならば、:
迷路[行][列]＝建設中。
迷路[Y1][X1]＝建設中。
行を0から(迷路高-1)まで繰り返す。:
列を0から(迷路幅-1)まで繰り返す。:
もし、迷路[行][列]＝建設中ならば、迷路[行][列]＝壁。
行を0から(迷路高-1)まで繰り返す。:
列を0から(迷路幅-1)まで繰り返す。:
もし、迷路[行][列]＝建設中ならば、迷路[行][列]＝道。
うーん、コレであってるのかなー？
なんか間違っていたら教えてください
一応、迷路はちゃんと出来ていると思うんだけど・・・（未検証💧）
再帰に頼っているせいか、迷路が大きくなると、他よりワンテンポ遅いような・・・
やっぱり間違ってました！
壁に接続した後戻らずに続けていたのが最大の原因でした（なおしました）
迷路の探索
深さ優先探索
得意の再帰でどんどこ調査していくだけ！
再帰使わずスタック使えとかもあったけど、知らん知らん💧
一つのルートをひたすら突き進んで、行き止まったら戻って又次のルート、と次の道がゴールと一致するまでやり続ける。
変数 調査済み迷路＝空配列。
●(現地点から出口まで迷路の)迷路深さ優先探索とは
調査済み迷路＝迷路を配列複製。
変数 [今ｘ,今ｙ]＝現地点。
変数 [終ｘ,終ｙ]＝出口。
変数 仮迷路＝迷路を配列複製。
変数 [道,壁,調査済み]＝[0,1,9]。# 地形の定義。
変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]。
上下左右を反復
ｘ,ｙ＝対象。
次ｘ,次ｙ＝[今ｘ＋ｘ,今ｙ＋ｙ]。
もし、(次ｘ＝終ｘ)かつ(次ｙ＝終ｙ)ならば、
仮迷路[今ｙ][今ｘ]＝調査済。
仮迷路[次ｙ][次ｘ]＝調査済。
調査済み迷路＝仮迷路を配列複製。
抜ける。
ここまで。
もし、調査済み迷路[終ｙ][終ｘ]＝調査済みならば、抜ける。
もし、仮迷路[次ｙ][次ｘ]＝壁ならば、続ける。
もし、仮迷路[次ｙ][次ｘ]＞0ならば、続ける。
仮迷路[今ｙ][今ｘ]＝調査済。
[次ｘ,次ｙ]から出口まで仮迷路の迷路深さ優先探索。
ここまで。
調査済み迷路で戻る。
ここまで。
幅優先探索
こちらは、行けるところを全て見て、総なめにしていく探し方。
出口が近くにある時は、深さ優先探索よりかなり早く到達出来ることもあるみたい。
でも、左上から右下、みたいな場合だと、ほとんど全てのマスを探索しなきゃなことも結構あります💧
- 今行ける場所を全て、迷路調査リストに配列追加する。
- 迷路調査リストの先頭を調査して、調査したらそれは配列削除。
１と２を繰り返して、次の調査対象がゴールと一致するまで続ける。
●(入口から出口まで迷路の)迷路幅優先探索とは
調査済み迷路＝迷路を配列複製。
変数 [終ｘ,終ｙ]＝出口。
変数 [道,壁,調査中]＝[0,1,8]。# 地形の定義。
変数 上下左右＝[[0,-1],[0,1],[-1,0],[1,0]]。
変数 仮迷路＝迷路を配列複製。
変数 調査中迷路＝迷路を配列複製。
変数 迷路調査リスト＝空配列。
迷路調査リストに入口を配列追加。
((迷路調査リストの配列要素数)＞０)の間
今ｘ,今ｙ＝迷路調査リスト[0]。
仮迷路[今ｙ][今ｘ]＝調査中。
迷路調査リストの0を配列削除。
上下左右を反復
ｘ,ｙ＝対象。
次ｘ,次ｙ＝[今ｘ＋ｘ,今ｙ＋ｙ]。
もし、(次ｘ＝終ｘ)かつ(次ｙ＝終ｙ)ならば、
調査中迷路[次ｙ][次ｘ]＝[今ｘ,今ｙ]。
調査中迷路の入口から出口まで最短ルート反映。
それで戻る。
ここまで。
もし、仮迷路[次ｙ][次ｘ]＝道でなければ、続ける。
迷路調査リストに[次ｘ,次ｙ]を配列追加。
調査中迷路[次ｙ][次ｘ]＝[今ｘ,今ｙ]
ここまで。
ここまで。
ここまで。
●(調査中迷路の入口から出口まで)最短ルート反映
始ｘ,始ｙ＝入口。
今ｘ,今ｙ＝出口。
永遠の間
前ｘ,前ｙ＝調査中迷路[今ｙ,今ｘ]。
調査済み迷路[今ｙ,今ｘ]＝9。
もし、(今ｘ＝始ｘ)かつ(今ｙ＝始ｙ)ならば、抜ける。
今ｘ,今ｙ＝[前ｘ,前ｙ]。
ここまで。
調査済み迷路で戻る。
ここまで。
鑑賞する！
ちょうどこの頃、なでしこさんに「秒待つ」命令が追加されたんですよねー。
これは、画期的でした！
コールバック式のタイマーを使わなくても、ｖ１と同じ感じにウェイトを掛けて実行したり出来るようになりました。
こりゃイイ♪ と、うれしがって迷路の自動生成される様子や、探索の様子を鑑賞出来るようにしてみました。
深さ優先探索と幅優先探索の違いも、見た方が一目瞭然で分かりますよね☆
ちなみに、にょろにょろというのは、深さ優先探索している様子からです
おわります
というわけで、今年、一時期迷路にはまっていた時に頑張った成果を一挙公開なのでした。
間違いなどあれば、是非教えてください
にょろにょろの方は、観賞用のウェイトが入っていますが、こちらは元の命令だけなので、何かに流用したり、取り込んでプラグイン的に使ったりも出来るかも？