https://twitter.com/AiAkaishi/status/539758443456765952

この迷路の生成アルゴリズムがいくら考えても分からないです。
分かる方はぜひ教えてください。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2015/04/29 20:07:23
  • 終了:2015/05/04 01:15:29

ベストアンサー

id:language_and_engineering No.1

lang_and_engine回答回数170ベストアンサー獲得回数632015/04/29 22:48:27

これはぱっと見,クラスタリングによる迷路生成のアルゴリズムですね。

ランダムに壁を壊して行き,
つながった部分を「同じ色」で満たす。
(Windowsのペイント等で閉じた領域を塗りつぶすイメージ)

閉じた領域がn個ある場合,n個の異なる色で塗り分ける。

次に壁を壊す際には,「色」の違う隣り合ったマス目にはさまれた壁だけを壊す。
そして開通した穴の両側にある閉じた領域を,新たに共通の一色で塗りつぶす。
そうすれば,同じ色で満たされているマス目の間にある壁を壊してループが発生するのを避けられる。

この調子で,最終的に領域の全体が一色の色で満たされるまで続ければ
ループのない迷路が完成する。


クラスタリングによる迷路作成アルゴリズム
http://apollon.issp.u-tokyo.ac.jp/~watanabe/tips/maze.html
「ランダムに壁を壊す。このとき、隣あう部屋がつながったとしてクラスタリングする」

その他の回答(0件)

id:language_and_engineering No.1

lang_and_engine回答回数170ベストアンサー獲得回数632015/04/29 22:48:27ここでベストアンサー

これはぱっと見,クラスタリングによる迷路生成のアルゴリズムですね。

ランダムに壁を壊して行き,
つながった部分を「同じ色」で満たす。
(Windowsのペイント等で閉じた領域を塗りつぶすイメージ)

閉じた領域がn個ある場合,n個の異なる色で塗り分ける。

次に壁を壊す際には,「色」の違う隣り合ったマス目にはさまれた壁だけを壊す。
そして開通した穴の両側にある閉じた領域を,新たに共通の一色で塗りつぶす。
そうすれば,同じ色で満たされているマス目の間にある壁を壊してループが発生するのを避けられる。

この調子で,最終的に領域の全体が一色の色で満たされるまで続ければ
ループのない迷路が完成する。


クラスタリングによる迷路作成アルゴリズム
http://apollon.issp.u-tokyo.ac.jp/~watanabe/tips/maze.html
「ランダムに壁を壊す。このとき、隣あう部屋がつながったとしてクラスタリングする」

id:okaj

質問者から

okaj2015/05/04 01:14:50

質問文を編集しました。詳細はこちら

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません