Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Maze PP

By: a guest on May 1st, 2012  |  syntax: C#  |  size: 8.06 KB  |  hits: 42  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. namespace PP.MazeSolver {
  2.     using System;
  3.     using System.Collections.Generic;
  4.     using System.Diagnostics;
  5.     using System.Threading;
  6.  
  7.     static class Program {
  8.  
  9.         // Solving maze (Sequential)
  10.         static List<Cell> ComputeSolution(Maze maze, Cell cell, int size, bool canUp, bool canDown, bool canRight, bool canLeft)
  11.         {
  12.             if ((cell.X == size - 1) && (cell.Y == size - 1)) // If arrived at Exit
  13.             {
  14.                 List<Cell> solution = new List<Cell>();
  15.                 solution.Add(cell);
  16.                 return solution;
  17.             }
  18.             else
  19.             {
  20.                 if (canUp == maze.HasConnectionUp(cell))
  21.                 {
  22.                     List<Cell> partialResult = ComputeSolution(maze, cell.Up, size, true, false, true, true);                  
  23.                     if (partialResult != null)
  24.                     {                        
  25.                         partialResult.Insert(0, cell);
  26.                         return partialResult;
  27.                     }
  28.                 }
  29.                 if (canDown == maze.HasConnectionDown(cell))
  30.                 {
  31.                     List<Cell> partialResult = ComputeSolution(maze, cell.Down, size, false, true, true, true);
  32.                     if (partialResult != null)
  33.                     {                      
  34.                         partialResult.Insert(0, cell);
  35.                         return partialResult;
  36.                     }
  37.                 }
  38.                 if (canRight == maze.HasConnectionRight(cell))
  39.                 {
  40.                     List<Cell> partialResult = ComputeSolution(maze, cell.Right, size, true, true, true, false);                    
  41.                     if (partialResult != null)
  42.                     {                        
  43.                         partialResult.Insert(0, cell);
  44.                         return partialResult;
  45.                     }
  46.                 }
  47.                 if (canLeft == maze.HasConnectionLeft(cell))
  48.                 {
  49.                     List<Cell> partialResult = ComputeSolution(maze, cell.Left, size, true, true, false, true);                  
  50.                     if (partialResult != null)
  51.                     {                      
  52.                         partialResult.Insert(0, cell);
  53.                         return partialResult;
  54.                     }
  55.                 }
  56.             }
  57.             return null;
  58.         }
  59.  
  60.         // Solving maze (parallel)
  61.         static List<Cell> ComputeSolutionParallel(Maze maze, Cell cell, int size, bool canUp, bool canDown, bool canRight, bool canLeft)
  62.         {
  63.             Thread t1 = new Thread(()=> CanUp(maze, cell.Up, size, true, false, true, true));
  64.             Thread t2 = new Thread(() => CanDown(maze, cell.Down, size, false, true, true, true));
  65.             Thread t3 = new Thread(() => CanRight(maze, cell.Right, size, true, true, true, false));
  66.             Thread t4 = new Thread(() => CanLeft(maze, cell.Left, size, true, true, false, true));
  67.  
  68.             if ((cell.X == size - 1) && (cell.Y == size - 1)) // If arrived at Exit
  69.             {
  70.                 List<Cell> solution = new List<Cell>();
  71.                 solution.Add(cell);
  72.                 return solution;
  73.             }
  74.             else
  75.             {
  76.                 t1.Start();
  77.                 t2.Start();
  78.                 t3.Start();
  79.                 t4.Start();
  80.  
  81.                 t1.Join();
  82.                 t2.Join();
  83.                 t3.Join();
  84.                 t4.Join();
  85.             }
  86.             return null;
  87.         }
  88.  
  89.         static List<Cell> CanUp(Maze m, Cell c, int size, bool canUp, bool canDown, bool canRight, bool canLeft)
  90.         {
  91.             if (canUp == m.HasConnectionUp(c))
  92.             {
  93.                 List<Cell> partialResult = ComputeSolutionParallel(m, c.Up, size, true, false, true, true);
  94.                 if (partialResult != null)
  95.                 {
  96.                     partialResult.Insert(0, c);
  97.                     return partialResult;
  98.                 }
  99.             }
  100.             return null;
  101.         }
  102.  
  103.         static List<Cell> CanDown(Maze m, Cell c, int size, bool canUp, bool canDown, bool canRight, bool canLeft)
  104.         {
  105.             if (canDown == m.HasConnectionDown(c))
  106.             {
  107.                 List<Cell> partialResult = ComputeSolutionParallel(m, c.Down, size, false, true, true, true);
  108.                 if (partialResult != null)
  109.                 {
  110.                     partialResult.Insert(0, c);
  111.                     return partialResult;
  112.                 }
  113.             }
  114.             return null;
  115.         }
  116.  
  117.         static List<Cell> CanRight(Maze m, Cell c, int size, bool canUp, bool canDown, bool canRight, bool canLeft)
  118.         {
  119.             if (canRight == m.HasConnectionRight(c))
  120.             {
  121.                 List<Cell> partialResult = ComputeSolutionParallel(m, c.Right, size, true, true, true, false);
  122.                 if (partialResult != null)
  123.                 {
  124.                     partialResult.Insert(0, c);
  125.                     return partialResult;
  126.                 }
  127.             }
  128.             return null;
  129.         }
  130.  
  131.         static List<Cell> CanLeft(Maze m, Cell c, int size, bool canUp, bool canDown, bool canRight, bool canLeft)
  132.         {
  133.             if (canLeft == m.HasConnectionLeft(c))
  134.             {
  135.                 List<Cell> partialResult = ComputeSolutionParallel(m, c.Left, size, true, true, false, true);
  136.                 if (partialResult != null)
  137.                 {
  138.                     partialResult.Insert(0, c);
  139.                     return partialResult;
  140.                 }
  141.             }
  142.             return null;
  143.         }
  144.  
  145.         static void Main(String[] args) {
  146.            
  147.             // read size of maze from user input
  148.             Console.Write("Size of maze: ");
  149.             int size = Int32.Parse(Console.ReadLine());
  150.  
  151.             // create a maze
  152.             Console.Write("Creating maze... ");
  153.             Stopwatch watch = Stopwatch.StartNew();
  154.             Maze maze = new Maze(size, size);
  155.             Console.WriteLine(watch.Elapsed);
  156.  
  157.             // solve the created maze
  158.             Console.Write("Solving maze... ");
  159.             watch.Restart();
  160.  
  161.             // MODIFY THIS SECTION BELOW TO SOLVE THE MAZE
  162.  
  163. //            List<Cell> solution = ComputeSolution(maze, new Cell(0, 0), size, true, true, true, true);
  164.             List<Cell> solutionParallel = ComputeSolutionParallel(maze, new Cell(0, 0), size, true, true, true, true);
  165.  
  166.             // END OF SECTION YOU SHOULD MODIFY
  167.  
  168. /*            Console.WriteLine(watch.Elapsed);
  169.  
  170.             ConsoleColor color = Console.ForegroundColor;
  171.             if (maze.IsSolutionCorrect(solution)) {
  172.                 Console.ForegroundColor = ConsoleColor.Green;
  173.                 Console.WriteLine("Correct!");
  174.             } else {
  175.                 Console.ForegroundColor = ConsoleColor.Red;
  176.                 Console.WriteLine("Incorrect!");
  177.             }
  178.             Console.ForegroundColor = color;
  179.  
  180.             Console.Write("Drawing maze... ");
  181.  
  182.             // this will draw the maze together with the solution
  183.             maze.Save("maze with path.png", solution);
  184.  
  185.             Console.WriteLine("done.");
  186.             Console.ReadLine();
  187.             */
  188.             //------------------------------------------------------
  189.  
  190.             Console.WriteLine(watch.Elapsed);
  191.  
  192.             ConsoleColor colorP = Console.ForegroundColor;
  193.             if (maze.IsSolutionCorrect(solutionParallel))
  194.             {
  195.                 Console.ForegroundColor = ConsoleColor.Green;
  196.                 Console.WriteLine("Correct!");
  197.             }
  198.             else
  199.             {
  200.                 Console.ForegroundColor = ConsoleColor.Red;
  201.                 Console.WriteLine("Incorrect!");
  202.             }
  203.             Console.ForegroundColor = colorP;
  204.  
  205.             Console.Write("Drawing maze... ");
  206.  
  207.             // this will draw the maze together with the solution
  208.             maze.Save("maze with path.png", solutionParallel);
  209.  
  210.             Console.WriteLine("done.");
  211.             Console.ReadLine();
  212.         }
  213.     }
  214. }
create a new version of this paste RAW Paste Data