2D迷路データとその解を自動生成する(4):「ポテンシャル法」で迷路を解いてみる

ここまでのエントリで、「どんな迷路を、どのようにつくるか」のうち、 (1)大きな構造の生成、(2)実際のMapに与えるdata生成　までを説明しました。 ここでは、(3)細部の構造の生成 について述べる前に、「どのように迷路の解をつくるか」について、具体的な例を示しながら解説をします。

次の図のような16x16の迷路があったとします。0が壁、1がスタート地点です。

この迷路について「ポテンシャル法(等高線法)」と呼ばれるアルゴリズムでの処理をした結果が次の図です。

• 「0」は、「壁」を表しています。
• 「0」以外の文字は、「道」を表しています。
• 「1」が出発点で、出発点から最短で到達可能な歩数によって、ASCIIコード順にそれぞれの文字や記号が示されています。

1の出発点から1歩離れるごとに、数値〜文字のASCIIコードが大きいものになっていく様子が読み取れるでしょうか？

さらに、スタート地点からの距離ごとに、迷路内地点をリスト化してまとめたものを示しておきます。

0:  1 (3,8)
1:  2 (2,8) (4,8)
2:  3 (2,7) (5,8)
3:  4 (2,6) (6,8)
4:  5 (2,5) (6,9) (7,8)
5:  6 (2,4) (6,10) (7,7) (8,8)
6:  7 (2,3) (6,11) (5,10) (7,10) (7,6) (8,7) (8,9)
7:  8 (2,2) (6,12) (5,11) (4,10) (8,10) (7,5) (6,6) (8,6) (9,9)
8:  9 (3,2) (5,12) (7,12) (4,11) (3,10) (9,10) (7,4) (6,5) (5,6) (9,6) (10,9)
9:  : (4,2) (5,13) (4,12) (8,12) (2,10) (9,11) (10,10) (6,4) (8,4) (4,6) (10,6)
10: ; (4,3) (5,14) (3,12) (8,13) (9,12) (10,11) (9,4) (4,5) (11,6)
11: < (4,4) (4,14) (6,14) (2,12) (8,14) (9,13) (11,11) (10,4) (12,6)
12: = (3,14) (7,14) (2,13) (10,13) (12,11) (11,4) (12,5)
13: > (2,14) (11,13) (12,12) (12,4)
14: ? (12,13) (12,3)
15: @ (12,2)
16: A (11,2)
17: B (10,2)
18: C (9,2)
19: D (8,2)
20: E (7,2)
21: F (6,2)

この例では、出発点からいちばん遠いのは、Fの文字が置かれている(6,2)の点で、ここが21歩で到達するゴール地点だということになります。

こうしたデータ構造を作ってしまえば、「迷路を解く」のは、もう簡単です。 このゴールの地点から始めて、ASCIIコードを逆順に文字を辿れるような方向へと歩いていけば、最短距離での経路が求められるということになるわけです。

次のエントリで、こうしたアルゴリズムの実装例を示していきます。