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