001package squidpony.squidgrid.mapping;
002
003import squidpony.squidgrid.Direction;
004import squidpony.squidmath.RNG;
005
006import java.util.ArrayList;
007import java.util.Arrays;
008import java.util.LinkedList;
009import java.util.List;
010
011/**
012 * Recursively divided maze. Creates only walls and passages.
013 *
014 * This dungeon generator is based on a port of the rot.js version.
015 *
016 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
017 */
018public class DividedMazeGenerator {
019
020    private class DividedMazeRoom {
021
022        private int left, top, right, bottom;
023
024        public DividedMazeRoom(int left, int top, int right, int bottom) {
025            this.left = left;
026            this.top = top;
027            this.right = right;
028            this.bottom = bottom;
029        }
030    }
031
032    private int width, height;
033    private boolean[][] map;
034    private RNG rng;
035
036    /**
037     * Sets up the generator to make mazes the given width and height. The mazes
038     * have a solid wall border.
039     *
040     * @param width
041     * @param height
042     */
043    public DividedMazeGenerator(int width, int height) {
044        this.width = width;
045        this.height = height;
046        rng = new RNG();
047    }
048
049    /**
050     * Sets up the generator to make mazes the given width and height. The mazes
051     * have a solid wall border.
052     *
053     * @param width in cells
054     * @param height in cells
055     * @param rng the random number generator to use
056     */
057    public DividedMazeGenerator(int width, int height, RNG rng) {
058        this.width = width;
059        this.height = height;
060        this.rng = rng;
061    }
062
063    /**
064     * Builds a maze. True values represent walls.
065     *
066     * @return
067     */
068    public boolean[][] create() {
069        map = new boolean[width][height];
070
071        for (int x = 0; x < width; x++) {
072            for (int y = 0; y < height; y++) {
073                map[x][y] = x == 0 || y == 0 || x + 1 == width || y + 1 == height;
074            }
075        }
076
077        process();
078
079        return map;
080    }
081
082    private void process() {
083        LinkedList<DividedMazeRoom> stack = new LinkedList<>();
084        stack.offer(new DividedMazeRoom(1, 1, width - 2, height - 2));
085        while (!stack.isEmpty()) {
086            DividedMazeRoom room = stack.removeFirst();
087            ArrayList<Integer> availX = new ArrayList<>(),
088                               availY = new ArrayList<>();
089
090            for (int x = room.left + 1; x < room.right; x++) {
091                boolean top = map[x][room.top - 1];
092                boolean bottom = map[x][room.bottom + 1];
093                if (top && bottom && x % 2 == 0) {
094                    availX.add(x);
095                }
096            }
097
098            for (int y = room.top + 1; y < room.bottom; y++) {
099                boolean left = map[room.left - 1][y];
100                boolean right = map[room.right + 1][y];
101                if (left && right && y % 2 == 0) {
102                    availY.add(y);
103                }
104            }
105
106            if (availX.isEmpty() || availY.isEmpty()) {
107                continue;
108            }
109
110            int x2 = rng.getRandomElement(availX);
111            int y2 = rng.getRandomElement(availY);
112
113            map[x2][y2] = true;
114
115            for (Direction dir : Direction.CARDINALS) {
116                switch (dir) {
117                    case LEFT:
118                        for (int x = room.left; x < x2; x++) {
119                            map[x][y2] = true;
120                        }
121                        break;
122                    case RIGHT:
123                        for (int x = x2 + 1; x <= room.right; x++) {
124                            map[x][y2] = true;
125                        }
126                        break;
127                    case UP:
128                        for (int y = room.top; y < y2; y++) {
129                            map[x2][y] = true;
130                        }
131                        break;
132                    case DOWN:
133                        for (int y = y2 + 1; y <= room.bottom; y++) {
134                            map[x2][y] = true;
135                        }
136                        break;
137                    case NONE:
138                        break;
139                                case DOWN_LEFT:
140                                case DOWN_RIGHT:
141                                case UP_LEFT:
142                                case UP_RIGHT:
143                                        throw new IllegalStateException("There should only be cardinal directions here");
144                }
145            }
146
147            List<Direction> dirs = Arrays.asList(Direction.CARDINALS);
148            dirs.remove(rng.getRandomElement(dirs));
149
150            for (Direction dir : dirs) {
151                switch (dir) {
152                    case LEFT:
153                        map[rng.between(room.left, x2)][y2] = false;
154                        break;
155                    case RIGHT:
156                        map[rng.between(x2 + 1, room.right + 1)][y2] = false;
157                        break;
158                    case UP:
159                        map[x2][rng.between(room.top, y2)] = false;
160                        break;
161                    case DOWN:
162                        map[x2][rng.between(y2 + 1, room.bottom + 1)] = false;
163                        break;
164                    case NONE:
165                        break;
166                                case DOWN_LEFT:
167                                case DOWN_RIGHT:
168                                case UP_LEFT:
169                                case UP_RIGHT:
170                                        throw new IllegalStateException("There should only be cardinal directions here");
171                }
172            }
173
174            stack.offer(new DividedMazeRoom(room.left, room.top, x2 - 1, y2 - 1));
175            stack.offer(new DividedMazeRoom(x2 + 1, room.top, room.right, y2 - 1));
176            stack.offer(new DividedMazeRoom(room.left, y2 + 1, x2 - 1, room.bottom));
177            stack.offer(new DividedMazeRoom(x2 + 1, y2 + 1, room.right, room.bottom));
178        }
179    }
180
181}