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