Parallel MazeSolver

ParallelMazeSolver.cs

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

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, ".p.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 void DrawSolution(BitmapData data, int pixelSize, IEnumerable<Point> path)
        {
            foreach(var point in path)
            {
                var row = (byte*)data.Scan0 + (point.Y * data.Stride);
                var pos = point.X * pixelSize;
                row[pos] = 0;
                row[pos + 1] = 0;
                row[pos + 2] = 255;
            }
        }

        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 int[bounds.Width, bounds.Height];

            Func<Point, int, Point[]> worker = (initial, id) =>
            {
                var work = new Stack<Point>();
                var parents = new Point[bounds.Width, bounds.Height];

                work.Push(initial);

                while (work.Count > 0)
                {
                    var current = work.Pop();

                    foreach (var exit in GetExits(data, pixelSize, current.X, current.Y))
                    {
                        var original = Interlocked.CompareExchange(ref visited[exit.X, exit.Y], id, 0);
                        if (original == 0)
                        {
                            parents[exit.X, exit.Y] = current;
                            work.Push(exit);
                            continue;
                        }

                        if (original == id)
                        {
                            continue;
                        }

                        var path = new List<Point> { exit } ;
                        var solvePoint = current;
                        while(solvePoint != initial)
                        {
                            path.Add(solvePoint);
                            solvePoint = parents[solvePoint.X, solvePoint.Y];
                        }

                        return path.ToArray();
                    }
                }

                return new Point[0];
            };

            var fromStart = Task.Factory.StartNew(() => worker(start, 1));
            var fromEnd = Task.Factory.StartNew(() => worker(end, 2));
            Task.WaitAll(fromStart, fromEnd);

            if (fromStart.Result.Length > 0 && fromEnd.Result.Length > 0)
            {
                Console.WriteLine("Found solution");
                var solutionLength = fromStart.Result.Length + fromEnd.Result.Length;

                DrawSolution(data, pixelSize, fromStart.Result.Concat(fromEnd.Result));

                Console.WriteLine("Solution length {0}", solutionLength);
            }
            else
            {
                Console.Error.WriteLine("No solution found");
            }

            image.UnlockBits(data);
        }
    }
}