MazeSolver

Program.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;

namespace MazeSolve
{
    class Program
    {
        const int UP = 0;
        const int LEFT = 1;
        const int DOWN = 2;
        const int RIGHT = 3;

        static int Main(string[] args)
        {
            if (args.Length < 1 || (args.Length > 1 && args.Length < 5))
            {
                Console.Error.WriteLine("[maze image] ([top offset] [bottom offset] [left offset] [right offset])");
                return 1;
            }
            var path = args[0];
            var offsets = new int[4];

            if (args.Length > 1)
            {
                offsets[0] = Int32.Parse(args[1]);
                offsets[1] = Int32.Parse(args[2]);
                offsets[2] = Int32.Parse(args[3]);
                offsets[3] = Int32.Parse(args[4]);
            }

            using (var image = (Bitmap)Bitmap.FromFile(path))
            {
                var watch = new Stopwatch();
                watch.Start();

                SolveMaze(image, offsets[0], offsets[1], offsets[2], offsets[3]);

                watch.Stop();
                Console.WriteLine("{0}ms elapsed", watch.ElapsedMilliseconds);

                image.Save(Path.ChangeExtension(path, ".done.gif"), ImageFormat.Gif);
            }


            return 0;
        }

        unsafe static bool IsClear(BitmapData data, int pixelSize, int x, int y)
        {
            if (x < 0 || x >= data.Width || y < 0 || y >= data.Height) return false;

            var row = (byte*)data.Scan0 + (y * data.Stride);
            var pos = x * pixelSize;
            return row[pos] > 200;
        }

        static IEnumerable<Point> GetExits(BitmapData data, int pixelSize, int x, int y)
        {
            if (IsClear(data, pixelSize, x, y + 1)) yield return new Point(x, y + 1);
            if (IsClear(data, pixelSize, x, y - 1)) yield return new Point(x, y - 1);
            if (IsClear(data, pixelSize, x + 1, y)) yield return new Point(x + 1, y);
            if (IsClear(data, pixelSize, x - 1, y)) yield return new Point(x - 1, y);
        }

        static IEnumerable<Point> GetGoals(BitmapData data, int pixelSize)
        {
            for (var x = 0; x < data.Width; ++x)
            {
                if (IsClear(data, pixelSize, x, 0)) yield return new Point(x, 0);
                if (IsClear(data, pixelSize, x, data.Height - 1)) yield return new Point(x, data.Height - 1);
            }
            for (var y = 0; y < data.Height; ++y)
            {
                if (IsClear(data, pixelSize, 0, y)) yield return new Point(0, y);
                if (IsClear(data, pixelSize, data.Width - 1, y)) yield return new Point(data.Width - 1, y);
            }
        }

        unsafe static int DrawSolution(BitmapData data, int pixelSize, Point end, Point[,] parents)
        {
            var solutionLength = 0;
            while (end != Point.Empty)
            {
                solutionLength += 1;
                var row = (byte*)data.Scan0 + (end.Y * data.Stride);
                var pos = end.X * pixelSize;
                row[pos] = 0;
                row[pos + 1] = 0;
                row[pos + 2] = 255;

                end = parents[end.X, end.Y];
            }

            return solutionLength;
        }

        unsafe static void SolveMaze(Bitmap image, int topOffset, int bottomOffset, int leftOffset, int rightOffset)
        {
            if (image.PixelFormat != PixelFormat.Format24bppRgb) throw new NotSupportedException(String.Format("Unsupported pixel format: {0}", image.PixelFormat));

            var bounds = new Rectangle(leftOffset, topOffset, image.Width - (leftOffset + rightOffset), image.Height - (topOffset + bottomOffset));
            var data = image.LockBits(bounds, ImageLockMode.ReadWrite, image.PixelFormat);
            var pixelSize = data.Stride / image.Width;

            var goals = GetGoals(data, pixelSize).Take(2).ToArray();

            if (goals.Length < 2) throw new NotSupportedException("Failed to find at least two exits from maze boundary");

            var start = goals[0];
            var end = goals[1];

            var visited = new bool[bounds.Width, bounds.Height];
            var parents = new Point[bounds.Width, bounds.Height];

            var work = new Stack<Point>();

            work.Push(start);

            var exits = new bool[4];

            var foundSolution = false;

            while (work.Count > 0)
            {
                var current = work.Pop();
                visited[current.X, current.Y] = true;

                var row = (byte*)data.Scan0 + (current.Y * data.Stride);
                var pos = current.X * pixelSize;
                row[pos] = 0;
                row[pos + 1] = 255;
                row[pos + 2] = 0;

                if (current.X == end.X && current.Y == end.Y)
                {
                    foundSolution = true;
                    break;
                }

                foreach (var exit in GetExits(data, pixelSize, current.X, current.Y))
                {
                    if (visited[exit.X, exit.Y]) continue;

                    parents[exit.X, exit.Y] = current;
                    work.Push(exit);
                }
            }

            if (!foundSolution)
            {
                Console.Error.WriteLine("No solution found");
            }
            else
            {
                var solutionLength = DrawSolution(data, pixelSize, end, parents);
                Console.WriteLine("Solution length {0}", solutionLength);
            }

            image.UnlockBits(data);
        }
    }
}