曲がった迷路その29 - とりあえずver0.1

とりあえず動作するものができた。

ver.0.1の動作

いっきに書き進めて動くところまでこぎつけた。まだちょっとリークが残ってたりするけど。

結局ドキュメントスタイルにするところが一番時間がかかった。書き慣れてないせいでどんどんぐちゃぐちゃになってしまった。Cocoa Bindingを使ったり、メソッドを直に呼んだりが入り乱れてる。本来ならwindowControllerに実装すべきものをNSDocumentに書いたりしてしまった。めちゃくちゃ。ちゃんとかかなければいけなくなったら全部書き換えよう。

ところで最初は名前を「Spaghetti Maze Creator」にしたけど、Creatorという語はどうも大袈裟な感じがしたのでアプリの名前としては「Spaghetti Maze Maker」にした。Objective-Cのクラスの名前の接頭辞は面倒なのでSMCのまま。

迷路作成例

パラメータの与え方によっては解を塞いでしまったり、全然壁が伸ばせないでデッドロックしたりするけど、もっともらしげな値を使うとだいたい思った通りのものができる。なかなかええんでないかい。スペックルをもとにしたのが功を奏して壁の密度が一様で、かつ壁一つ一つは十分にランダムな感じになった。図-31みたいな感じ。

迷路生成のアルゴリズムとして壁を伸ばしていく方法をとったので、解が単純でぱっとみてわかるようなものができる場合が多い。ぱっと見てわからないような迷路にするためには二つの壁グループがなるべく入れ子になるように伸ばしていかないといけないけど、安定にできるようにするにはそれなりに工夫が必要になる。下手にやると効率が悪くなったり最悪デッドロックに陥ってビーチボールが回り出す、なんてことになる。

例えば、単位壁は自分の周りのポテンシャルの一番低いところに作るようにしたけど、えり好みさせるようにしないといけない。ポテンシャルの高いところは壁グループで同じに見えて、低いところは相手グループの壁に近いところがさらに低く見えるようにする、などとすればいいかもしれない。こういうアルゴリズムの改良は実験をやらないと最終的にいいものにたどり着かないのが普通だろう。

こういうのが他にもないかぐぐってみたけど、なかなか見当たらなかった。ひとつ、Wikipedia英語の「Maze generation algorithm」の「Non-cell-based algorithm」に紹介があった。こういうの。生成法の詳細もあってみてみると壁どうしの交点を探して交差したら作るのをやめる、というアルゴリズムらしい。新しい壁の作り方は書いてないけど一様乱数を使えばランダムウォークになる。サンプルを見るとランダムウォークほどランダムでないように見えるのでどうやってるのかわからない。でも、これよりはスマートな気がする。自画自賛。

また、似たアプローチで経路の方を曲げている人がいた。ランダムウォークっぽさを減らす工夫があってさっきのよりはこちらの方が美しい。

ああ、ちょっと寝よ。