前回：
blog/7025
のつづき．

・作った迷路の正解経路を改変して難しくする
とかの方が考えるのが簡単かも．

今回作った迷路にはループが無いから，例えば，
「正解ルートのどこかを壁で塞いで代わりに他の箇所を開けて別ルートを開通させ，正解経路長が長くなったら採用」
みたいな処理を後段に加えればいいのかも．

これをやっていくことにする．

---

（１）塞ぐ箇所はどこなのか

さて，↑の迷路の更新処理を行うには，
まず【迷路の正解ルート】を知ることができる必要がある．どうやるのか？

馬鹿正直にルート探索アルゴリズムを実装しはじめる前に少し落ち着いて考えれば，
今回作った迷路は【ループが無くて，迷路の壁は２つのグループに分かれている】のだから，
正解ルートは，２つのグループの間を通るはずだということがわかる．

見やすくするために，一方のグループの壁だけを赤に塗り替えてみれば，以下のようになる． 青点の箇所が正解ルートである．この青点群は，
「グリッド頂点群がどちらのグループに所属しているか？」に関するデータがあれば
隣接頂点間の所属先グループが異なる場所を列挙するだけで簡単に得られるわけだ．良かった．

「経路」にするためには点群の順序を並び替える必要があるが，今回は列挙だけできればよいので，その処理は不要．
この中のどれかをランダムに選んで塞ぎ，かわりに別のどこかを開通させればよいわけだ．ふむ．

(2)かわりに開ける場所はどこなのか

さて，そうなると，「どの壁をぶっ壊せば開通するん？」という問題が生じる．
ぶっ壊すべき壁を列挙できる必要がある．

例えば，下図の緑で囲った箇所を塞ぐとき，
壊すべき壁は，紫でなぞったものになるだろう． つまり，塞いだ壁の両端の頂点から壁伝いに外周まで行く経路だ．
うーん，これはちょっとした探索処理が必要そうだなぁ．

新しい経路が長くなったかだけでなく、どれだけ分岐にあたる数が増えたかも条件に加えたいところですね。
でも、単に分岐数が多いだけで難しい迷路になるかな？適度に長い道が結局行き止まりだったの方が難しい迷路のような気もしますが。

このまま極めたら道を全部一筆書きして網羅する勢いの迷路がいつか出来てしまいそう(´・ω・｀)
と思ったけど、距離が長いだけの一本道になってしまうので迷路では無くなりますね(笑)

やってみた．

最初に生成された迷路．一直線丸出しな正解ルートだ．
とにかく目的地方向に進もうとすれば苦も無く終わる感じ． ↓
経路修正．
経路長が閾値を超えるかあるいは回数制限であきらめるまでループする形で修正処理を組んだので
実際何回修正入ったのか良くわからんが，経路は長くなった模様． ↓
さらに修正させると，まさに
> 距離が長いだけの一本道
という様相に．やりすぎイクナイ．
（もっとでかい迷路ならそうそう一本道にはならないだろうとは思う）

> 分岐数

今回の処理では分岐数がどうなるのかは良くわかりませんが，多分，個数はそう変わらないのかな．

多分，分岐先が「人間がぱっと見で枝狩りできない程度の部分迷路」になっている箇所が多いほど良いのだろうけど，
それを増やす方向に修正する戦略がすぐには思いつかないですね．
（評価処理も大変そう）

おまけ：

でかいの作ってみた．どうすか．

一本道のみっちり感すごいですね(笑)

最後の迷路は規模の大きさだけで怯んでしまいます(;^ω^)わーお

線を描いて潰していかないと難しいですね。
目がショボショボです(*-*)
真ん中に行くこと自体がハズレでかなり悩みました(;^ω^)
その分、達成感が半端ないです( ´∀｀ )

画像は隠しときます。

解かれてるｗ　激しく乙です．

もるも さんが書きました:

6年前

目がショボショボです(*-*)

なんというか，コレ，迷路の最大の敵かもですね．
目に来ない提示方式があれば良いのですが…


しかし「迷路生成処理」ってのは，あれですね．
いざ成果物たる迷路が出力されてみると「迷路作ったけど……で，何？」っていう虚無の世界ですな…
なんだろう，例えるなら，大学に入ることが人生の目的になっちゃってる受験生みたいな…

私の場合、このレベルの迷路はもはや解くものではなく観賞するものですね(;´･ω･)
作るプログラムのほうでも、だいぶ前から解くための迷路作成から見るための迷路作成にシフトしてますけど。