C#でパズルを解く - 迷路を幅優先探索で解く

迷路を解くプログラムです。幅優先探索を用いて解いてみました。

幅優先探索

幅優先探索の特徴は、深さ優先探索とは異なり、最初に見つかった経路が最短経路となるという点です。

幅優先探索がどんな方法かを簡単に記すと、

• 一歩進むたびにその時にその時の迷路の状態と、次に進める一歩先の道をキューに入れていきます。

• 進める道がなくなってしまったら、その経路はあきらめ、キューからデータを一つ取り出し、そこから探索を再開します。

これを繰り返せば、いつかはゴールにたどり着くことになります（ゴールにたどり着く道があればですが)。

幅優先探索についての詳細は、 Wikipediaの「幅優先探索」を参照してください。

コンソールアプリケーションとして作成しています。

実行結果

ソースコードを示す前に、どんな実行結果なのかを示します。

コンソールに表示される記号の意味は以下の通りです。

記号	意味
*	壁
S	スタート地点
G	ゴール地点
空白	通路
・	経路

以下、その実行結果です。

実行途中のスクリーンショット

実際には、探索が終わってから、このような、解の経路を描画しています。スタート位置からカーソルが動いて、足跡(経路)を残しながら、ゴールに進んでいきます。

ゴールにたどり着いた時のスクリーンショット

見てお分かりのように、Macで動作させています。.NET Core2.1で作成しているのですが、ソースコードはそのまま.NET Frameworkでもビルドできるはずです。

迷路データ

このプログラムでは、テキストファイルで作成した迷路データを読み込むようにしています。

なので、データを作成すれば様々なパターンでの確認ができるようになっています。

自動で迷路を生成するプログラムも併せて作成すればよいのでしょうが、今回はそこまではやっていません。

上記実行例の迷路データを以下に示します。

******************************
S *     *     *              *
* * * *** ***** ************ *
* * * * *  * ** *        * * *
* * * * *  * ** * *** *  * * *
*   *           * *   *      *
***************** ***** ******
*                     *    * *
*** ********* ************** *
*    * * *       *           *
* **** * * ***** *** **** ****
*      * * *   * *   *     * G
***  * * * ***** *** ******* *
*    *   *       *         * *
* ***************** **** * * *
*     *      *      *  * * * *
* ***** **** * **** **** * * *
*       *      *         *   *
******************************

作成したクラス

作成したクラス等は以下の通りです。

Mazeクラス

迷路を表すクラスで、ある地点の四方の位置を列挙したり、ゴールまでたどり着いたかなどのメソッドを持ちます。

Positionクラス

迷路の位置をX,Y座標で示します。

Place列挙型

Wall, Path, Goal, Startの４つを定義

Direction列挙型

None, East, West, South, Northの５つを定義

MazeSolverクラス

迷路を探索するクラス

Tracksクラス

経路を示すクラス

Viewerクラス

迷路と経路を可視化するクラス

C#のプログラム

Program.cs

using System;
using System.Diagnostics;

namespace MazeBreadthFirstSearch {
    class Program {
        static void Main(string[] args) {
            var sw = Stopwatch.StartNew();

            var maze = new Maze("map.txt");
            var v = new Viewer(maze);
            var solver = new MazeSolver();
            // solver.Subscribe(v);
            var ans = solver.Solve(maze);

            sw.Stop();
            v.Replay(ans);
            Console.WriteLine("{0}ミリ秒", sw.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }
}

Maze.cs

using System;
using System.IO;

namespace MazeBreadthFirstSearch {
    // 迷路クラス
    public class Maze {
        private char[,] _map;
        public int XSize { get; private set; }
        public int YSize { get; private set; }

        private Position _start;

        // コンストラクタ
        public Maze(string mapfile) {
            ReadMap(mapfile);
            _start = FindPosition('S');
        }

        // Mapデータを読み込む
        public void ReadMap(string mapfile) {
            string[] map = File.ReadAllLines(mapfile);
            this._map = new char[map[0].Length, map.Length];
            for (int y = 0; y < map.Length; y++) {
                var line = map[y];
                for (int x = 0; x < line.Length; x++) {
                    this._map[x, y] = line[x];
                }
            }
            XSize = map[0].Length;
            YSize = map.Length;
        }

