迷路作成編


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

迷路作成編
このページでは、迷路の作り方についての出題がされています。(現在作成中です)

この記事は、以下のサイトの内容を一部参考にしています。




手順A(道を延ばす方式)

以下のような配列を作成し、初期化する。

R R R R R R R R R R R R R R R R R R R R R R R R R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W S W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R W K W K W K W K W K W K W K W K W K W K W K W R
R W W W W W W W W W W W W W W W W W W W W W W W R
R R R R R R R R R R R R R R R R R R R R R R R R R


以下の処理を、Sのマスがなくなるまで繰り返す。
1. Sのマスをランダムにひとつ取り出す。
2. このマスをRに変更する。
3. 取り出したSのマスの上下左右の各方向について以下の処理を行う。
3-1. その方向の隣の隣のマスがK以外であれば何もせず次の方向の処理を行う。
3-2. その方向の隣の隣のマスがKであれば、そのマスをSにし、その方向の隣のマス(必ずWであるはず)をRにする。

4. 1.に戻る。(次のSのマスをランダムに選択する)

5.(補足)上下左右の方向が全て3-2に合致しない場合、すなわち、全て3-1に該当する場合、袋小路に突き当たっています。(Sのマスがひとつ減ります)

(手順B 終わり)

上記初期化配列を任意に拡張し、この手順を適用せよ。

上記処理終了後の配列を、Wを黒い四角で、Rを白い四角で配置どおりに表示せよ。外周のRに関する表示は省略しても良い。外周を囲むWの壁の、内側のRに接する二ヵ所を白で表示するようにして、入り口と出口を設定せよ。

この手順で作成される迷路は「つまらない」ものになりがちである。なぜかを考察せよ。手順Aは(1)任意の二点間を結ぶ経路が一通りしかない。(2)任意の二点間を結ぶ経路が必ず存在する。の二つの条件を満たされるようになっている。

上記二つの条件を満たすように手順Bの改良を検討せよ。その手順は条件(1)(2)を満たすように考慮せよ。また確実に終了するように考慮せよ。


(2013/05/05)