迷路作成アルゴリズム
ちょっと面白かったので調べてみた。
棒倒し法。
1.奇数の枠を準備します(21×21等)![迷路 棒倒し法1](http://image.blog.livedoor.jp/hir0yas/imgs/a/6/a6f6c6d1-s.jpg)
2.外周を壁にします。![迷路 棒倒し法2](http://image.blog.livedoor.jp/hir0yas/imgs/b/7/b7d0e485-s.jpg)
3.内側は2個飛びに柱を立てます。![迷路 棒倒し法3](http://image.blog.livedoor.jp/hir0yas/imgs/c/4/c4719aee-s.jpg)
4.柱1行目は上下左右のいずれかに柱を倒します。柱が重なったら、別の方向に柱を倒します。![迷路 棒倒し法4](http://image.blog.livedoor.jp/hir0yas/imgs/2/0/20e3e125-s.jpg)
5.柱2行目以降は下左右のいずれかに柱を倒します。柱が重なったら、別の方向に柱を倒します。![迷路 棒倒し法5](http://image.blog.livedoor.jp/hir0yas/imgs/5/0/501c95a1-s.jpg)
6.迷路完成![迷路 棒倒し法6](http://image.blog.livedoor.jp/hir0yas/imgs/7/1/71fffaf2-s.jpg)
いかにもシンプルなアルゴリズムなんだけど、やはり弱点があるらしく、1行目の棒の倒し方は上下左右に散らばることから、一行目、二行目に横方向の通路が出来やすいという事らしい。迷路だとすれば、起点と終点をランダムに選択することで弱点はかなり緩和できるのではないか?と思った。むしろ、本当の通路になってしまう点が面白くないなと思った。所々大広間みたいなのが出来てたほうが迷う気がする。
久々にちょっとC言語で書いてみたけど、アルゴリズムも単純だから、あっさり実装できた。表示の仕方をいじくって、縦方向、横方向共に「最初に柱を立てた行/列」の幅を薄くすると、それなりに迷路っぽくなる。![迷路 棒倒し法7](http://image.blog.livedoor.jp/hir0yas/imgs/e/2/e2fba95f-s.jpg)
ちょっと調べただけだけど、迷路作成ってのもなかなか面白そうだな。
コメント