        // インデクサ （これは、表示のみに利用する)
        public char this[int x, int y] {
            get { return _map[x, y]; }
        }

        // relativeの場所が何かを返す
        public Place Look(Position relative) {
            var pos = GetAbsolutePosition(relative);
            // pos = GetPosition(pos, direction);
            if (pos.X < 0 || pos.X >= this.XSize)
                return Place.Wall;
            if (pos.Y < 0 || pos.Y >= this.YSize)
                return Place.Wall;
            switch (_map[pos.X, pos.Y]) {
                case 'G':
                    return Place.Goal;
                case 'S':
                    return Place.Start;
                case ' ':
                    return Place.Path;
                default:
                    return Place.Wall;
            }
        }

        // 相対位置から絶対位置に変換 （相対位置は、startの位置を基準とする)
        public Position GetAbsolutePosition(Position relative) {
            return new Position {
                X = _start.X + relative.X,
                Y = _start.Y + relative.Y
            };
        }

        // target で指定した文字がある場所を求める。
        public Position FindPosition(char target) {
            for (int x = 0; x < XSize; x++) {
                for (int y = 0; y < YSize; y++) {
                    if (_map[x, y] == target)
                        return new Position { X = x, Y = y };
                }
            }
            throw new ApplicationException();
        }


        // Positionは値型なので、呼び出し元には影響を与えない
        public static Position GetPosition(Position current, Direction direction) {
            switch (direction) {
                case Direction.South:
                    current.Y++;
                    break;
                case Direction.East:
                    current.X++;
                    break;
                case Direction.North:
                    current.Y--;
                    break;
                case Direction.West:
                    current.X--;
                    break;
            }
            return current;
        }

        // 反対方向を求める
        public static Direction BackDirection(Direction direction) {
            switch (direction) {
                case Direction.South:
                    return Direction.North;
                case Direction.East:
                    return Direction.West;
                case Direction.North:
                    return Direction.South;
                case Direction.West:
                    return Direction.East;
            }
            return Direction.None;
        }

    }
}

Position.cs

using System;
namespace MazeBreadthFirstSearch {
    // 位置情報構造体
    public struct Position {
        public int X { get; set; }
        public int Y { get; set; }

        public override string ToString() {
            return $"({X},{Y})";
        }
    }
    // Direction
    public enum Direction {
        None,
        East,
        West,
        South,
        North
    }

