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}