Path Finder in C#

A recent question on Stack Overflow asked how to write recursive code to navigate a maze. Here’s my attempt at a solution (written in C#).

//Program.cs
using System;
using System.Collections.Generic;

namespace PathFinder
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program();
            Console.WriteLine("Done");
            Console.ReadKey();
        }

        private Program()
        {
            Maze maze = new Maze
                (
                    new bool[4, 4]
                {
                    {true,false,true,false}
                    ,{true,true,true,true}
                    ,{false,true,false,true}
                    ,{false,true,true,true}
                }
                );
            
            foreach (IEnumerable<Point> path in maze.FindPaths(0, 0, 3, 3))
            {
                OutputPath(path);
            }

        }


        private static void OutputPath(IEnumerable<Point> path)
        {
            Console.WriteLine();
            foreach (Point p in path)
            {
                Console.Write(p.ToString());
            }
            Console.WriteLine();
        }
    }
}

//Maze.cs
using System.Collections.Generic;
using System.Linq;

namespace PathFinder
{
    public class Maze
    {
        bool[,] maze;
        public Maze(bool[,] maze)
        {
            this.maze = maze;
        }

        private int MaxPathLength
        {
            get { return this.maze.Length; }
        }

        private bool IsOnPath(Point p)
        {
            return maze[p.X, p.Y];
        }

        public IEnumerable<IEnumerable<Point>> FindPaths(int startX, int startY, int endX, int endY)
        {
            Point start = new Point(startX, startY, 0, 0, this.maze.GetLength(0)-1, this.maze.GetLength(1)-1);
            Point end = new Point(endX, endY);
            if (!start.IsOnGrid) throw new OffGridException(start);
            if (!end.IsOnGrid) throw new OffGridException(end);
            if (!IsOnPath(start)) throw new OffPathException(start);
            if (!IsOnPath(end)) throw new OffPathException(end);
            return Step(start, end, this.MaxPathLength, Direction.StandStill);
        }
        private IEnumerable<IEnumerable<Point>> Step(Point current, Point end, int stepsRemaining, Direction direction)
        {
            if (stepsRemaining > 0 && current.IsOnGrid && IsOnPath(current))
            {
                stepsRemaining--;
                if (current.Equals(end))
                {
                    yield return new[] { current };
                }
                else
                {
                    //could be improved by threading (parallel.foreach won't work though due to use of yield return)
                    foreach (Direction d in Direction.Directions)
                    {
                        if (!direction.IsOppositeOf(d))
                        {
                            foreach (IEnumerable<Point> path in Step(d.Move(current), end, stepsRemaining, d))
                            {
                                yield return (new[] { current }).Concat(path);
                            }
                        }
                    }
                }
            }
        }
    }
}

//Point.cs
namespace PathFinder
{

    public struct Point
    {
        const string DisplayFormat = "({0},{1})";

        public static int MaxX { get; set; }
        public static int MaxY { get; set; }
        public static int MinX { get; set; }
        public static int MinY { get; set; }

        public int X { get; set; }
        public int Y { get; set; }
        public Point(int x, int y)
            : this()
        {
            this.X = x;
            this.Y = y;
        }
        public Point(int x, int y, int minX, int minY, int maxX, int maxY)
            : this(x, y)
        {
            MinX = minX;
            MinY = minY;
            MaxX = maxX;
            MaxY = maxY;
        }

        public bool IsOnGrid
        {
            get
            {
                return this.X <= MaxX
                    && this.X >= MinX
                    && this.Y <= MaxY
                    && this.Y >= MinY;
            }
        }

        public override string ToString()
        {
            return string.Format(DisplayFormat, this.X, this.Y);
        }

    }
}

//Direction.cs
using System.Collections.Generic;

namespace PathFinder
{

    //thanks to Roelof for this trick (http://stackoverflow.com/questions/10704863/c-sharp-ensure-valid-enum-values-futureproof-method)
    class Direction
    {
        private string name;
        private int horizontalMovement;
        private int verticalMovement;

        private Direction(int horizontalMovement, int verticalMovement, string name)
        {
            this.horizontalMovement = horizontalMovement;
            this.verticalMovement = verticalMovement;
            this.name = name;
        }

        public static readonly Direction StandStill = new Direction(0, 0, "Still");//don't include this in directions

        public static readonly Direction Left = new Direction(-1, 0, "Left");
        public static readonly Direction Right = new Direction(1, 0, "Right");
        public static readonly Direction Up = new Direction(0, 1, "Up");
        public static readonly Direction Down = new Direction(0, -1, "Down");
        //if required we could add diagonals / jumps (i.e. values > 1 or <-1)
        //if we add anything above, also add to the GetDirections list - that way all logic will be auto applied
        public static readonly IEnumerable<Direction> Directions = new Direction[] { Left, Right, Up, Down };

        public bool IsOppositeOf(Direction d)
        {
            return
                (this.horizontalMovement + d.horizontalMovement) == 0
                &&
                (this.verticalMovement + d.verticalMovement) == 0;
        }

        public Point Move(Point from)
        {
            return new Point(from.X + this.horizontalMovement, from.Y + this.verticalMovement);
        }

        public override string ToString()
        {
            return this.name;
        }
    }
}

//OffGridException.cs
using System;

namespace PathFinder
{
    class OffGridException: Exception
    {

        const string ExceptionText = "Provided point ({0},{1}) is outside the bounds of the grid (({2},{3}),({4},{5})).";
        
        public OffGridException(Point p)
            :base(string.Format(ExceptionText,p.X,p.Y,Point.MinX, Point.MinY, Point.MaxX, Point.MaxY))
        {}
    }
}

//OffPathException.cs
using System;

namespace PathFinder
{
    class OffPathException : Exception
    {

        const string ExceptionText = "Provided point ({0},{1}) is not located on a path in the maze.";

        public OffPathException(Point p)
            : base(string.Format(ExceptionText, p.X, p.Y))
        { }
    }
}

About these ads