hirax.net::Tech-logs::2011-09-22

2011-09-22[n年前へ]

迷路自動生成アルゴリズム 

 「巨大なAKB48 篠田麻里子 迷路」を作ってみたで使用した迷路自動生成アルゴリズムは、以下の手順です。このアルゴリズムは、「迷路の壁生成はするけれども、”経路をふさぐ=壁と壁の間を新しい壁でつなぐ”とことはしない」というものです。そのため、このアルゴリズムにもとづく限りは、入り口から出口まで辿り着く(ひとつ以上の)経路の存在が必ず保証されます(といっても、動作確認のためのテストはしてないんですけど…)*。

 …というわけで!?、「行き止まりしかないという不安」を気にせずに、「巨大なまりこ様 迷路」選手権、もしくは、「たかみな巨大迷路 脱出レース」に挑戦して参加して頂ければ、と思います。

  1. 周囲の壁を作る。
  2. まだ壁が作られていない壁格子点をランダムに選び、そこから壁生成を(所定のランダム量にもとづいた回数・長さだけ)スタートさせる
  3. 壁生成の先が壁の存在する格子点であれば、その壁生成はせず、次の壁生成を行う
  4. すべての壁格子点について処理済みであれば、迷路生成を終了する


 * …しかし、実際にテストをしてみたところ、存在しないはずの「閉じた部分」がチラホラあるじゃあーりませんか!つまり、壁と壁の間を閉ざしてしまうことがある=入り口から出口にいたる”経路がふさがれてしまうことがある”ということで、運次第でゴールに絶対たどり着けないということになってしまいます。…うーん、テストって重要だなあ。