DouKaku?beta

Comment detail

必ず解ける迷路 (Nested Flatten)

This comment is reply for 5307 squld: 壁伸ばし法の変種ですね。 >...(必ず解ける迷路). Go to thread root. 

棒倒し方では, 格子状に壁を生成し, それを起点に周
囲に1つ以上の壁を生成していきます. 
そのため, 必ず格子状に壁が存在し, かつその周辺に
1つ以上壁が存在することになり, 一部の構造の迷路
が生成できないということなんだと思います.  
棒倒し法の問題点は以下のようです。

1. 一行目に壁が少なくなってしまう。
2. 閉じた領域が出来てしまう。
3. 全ての道と連絡する抜け道ができてしまう。
4. 隙間だらけになってしまう。
5. 生成方向に逆行する経路ができない。

1～4の問題を克服した発散棒倒し法が紹介されていますが、
放射状に迷路を作るのでO(n)で実装するのは無理かもしれません。

参考
迷路自動生成アルゴリズム「発散棒倒し法」
http://aoyzsas.hp.infoseek.co.jp/maze/maze_hpillar.html

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]