001package squidpony.squidgrid.mapping; 002 003import squidpony.squidai.DijkstraMap; 004import squidpony.squidgrid.Measurement; 005import squidpony.squidgrid.mapping.styled.DungeonBoneGen; 006import squidpony.squidgrid.mapping.styled.TilesetType; 007import squidpony.squidmath.*; 008 009import java.util.ArrayList; 010import java.util.EnumMap; 011 012/** 013 * The primary way to create a more-complete dungeon, layering different effects and modifications on top of 014 * a DungeonBoneGen's dungeon or another dungeon without such effects. Also ensures only connected regions of the map 015 * are used by filling unreachable areas with walls, and can find far-apart staircase positions if generate() is used or 016 * can keep existing staircases in a map if generateRespectingStairs() is used. 017 * <br> 018 * The main technique for using this is simple: Construct a DungeonGenerator, usually with the desired width and height, 019 * then call any feature adding methods that you want in the dungeon, like addWater(), addTraps, addGrass(), or 020 * addDoors(). Some of these take different parameters, like addDoors() which need to know if it should check openings 021 * that are two cells wide to add a door and a wall to, or whether it should only add doors to single-cell openings. 022 * Then call generate() to get a char[][] with the desired dungeon map, using a fixed repertoire of chars to represent 023 * the different features. After calling generate(), you can safely get the values from the stairsUp and stairsDown 024 * fields, which are Coords that should be a long distance from each other but connected in the dungeon. You may want 025 * to change those to staircase characters, but there's no requirement to do anything with them. It's recommended that 026 * you keep the resulting char[][] maps in some collection that can be saved, since DungeonGenerator only stores a 027 * temporary copy of the most recently-generated map. The DungeonUtility field of this class, utility, is a convenient 028 * way of accessing the non-static methods in that class, such as randomFloor(), without needing to create another 029 * DungeonUtility (this class creates one, so you don't have to). 030 * <br> 031 * Previews for the kinds of dungeon this generates, given a certain argument to generate(): 032 * <ul> 033 * <li>Using TilesetType.DEFAULT_DUNGEON (text, click "Raw", may need to zoom out): https://gist.github.com/tommyettinger/a3bd413b903f2e103541</li> 034 * <li>Using TilesetType.DEFAULT_DUNGEON (graphical, scroll down and to the right): http://tommyettinger.github.io/home/PixVoxel/dungeon/dungeon.html</li> 035 * <li>Using SerpentMapGenerator.generate() (text, click "Raw", may need to zoom out): https://gist.github.com/tommyettinger/93b47048fc8a209a9712</li> 036 * </ul> 037 * <br> 038 * As of March 6, 2016, the algorithm this uses to place water and grass was swapped for a more precise version. You no 039 * longer need to give this 150% in addWater or addGrass to effectively produce 100% water or grass, and this should be 040 * no more than 1.1% different from the percentage you request for any effects. If you need to reproduce dungeons with 041 * the same seed and get the same (imprecise) results as before this change, it's probably not possible unless you save 042 * the previously-generated char[][] dungeons, since several other things may have changed as well. 043 * @see squidpony.squidgrid.mapping.DungeonUtility this class exposes a DungeonUtility member; DungeonUtility also has many useful static methods 044 * 045 * @author Eben Howard - http://squidpony.com - howard@squidpony.com 046 * @author Tommy Ettinger - https://github.com/tommyettinger 047 */ 048public class DungeonGenerator implements IDungeonGenerator { 049 /** 050 * The effects that can be applied to this dungeon. More may be added in future releases. 051 */ 052 public enum FillEffect 053 { 054 /** 055 * Water, represented by '~' 056 */ 057 WATER, 058 /** 059 * Doors, represented by '+' for east-to-west connections or '/' for north-to-south ones. 060 */ 061 DOORS, 062 /** 063 * Traps, represented by '^' 064 */ 065 TRAPS, 066 /** 067 * Grass, represented by '"' 068 */ 069 GRASS, 070 /** 071 * Boulders strewn about open areas, represented by '#' and treated as walls 072 */ 073 BOULDERS, 074 /** 075 * Islands of ground, '.', surrounded by shallow water, ',', to place in water at evenly spaced points 076 */ 077 ISLANDS 078 } 079 080 /** 081 * The effects that will be applied when generate is called. Strongly prefer using addWater, addDoors, addTraps, 082 * and addGrass. 083 */ 084 public EnumMap<FillEffect, Integer> fx; 085 protected DungeonBoneGen gen; 086 public DungeonUtility utility; 087 protected int height, width; 088 public Coord stairsUp, stairsDown; 089 public IStatefulRNG rng; 090 protected long rebuildSeed; 091 protected boolean seedFixed; 092 093 protected char[][] dungeon; 094 095 /** 096 * Get the most recently generated char[][] dungeon out of this class. The 097 * dungeon may be null if generate() or setDungeon() have not been called. 098 * @return a char[][] dungeon, or null. 099 */ 100 public char[][] getDungeon() { 101 return dungeon; 102 } 103 /** 104 * Get the most recently generated char[][] dungeon out of this class without any chars other than '#' or '.', for 105 * walls and floors respectively. The dungeon may be null if generate() or setDungeon() have not been called. 106 * @return a char[][] dungeon with only '#' for walls and '.' for floors, or null. 107 */ 108 public char[][] getBareDungeon() { 109 return DungeonUtility.simplifyDungeon(dungeon); 110 } 111 112 /** 113 * Change the underlying char[][]; only affects the toString method, and of course getDungeon. 114 * @param dungeon a char[][], probably produced by an earlier call to this class and then modified. 115 */ 116 public void setDungeon(char[][] dungeon) { 117 this.dungeon = dungeon; 118 if(dungeon == null) 119 { 120 width = 0; 121 height = 0; 122 return; 123 } 124 width = dungeon.length; 125 if(width > 0) 126 height = dungeon[0].length; 127 } 128 129 /** 130 * Height of the dungeon in cells. 131 * @return Height of the dungeon in cells. 132 */ 133 public int getHeight() { 134 return height; 135 } 136 137 /** 138 * Width of the dungeon in cells. 139 * @return Width of the dungeon in cells. 140 */ 141 public int getWidth() { 142 return width; 143 } 144 145 146 /** 147 * Make a DungeonGenerator with a GWTRNG using a random seed, height 40, and width 40. 148 */ 149 public DungeonGenerator() 150 { 151 rng = new GWTRNG(); 152 gen = new DungeonBoneGen(rng); 153 utility = new DungeonUtility(rng); 154 rebuildSeed = rng.getState(); 155 height = 40; 156 width = 40; 157 fx = new EnumMap<>(FillEffect.class); 158 } 159 160 /** 161 * Make a DungeonGenerator with the given height and width; a GWTRNG will be used for generating a dungeon and 162 * adding features using a random seed. If width or height is greater than 256, then this will 163 * expand the Coord pool from its 256x256 default so it stores a reference to each Coord that might be used in the 164 * creation of the dungeon (if width and height are 300 and 300, the Coord pool will be 300x300; if width and height 165 * are 500 and 100, the Coord pool will be 500x256 because it won't shrink below the default size of 256x256). 166 * @param width The width of the dungeon in cells 167 * @param height The height of the dungeon in cells 168 */ 169 public DungeonGenerator(int width, int height) 170 { 171 this(width, height, new GWTRNG()); 172 } 173 174 /** 175 * Make a DungeonGenerator with the given height, width, and RNG. Use this if you want to seed the RNG. If width or 176 * height is greater than 256, then this will expand the Coord pool from its 256x256 default so it stores a 177 * reference to each Coord that might be used in the creation of the dungeon (if width and height are 300 and 300, 178 * the Coord pool will be 300x300; if width and height are 500 and 100, the Coord pool will be 500x256 because it 179 * won't shrink below the default size of 256x256). 180 * @param width The width of the dungeon in cells 181 * @param height The height of the dungeon in cells 182 * @param rng The RNG to use for all purposes in this class; if it is a StatefulRNG, then it will be used as-is, 183 * but if it is not a StatefulRNG, a new StatefulRNG will be used, randomly seeded by this parameter 184 */ 185 public DungeonGenerator(int width, int height, IRNG rng) 186 { 187 Coord.expandPoolTo(width, height); 188 this.rng = (rng instanceof IStatefulRNG) ? (IStatefulRNG) rng : new GWTRNG(rng.nextLong()); 189 gen = new DungeonBoneGen(this.rng); 190 utility = new DungeonUtility(this.rng); 191 rebuildSeed = this.rng.getState(); 192 this.height = height; 193 this.width = width; 194 fx = new EnumMap<>(FillEffect.class); 195 } 196 197 /** 198 * Copies all fields from copying and makes a new DungeonGenerator. 199 * @param copying the DungeonGenerator to copy 200 */ 201 public DungeonGenerator(DungeonGenerator copying) 202 { 203 rng = new GWTRNG(copying.rng.getState()); 204 gen = new DungeonBoneGen(rng); 205 utility = new DungeonUtility(rng); 206 rebuildSeed = rng.getState(); 207 height = copying.height; 208 width = copying.width; 209 Coord.expandPoolTo(width, height); 210 fx = new EnumMap<>(copying.fx); 211 dungeon = copying.dungeon; 212 } 213 214 /** 215 * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be 216 * clustered into a random number of pools, with more appearing if needed to fill the percentage. 217 * Each pool will have randomized volume that should fill or get very close to filling the requested 218 * percentage, unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater 219 * called, the latest call will take precedence. No islands will be placed with this variant, but the edge of the 220 * water will be shallow, represented by ','. 221 * @param percentage the percentage of floor cells to fill with water 222 * @return this DungeonGenerator; can be chained 223 */ 224 public DungeonGenerator addWater(int percentage) 225 { 226 if(percentage < 0) percentage = 0; 227 if(percentage > 100) percentage = 100; 228 fx.remove(FillEffect.WATER); 229 fx.put(FillEffect.WATER, percentage); 230 return this; 231 } 232 /** 233 * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be 234 * clustered into a random number of pools, with more appearing if needed to fill the percentage. Each pool will 235 * have randomized volume that should fill or get very close to filling the requested percentage, 236 * unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater called, the 237 * latest call will take precedence. If islandSpacing is greater than 1, then this will place islands of floor, '.', 238 * surrounded by shallow water, ',', at about the specified distance with Euclidean measurement. 239 * @param percentage the percentage of floor cells to fill with water 240 * @param islandSpacing if greater than 1, islands will be placed randomly this many cells apart. 241 * @return this DungeonGenerator; can be chained 242 */ 243 public DungeonGenerator addWater(int percentage, int islandSpacing) 244 { 245 if(percentage < 0) percentage = 0; 246 if(percentage > 100) percentage = 100; 247 fx.remove(FillEffect.WATER); 248 fx.put(FillEffect.WATER, percentage); 249 fx.remove(FillEffect.ISLANDS); 250 if(islandSpacing > 1) 251 fx.put(FillEffect.ISLANDS, islandSpacing); 252 return this; 253 } 254 255 /** 256 * Turns the majority of the given percentage of floor cells into grass cells, represented by '"'. Grass will be 257 * clustered into a random number of patches, with more appearing if needed to fill the percentage. Each area will 258 * have randomized volume that should fill or get very close to filling the requested percentage, 259 * unless the patches encounter too much tight space. If this DungeonGenerator previously had addGrass called, the 260 * latest call will take precedence. 261 * @param percentage the percentage of floor cells to fill with grass 262 * @return this DungeonGenerator; can be chained 263 */ 264 public DungeonGenerator addGrass(int percentage) 265 { 266 if(percentage < 0) percentage = 0; 267 if(percentage > 100) percentage = 100; 268 fx.remove(FillEffect.GRASS); 269 fx.put(FillEffect.GRASS, percentage); 270 return this; 271 } 272 /** 273 * Turns the given percentage of floor cells not already adjacent to walls into wall cells, represented by '#'. 274 * If this DungeonGenerator previously had addBoulders called, the latest call will take precedence. 275 * @param percentage the percentage of floor cells not adjacent to walls to fill with boulders. 276 * @return this DungeonGenerator; can be chained 277 */ 278 public DungeonGenerator addBoulders(int percentage) 279 { 280 if(percentage < 0) percentage = 0; 281 if(percentage > 100) percentage = 100; 282 fx.remove(FillEffect.BOULDERS); 283 fx.put(FillEffect.BOULDERS, percentage); 284 return this; 285 } 286 /** 287 * Turns the given percentage of viable doorways into doors, represented by '+' for doors that allow travel along 288 * the x-axis and '/' for doors that allow travel along the y-axis. If doubleDoors is true, 289 * 2-cell-wide openings will be considered viable doorways and will fill one cell with a wall, the other a door. 290 * If this DungeonGenerator previously had addDoors called, the latest call will take precedence. 291 * @param percentage the percentage of valid openings to corridors to fill with doors; should be between 10 and 292 * 20 if you want doors to appear more than a few times, but not fill every possible opening. 293 * @param doubleDoors true if you want two-cell-wide openings to receive a door and a wall; false if only 294 * one-cell-wide openings should receive doors. Usually, this should be true. 295 * @return this DungeonGenerator; can be chained 296 */ 297 public DungeonGenerator addDoors(int percentage, boolean doubleDoors) 298 { 299 if(percentage < 0) percentage = 0; 300 if(percentage > 100) percentage = 100; 301 if(doubleDoors) percentage *= -1; 302 fx.remove(FillEffect.DOORS); 303 fx.put(FillEffect.DOORS, percentage); 304 return this; 305 } 306 307 /** 308 * Turns the given percentage of open area floor cells into trap cells, represented by '^'. Corridors that have no 309 * possible way to move around a trap will not receive traps, ever. If this DungeonGenerator previously had 310 * addTraps called, the latest call will take precedence. 311 * @param percentage the percentage of valid cells to fill with traps; should be no higher than 5 unless 312 * the dungeon floor is meant to be a kill screen or minefield. 313 * @return this DungeonGenerator; can be chained 314 */ 315 public DungeonGenerator addTraps(int percentage) 316 { 317 if(percentage < 0) percentage = 0; 318 if(percentage > 100) percentage = 100; 319 fx.remove(FillEffect.TRAPS); 320 fx.put(FillEffect.TRAPS, percentage); 321 return this; 322 } 323 324 /** 325 * Removes any door, water, or trap insertion effects that this DungeonGenerator would put in future dungeons. 326 * @return this DungeonGenerator, with all effects removed. Can be chained. 327 */ 328 public DungeonGenerator clearEffects() 329 { 330 fx.clear(); 331 return this; 332 } 333 334 protected OrderedSet<Coord> removeAdjacent(OrderedSet<Coord> coll, Coord pt) 335 { 336 for(Coord temp : new Coord[]{Coord.get(pt.x + 1, pt.y), Coord.get(pt.x - 1, pt.y), 337 Coord.get(pt.x, pt.y + 1), Coord.get(pt.x, pt.y - 1)}) 338 { 339 if(coll.contains(temp) && !(temp.x == pt.x && temp.y == pt.y)) 340 coll.remove(temp); 341 } 342 343 return coll; 344 } 345 protected OrderedSet<Coord> removeAdjacent(OrderedSet<Coord> coll, Coord pt1, Coord pt2) 346 { 347 348 for(Coord temp : new Coord[]{Coord.get(pt1.x + 1, pt1.y), Coord.get(pt1.x - 1, pt1.y), 349 Coord.get(pt1.x, pt1.y + 1), Coord.get(pt1.x, pt1.y - 1), 350 Coord.get(pt2.x + 1, pt2.y), Coord.get(pt2.x - 1, pt2.y), 351 Coord.get(pt2.x, pt2.y + 1), Coord.get(pt2.x, pt2.y - 1),}) 352 { 353 if(coll.contains(temp) && !(temp.x == pt1.x && temp.y == pt1.y) && !(temp.x == pt2.x && temp.y == pt2.y)) 354 coll.remove(temp); 355 } 356 357 return coll; 358 } 359 protected OrderedSet<Coord> viableDoorways(boolean doubleDoors, char[][] map) 360 { 361 OrderedSet<Coord> doors = new OrderedSet<>(); 362 OrderedSet<Coord> blocked = new OrderedSet<>(4); 363 DijkstraMap dm = new DijkstraMap(map, Measurement.EUCLIDEAN); 364 for(int x = 1; x < map.length - 1; x++) { 365 for (int y = 1; y < map[x].length - 1; y++) { 366 if(map[x][y] == '#') 367 continue; 368 if (doubleDoors) { 369 if (x >= map.length - 2 || y >= map[x].length - 2) 370 continue; 371 else { 372 if (map[x+1][y] != '#' && 373 map[x + 2][y] == '#' && map[x - 1][y] == '#' 374 && map[x][y + 1] != '#' && map[x][y - 1] != '#' 375 && map[x+1][y + 1] != '#' && map[x+1][y - 1] != '#') { 376 if (map[x + 2][y + 1] != '#' || map[x - 1][y + 1] != '#' || map[x + 2][y - 1] != '#' || map[x - 1][y - 1] != '#') { 377 dm.resetMap(); 378 dm.clearGoals(); 379 dm.setGoal(x, y+1); 380 blocked.clear(); 381 blocked.add(Coord.get(x, y)); 382 blocked.add(Coord.get(x + 1, y)); 383 dm.partialScan(null, 16, blocked); 384 if(dm.gradientMap[x][y-1] < DijkstraMap.FLOOR) 385 continue; 386 doors.add(Coord.get(x, y)); 387 doors.add(Coord.get(x + 1, y)); 388 doors = removeAdjacent(doors, Coord.get(x, y), Coord.get(x + 1, y)); 389 continue; 390 } 391 } else if (map[x][y+1] != '#' && 392 map[x][y + 2] == '#' && map[x][y - 1] == '#' 393 && map[x + 1][y] != '#' && map[x - 1][y] != '#' 394 && map[x + 1][y+1] != '#' && map[x - 1][y+1] != '#') { 395 if (map[x + 1][y + 2] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y + 2] != '#' || map[x - 1][y - 1] != '#') { 396 dm.resetMap(); 397 dm.clearGoals(); 398 dm.setGoal(x+1, y); 399 blocked.clear(); 400 blocked.add(Coord.get(x, y)); 401 blocked.add(Coord.get(x, y+1)); 402 dm.partialScan(null, 16, blocked); 403 if(dm.gradientMap[x-1][y] < DijkstraMap.FLOOR) 404 continue; 405 doors.add(Coord.get(x, y)); 406 doors.add(Coord.get(x, y+1)); 407 doors = removeAdjacent(doors, Coord.get(x, y), Coord.get(x, y + 1)); 408 continue; 409 } 410 } 411 } 412 } 413 if (map[x + 1][y] == '#' && map[x - 1][y] == '#' && map[x][y + 1] != '#' && map[x][y - 1] != '#') { 414 if (map[x + 1][y + 1] != '#' || map[x - 1][y + 1] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y - 1] != '#') { 415 dm.resetMap(); 416 dm.clearGoals(); 417 dm.setGoal(x, y+1); 418 blocked.clear(); 419 blocked.add(Coord.get(x, y)); 420 dm.partialScan(null, 16, blocked); 421 if(dm.gradientMap[x][y-1] < DijkstraMap.FLOOR) 422 continue; 423 doors.add(Coord.get(x, y)); 424 doors = removeAdjacent(doors, Coord.get(x, y)); 425 } 426 } else if (map[x][y + 1] == '#' && map[x][y - 1] == '#' && map[x + 1][y] != '#' && map[x - 1][y] != '#') { 427 if (map[x + 1][y + 1] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y + 1] != '#' || map[x - 1][y - 1] != '#') { 428 dm.resetMap(); 429 dm.clearGoals(); 430 dm.setGoal(x+1, y); 431 blocked.clear(); 432 blocked.add(Coord.get(x, y)); 433 dm.partialScan(null, 16, blocked); 434 if(dm.gradientMap[x-1][y] < DijkstraMap.FLOOR) 435 continue; 436 doors.add(Coord.get(x, y)); 437 doors = removeAdjacent(doors, Coord.get(x, y)); 438 } 439 } 440 441 } 442 } 443 444 return doors; 445 } 446 447 /** 448 * Generate a char[][] dungeon using TilesetType.DEFAULT_DUNGEON; this produces a dungeon appropriate for a level 449 * of ruins or a partially constructed dungeon. This uses '#' for walls, '.' for floors, '~' for deep water, ',' for 450 * shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that provide 451 * vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in 452 * the generated map. 453 * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells. 454 * @return a char[][] dungeon 455 */ 456 public char[][] generate() { 457 return generate(TilesetType.DEFAULT_DUNGEON); 458 } 459 460 /** 461 * Generate a char[][] dungeon given a TilesetType; the comments in that class provide some opinions on what 462 * each TilesetType value could be used for in a game. This uses '#' for walls, '.' for floors, '~' for deep water, 463 * ',' for shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that 464 * provide vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request 465 * these in the generated map. 466 * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells. 467 * @see squidpony.squidgrid.mapping.styled.TilesetType 468 * @param kind a TilesetType enum value, such as TilesetType.DEFAULT_DUNGEON 469 * @return a char[][] dungeon 470 */ 471 public char[][] generate(TilesetType kind) 472 { 473 seedFixed = true; 474 rebuildSeed = rng.getState(); 475 return generate(gen.generate(kind, width, height)); 476 } 477 478 /** 479 * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated. 480 * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method 481 * is meant for adding features like water and doors to existing simple maps. 482 * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors 483 * that provide horizontal passage, and '/' for doors that provide vertical passage. 484 * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map. 485 * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells. 486 * <br> 487 * Special behavior here: If tab characters are present in the 2D char array, they will be replaced with '.' in the 488 * final dungeon, but will also be tried first as valid staircase locations (with a high distance possible to travel 489 * away from the starting staircase). If no tab characters are present this will search for '.' floors to place 490 * stairs on, as normal. This tab-first behavior is useful in conjunction with some methods that establish a good 491 * path in an existing dungeon; an example is {@code DungeonUtility.ensurePath(dungeon, rng, '\t', '#');} then 492 * passing dungeon (which that code modifies) in as baseDungeon to this method. 493 * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors; may be modified in-place 494 * @return a char[][] dungeon 495 */ 496 public char[][] generate(char[][] baseDungeon) 497 { 498 if(!seedFixed) 499 { 500 rebuildSeed = rng.getState(); 501 } 502 seedFixed = false; 503 char[][] map = DungeonUtility.wallWrap(baseDungeon); 504 width = map.length; 505 height = map[0].length; 506 DijkstraMap dijkstra = new DijkstraMap(map); 507 int frustrated = 0; 508 do { 509 dijkstra.clearGoals(); 510 stairsUp = utility.randomMatchingTile(map, '\t'); 511 if(stairsUp == null) { 512 stairsUp = utility.randomFloor(map); 513 if (stairsUp == null) { 514 frustrated++; 515 continue; 516 } 517 } 518 dijkstra.setGoal(stairsUp); 519 dijkstra.scan(null, null); 520 frustrated++; 521 }while (dijkstra.getMappedCount() < width + height && frustrated < 8); 522 if(frustrated >= 8) 523 { 524 return generate(); 525 } 526 double maxDijkstra = 0.0; 527 for (int i = 0; i < width; i++) { 528 for (int j = 0; j < height; j++) { 529 if (dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) { 530 map[i][j] = '#'; 531 } else if (dijkstra.gradientMap[i][j] > maxDijkstra) { 532 maxDijkstra = dijkstra.gradientMap[i][j]; 533 } 534 if (map[i][j] == '\t') { 535 map[i][j] = '.'; 536 } 537 } 538 } 539 stairsDown = new GreasedRegion(dijkstra.gradientMap, maxDijkstra * 0.7, 540 DijkstraMap.FLOOR).singleRandom(rng); 541 542 return innerGenerate(map); 543 } 544 545 /** 546 * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated, and that 547 * already has staircases represented by greater than and less than signs. 548 * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method 549 * is meant for adding features like water and doors to existing simple maps. 550 * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors 551 * that provide horizontal passage, and '/' for doors that provide vertical passage. 552 * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map. 553 * Also sets the fields stairsUp and stairsDown to null, and expects stairs to be already handled. 554 * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors, with stairs already in; 555 * may be modified in-place 556 * @return a char[][] dungeon 557 */ 558 public char[][] generateRespectingStairs(char[][] baseDungeon) { 559 if(!seedFixed) 560 { 561 rebuildSeed = rng.getState(); 562 } 563 seedFixed = false; 564 char[][] map = DungeonUtility.wallWrap(baseDungeon); 565 DijkstraMap dijkstra = new DijkstraMap(map); 566 stairsUp = null; 567 stairsDown = null; 568 569 dijkstra.clearGoals(); 570 ArrayList<Coord> stairs = DungeonUtility.allMatching(map, '<', '>'); 571 for (int j = 0; j < stairs.size(); j++) { 572 dijkstra.setGoal(stairs.get(j)); 573 } 574 dijkstra.scan(null, null); 575 for (int i = 0; i < width; i++) { 576 for (int j = 0; j < height; j++) { 577 if (dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) { 578 map[i][j] = '#'; 579 } 580 } 581 } 582 return innerGenerate(map); 583 } 584 585 586 587 588 private char[][] innerGenerate(char[][] map) 589 { 590 OrderedSet<Coord> doorways; 591 OrderedSet<Coord> hazards = new OrderedSet<>(); 592 Coord temp; 593 boolean doubleDoors = false; 594 int floorCount = DungeonUtility.countCells(map, '.'), 595 doorFill = 0, 596 waterFill = 0, 597 grassFill = 0, 598 trapFill = 0, 599 boulderFill = 0, 600 islandSpacing = 0; 601 if(fx.containsKey(FillEffect.DOORS)) 602 { 603 doorFill = fx.get(FillEffect.DOORS); 604 if(doorFill < 0) 605 { 606 doubleDoors = true; 607 doorFill *= -1; 608 } 609 } 610 if(fx.containsKey(FillEffect.GRASS)) { 611 grassFill = fx.get(FillEffect.GRASS); 612 } 613 if(fx.containsKey(FillEffect.WATER)) { 614 waterFill = fx.get(FillEffect.WATER); 615 } 616 if(fx.containsKey(FillEffect.BOULDERS)) { 617 boulderFill = fx.get(FillEffect.BOULDERS) * floorCount / 100; 618 } 619 if(fx.containsKey(FillEffect.ISLANDS)) { 620 islandSpacing = fx.get(FillEffect.ISLANDS); 621 } 622 if(fx.containsKey(FillEffect.TRAPS)) { 623 trapFill = fx.get(FillEffect.TRAPS); 624 } 625 626 doorways = viableDoorways(doubleDoors, map); 627 628 OrderedSet<Coord> obstacles = new OrderedSet<>(doorways.size() * doorFill / 100); 629 if(doorFill > 0) 630 { 631 int total = doorways.size() * doorFill / 100; 632 633 BigLoop: 634 for(int i = 0; i < total; i++) 635 { 636 Coord entry = rng.getRandomElement(doorways); 637 if(map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '>') 638 continue; 639 if(map[entry.x - 1][entry.y] != '#' && map[entry.x + 1][entry.y] != '#') 640 { 641 map[entry.x][entry.y] = '+'; 642 } 643 else { 644 map[entry.x][entry.y] = '/'; 645 } 646 obstacles.add(entry); 647 Coord[] adj = new Coord[]{Coord.get(entry.x + 1, entry.y), Coord.get(entry.x - 1, entry.y), 648 Coord.get(entry.x, entry.y + 1), Coord.get(entry.x, entry.y - 1)}; 649 for(Coord near : adj) { 650 if (doorways.contains(near)) { 651 map[near.x][near.y] = '#'; 652 obstacles.add(near); 653 doorways.remove(near); 654 i++; 655 doorways.remove(entry); 656 continue BigLoop; 657 } 658 } 659 doorways.remove(entry); 660 } 661 } 662 if (boulderFill > 0.0) { 663 /* 664 short[] floor = pack(map, '.'); 665 short[] viable = retract(floor, 1, width, height, true); 666 ArrayList<Coord> boulders = randomPortion(viable, boulderFill, rng); 667 for (Coord boulder : boulders) { 668 map[boulder.x][boulder.y] = '#'; 669 } 670 */ 671 Coord[] boulders = new GreasedRegion(map, '.').retract8way(1).randomPortion(rng, boulderFill); 672 Coord t; 673 for (int i = 0; i < boulders.length; i++) { 674 t = boulders[i]; 675 map[t.x][t.y] = '#'; 676 } 677 } 678 679 680 if(trapFill > 0) { 681 for (int x = 1; x < map.length - 1; x++) { 682 for (int y = 1; y < map[x].length - 1; y++) { 683 temp = Coord.get(x, y); 684 if (map[x][y] == '.' && !obstacles.contains(temp)) { 685 int ctr = 0; 686 if (map[x + 1][y] != '#') ++ctr; 687 if (map[x - 1][y] != '#') ++ctr; 688 if (map[x][y + 1] != '#') ++ctr; 689 if (map[x][y - 1] != '#') ++ctr; 690 if (map[x + 1][y + 1] != '#') ++ctr; 691 if (map[x - 1][y + 1] != '#') ++ctr; 692 if (map[x + 1][y - 1] != '#') ++ctr; 693 if (map[x - 1][y - 1] != '#') ++ctr; 694 if (ctr >= 5) hazards.add(Coord.get(x, y)); 695 } 696 } 697 } 698 } 699 GreasedRegion floors = new GreasedRegion(map, '.'), working = new GreasedRegion(width, height); 700 floorCount = floors.size(); 701 float waterRate = waterFill / 100.0f, grassRate = grassFill / 100.0f; 702 if(waterRate + grassRate > 1.0f) 703 { 704 waterRate /= (waterFill + grassFill) / 100.0f; 705 grassRate /= (waterFill + grassFill) / 100.0f; 706 } 707 int targetWater = Math.round(floorCount * waterRate), 708 targetGrass = Math.round(floorCount * grassRate), 709 sizeWaterPools = targetWater / rng.between(3, 6), 710 sizeGrassPools = targetGrass / rng.between(2, 5); 711 712 Coord[] scatter; 713 int remainingWater = targetWater, remainingGrass = targetGrass; 714 if(targetWater > 0) { 715 scatter = floors.quasiRandomSeparated(1.0 / 7.0); 716 rng.shuffleInPlace(scatter); 717 GreasedRegion allWater = new GreasedRegion(width, height); 718 for (int i = 0; i < scatter.length; i++) { 719 if (remainingWater > 5) 720 { 721 if(!floors.contains(scatter[i])) 722 continue; 723 working.empty().insert(scatter[i]).spill(floors, rng.between(4, Math.min(remainingWater, sizeWaterPools)), rng); 724 725 floors.andNot(working); 726 remainingWater -= working.size(); 727 allWater.addAll(working); 728 } else 729 break; 730 } 731 732 for (Coord pt : allWater) { 733 hazards.remove(pt); 734 //obstacles.add(pt); 735 if (map[pt.x][pt.y] != '<' && map[pt.x][pt.y] != '>') 736 map[pt.x][pt.y] = '~'; 737 } 738 for (Coord pt : allWater) { 739 if (map[pt.x][pt.y] != '<' && map[pt.x][pt.y] != '>' && 740 (map[pt.x - 1][pt.y] == '.' || map[pt.x + 1][pt.y] == '.' || 741 map[pt.x][pt.y - 1] == '.' || map[pt.x][pt.y + 1] == '.')) 742 map[pt.x][pt.y] = ','; 743 } 744 } 745 if(targetGrass > 0) { 746 scatter = floors.quasiRandomSeparated(1.03/6.7); 747 rng.shuffleInPlace(scatter); 748 for (int i = 0; i < scatter.length; i++) { 749 if (remainingGrass > 5) //remainingGrass >= targetGrass * 0.02 && 750 { 751 working.empty().insert(scatter[i]).spill(floors, rng.between(4, Math.min(remainingGrass, sizeGrassPools)), rng); 752 if (working.isEmpty()) 753 continue; 754 floors.andNot(working); 755 remainingGrass -= working.size(); 756 map = working.inverseMask(map, '"'); 757 } else 758 break; 759 } 760 } 761 762 if(islandSpacing > 1 && targetWater > 0) { 763 OrderedSet<Coord> islands = PoissonDisk.sampleMap(map, 1f * islandSpacing, rng, '#', '.', '"', '+', '/', '^', '<', '>'); 764 for (Coord c : islands) { 765 map[c.x][c.y] = '.'; 766 if (map[c.x - 1][c.y] != '#' && map[c.x - 1][c.y] != '<' && map[c.x - 1][c.y] != '>') 767 map[c.x - 1][c.y] = ','; 768 if (map[c.x + 1][c.y] != '#' && map[c.x + 1][c.y] != '<' && map[c.x + 1][c.y] != '>') 769 map[c.x + 1][c.y] = ','; 770 if (map[c.x][c.y - 1] != '#' && map[c.x][c.y - 1] != '<' && map[c.x][c.y - 1] != '>') 771 map[c.x][c.y - 1] = ','; 772 if (map[c.x][c.y + 1] != '#' && map[c.x][c.y + 1] != '<' && map[c.x][c.y + 1] != '>') 773 map[c.x][c.y + 1] = ','; 774 } 775 } 776 777 if(trapFill > 0) 778 { 779 int total = hazards.size() * trapFill / 100; 780 781 for(int i = 0; i < total; i++) 782 { 783 Coord entry = rng.getRandomElement(hazards); 784 if(map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '>') 785 continue; 786 map[entry.x][entry.y] = '^'; 787 hazards.remove(entry); 788 } 789 } 790 791 dungeon = map; 792 return map; 793 794 } 795 796 797 /** 798 * Gets the seed that can be used to rebuild an identical dungeon to the latest one generated (or the seed that 799 * will be used to generate the first dungeon if none has been made yet). You can pass the long this returns to 800 * the setState() method on this class' rng field, which assuming all other calls to generate a dungeon are 801 * identical, will ensure generate() or generateRespectingStairs() will produce the same dungeon output as the 802 * dungeon originally generated with the seed this returned. 803 * <br> 804 * You can also call getState() on the rng field yourself immediately before generating a dungeon, but this method 805 * handles some complexities of when the state is actually used to generate a dungeon; since StatefulRNG objects can 806 * be shared between different classes that use random numbers, the state could change between when you call 807 * getState() and when this class generates a dungeon. Using getRebuildSeed() eliminates that confusion. 808 * @return a seed as a long that can be passed to setState() on this class' rng field to recreate a dungeon 809 */ 810 public long getRebuildSeed() { 811 return rebuildSeed; 812 } 813 814 /** 815 * Provides a string representation of the latest generated dungeon. 816 * 817 * @return a printable string version of the latest generated dungeon. 818 */ 819 @Override 820 public String toString() { 821 char[][] trans = new char[height][width]; 822 for (int x = 0; x < width; x++) { 823 for (int y = 0; y < height; y++) { 824 trans[y][x] = dungeon[x][y]; 825 } 826 } 827 StringBuffer sb = new StringBuffer(); 828 for (int row = 0; row < height; row++) { 829 sb.append(trans[row]); 830 sb.append('\n'); 831 } 832 return sb.toString(); 833 } 834 835}