Maze.java

/*************************************************************************
 *  Compilation:  javac Maze.java
 *  Execution:    java Maze.java N
 *  Dependecies:  StdDraw.java
 *
 *  Generates a perfect N-by-N maze using depth-first search with a stack.
 *
 *  % java Maze 62
 *
 *  Note: this program generalizes nicely to finding a random tree
 *        in a graph.
 *
 *************************************************************************/

import java.awt.Color;

public class Maze {
   private int N;                 // dimension of maze
   private boolean[][] north;     // is there a wall to north of cell i, j
   private boolean[][] east;
   private boolean[][] south;
   private boolean[][] west;
   private boolean[][] visited;
   private double size;
   boolean done = false;

   public Maze(int N) {
      this.N = N;
      StdDraw.create(512, 512);
      size = 512.0 / (N + 2);
      init();
      generate();
   }

   private void init() {
      // initialize border cells as already visited
      visited = new boolean[N+2][N+2];
      for (int x = 0; x < N+2; x++) visited[x][0] = visited[x][N+1] = true;
      for (int y = 0; y < N+2; y++) visited[0][y] = visited[N+1][y] = true;


      // initialze all wells as present
      north = new boolean[N+2][N+2];
      east  = new boolean[N+2][N+2];
      south = new boolean[N+2][N+2];
      west  = new boolean[N+2][N+2];
      for (int x = 0; x < N+2; x++)
         for (int y = 0; y < N+2; y++)
            north[x][y] = east[x][y] = south[x][y] = west[x][y] = true;
   }


   // generate the maze
   private void generate(int x, int y) {
      visited[x][y] = true;

      // while there is an univisited neighbor
      while (!visited[x][y+1] || !visited[x+1][y] || !visited[x][y-1] || !visited[x-1][y]) {

         // pick random neighbor (could use Knuth's trick instead)
         while (true) {
            double r = Math.random();
            if (r < 0.25 && !visited[x][y+1]) {
               north[x][y] = south[x][y+1] = false;
               generate(x, y + 1);
               break;
            }
            else if (r < 0.50 && !visited[x+1][y]) {
               east[x][y] = west[x+1][y] = false;
               generate(x+1, y);
               break;
            }
            else if (r < 0.75 && !visited[x][y-1]) {
               south[x][y] = north[x][y-1] = false;
               generate(x, y-1);
               break;
            }
            else if (r < 1.00 && !visited[x-1][y]) {
               west[x][y] = east[x-1][y] = false;
               generate(x-1, y);
               break;
            }
         }
      }
   }

   // generate the maze starting from lower left
   private void generate() {
      generate(1, 1);

      // delete some random walls
      for (int i = 0; i < N; i++) {
         int x = (int) (1 + Math.random() * (N-1));
         int y = (int) (1 + Math.random() * (N-1));
         north[x][y] = south[x][y+1] = false;
      }

      // add some random walls
      for (int i = 0; i < 10; i++) {
         int x = (int) (N / 2 + Math.random() * (N / 2));
         int y = (int) (N / 2 + Math.random() * (N / 2));
         east[x][y] = west[x+1][y] = true;
      }
     
   }



   // solve the maze using depth first search
   private void solve(int x, int y) {
      if (x == 0 || y == 0 || x == N+1 || y == N+1) return;
      if (done || visited[x][y]) return;
      visited[x][y] = true;

      StdDraw.setColor(Color.blue);
      StdDraw.go(size * (x + 0.5), size * (y + 0.5));
      StdDraw.spot(size / 2);
      StdDraw.pause(30);

      // reached upper right
      if (x == N/2 && y == N/2) done = true;

      if (!north[x][y]) solve(x, y + 1);
      if (!east[x][y])  solve(x + 1, y);
      if (!south[x][y]) solve(x, y - 1);
      if (!west[x][y])  solve(x - 1, y);

      if (done) return;

      StdDraw.setColor(Color.gray);
      StdDraw.go(size * (x + 0.5), size * (y + 0.5));
      StdDraw.spot(size / 2);
      StdDraw.pause(30);
   }

   // solve the maze starting from the start state
   public void solve() {
      for (int x = 1; x <= N; x++)
         for (int y = 1; y <= N; y++)
            visited[x][y] = false;
      done = false;
      solve(1, 1);
   }

   // display the maze in turtle graphics
   public void draw() {
      StdDraw.setColor(Color.red);
      StdDraw.go(size * (N/2 + 0.5), size * (N/2 + 0.5));
      StdDraw.spot(3 * size / 4);
      StdDraw.go(size * (1 + 0.5), size * (1 + 0.5));
      StdDraw.spot(3 * size / 4);

      StdDraw.setColor(Color.black);
      for (int x = 1; x <= N; x++) {
         for (int y = 1; y <= N; y++) {
            if (south[x][y]) {
               StdDraw.go(x*size, y*size);
               StdDraw.penDown();
               StdDraw.go(x*size + size, y*size);
               StdDraw.penUp();
            }
            if (north[x][y]) {
               StdDraw.go(x*size, y*size + size);
               StdDraw.penDown();
               StdDraw.go(x*size + size, y*size + size);
               StdDraw.penUp();
            }
            if (west[x][y]) {
               StdDraw.go(x*size, y*size);
               StdDraw.penDown();
               StdDraw.go(x*size, y*size + size);
               StdDraw.penUp();
            }
            if (east[x][y]) {
               StdDraw.go(x*size + size, y*size);
               StdDraw.penDown();
               StdDraw.go(x*size + size, y*size + size);
               StdDraw.penUp();
            }
         }
      }
      StdDraw.pause(1000);
      StdDraw.show();
   }



   // a test client
   public static void main(String[] args) {
      int N = Integer.parseInt(args[0]);
      Maze maze = new Maze(N);
      maze.draw();
      maze.solve();
   }

}