001package squidpony.squidgrid.mapping; 002 003import squidpony.squidgrid.Direction; 004import squidpony.squidmath.*; 005 006import java.util.ArrayList; 007import java.util.Arrays; 008import java.util.List; 009import java.util.Map; 010 011/** 012 * A dungeon generator that can use a mix of techniques to have part-cave, part-room dungeons. Not entirely intended for 013 * normal use outside of this library, though it can be very useful when you want to make a dungeon match a specific 014 * path and existing generators that use MixedGenerator aren't sufficient. You may want to use a simpler generator based 015 * on this, like SerpentMapGenerator, which generates a long, winding path that loops around on itself. This supports 016 * the getEnvironment() method, which can be used in conjunction with RoomFinder to find where separate room, corridor, 017 * and cave areas have been placed. 018 * <br> 019 * Based on Michael Patraw's excellent Drunkard's Walk dungeon generator. 020 * http://mpatraw.github.io/libdrunkard/ 021 * @see squidpony.squidgrid.mapping.SerpentMapGenerator a normal use for MixedGenerator that makes winding dungeons 022 * @see squidpony.squidgrid.mapping.SerpentDeepMapGenerator uses MixedGenerator as it makes a multi-level dungeon 023 * Created by Tommy Ettinger on 10/22/2015. 024 */ 025public class MixedGenerator implements IDungeonGenerator { 026 public static final int CAVE = 0, 027 BOX = 1, 028 ROUND = 2, 029 BOX_WALLED = 3, 030 ROUND_WALLED = 4; 031 032 /** 033 * Constant for environment tiles that are not near a cave, room, or corridor. Value is 0. 034 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 035 * Present here for compatibility; you should prefer {@link DungeonUtility#UNTOUCHED}. 036 */ 037 public static final int UNTOUCHED = 0; 038 /** 039 * Constant for environment tiles that are floors for a room. Value is 1. 040 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 041 * Present here for compatibility; you should prefer {@link DungeonUtility#ROOM_FLOOR}. 042 */ 043 public static final int ROOM_FLOOR = 1; 044 /** 045 * Constant for environment tiles that are walls near a room. Value is 2. 046 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 047 * Present here for compatibility; you should prefer {@link DungeonUtility#ROOM_WALL}. 048 */ 049 public static final int ROOM_WALL = 2; 050 /** 051 * Constant for environment tiles that are floors for a cave. Value is 3. 052 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 053 * Present here for compatibility; you should prefer {@link DungeonUtility#CAVE_FLOOR}. 054 */ 055 public static final int CAVE_FLOOR = 3; 056 /** 057 * Constant for environment tiles that are walls near a cave. Value is 4. 058 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 059 * Present here for compatibility; you should prefer {@link DungeonUtility#CAVE_WALL}. 060 */ 061 public static final int CAVE_WALL = 4; 062 /** 063 * Constant for environment tiles that are floors for a corridor. Value is 5. 064 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 065 * Present here for compatibility; you should prefer {@link DungeonUtility#CORRIDOR_FLOOR}. 066 */ 067 public static final int CORRIDOR_FLOOR = 5; 068 /** 069 * Constant for environment tiles that are walls near a corridor. Value is 6. 070 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 071 * Present here for compatibility; you should prefer {@link DungeonUtility#CORRIDOR_WALL}. 072 */ 073 public static final int CORRIDOR_WALL = 6; 074 075 //protected EnumMap<CarverType, Integer> carvers; 076 protected double[] carvers; 077 protected WeightedTable carverTable; 078 protected int width, height; 079 protected float roomWidth, roomHeight; 080 public IRNG rng; 081 protected char[][] dungeon; 082 protected boolean generated; 083 protected int[][] environment; 084 protected boolean[][] marked, walled, fixedRooms; 085 protected IntVLA points; 086 protected int totalPoints; 087 088 /** 089 * Mainly for internal use; this is used by {@link #MixedGenerator(int, int, IRNG)} to get its room positions. 090 * This is (and was) the default for generating a List of Coord if no other collection of Coord was supplied to the 091 * constructor. For some time this was not the default, and {@link #cleanPoints(int, int, IRNG)} was used instead. 092 * Both are still options, but this technique seems to keep corridors shorter and makes connections between rooms 093 * more relevant to the current area. 094 * <br> 095 * <a href="https://gist.githubusercontent.com/tommyettinger/be0ed51858cb492bc7e8cda43a04def1/raw/dae9d8e4f45dd3a3577bdd5f58b419ea5f9ed570/PoissonDungeon.txt">Preview map.</a> 096 * @param width dungeon width in cells 097 * @param height dungeon height in cells 098 * @param rng rng to use 099 * @return evenly spaced Coord points in a list made by PoissonDisk, trimmed down so they aren't all used 100 * @see PoissonDisk used to make the list 101 */ 102 public static OrderedSet<Coord> basicPoints(int width, int height, IRNG rng) 103 { 104 return PoissonDisk.sampleRectangle(Coord.get(2, 2), Coord.get(width - 3, height - 3), 105 8.5f * (width + height) / 120f, width, height, 35, rng); 106 } 107 /** 108 * Mainly for internal use; this was used by {@link #MixedGenerator(int, int, IRNG)} to get its room positions, and 109 * you can choose to use it with {@code new MixedGenerator(width, height, rng, cleanPoints(width, height, rng))}. 110 * It produces a fairly rigid layout of rooms that should have less overlap between rooms and corridors; the 111 * downside to this is that corridors can become extremely long. The exact technique used here is to get points from 112 * a Halton-like sequence, formed using {@link VanDerCorputQRNG} to get a van der Corput sequence, for the x axis 113 * and a scrambled van der Corput sequence for the y axis. MixedGenerator will connect these points in pairs. The 114 * current method is much better at avoiding "clumps" of closely-positioned rooms in the center of the map. 115 * <br> 116 * <a href="https://gist.githubusercontent.com/tommyettinger/2745e6fc16fc2acebe2fc959fb4e4c2e/raw/77e1f4dbc844d8892c1a686754535c02cadaa270/TenDungeons.txt">Preview maps, with and without box drawing characters.</a> 117 * Note that one of the dungeons in that gist was produced as a fallback by {@link DungeonGenerator} with no 118 * arguments (using DEFAULT_DUNGEON as the dungeon style), because the map this method produced in one case had too 119 * few floor cells to be used. 120 * @param width dungeon width in cells; must be at least 3 because the edges will be walls 121 * @param height dungeon height in cells; must be at least 3 because the edges will be walls 122 * @param rng IRNG to use, such as an RNG, StatefulRNG, or GWTRNG 123 * @return erratically-positioned but generally separated Coord points to pass to a MixedGenerator constructor 124 * @see VanDerCorputQRNG used to get separated positions 125 */ 126 public static List<Coord> cleanPoints(int width, int height, IRNG rng) 127 { 128 width -= 2; 129 height -= 2; 130 //float mx = rng.nextFloat() * 0.2f, my = rng.nextFloat() * 0.2f; 131 int sz = width * height * 3 + 255 >>> 8, 132 seed = rng.next(9); 133 //System.out.println("mx: " + mx + ", my: " + my + ", index: " + index); 134 List<Coord> list = new ArrayList<>(sz); 135 for (int i = 0; i < sz; i++) { 136 list.add(VanDerCorputQRNG.roberts(width, height, 1, 1, i + seed)); 137 } 138// for (int i = 0; i < blocks; i++) { 139// Coord area = VanDerCorputQRNG.roberts(width * 3 >> 2, height * 3 >> 2, 1, 1, i + seed); 140// for (int j = 0; j < 5; j++) { 141// list.add(VanDerCorputQRNG.roberts(width >> 2, height >> 2, area.x, area.y, index++ + seed2)); 142// } 143// } 144 return list; 145 } 146 147 /** 148 * This prepares a map generator that will generate a map with the given width and height, using the given RNG. 149 * This version of the constructor uses a sub-random point sequence to generate the points it will draw caves and 150 * corridors between, helping to ensure a minimum distance between points, but it does not ensure that paths between 151 * points will avoid overlapping with rooms or other paths. You call the different carver-adding methods to affect 152 * what the dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to 153 * only caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 154 * @param width the width of the final map in cells 155 * @param height the height of the final map in cells 156 * @param rng an RNG object to use for random choices; this make a lot of random choices. 157 * @see PoissonDisk used to ensure spacing for the points. 158 */ 159 public MixedGenerator(int width, int height, IRNG rng) { 160 this(width, height, rng, cleanPoints(width, height, rng)); 161 } 162 163 /** 164 * This prepares a map generator that will generate a map with the given width and height, using the given RNG. 165 * This version of the constructor uses a List of Coord points from some other source to determine the path to add 166 * rooms or caves to and then connect. You call the different carver-adding methods to affect what the 167 * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only 168 * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 169 * @param width the width of the final map in cells 170 * @param height the height of the final map in cells 171 * @param rng an RNG object to use for random choices; this make a lot of random choices. 172 * @param sequence a List of Coord to connect in order; index 0 is the start, index size() - 1 is the end. 173 * @see SerpentMapGenerator a class that uses this technique 174 */ 175 public MixedGenerator(int width, int height, IRNG rng, List<Coord> sequence) { 176 this.width = width; 177 this.height = height; 178 this.roomWidth = width / 64.0f; 179 this.roomHeight = height / 64.0f; 180 if(width <= 2 || height <= 2) 181 throw new IllegalStateException("width and height must be greater than 2"); 182 this.rng = rng; 183 dungeon = new char[width][height]; 184 environment = new int[width][height]; 185 marked = new boolean[width][height]; 186 walled = new boolean[width][height]; 187 fixedRooms = new boolean[width][height]; 188 Arrays.fill(dungeon[0], '#'); 189 Arrays.fill(environment[0], DungeonUtility.UNTOUCHED); 190 for (int i = 1; i < width; i++) { 191 System.arraycopy(dungeon[0], 0, dungeon[i], 0, height); 192 System.arraycopy(environment[0], 0, environment[i], 0, height); 193 } 194 totalPoints = sequence.size() - 1; 195 points = new IntVLA(totalPoints); 196 for (int i = 0; i < totalPoints; i++) { 197 Coord c1 = sequence.get(i), c2 = sequence.get(i + 1); 198 points.add(((c1.x & 0xff) << 24) | ((c1.y & 0xff) << 16) | ((c2.x & 0xff) << 8) | (c2.y & 0xff)); 199 } 200 carvers = new double[5]; 201 } 202 /** 203 * This prepares a map generator that will generate a map with the given width and height, using the given IRNG. 204 * This version of the constructor uses a Map with Coord keys and Coord array values to determine a 205 * branching path for the dungeon to take; each key will connect once to each of the Coords in its value, and you 206 * usually don't want to connect in both directions. You call the different carver-adding methods to affect what the 207 * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only 208 * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 209 * @param width the width of the final map in cells 210 * @param height the height of the final map in cells 211 * @param rng an IRNG object to use for random choices; this make a lot of random choices. 212 * @param connections a Map of Coord keys to arrays of Coord to connect to next; shouldn't connect both ways 213 * @see SerpentMapGenerator a class that uses this technique 214 */ 215 public MixedGenerator(int width, int height, IRNG rng, Map<Coord, List<Coord>> connections) 216 { 217 this(width, height, rng, connections, 0.8f); 218 } 219 /** 220 * This prepares a map generator that will generate a map with the given width and height, using the given IRNG. 221 * This version of the constructor uses a Map with Coord keys and Coord array values to determine a 222 * branching path for the dungeon to take; each key will connect once to each of the Coords in its value, and you 223 * usually don't want to connect in both directions. You call the different carver-adding methods to affect what the 224 * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only 225 * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 226 * @param width the width of the final map in cells 227 * @param height the height of the final map in cells 228 * @param rng an IRNG object to use for random choices; this make a lot of random choices. 229 * @param connections a Map of Coord keys to arrays of Coord to connect to next; shouldn't connect both ways 230 * @param roomSizeMultiplier a float multiplier that will be applied to each room's width and height 231 * @see SerpentMapGenerator a class that uses this technique 232 */ 233 public MixedGenerator(int width, int height, IRNG rng, Map<Coord, List<Coord>> connections, 234 float roomSizeMultiplier) { 235 this.width = width; 236 this.height = height; 237 roomWidth = (width / 64.0f) * roomSizeMultiplier; 238 roomHeight = (height / 64.0f) * roomSizeMultiplier; 239 if(width <= 2 || height <= 2) 240 throw new IllegalStateException("width and height must be greater than 2"); 241 this.rng = rng; 242 dungeon = new char[width][height]; 243 environment = new int[width][height]; 244 marked = new boolean[width][height]; 245 walled = new boolean[width][height]; 246 fixedRooms = new boolean[width][height]; 247 Arrays.fill(dungeon[0], '#'); 248 Arrays.fill(environment[0], DungeonUtility.UNTOUCHED); 249 for (int i = 1; i < width; i++) { 250 System.arraycopy(dungeon[0], 0, dungeon[i], 0, height); 251 System.arraycopy(environment[0], 0, environment[i], 0, height); 252 } 253 totalPoints = 0; 254 for(List<Coord> vals : connections.values()) 255 { 256 totalPoints += vals.size(); 257 } 258 points = new IntVLA(totalPoints); 259 for (Map.Entry<Coord, List<Coord>> kv : connections.entrySet()) { 260 Coord c1 = kv.getKey(); 261 for (Coord c2 : kv.getValue()) { 262 points.add(((c1.x & 0xff) << 24) | ((c1.y & 0xff) << 16) | ((c2.x & 0xff) << 8) | (c2.y & 0xff)); 263 } 264 } 265 carvers = new double[5]; 266 } 267 268 /** 269 * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves 270 * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make 271 * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically 272 * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10 273 * between the count of putCaveCarvers(), putBoxRoomCarvers(), putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and 274 * putWalledRoundRoomCarvers() is reasonable. 275 * @param count the number of carvers making caves between rooms; only matters in relation to other carvers 276 */ 277 public void putCaveCarvers(int count) 278 { 279 carvers[CAVE] = count; 280 } 281 /** 282 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 283 * with a random size in a box shape at the start and end, and a small room at the corner if there is one. If count 284 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 285 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 286 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 287 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 288 * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable. 289 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 290 * to other carvers 291 */ 292 public void putBoxRoomCarvers(int count) 293 { 294 carvers[BOX] = count; 295 } 296 297 /** 298 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 299 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 300 * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 301 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 302 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 303 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 304 * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable. 305 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 306 * to other carvers 307 */ 308 public void putRoundRoomCarvers(int count) 309 { 310 carvers[ROUND] = count; 311 } 312 /** 313 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 314 * with a random size in a box shape at the start and end, and a small room at the corner if there is one, enforcing 315 * the presence of walls around the rooms even if another room is already there or would be placed there. Corridors 316 * can always pass through enforced walls, but caves will open at most one cell in the wall. If count 317 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 318 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 319 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 320 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 321 * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable. 322 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 323 * to other carvers 324 */ 325 public void putWalledBoxRoomCarvers(int count) 326 { 327 carvers[BOX_WALLED] = count; 328 } 329 330 /** 331 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 332 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 333 * one, enforcing the presence of walls around the rooms even if another room is already there or would be placed 334 * there. Corridors can always pass through enforced walls, but caves will open at most one cell in the wall. If 335 * count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 336 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 337 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 338 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 339 * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable. 340 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 341 * to other carvers 342 */ 343 public void putWalledRoundRoomCarvers(int count) 344 { 345 carvers[ROUND_WALLED] = count; 346 } 347 348 /** 349 * Uses the added carvers (or just makes caves if none were added) to carve from point to point in sequence, if it 350 * was provided by the constructor, or evenly-spaced randomized points if it was not. This will never carve out 351 * cells on the very edge of the map. Uses the numbers of the various kinds of carver that were added relative to 352 * each other to determine how frequently to use a given carver type. 353 * @return a char[][] where '#' is a wall and '.' is a floor or corridor; x first y second 354 */ 355 public char[][] generate() 356 { 357 if(carvers[0] <= 0 && carvers[1] <= 0 && carvers[2] <= 0 && carvers[3] <= 0 && carvers[4] <= 0) 358 carvers[0] = 1; 359 carverTable = new WeightedTable(carvers); 360// CarverType[] carvings = carvers.keySet().toArray(new CarverType[carvers.size()]); 361// int[] carvingsCounters = new int[carvings.length]; 362// int totalLength = 0; 363// for (int i = 0; i < carvings.length; i++) { 364// carvingsCounters[i] = carvers.get(carvings[i]); 365// totalLength += carvingsCounters[i]; 366// } 367// CarverType[] allCarvings = new CarverType[totalLength]; 368// 369// for (int i = 0, c = 0; i < carvings.length; i++) { 370// for (int j = 0; j < carvingsCounters[i]; j++) { 371// allCarvings[c++] = carvings[i]; 372// } 373// } 374// if(allCarvings.length == 0) 375// { 376// allCarvings = new CarverType[]{CarverType.CAVE}; 377// totalLength = 1; 378// } 379// else 380// allCarvings = rng.shuffle(allCarvings, new CarverType[allCarvings.length]); 381 382 for (int p = 0; p < totalPoints; p++) { 383 int pair = points.get(p); 384 Coord start = Coord.get(pair >>> 24 & 0xff, pair >>> 16 & 0xff), 385 end = Coord.get(pair >>> 8 & 0xff, pair & 0xff); 386 int ct = carverTable.random(rng.nextLong()); 387 Direction dir; 388 switch (ct) 389 { 390 case CAVE: 391 markPiercing(end); 392 markEnvironmentCave(end.x, end.y); 393 store(); 394 double weight = 0.75; 395 do { 396 Coord cent = markPlusCave(start); 397 if(cent != null) 398 { 399 markPiercingCave(cent); 400 markPiercingCave(cent.translate(1, 0)); 401 markPiercingCave(cent.translate(-1, 0)); 402 markPiercingCave(cent.translate(0, 1)); 403 markPiercingCave(cent.translate(0, -1)); 404 weight = 0.95; 405 } 406 dir = stepWobbly(start, end, weight); 407 start = start.translate(dir); 408 }while (dir != Direction.NONE); 409 break; 410 case BOX: 411 markRectangle(end, rng.between(1, 5), rng.between(1, 5)); 412 markRectangle(start, rng.between(1, 4), rng.between(1, 4)); 413 store(); 414 dir = Direction.getDirection(end.x - start.x, end.y - start.y); 415 if(dir.isDiagonal()) 416 dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0) 417 : Direction.getCardinalDirection(0, dir.deltaY); 418 while (start.x != end.x && start.y != end.y) 419 { 420 markPiercing(start); 421 markEnvironmentCorridor(start.x, start.y); 422 start = start.translate(dir); 423 } 424 markRectangle(start, 1, 1); 425 dir = Direction.getCardinalDirection(end.x - start.x, (end.y - start.y)); 426 while (!(start.x == end.x && start.y == end.y)) 427 { 428 markPiercing(start); 429 markEnvironmentCorridor(start.x, start.y); 430 start = start.translate(dir); 431 } 432 break; 433 case BOX_WALLED: 434 markRectangleWalled(end, rng.between(1, 5), rng.between(1, 5)); 435 markRectangleWalled(start, rng.between(1, 4), rng.between(1, 4)); 436 store(); 437 dir = Direction.getDirection(end.x - start.x, end.y - start.y); 438 if(dir.isDiagonal()) 439 dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0) 440 : Direction.getCardinalDirection(0, dir.deltaY); 441 while (start.x != end.x && start.y != end.y) 442 { 443 markPiercing(start); 444 markEnvironmentCorridor(start.x, start.y); 445 start = start.translate(dir); 446 } 447 markRectangleWalled(start, 1, 1); 448 dir = Direction.getCardinalDirection(end.x - start.x, (end.y - start.y)); 449 while (!(start.x == end.x && start.y == end.y)) 450 { 451 markPiercing(start); 452 markEnvironmentCorridor(start.x, start.y); 453 start = start.translate(dir); 454 } 455 break; 456 case ROUND: 457 markCircle(end, rng.between(2, 6)); 458 markCircle(start, rng.between(2, 6)); 459 store(); 460 dir = Direction.getDirection(end.x - start.x, end.y - start.y); 461 if(dir.isDiagonal()) 462 dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0) 463 : Direction.getCardinalDirection(0, dir.deltaY); 464 while (start.x != end.x && start.y != end.y) 465 { 466 markPiercing(start); 467 markEnvironmentCorridor(start.x, start.y); 468 start = start.translate(dir); 469 } 470 markCircle(start, 2); 471 dir = Direction.getCardinalDirection(end.x - start.x, (end.y - start.y)); 472 while (!(start.x == end.x && start.y == end.y)) 473 { 474 markPiercing(start); 475 markEnvironmentCorridor(start.x, start.y); 476 start = start.translate(dir); 477 } 478 break; 479 case ROUND_WALLED: 480 markCircleWalled(end, rng.between(2, 6)); 481 markCircleWalled(start, rng.between(2, 6)); 482 store(); 483 dir = Direction.getDirection(end.x - start.x, end.y - start.y); 484 if(dir.isDiagonal()) 485 dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0) 486 : Direction.getCardinalDirection(0, dir.deltaY); 487 while (start.x != end.x && start.y != end.y) 488 { 489 markPiercing(start); 490 markEnvironmentCorridor(start.x, start.y); 491 start = start.translate(dir); 492 } 493 markCircleWalled(start, 2); 494 dir = Direction.getCardinalDirection(end.x - start.x, (end.y - start.y)); 495 while (!(start.x == end.x && start.y == end.y)) 496 { 497 markPiercing(start); 498 markEnvironmentCorridor(start.x, start.y); 499 start = start.translate(dir); 500 } 501 break; 502 } 503 store(); 504 } 505 for (int x = 0; x < width; x++) { 506 for (int y = 0; y < height; y++) { 507 if(fixedRooms[x][y]) 508 markPiercingCave(Coord.get(x, y)); // this is only used by LanesMapGenerator, where caves make sense 509 } 510 } 511 store(); 512 markEnvironmentWalls(); 513 generated = true; 514 return dungeon; 515 } 516 517 public char[][] getDungeon() { 518 return dungeon; 519 } 520 521 public int[][] getEnvironment() 522 { 523 return environment; 524 } 525 526 public boolean hasGenerated() 527 { 528 return generated; 529 } 530 531 public boolean[][] getFixedRooms() { 532 return fixedRooms; 533 } 534 535 public void setFixedRooms(boolean[][] fixedRooms) { 536 this.fixedRooms = fixedRooms; 537 } 538 539 /** 540 * Internal use. Takes cells that have been previously marked and permanently stores them as floors in the dungeon. 541 */ 542 protected void store() 543 { 544 for (int i = 0; i < width; i++) { 545 for (int j = 0; j < height; j++) { 546 if(marked[i][j]) 547 { 548 dungeon[i][j] = '.'; 549 marked[i][j] = false; 550 } 551 } 552 } 553 } 554 555 /** 556 * Internal use. Finds all floor cells by environment and marks untouched adjacent (8-way) cells as walls, using the 557 * appropriate type for the nearby floor. 558 */ 559 protected void markEnvironmentWalls() 560 { 561 for (int i = 0; i < width; i++) { 562 for (int j = 0; j < height; j++) { 563 if(environment[i][j] == DungeonUtility.UNTOUCHED) 564 { 565 boolean allWalls = true; 566 //lowest precedence, also checks for any floors 567 for (int x = Math.max(0, i - 1); x <= Math.min(width - 1, i + 1); x++) { 568 569 for (int y = Math.max(0, j - 1); y <= Math.min(height - 1, j + 1); y++) { 570 if (environment[x][y] == DungeonUtility.CORRIDOR_FLOOR) { 571 markEnvironment(i, j, DungeonUtility.CORRIDOR_WALL); 572 } 573 if(dungeon[x][y] == '.') 574 allWalls = false; 575 } 576 } 577 //if there are no floors we don't need to check twice again. 578 if(allWalls) 579 continue; 580 //more precedence 581 for (int x = Math.max(0, i - 1); x <= Math.min(width - 1, i + 1); x++) { 582 583 for (int y = Math.max(0, j - 1); y <= Math.min(height - 1, j + 1); y++) { 584 if (environment[x][y] == DungeonUtility.CAVE_FLOOR) { 585 markEnvironment(i, j, DungeonUtility.CAVE_WALL); 586 } 587 } 588 } 589 //highest precedence 590 for (int x = Math.max(0, i - 1); x <= Math.min(width - 1, i + 1); x++) { 591 592 for (int y = Math.max(0, j - 1); y <= Math.min(height - 1, j + 1); y++) { 593 if (environment[x][y] == DungeonUtility.ROOM_FLOOR) { 594 markEnvironment(i, j, DungeonUtility.ROOM_WALL); 595 } 596 } 597 } 598 599 } 600 } 601 } 602 } 603 604 /** 605 * Internal use. Marks a point to be made into floor. 606 * @param x x position to mark 607 * @param y y position to mark 608 * @return false if everything is normal, true if and only if this failed to mark because the position is walled 609 */ 610 protected boolean mark(int x, int y) { 611 if (x > 0 && x < width - 1 && y > 0 && y < height - 1 && !walled[x][y]) { 612 marked[x][y] = true; 613 return false; 614 } 615 else return x > 0 && x < width - 1 && y > 0 && y < height - 1 && walled[x][y]; 616 } 617 618 /** 619 * Internal use. Marks a point to be made into floor. 620 * @param x x position to mark 621 * @param y y position to mark 622 */ 623 protected void markPiercing(int x, int y) { 624 if (x > 0 && x < width - 1 && y > 0 && y < height - 1) { 625 marked[x][y] = true; 626 } 627 } 628 /** 629 * Internal use. Marks a point's environment type as the appropriate kind of environment. 630 * @param x x position to mark 631 * @param y y position to mark 632 * @param kind an int that should be one of the constants in MixedGenerator for environment types. 633 */ 634 protected void markEnvironment(int x, int y, int kind) { 635 environment[x][y] = kind; 636 } 637 638 /** 639 * Internal use. Marks a point's environment type as a corridor floor. 640 * @param x x position to mark 641 * @param y y position to mark 642 */ 643 protected void markEnvironmentCorridor(int x, int y) { 644 if (x > 0 && x < width - 1 && y > 0 && y < height - 1 && environment[x][y] != DungeonUtility.ROOM_FLOOR && environment[x][y] != DungeonUtility.CAVE_FLOOR) { 645 markEnvironment(x, y, DungeonUtility.CORRIDOR_FLOOR); 646 } 647 } 648 649 /** 650 * Internal use. Marks a point's environment type as a room floor. 651 * @param x x position to mark 652 * @param y y position to mark 653 */ 654 protected void markEnvironmentRoom(int x, int y) { 655 if (x > 0 && x < width - 1 && y > 0 && y < height - 1) { 656 markEnvironment(x, y, DungeonUtility.ROOM_FLOOR); 657 } 658 } 659 660 /** 661 * Internal use. Marks a point's environment type as a cave floor. 662 * @param x x position to mark 663 * @param y y position to mark 664 */ 665 protected void markEnvironmentCave(int x, int y) { 666 if (x > 0 && x < width - 1 && y > 0 && y < height - 1 && environment[x][y] != DungeonUtility.ROOM_FLOOR) { 667 markEnvironment(x, y, DungeonUtility.CAVE_FLOOR); 668 } 669 } 670 /** 671 * Internal use. Marks a point to be considered a hard wall. 672 * @param x x position to mark 673 * @param y y position to mark 674 */ 675 protected void wallOff(int x, int y) { 676 if (x > 0 && x < width - 1 && y > 0 && y < height - 1) { 677 walled[x][y] = true; 678 } 679 } 680 681 /** 682 * Internal use. Marks a point to be made into floor. 683 * @param pos position to mark 684 * @return false if everything is normal, true if and only if this failed to mark because the position is walled 685 */ 686 protected boolean mark(Coord pos) 687 { 688 return mark(pos.x, pos.y); 689 } 690 691 /** 692 * Internal use. Marks a point to be made into floor, piercing walls. 693 * @param pos position to mark 694 */ 695 protected void markPiercing(Coord pos) 696 { 697 markPiercing(pos.x, pos.y); 698 } 699 /** 700 * Internal use. Marks a point to be made into floor, piercing walls, and also marks the point as a cave floor. 701 * @param pos position to mark 702 */ 703 protected void markPiercingCave(Coord pos) 704 { 705 markPiercing(pos.x, pos.y); 706 markEnvironmentCave(pos.x, pos.y); 707 } 708 /** 709 * Internal use. Marks a point to be made into floor, piercing walls, and also marks the point as a room floor. 710 * @param x x coordinate of position to mark 711 * @param y y coordinate of position to mark 712 */ 713 protected void markPiercingRoom(int x, int y) 714 { 715 markPiercing(x, y); 716 markEnvironmentRoom(x, y); 717 } 718 719 /** 720 * Internal use. Marks a point and the four cells orthogonally adjacent to it. 721 * @param pos center position to mark 722 * @return null if the center of the plus shape wasn't blocked by wall, otherwise the Coord of the center 723 */ 724 private Coord markPlus(Coord pos) { 725 Coord block = null; 726 if (mark(pos.x, pos.y)) 727 block = pos; 728 mark(pos.x + 1, pos.y); 729 mark(pos.x - 1, pos.y); 730 mark(pos.x, pos.y + 1); 731 mark(pos.x, pos.y - 1); 732 return block; 733 } 734 735 /** 736 * Internal use. Marks a point and the four cells orthogonally adjacent to it, and also marks any cells that weren't 737 * blocked as cave floors. 738 * @param pos center position to mark 739 * @return null if the center of the plus shape wasn't blocked by wall, otherwise the Coord of the center 740 */ 741 private Coord markPlusCave(Coord pos) { 742 Coord block = null; 743 if (mark(pos.x, pos.y)) 744 block = pos; 745 else 746 markEnvironmentCave(pos.x, pos.y); 747 if(!mark(pos.x + 1, pos.y)) 748 markEnvironmentCave(pos.x + 1, pos.y); 749 if(!mark(pos.x - 1, pos.y)) 750 markEnvironmentCave(pos.x - 1, pos.y); 751 if(!mark(pos.x, pos.y + 1)) 752 markEnvironmentCave(pos.x, pos.y + 1); 753 if(!mark(pos.x, pos.y - 1)) 754 markEnvironmentCave(pos.x, pos.y - 1); 755 return block; 756 } 757 /** 758 * Internal use. Marks a rectangle of points centered on pos, extending halfWidth in both x directions and 759 * halfHeight in both vertical directions. Marks all cells in the rectangle as room floors. 760 * @param pos center position to mark 761 * @param halfWidth the distance from the center to extend horizontally 762 * @param halfHeight the distance from the center to extend vertically 763 * @return null if no points in the rectangle were blocked by walls, otherwise a Coord blocked by a wall 764 */ 765 private Coord markRectangle(Coord pos, int halfWidth, int halfHeight) 766 { 767 halfWidth = Math.max(1, Math.round(halfWidth * roomWidth)); 768 halfHeight = Math.max(1, Math.round(halfHeight * roomHeight)); 769 Coord block = null; 770 for (int i = pos.x - halfWidth; i <= pos.x + halfWidth; i++) { 771 for (int j = pos.y - halfHeight; j <= pos.y + halfHeight; j++) { 772 if(mark(i, j)) 773 block = Coord.get(i, j); 774 else 775 markEnvironmentRoom(i, j); 776 } 777 } 778 return block; 779 } 780 /** 781 * Internal use. Marks a rectangle of points centered on pos, extending halfWidth in both x directions and 782 * halfHeight in both vertical directions. Also considers the area just beyond each wall, but not corners, to be 783 * a blocking wall that can only be passed by corridors and small cave openings. Marks all cells in the rectangle as 784 * room floors. 785 * @param pos center position to mark 786 * @param halfWidth the distance from the center to extend horizontally 787 * @param halfHeight the distance from the center to extend vertically 788 * @return null if no points in the rectangle were blocked by walls, otherwise a Coord blocked by a wall 789 */ 790 private Coord markRectangleWalled(Coord pos, int halfWidth, int halfHeight) 791 { 792 halfWidth = Math.max(1, Math.round(halfWidth * roomWidth)); 793 halfHeight = Math.max(1, Math.round(halfHeight * roomHeight)); 794 Coord block = null; 795 for (int i = pos.x - halfWidth; i <= pos.x + halfWidth; i++) { 796 for (int j = pos.y - halfHeight; j <= pos.y + halfHeight; j++) { 797 markPiercing(i, j); 798 markEnvironmentRoom(i, j); 799 } 800 } 801 for (int i = Math.max(0, pos.x - halfWidth - 1); i <= Math.min(width - 1, pos.x + halfWidth + 1); i++) { 802 for (int j = Math.max(0, pos.y - halfHeight - 1); j <= Math.min(height - 1, pos.y + halfHeight + 1); j++) 803 { 804 wallOff(i, j); 805 } 806 } 807 return null; 808 } 809 810 /** 811 * Internal use. Marks a circle of points centered on pos, extending out to radius in Euclidean measurement. Marks 812 * all cells in the circle as room floors. 813 * @param pos center position to mark 814 * @param radius radius to extend in all directions from center 815 * @return null if no points in the circle were blocked by walls, otherwise a Coord blocked by a wall 816 */ 817 private Coord markCircle(Coord pos, int radius) 818 { 819 Coord block = null; 820 int high; 821 radius = Math.max(1, Math.round(radius * Math.min(roomWidth, roomHeight))); 822 for (int dx = -radius; dx <= radius; ++dx) 823 { 824 high = (int)Math.floor(Math.sqrt(radius * radius - dx * dx)); 825 for (int dy = -high; dy <= high; ++dy) 826 { 827 if(mark(pos.x + dx, pos.y + dy)) 828 block = pos.translate(dx, dy); 829 else 830 markEnvironmentRoom(pos.x + dx, pos.y + dy); 831 } 832 } 833 return block; 834 } 835 /** 836 * Internal use. Marks a circle of points centered on pos, extending out to radius in Euclidean measurement. 837 * Also considers the area just beyond each wall, but not corners, to be a blocking wall that can only be passed by 838 * corridors and small cave openings. Marks all cells in the circle as room floors. 839 * @param pos center position to mark 840 * @param radius radius to extend in all directions from center 841 * @return null if no points in the circle were blocked by walls, otherwise a Coord blocked by a wall 842 */ 843 private Coord markCircleWalled(Coord pos, int radius) 844 { 845 Coord block = null; 846 int high; 847 radius = Math.max(1, Math.round(radius * Math.min(roomWidth, roomHeight))); 848 for (int dx = -radius; dx <= radius; ++dx) 849 { 850 high = (int)Math.floor(Math.sqrt(radius * radius - dx * dx)); 851 for (int dy = -high; dy <= high; ++dy) 852 { 853 markPiercing(pos.x + dx, pos.y + dy); 854 markEnvironmentRoom(pos.x + dx, pos.y + dy); 855 } 856 } 857 for (int dx = -radius; dx <= radius; ++dx) 858 { 859 high = (int)Math.floor(Math.sqrt(radius * radius - dx * dx)); 860 int dx2 = Math.max(1, Math.min(pos.x + dx, width - 2)); 861 for (int dy = -high; dy <= high; ++dy) 862 { 863 int dy2 = Math.max(1, Math.min(pos.y + dy, height - 2)); 864 865 wallOff(dx2, dy2-1); 866 wallOff(dx2+1, dy2-1); 867 wallOff(dx2-1, dy2-1); 868 wallOff(dx2, dy2); 869 wallOff(dx2+1, dy2); 870 wallOff(dx2-1, dy2); 871 wallOff(dx2, dy2+1); 872 wallOff(dx2+1, dy2+1); 873 wallOff(dx2-1, dy2+1); 874 875 } 876 } 877 return null; 878 } 879 880 /** 881 * Internal use. Drunkard's walk algorithm, single step. Based on Michael Patraw's C code, used for cave carving. 882 * http://mpatraw.github.io/libdrunkard/ 883 * @param current the current point 884 * @param target the point to wobble towards 885 * @param weight between 0.5 and 1.0, usually. 0.6 makes very random caves, 0.9 is almost a straight line. 886 * @return a Direction, either UP, DOWN, LEFT, or RIGHT if we should move, or NONE if we have reached our target 887 */ 888 private Direction stepWobbly(Coord current, Coord target, double weight) 889 { 890 int dx = target.x - current.x; 891 int dy = target.y - current.y; 892 893 if (dx > 1) dx = 1; 894 if (dx < -1) dx = -1; 895 if (dy > 1) dy = 1; 896 if (dy < -1) dy = -1; 897 898 double r = rng.nextDouble(); 899 Direction dir; 900 if (dx == 0 && dy == 0) 901 { 902 return Direction.NONE; 903 } 904 else if (dx == 0 || dy == 0) 905 { 906 int dx2 = (dx == 0) ? dx : dy, dy2 = (dx == 0) ? dy : dx; 907 if (r >= (weight * 0.5)) 908 { 909 r -= weight * 0.5; 910 if (r < weight * (1.0 / 6) + (1 - weight) * (1.0 / 3)) 911 { 912 dx2 = -1; 913 dy2 = 0; 914 } 915 else if (r < weight * (2.0 / 6) + (1 - weight) * (2.0 / 3)) 916 { 917 dx2 = 1; 918 dy2 = 0; 919 } 920 else 921 { 922 dx2 = 0; 923 dy2 *= -1; 924 } 925 } 926 dir = Direction.getCardinalDirection(dx2, dy2); 927 928 } 929 else 930 { 931 if (r < weight * 0.5) 932 { 933 dy = 0; 934 } 935 else if (r < weight) 936 { 937 dx = 0; 938 } 939 else if (r < weight + (1 - weight) * 0.5) 940 { 941 dx *= -1; 942 dy = 0; 943 } 944 else 945 { 946 dx = 0; 947 dy *= -1; 948 } 949 dir = Direction.getCardinalDirection(dx, dy); 950 } 951 if(current.x + dir.deltaX <= 0 || current.x + dir.deltaX >= width - 1) { 952 if (current.y < target.y) dir = Direction.DOWN; 953 else if (current.y > target.y) dir = Direction.UP; 954 } 955 else if(current.y + dir.deltaY <= 0 || current.y + dir.deltaY >= height - 1) { 956 if (current.x < target.x) dir = Direction.RIGHT; 957 else if (current.x > target.x) dir = Direction.LEFT; 958 } 959 return dir; 960 } 961 962}