「迷路を幅優先探索で解く」「迷路を深さ優先探索で解く」に続く第３弾です。
波状探索とは
幅優先でも深さ優先でもないアルゴリズムで迷路を解いています。
ここで示したアルゴリズムはあるサイトで見つけたものなのだと記憶しているのですが、この迷路プログラムの原型は、もう十年も前に書いたものなので、それがどこのサイトなのかがわからなくなってしまいいました(T T)。
そのためこのアルゴリズムの名前もわかりません。 ここでは、勝手に波紋探索という名前を付けました。
どうやって経路を求めていくかというと、次のような手順となります。
- スタート地点に番号 0 を振ります。0 は歩数を表します。現在の歩数に 0を代入します。
- 次に進めるすべての位置に 現在の歩数 + 1を振ります。 この時すでに番号が振られている位置には、番号を振り直すことはしません。
- 現在の歩数 に +1 します。
- 現在の歩数が振られたすべての位置について、2,3 の処理を行います。
- ゴールにたどり着いたら終了です。
最終的な経路は、ゴールから逆に（番号を一つ減らしながら）たどっていくことで得られます。 逆順に辿る際に、同じ番号が現れた場合はどちらを辿っても構いません。
例
以下の小さな迷路を例に説明します。
****************
S * *
* ***** ****** *
* * *
* *** ****** ***
* * * *
*** ******** ***
* * *
********G*******
以下がその実行過程です。
数字が歩数を示しています。0がスタート地点です。
7歩までと11歩まで進んだところを示しいています。
数字を表示するために、横幅を3倍にしています。
************************************************
0 1 *** ***
*** 2 *************** ****************** ***
*** 3 4 5 6 7 *** ***
*** 4 ********* ****************** *********
*** 5 6 7 *** *** ***
********* ************************ *********
*** *** ***
************************************************
************************************************
0 1 *** 11 ***
*** 2 ***************10 ****************** ***
*** 3 4 5 6 7 8 9 10 11 *** ***
*** 4 ********* 8 ****************** *********
*** 5 6 7 *** 9 10 11 *** ***
********* 8 ************************ *********
***11 10 9 10 11 *** ***
************************************************
これで、このアルゴリズムのイメージがつかめると思います。
この途中結果から分かるように、迷路を全て把握し、自由にアクセスできる神の視点でのアルゴリズムですね。
なお、後述するコードで、DebugPrintというメソッドを用意しているので、これを有効にすれば、上記のような表示が得られます。
C#のコード
以下C#のコードです。
program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.IO;
namespace MazeSolverWavelikeSearch {
class Program {
static void Main(string[] args) {
var sw = Stopwatch.StartNew();
var solver = new MazeSolver();
Maze ans = solver.Solve(new Maze("maze.txt"));
sw.Stop();
Console.WriteLine("{0}ミリ秒", sw.ElapsedMilliseconds);
ans.Print();
Console.ReadLine();
}
}
}
MazeSolver.cs
using System;
namespace MazeSolverWavelikeSearch {
// 波状探索
public class MazeSolver {
public Maze Solve(Maze maze) {
Maze workmaze = maze.Clone();
int step = 0; // step は、何歩目かを示す。今は 0 歩目
while (!workmaze.IsFin()) {
foreach (var pos in workmaze.SearchLocations(step)) {
foreach (var next in workmaze.NextPositions(pos)) {
workmaze.FootMark(next, step + 1);
}
}
step++; // 歩数を一歩進める
// 次の２行はデバッグ用
workmaze.DebugPrint();
Console.ReadLine();
}
return workmaze;
}
}
}
Position.cs
using System;
namespace MazeSolverWavelikeSearch {
// 位置情報構造体
public struct Position {
public int X { get; set; }
public int Y { get; set; }
}
}
Maze.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
namespace MazeSolverWavelikeSearch {
public class Maze {
private const int Goal = -2;
private const int Wall = -3;
private const int Road = -1;
private const int Mark = -4;
private int[,] _map;
private int _xSize;
private int _ySize;
// コンストラクタ
private Maze() {
}
// コンストラクタ
public Maze(string mapfile) {
ReadMap(mapfile);
}
// Mapデータを読み込む
public void ReadMap(string mapfile) {
string[] data = File.ReadAllLines(mapfile);
this._map = new int[data.Length, data[0].Length];
for (int x = 0; x < data.Length; x++) {
for (int y = 0; y < data[0].Length; y++) {
if (data[x][y] == 'S')
this._map[x, y] = 0;
else if (data[x][y] == 'G')
this._map[x, y] = Goal;
else if (data[x][y] == '*')
this._map[x, y] = Wall;
else
this._map[x, y] = Road;
}
}
_xSize = data.Length;
_ySize = data[0].Length;
}
// 複製を作成する
public Maze Clone() {
Maze maze = new Maze();
maze._map = (int[,])_map.Clone();
maze._xSize = this._xSize;
maze._ySize = this._ySize;
return maze;
}
// 足跡を付ける
public void FootMark(Position pos, int step) {
_map[pos.X, pos.Y] = step;
}
// すべての位置を列挙する
public IEnumerable<Position> AllPositions() {
for (int x = 0; x < _xSize; x++) {
for (int y = 0; y < _ySize; y++) {
yield return new Position { X = x, Y = y };
}
}
}
// target で指定したマークがある場所を求める。
public Position FindPosition(int target) {
return SearchLocations(target).First();
}
// stepで示した位置を列挙する。
public IEnumerable<Position> SearchLocations(int step) {
return AllPositions().Where(p => _map[p.X, p.Y] == step);
}
// posの四方にある道の位置を列挙する
public IEnumerable<Position> AroundPositions(Position pos) {
if (pos.Y + 1 < _ySize)
yield return new Position { X = pos.X, Y = pos.Y + 1 };
if (pos.X + 1 < _xSize)
yield return new Position { X = pos.X + 1, Y = pos.Y };
if (pos.Y > 0)
yield return new Position { X = pos.X, Y = pos.Y - 1 };
if (pos.X > 0)
yield return new Position { X = pos.X - 1, Y = pos.Y };
}
// ゴール直前までたどり着いたか。
public bool IsFin() {
var pos = FindPosition(Goal);
return AroundPositions(pos).Any(p => _map[p.X, p.Y] > 0);
}
// posの四方にある道の位置を列挙する
public IEnumerable<Position> AroundRoads(Position pos) {
return AroundPositions(pos).Where(p => _map[p.X, p.Y] >= -1);
}
// 次に移動できる位置を列挙する
public IEnumerable<Position> NextPositions(Position pos) {
return AroundPositions(pos).Where(p => _map[p.X, p.Y] == Road);
}
// 迷路をConsoleに表示する
public void Print() {
// Goalから逆にたどり、Markを置いてゆく
var pos = FindPosition(Goal);
pos = AroundRoads(pos).Where(p => _map[p.X, p.Y] > 0).OrderBy(p => _map[p.X, p.Y]).First();
int step = _map[pos.X, pos.Y];
_map[pos.X, pos.Y] = Mark;
while (step > 1) { // stepが1になるまで繰り返す。
foreach (var p in AroundRoads(pos)) {
if (_map[p.X, p.Y] == step - 1) {
pos = p;
step = _map[pos.X, pos.Y];
_map[pos.X, pos.Y] = Mark;
break;
}
}
}
// mapをプリント
for (int x = 0; x < _xSize; x++) {
for (int y = 0; y < _ySize; y++) {
char c = ' ';
int v = _map[x, y];
c = (v == Wall) ? '*' : (v == 0) ? 'S' : (v == Goal) ? 'G' : (v == Mark) ? '･' : ' ';
Console.Write("{0}", c);
}
Console.WriteLine();
}
Console.WriteLine();
}
// 迷路をConsoleに表示する [Debug用]
[Conditional("DEBUG")]
public void DebugPrint() {
for (int x = 0; x < _xSize; x++) {
for (int y = 0; y < _ySize; y++) {
string s = (_map[x, y] <= -2)
? "***"
: (_map[x, y] == -1)
? " "
: string.Format("{0,2} ", _map[x, y]);
Console.Write(s);
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
テストデータ
「迷路を幅優先探索で解く」「迷路を深さ優先探索で解く」同様、以下のようなテキストファイルをこのプログラムに読み込ませれば、解を表示してくれます。
テストデータ１
******************************
S * * * *
* * * *** ***** ************ *
* * * * * * ** * * * *
* * * * * * ** * *** * * * *
* * * * * *
***************** ***** ******
* * * G
*** ********* ************** *
* * * * * *
* **** * * ***** *** **** ****
* * * * * * * * *
*** * * * ***** *** ******* *
* * * * * *
* ***************** **** * * *
* * * * * * * *
* ***** **** * **** **** * * *
* * * * *
******************************
テストデータ２
*S*****************************
* * * *
*** ******* ***** * *** *** * *
* * * * * * * *
***** *** * *** * *** *** *****
* * * * * * *
*** * *** * * *** * * ******* *
* * * * * * * * *
*** ***** *** * * * *** * *****
* * * * * * * *
* *********** ********* ***** *
* * * * * * * * *
* *** * * *** * *** ***** *** *
* * * * * * *
* ********* ********* * ***** *
* * * * * * *
* * ******* *** ******* *** ***
* * * * * * * * * * *
*** * * *** * *** * * *** * * *
* * * * * *
*****************************G*
記号の意味は以下の通りです。
| 記号 | 意味 |
|---|---|
| * | 壁 |
| S | スタート地点 |
| G | ゴール地点 |
| 空白 | 通路 |
実行例
実行した結果を載せます。・ は経路を示しています。
.NET Coreで作成し、Macで動かしていますが、コードはそのままでWindowsでも動作します。
テストデータ1の実行例
テストデータ2の実行例
実際に確かめてはいませんが、この探索方法は解を得るまでの時間が非常に安定していると思います。