    public enum Place {
        Wall,
        Path,
        Goal,
        Start
    }

}

Tracks.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace MazeBreadthFirstSearch {
    // 経路を表すクラス 位置と進行方向からなる
    public class Tracks {
        private List<Direction> _directionPath = new List<Direction>();
        private List<Position> _positionPath = new List<Position>();

        // コンストラクタ
        public Tracks() {
            _directionPath.Add(Direction.None);
            _positionPath.Add(new Position { X = 0, Y = 0 });
        }

        // 進行方向の履歴
        public IEnumerable<Direction> GetDirectionPath() {
            return _directionPath;
        }

        // 位置の履歴
        public IEnumerable<Position> GetPositionPathh() {
            return _positionPath;
        }

        // 経路を追加
        public void Add(Position pos, Direction dir) {
            _positionPath.Add(pos);
            _directionPath.Add(dir);
        }

        // 最後の位置と方向を取得
        public (Position, Direction) Last() {
            return (_positionPath.Last(), _directionPath.Last());
        }

        // 現在の位置と方向を取得
        public (Position, Direction) Current {
            get {
                return (_positionPath.Last(), _directionPath.Last());
            }
        }

        public Tracks Clone() {
            var obj = new Tracks() {
                _directionPath = this._directionPath.ToList(),
                _positionPath = this._positionPath.ToList()
            };
            return obj;
        }

    }
}

MazeSolver.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace MazeBreadthFirstSearch {
    // 幅優先探索で解く
    public class MazeSolver : IObservable<Position> {
        private Maze _maze;

        // 解く。必ず解が存在することが前提。
        public IEnumerable<Direction> Solve(Maze maze) {
            _maze = maze;
            var tracks = _Solve();
            return tracks.GetDirectionPath();
        }

        public Tracks _Solve() {
            Queue<Tracks> queu = new Queue<Tracks>();
            queu.Enqueue(new Tracks());

            while (queu.Count != 0) {
                //キューの先頭から経路情報取り出す
                var tracks = queu.Dequeue();
                var (currentPosition, currentDirection) = tracks.Current;
                foreach (var direction in Directions(currentDirection).ToList()) {
                    // 次に進む位置を求める
                    var nextpos = Maze.GetPosition(currentPosition, direction);
                    // その場所の種類を調べる
                    switch (_maze.Look(nextpos)) {
                        case Place.Goal:
                            return tracks;
                        case Place.Path:
                            if (!AlreadyPassed(tracks, nextpos)) {
                                // 通路でまだ通っていない場所ならば、キューに入れて覚えてく
                                var clone = tracks.Clone();
                                clone.Add(nextpos, direction);
                                queu.Enqueue(clone);
                                Publish(nextpos);
                            }
                            break;
                    }
                    // 壁とStart位置ならば何もせずに、次の方向を調べる
                }
            }
            return null;
        }


        // ４つの方向を列挙する （できるだけ直進するように直前の方向を最初にする)
        public IEnumerable<Direction> Directions(Direction lastDirection) {
            if (lastDirection != Direction.None)
                yield return lastDirection;
            if (lastDirection != Direction.South)
                yield return Direction.South;
            if (lastDirection != Direction.East)
                yield return Direction.East;
            if (lastDirection != Direction.North)
                yield return Direction.North;
            if (lastDirection != Direction.West)
                yield return Direction.West;
        }

        // 指定した方向は既に通った場所か
        private bool AlreadyPassed(Tracks tracks, Position pos) {
            return tracks.GetPositionPathh().Any(p => p.X == pos.X && p.Y == pos.Y);
        }

        // このプログラムでは購読者は、Viewerオブジェクトの一つだけ。
        private List<IObserver<Position>> _observers = new List<IObserver<Position>>();

        // 終了を通知する
        private void Complete() {
            foreach (var observer in _observers) {
                observer.OnCompleted();
            }
        }

        // 状況変化を購読者に通知する
        private void Publish(Position state) {
            foreach (var observer in _observers) {
                observer.OnNext(state);
            }
        }

        // observer(購読者) が通知を受け取れるようにする
        public IDisposable Subscribe(IObserver<Position> observer) {
            _observers.Add(observer);
            return observer as IDisposable;
        }
    }
}

Viewer.cs

using System;
using System.Collections.Generic;

namespace MazeBreadthFirstSearch {
    class Viewer : IObserver<Position> {
        private Maze _maze;

        public Viewer(Maze maze) {
            _maze = maze;
            Console.SetCursorPosition(0, 0);
            Print();
        }

        public void OnCompleted() {
        }

        public void OnError(Exception error) {
        }

        private Position _current = new Position { X = 0, Y = 0 };

        // 状態が変化した （引数 relative は、相対位置)
        public void OnNext(Position relative) {
            // 絶対位置を求め
            var pos = _maze.GetAbsolutePosition(relative);
            // 足跡を残す
            Console.SetCursorPosition(pos.X, pos.Y);
            Console.Write('.');
            Console.SetCursorPosition(pos.X, pos.Y);
            System.Threading.Thread.Sleep(100);
        }

        // リプレイする
        public void Replay(IEnumerable<Direction> path) {
            var current = new Position { X = 0, Y = 0 };
            foreach (var d in path) {
                current = Maze.GetPosition(current, d);
                var pos = _maze.GetAbsolutePosition(current);
                Console.SetCursorPosition(pos.X, pos.Y);
                Console.Write('.');
                Console.SetCursorPosition(pos.X, pos.Y);
                System.Threading.Thread.Sleep(80);
            }
            Console.SetCursorPosition(0, _maze.YSize + 1);

        }

        // 迷路をConsoleに表示する
        public void Print() {
            for (int y = 0; y < _maze.YSize; y++) {
                for (int x = 0; x < _maze.XSize; x++) {
                    Console.Write(_maze[x, y]);
                }
                Console.WriteLine();
            }
        }

    }
}

---

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。