001package algs41;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac Maze.java
005 *  Execution:    java Maze.java N
006 *  Dependecies:  StdDraw.java
007 *
008 *  Generates a perfect N-by-N maze using depth-first search with a stack.
009 *
010 *  % java Maze 62
011 *
012 *  Note: this program generalizes nicely to finding a random tree
013 *        in a graph.
014 *
015 *************************************************************************/
016
017public class XMaze {
018        private final int N;           // dimension of maze
019        private boolean[][] north;     // is there a wall to north of cell i, j
020        private boolean[][] east;
021        private boolean[][] south;
022        private boolean[][] west;
023        private boolean[][] visited;
024        //private double size;
025        private boolean done = false;
026
027        public XMaze(int N) {
028                this.N = N;
029                StdDraw.setXscale(0, N+2);
030                StdDraw.setYscale(0, N+2);
031                init();
032                generate();
033        }
034
035        private void init() {
036                // initialize border cells as already visited
037                visited = new boolean[N+2][N+2];
038                for (int x = 0; x < N+2; x++) visited[x][0] = visited[x][N+1] = true;
039                for (int y = 0; y < N+2; y++) visited[0][y] = visited[N+1][y] = true;
040
041
042                // initialize all walls as present
043                north = new boolean[N+2][N+2];
044                east  = new boolean[N+2][N+2];
045                south = new boolean[N+2][N+2];
046                west  = new boolean[N+2][N+2];
047                for (int x = 0; x < N+2; x++)
048                        for (int y = 0; y < N+2; y++)
049                                north[x][y] = east[x][y] = south[x][y] = west[x][y] = true;
050        }
051
052
053        // generate the maze
054        private void generate(int x, int y) {
055                visited[x][y] = true;
056
057                // while there is an unvisited neighbor
058                while (!visited[x][y+1] || !visited[x+1][y] || !visited[x][y-1] || !visited[x-1][y]) {
059
060                        // pick random neighbor (could use Knuth's trick instead)
061                        while (true) {
062                                double r = Math.random();
063                                if (r < 0.25 && !visited[x][y+1]) {
064                                        north[x][y] = south[x][y+1] = false;
065                                        generate(x, y + 1);
066                                        break;
067                                }
068                                else if (r >= 0.25 && r < 0.50 && !visited[x+1][y]) {
069                                        east[x][y] = west[x+1][y] = false;
070                                        generate(x+1, y);
071                                        break;
072                                }
073                                else if (r >= 0.5 && r < 0.75 && !visited[x][y-1]) {
074                                        south[x][y] = north[x][y-1] = false;
075                                        generate(x, y-1);
076                                        break;
077                                }
078                                else if (r >= 0.75 && r < 1.00 && !visited[x-1][y]) {
079                                        west[x][y] = east[x-1][y] = false;
080                                        generate(x-1, y);
081                                        break;
082                                }
083                        }
084                }
085        }
086
087        // generate the maze starting from lower left
088        private void generate() {
089                generate(1, 1);
090                /*
091                // delete some random walls
092                for (int i = 0; i < N; i++) {
093                        int x = (int) (1 + Math.random() * (N-1));
094                        int y = (int) (1 + Math.random() * (N-1));
095                        north[x][y] = south[x][y+1] = false;
096                }
097                // add some random walls
098                for (int i = 0; i < N; i++) {
099                        int x = (int) (N / 2 + Math.random() * (N / 2));
100                        int y = (int) (N / 2 + Math.random() * (N / 2));
101                        east[x][y] = west[x+1][y] = true;
102                }
103                */
104        }
105
106
107
108        // solve the maze using depth first search
109        private void solve(int x, int y) {
110                if (x == 0 || y == 0 || x == N+1 || y == N+1) return;
111                if (done || visited[x][y]) return;
112                visited[x][y] = true;
113
114                StdDraw.setPenColor(StdDraw.BLUE);
115                StdDraw.filledCircle(x + 0.5, y + 0.5, 0.25);
116                StdDraw.show(30);
117
118                // reached middle
119                if (x == N/2 && y == N/2) done = true;
120
121                if (!north[x][y]) solve(x, y + 1);
122                if (!east[x][y])  solve(x + 1, y);
123                if (!south[x][y]) solve(x, y - 1);
124                if (!west[x][y])  solve(x - 1, y);
125
126                if (done) return;
127
128                StdDraw.setPenColor(StdDraw.GRAY);
129                StdDraw.filledCircle(x + 0.5, y + 0.5, 0.25);
130                StdDraw.show(30);
131        }
132
133        // solve the maze starting from the start state
134        public void solve() {
135                for (int x = 1; x <= N; x++)
136                        for (int y = 1; y <= N; y++)
137                                visited[x][y] = false;
138                done = false;
139                solve(1, 1);
140        }
141
142        // display the maze in turtle graphics
143        public void draw() {
144                StdDraw.setPenColor(StdDraw.RED);
145                StdDraw.filledCircle(0.5*N + 0.5, 0.5*N + 0.5, 0.375);
146                StdDraw.filledCircle(1.5, 1.5, 0.375);
147
148                StdDraw.setPenColor(StdDraw.BLACK);
149                for (int x = 1; x <= N; x++) {
150                        for (int y = 1; y <= N; y++) {
151                                if (south[x][y]) StdDraw.line(x, y, x + 1, y);
152                                if (north[x][y]) StdDraw.line(x, y + 1, x + 1, y + 1);
153                                if (west[x][y])  StdDraw.line(x, y, x, y + 1);
154                                if (east[x][y])  StdDraw.line(x + 1, y, x + 1, y + 1);
155                        }
156                }
157                StdDraw.show(1000);
158        }
159
160
161
162        // a test client
163        public static void main(String[] args) {
164                args = new String[] { "20" };
165
166                int N = Integer.parseInt(args[0]);
167                XMaze maze = new XMaze(N);
168                StdDraw.show(0);
169                maze.draw();
170                maze.solve();
171        }
172
173}
174