Skip to content

Instantly share code, notes, and snippets.

@jkingry
Created October 16, 2015 20:10
Show Gist options
  • Save jkingry/124fbe0c0e2a0f1d4474 to your computer and use it in GitHub Desktop.
Save jkingry/124fbe0c0e2a0f1d4474 to your computer and use it in GitHub Desktop.
Parallel MazeSolver
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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment