生成した迷路のスタートとゴールを決める【後編】その１
【前編】では、スタートとゴールを決めるときの問題点を説明しました。
【後編】その１では、実際にどのようにスタートとゴールを決めるのかを解説したいと思います。プログラムについては【後編】その２で解説します。
考え方
この解説では、31x31で生成した迷路を使用します。
白: 道(path), 黒: 壁(wall)
まず、この迷路を”道”ベースで考えます。道を青で示します。
この道の中で、３つ以上の道に分かれているマスを選択します。選択したマスをノードとし、赤で示します。
それぞれのノードを見た時、ノードにつながる道の状態によって処理します。
- １つの別のノードにつながっている時（ノード１）
ノードにつながらない（行き止まりの）道の中で、最も長い道以外を削除する。最も長い道が複数ある場合その中の１つだけ残し、その他のノードにつながらない（行き止まりの）道を削除する。 - ２つ以上の別のノードにつながっている時（ノード２）
ノードにつながらない（行き止まりの）道をすべて削除する。
例を示します。
処理前 >> 処理後
この処理を迷路に適用すると以下のようになります。
この処理を迷路内のノードの数が１つ以下になるまで繰り返します。
現在の迷路の状態 >> ノードを選択 >> 処理
現在の迷路の状態 >> ノードを選択
ここで、迷路内のノード数が１つ以下になったので、以下の処理を行います。ノードが存在しない場合はこの処理はスキップできます。
- ノードにつながる道の中から、長い道上位２つを残し、そのほかの道を削除する。
これで、迷路の経路を求めることが出来ました。この経路の端をそれぞれスタートとゴールにすれば終了です。
最初の状態と比較してみる
いい感じに経路が決定できていますね！
これで、考え方の解説を終わります。
考え方の解説が想定よりも長くなってしまったので、これをプログラムにしたものを【後編】その２で解説したいと思います。
【後編】その２ >> 時間があったら。
