曲がった迷路その2 - 迷路の一般論

また突然きまぐれに始めた、曲がった壁の迷路生成。
とりあえず、迷路の一般論を整理することから始めることにする。

迷路の特徴

ゲームとしての迷路にはいくつかの特徴がある

1. 入り口と出口がある
2. 入り口と出口はそれぞれひとつであることが多い
3. 入り口から出口まで到達する経路がある。これを「解」と呼ぶ
4. 解はただ一通りであることが多い
5. 解に接続した「袋小路」（最終的に行き止まり）がある
6. 解に接続していない袋小路（どこにも繋がっていない）は存在しないことが多い

などである。ゲームでない迷路にはこのような特徴はない。鍾乳洞を迷路と見た場合には出口がないこともある。そんな迷路は一生その中で暮らす場合を除いて入り口に戻って外に出るしかない。そのような迷路をゲームとしてみたとき迷路そのものではなく、内部にある他の何か（宝ラスボス美女etc.）が目的でなければ意味がない。そのような迷路をダンジョンと呼ぶことがある。

迷路の例を図-1に示す。

入り口と出口が矢印で示されている。中の赤い線が解である。

迷路の要素

黒い線は通過できないことを表している。これを「壁」と呼ぶことにする。最も外側の周囲の壁を「外壁」、それ以外の壁を「内壁」と呼んで区別することにする。

壁のない、通過可能な部分を「経路」と呼ぶことにする。入り口から出口まで経路をつないでたどり着くことができればそれが解である。

この例の場合、外壁の一部がなくなってそれが入り口あるいは出口になっている。

迷路の発展型

入り口から出口までの解を探すゲームとしての迷路は、さっきのが一番簡単なものだけど、他の要素を組み合わせることもできる。たとえば

• 立体迷路
• 内部に入り口出口を持つ迷路
• 経路の交差やワープのある迷路
• 壁でなく経路が（矢印など、何らかの方法で）示されている迷路

などいろいろ考えられる。

今回は一番純なものを考えることにする。つまり

• 平面上の迷路
• 外部からの入り口と外部への出口をそれぞれひとつずつ持つ
• 経路を決める障害物は壁だけ

というものに限ることにする。

迷路のその他の特徴

袋小路

図-2の中のグレーに塗った経路の部分が袋小路である。これは解に接続しているが、ここを通ってもどこにも行けず、解の一部とはならない。

解の探索のひとつに、この袋小路をこうやって塗りつぶす方法がある。残った経路が解である。

トリビアルな袋小路

どこにも繋がっていない袋小路のことを「トリビアルな袋小路」と呼ぶことにする。図-3にトリビアルな袋小路を示す。図中A部はどこにも繋がっていないので、入ることも出ることもできない。

トリビアルな袋小路はあってもかまわないが迷路を単純化する以外に何の役目も果たさない。

解を複数持つ迷路

図-4は解が複数ある場合の例である。

これを見てわかるように、出入り口が外壁にある場合、

1. 連結している壁をたどることで壁全体をグループに分けることができる
2. 壁のグループがちょうど2個のとき、解がただひとつとなる
3. 壁のグループが3個以上ある場合、解は二つ以上ある

ということが言える。

壁のグループ分け

以上のことから迷路の中に入って解を探索することを考えると、図-5に描いたようにもし壁のグループごとに色付けされていれば一目瞭然である。

出口に到達するには左右の壁の色が違う経路をたどればよい。分かれ道で3色めが現れた場合、解が二つ以上ある迷路であり、どちらに進んでも出口に到達できる。もちろんそんな親切な迷路は作られることはないが、迷路生成や解の探索には役に立つ考え方である。