001package squidpony.squidgrid.mapping; 002 003import squidpony.squidmath.Coord; 004import squidpony.squidmath.CoordPacker; 005import squidpony.squidmath.RNG; 006 007import java.util.ArrayList; 008import java.util.LinkedHashMap; 009import java.util.LinkedHashSet; 010import java.util.List; 011 012/** 013 * Generate dungeons based on a random, winding, looping path through 3D space, requiring a character to move up and 014 * down as well as north/south/east/west to get through the dungeon. Uses techniques from MixedGenerator. 015 * Uses a Moore Curve, which is related to Hilbert Curves but loops back to its starting point, and stretches and 016 * distorts the grid to make sure a visual correlation isn't obvious. 017 * <br> 018 * The name comes from a vivid dream I had about gigantic, multi-colored snakes that completely occupied a roguelike 019 * dungeon. Shortly after, I made the connection to the Australian mythology I'd heard about the Rainbow Serpent, which 020 * in some stories dug water-holes and was similarly gigantic. 021 * Created by Tommy Ettinger on 10/24/2015. 022 */ 023public class SerpentDeepMapGenerator { 024 private MixedGenerator[] mix; 025 private int[] columns, rows; 026 private int width, height, depth; 027 private ArrayList<LinkedHashSet<Coord>> linksUp,linksDown; 028 private RNG random; 029 030 /** 031 * This prepares a map generator that will generate a map with the given width, height and depth, using the given 032 * RNG. The intended purpose is to carve a long path that loops through the whole dungeon's 3D space, while 033 * hopefully maximizing the amount of rooms the player encounters. You call the different carver-adding methods to 034 * affect what the dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), 035 * defaulting to only caves if none are called. You call generate() after adding carvers, which returns a char[][][] 036 * for a map. 037 * @param width the width of the final map in cells 038 * @param height the height of the final map in cells 039 * @param depth the number of levels deep to create 040 * @param rng an RNG object to use for random choices; this make a lot of random choices. 041 * @see MixedGenerator 042 */ 043 public SerpentDeepMapGenerator(int width, int height, int depth, RNG rng) { 044 this(width, height, depth, rng, 0.3); 045 } 046 /** 047 * This prepares a map generator that will generate a map with the given width, height and depth, using the given 048 * RNG, and will branch out to other nearby rooms that (probably) do not have staircases between layers. 049 * The intended purpose is to carve a long path that loops through the whole dungeon's 3D space, while 050 * hopefully maximizing the amount of rooms the player encounters. You call the different carver-adding methods to 051 * affect what the dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), 052 * defaulting to only caves if none are called. You call generate() after adding carvers, which returns a char[][][] 053 * for a map. 054 * @param width the width of the final map in cells 055 * @param height the height of the final map in cells 056 * @param depth the number of levels deep to create 057 * @param rng an RNG object to use for random choices; this make a lot of random choices. 058 * @param branchingChance the odds from 0.0 to 1.0 that a branch will be created near each necessary room. 059 * @see MixedGenerator 060 */ 061 public SerpentDeepMapGenerator(int width, int height, int depth, RNG rng, double branchingChance) 062 { 063 if(width <= 2 || height <= 2) 064 throw new IllegalArgumentException("width and height must be greater than 2"); 065 if(depth < 1) 066 throw new IllegalArgumentException("depth must be at least 1"); 067 random = rng; 068 this.width = width; 069 this.height = height; 070 this.depth = depth; 071 int numLayers = (int)Math.ceil(depth / 4.0f); 072 long columnAlterations = random.nextLong(0x100000000L); 073 float columnBase = width / (Long.bitCount(columnAlterations) + 16.0f); 074 long rowAlterations = random.nextLong(0x100000000L); 075 float rowBase = height / (Long.bitCount(rowAlterations) + 16.0f); 076 077 columns = new int[16]; 078 rows = new int[16]; 079 linksUp = new ArrayList<>(depth); 080 linksDown = new ArrayList<>(depth); 081 for (int i = 0; i < depth; i++) { 082 linksUp.add(new LinkedHashSet<Coord>(80)); 083 linksDown.add(new LinkedHashSet<Coord>(80)); 084 } 085 int csum = 0, rsum = 0; 086 long b = 3; 087 for (int i = 0; i < 16; i++, b <<= 2) { 088 columns[i] = csum + (int)(columnBase * 0.5f * (1 + Long.bitCount(columnAlterations & b))); 089 csum += (int)(columnBase * (1 + Long.bitCount(columnAlterations & b))); 090 rows[i] = rsum + (int)(rowBase * 0.5f * (1 + Long.bitCount(rowAlterations & b))); 091 rsum += (int)(rowBase * (1 + Long.bitCount(rowAlterations & b))); 092 } 093 int cs = (width - csum); 094 int rs = (height - rsum); 095 int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs; 096 for (int i = 0; i <= 7; i++) { 097 cs2= cs2 * i / 7; 098 rs2 = rs2 * i / 7; 099 columns[i] -= cs2; 100 rows[i] -= rs2; 101 } 102 for (int i = 15; i >= 8; i--) { 103 cs3 = cs3 * (i - 8) / 8; 104 rs3 = rs3 * (i - 8) / 8; 105 columns[i] += cs3; 106 rows[i] += rs3; 107 } 108 109 List<LinkedHashMap<Coord, List<Coord>>> connections = new ArrayList<>(depth); 110 for (int i = 0; i < depth; i++) { 111 connections.add(new LinkedHashMap<Coord, List<Coord>>(80)); 112 } 113 int m = random.nextInt(0x800 * numLayers); 114 int x = CoordPacker.getXMoore3D(m, numLayers), y = CoordPacker.getYMoore3D(m, numLayers), 115 z = (int)Math.floor(CoordPacker.getZMoore3D(m, numLayers) * depth / (8f * numLayers)), 116 sx = x, sy = y, sz = z, tz = z; 117 int r = random.between(12, 33); 118 m += r; 119 for (int i = 0; i < 0x800 * numLayers; r = random.between(12, 33), i += r, m = (m + r) % (0x800 * numLayers)) { 120 tz = z; 121 int tx = x, ty = y; 122 do { 123 List<Coord> cl = new ArrayList<>(4); 124 125 for (int j = 0; 126 j < 2; 127 j++) { 128 int x2 = random.between(Math.max(0, tx - 2), tx); 129 int x3 = random.between(tx + 1, Math.min(tx + 3, 15)); 130 int y2 = random.between(Math.max(0, ty - 2), ty); 131 int y3 = random.between(ty + 1, Math.min(ty + 3, 15)); 132 if (x3 < 16 && random.nextBoolean()) 133 x2 = x3; 134 if (y3 < 16 && random.nextBoolean()) 135 y2 = y3; 136 cl.add(Coord.get(columns[x2], rows[y2])); 137 if (random.nextDouble() >= branchingChance) 138 break; 139 } 140 141 List<Coord> connect = connections.get(tz).get(Coord.get(columns[tx], rows[ty])); 142 if(connect != null) 143 connections.get(tz).get(Coord.get(columns[tx], rows[ty])).addAll(cl); 144 else 145 connections.get(tz).put(Coord.get(columns[tx], rows[ty]), new ArrayList<>(cl)); 146 147 x = CoordPacker.getXMoore3D(m, numLayers); 148 y = CoordPacker.getYMoore3D(m, numLayers); 149 z = (int)Math.floor(CoordPacker.getZMoore3D(m, numLayers) * depth / (8f * numLayers)); 150 if(z != tz) 151 cl.clear(); 152 cl.add(Coord.get(columns[x], rows[y])); 153 154 if (tz == z) { 155 List<Coord> conn = connections.get(z).get(Coord.get(columns[tx], rows[ty])); 156 if(conn != null) 157 connections.get(z).get(Coord.get(columns[tx], rows[ty])).addAll(cl); 158 else 159 connections.get(z).put(Coord.get(columns[tx], rows[ty]), new ArrayList<>(cl)); 160 break; 161 } 162 else { 163 if (z > tz) { 164 linksDown.get(tz).add(Coord.get(tx, ty)); 165 tz++; 166 linksUp.get(tz).add(Coord.get(tx, ty)); 167 } 168 else 169 { 170 linksUp.get(tz).add(Coord.get(tx, ty)); 171 tz--; 172 linksDown.get(tz).add(Coord.get(tx, ty)); 173 } 174 } 175 }while (true); 176 } 177 178 do { 179 List<Coord> cl = new ArrayList<>(4); 180 181 for (int j = 0; 182 j < 2; 183 j++) { 184 int x2 = random.between(Math.max(0, x - 2), x); 185 int x3 = random.between(x + 1, Math.min(x + 3, 15)); 186 int y2 = random.between(Math.max(0, y - 2), y); 187 int y3 = random.between(y + 1, Math.min(y + 3, 15)); 188 if (x3 < 16 && random.nextBoolean()) 189 x2 = x3; 190 if (y3 < 16 && random.nextBoolean()) 191 y2 = y3; 192 cl.add(Coord.get(columns[x2], rows[y2])); 193 if (Math.min(random.nextDouble(), random.nextDouble()) >= branchingChance) 194 break; 195 } 196 197 List<Coord> connect = connections.get(tz).get(Coord.get(columns[x], rows[y])); 198 if(connect != null) 199 connections.get(tz).get(Coord.get(columns[x], rows[y])).addAll(cl); 200 else 201 connections.get(tz).put(Coord.get(columns[x], rows[y]), new ArrayList<>(cl)); 202 203 if(sz != tz) 204 cl.clear(); 205 cl.add(Coord.get(columns[x], rows[y])); 206 207 if (tz == sz) { 208 connections.get(sz).get(Coord.get(columns[x], rows[y])).add( 209 Coord.get(columns[sx], rows[sy])); 210 break; 211 } 212 else { 213 if (sz > tz) { 214 linksDown.get(tz).add(Coord.get(x, y)); 215 tz++; 216 linksUp.get(tz).add(Coord.get(x, y)); 217 } 218 else 219 { 220 linksUp.get(tz).add(Coord.get(x, y)); 221 tz--; 222 linksDown.get(tz).add(Coord.get(x, y)); 223 } 224 } 225 }while (true); 226 227 mix = new MixedGenerator[depth]; 228 for (int i = 0; i < depth; i++) { 229 mix[i] = new MixedGenerator(width, height, random, connections.get(i), 0.35f); 230 } 231 } 232 /** 233 * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves 234 * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make 235 * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically 236 * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10 237 * between the count of putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers() is reasonable. 238 * @see MixedGenerator 239 * @param count the number of carvers making caves between rooms; only matters in relation to other carvers 240 */ 241 public void putCaveCarvers(int count) 242 { 243 for (int i = 0; i < depth; i++) { 244 mix[i].putCaveCarvers(count); 245 } 246 } 247 /** 248 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 249 * 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 250 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 251 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 252 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 253 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 254 * and putRoundRoomCarvers() is reasonable. 255 * @see MixedGenerator 256 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 257 * to other carvers 258 */ 259 public void putBoxRoomCarvers(int count) 260 { 261 for (int i = 0; i < depth; i++) { 262 mix[i].putBoxRoomCarvers(count); 263 } 264 } 265 /** 266 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 267 * with a random size in a box shape at the start and end, and a small room at the corner if there is one. This also 268 * ensures walls will be placed around the room, only allowing corridors and small cave openings to pass. If count 269 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 270 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 271 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 272 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 273 * and putRoundRoomCarvers() is reasonable. 274 * @see MixedGenerator 275 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 276 * to other carvers 277 */ 278 public void putWalledBoxRoomCarvers(int count) 279 { 280 for (int i = 0; i < depth; i++) { 281 mix[i].putWalledBoxRoomCarvers(count); 282 } 283 } 284 /** 285 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 286 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 287 * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 288 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 289 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 290 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 291 * and putRoundRoomCarvers() is reasonable. 292 * @see MixedGenerator 293 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 294 * to other carvers 295 */ 296 public void putRoundRoomCarvers(int count) 297 { 298 for (int i = 0; i < depth; i++) { 299 mix[i].putRoundRoomCarvers(count); 300 } 301 } 302 303 /** 304 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 305 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 306 * one. This also ensures walls will be placed around the room, only allowing corridors and small cave openings to 307 * pass. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 308 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 309 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 310 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 311 * and putRoundRoomCarvers() is reasonable. 312 * @see MixedGenerator 313 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 314 * to other carvers 315 */ 316 public void putWalledRoundRoomCarvers(int count) 317 { 318 for (int i = 0; i < depth; i++) { 319 mix[i].putWalledRoundRoomCarvers(count); 320 } 321 } 322 323 /** 324 * This generates a new map by stretching a 32x32x(multiple of 8) grid of potential rooms to fit the width, height, 325 * and depth passed to the constructor, randomly expanding columns and rows before contracting the whole to fit 326 * perfectly. This uses the Moore Curve, a space-filling curve that loops around on itself, to guarantee that the 327 * rooms will always have a long path through the dungeon, going up and down as well as north/south/east/west, that, 328 * if followed completely, will take you back to your starting room. Some small branches are possible, and large 329 * rooms may merge with other rooms nearby. This uses MixedGenerator. 330 * @see MixedGenerator 331 * @return a char[][][] where the outermost array is layers, then inside that are x and y in order (z x y) 332 */ 333 public char[][][] generate() 334 { 335 char[][][] dungeon = new char[depth][][]; 336 short[][] floors = new short[depth][]; 337 int dlimit = (height + width) / 3; 338 for (int i = 0; i < depth; i++) { 339 dungeon[i] = mix[i].generate(); 340 floors[i] = CoordPacker.pack(dungeon[i], '.'); 341 } 342 //using actual dungeon space per layer, not row/column 3D grid space 343 ArrayList<LinkedHashSet<Coord>> ups = new ArrayList<>(depth), 344 downs = new ArrayList<>(depth); 345 for (int i = 0; i < depth; i++) { 346 ups.add(new LinkedHashSet<Coord>(40)); 347 downs.add(new LinkedHashSet<Coord>(40)); 348 LinkedHashSet<Coord> above = null; 349 if (i > 0) { 350 above = new LinkedHashSet<>(linksDown.get(i - 1)); 351 if(above.size() == 0) 352 continue; 353 Coord higher = random.getRandomElement(above.toArray(new Coord[above.size()])); 354 while(above.size() > 0) 355 { 356 short[] nearAbove = CoordPacker.flood(floors[i - 1], 357 CoordPacker.packOne(columns[higher.x], rows[higher.y]), 358 dlimit); 359 short[] near = CoordPacker.intersectPacked(nearAbove, CoordPacker.flood(floors[i], 360 CoordPacker.packOne(columns[higher.x], rows[higher.y]), 361 dlimit)); 362 ArrayList<Coord> subLinks = CoordPacker.randomPortion(near, 1, random); 363 ups.get(i).addAll(subLinks); 364 downs.get(i-1).addAll(subLinks); 365 for(Coord abv : linksDown.get(i-1)) 366 { 367 if(CoordPacker.queryPacked(nearAbove, columns[abv.x], rows[abv.y])) //scannedAbove[columns[abv.x]][rows[abv.y]] <= dlimit 368 above.remove(abv); 369 } 370 if(above.isEmpty()) 371 break; 372 higher = random.getRandomElement(above.toArray(new Coord[above.size()])); 373 } 374 } 375 } 376 377 for (int i = 0; i < depth; i++) { 378 LinkedHashMap<Coord, Integer> used = new LinkedHashMap<>(128); 379 for(Coord up : ups.get(i)) 380 { 381 Integer count = used.get(up); 382 if(count != null && count > 1) 383 continue; 384 dungeon[i][up.x][up.y] = '<'; 385 386 used.put(up, (count == null) ? 1 : count + 1); 387 } 388 used.clear(); 389 for(Coord down : downs.get(i)) 390 { 391 Integer count = used.get(down); 392 if(count != null && count > 1) 393 continue; 394 dungeon[i][down.x][down.y] = '>'; 395 396 used.put(down, (count == null) ? 1 : count + 1); 397 } 398 } 399 return dungeon; 400 } 401 402 /** 403 * Gets an array (length equals depth) of 2D int arrays representing the environments for levels. 404 * @return an array of 2D int arrays, where each 2D array is a level's environment 405 */ 406 public int[][][] getEnvironments() 407 { 408 int[][][] env = new int[depth][][]; 409 for (int i = 0; i < depth; i++) { 410 env[i] = mix[i].getEnvironment(); 411 } 412 return env; 413 } 414 415 /** 416 * Gets a 2D int array representing the environment for the requested level. 417 * @param level the level to get from the generated dungeon; will be clamped between 0 and depth - 1 418 * @return a 2D int array representing the requested level's environment 419 */ 420 public int[][] getEnvironment(int level) 421 { 422 return mix[Math.max(0, Math.min(depth - 1, level))].getEnvironment(); 423 } 424}