LSSさんがはてなブログで迷路の自動生成を完成させました!
簡単に、一瞬で色々なサイズの迷路が生成できます!
すごい・・・
ぜひ触ってみてください^^
好きなだけ迷路を作れるのでいっぱい遊んでみました。
また、その中で最大サイズ(99×99)の迷路を5回ほど解答を入力しながら解いてみました。
その結果がこちらです。
ランダム生成を使ったアルゴリズム(はてなブログで表示できるようJavaScriptで実装)とのことですが、どれもしっかりと迷路ですね!
難しいプログラミングの話は置いておいて、私が得意としている『迷路』について傾向を見ていきましょう。
(サンプルが少なさ過ぎて正しい傾向ではないかもしれません)
----------
基本的にはスタートからゴールまで、ジグザグしながら進んでいきます。
ゴールから大きく離れる移動はなく、極端に右上や極端に左下は通らないようになっています。
中心エリアを通ることが多く、最初は中心に向かって進むようにすると解きやすい傾向が見て取れます。
また人が作るとありがちな、迷路の左右や上下に目いっぱい何往復させたり、特定の図形をモチーフとしたルートを作ったりといった要素はありません。
あくまでもランダム生成したという感じですね。
----------
ちょっと否定的に感じられるような意見が多くなってしまいましたが、迷路がこのクオリティで自動生成できること(しかもほぼ一瞬で生成できること)はすごいと思います。
私が過去に作った迷路の自動生成アルゴリズムよりも、できあがる迷路の偏りがすくないのでランダムで迷路を生成するアルゴリズムとしては◎だと思います。
一方、確率に偏りが生まれにくいランダムを使った迷路だからこそ、中心エリアに正解ルートが寄りやすいという傾向が生まれている気がします。
厳密ではないですが、ランダム生成という要素から、通るルートは確率はパスカルの三角形で近似できる気がします。
大きく戻ったり、行ったり来たりさせるのは複雑なアルゴリズムを考えれば実現できるのでしょうか?
もしかしたら、アルゴリズムの世界で実現すべきものではなくAIの世界なのかもしれません。
LSSさん、迷路を語ってしまったので辛口になってしまいましたが、楽しい迷路をありがとうございました!
今回遊んだ記事を再度貼っておきます。
遊び方としては、幅を最小の11・高さを最大の99とすると、先が見えないワクワクな迷路ができあがるので楽しかったです^^
迷路の壁が薄くなった続編もあります。
いずれ続編の方も遊ばせていただきます。