001package squidpony.squidgrid.mapping; 002 003import squidpony.GwtCompatibility; 004import squidpony.annotation.Beta; 005import squidpony.squidmath.*; 006 007import java.util.*; 008 009/** 010 * Generator for maps of high-tech areas like space stations or starships, with repeated modules laid out in random ways. 011 * Different from traditional fantasy dungeon generation in that it should seem generally less chaotic in how it's laid 012 * out, and repeated elements with minor tweaks should be especially common. May also be useful in fantasy games for 013 * regimented areas built by well-organized military forces. 014 * <br> 015 * Preview: https://gist.github.com/tommyettinger/c711f8fc83fa9919245d88092444bf7f 016 * Created by Tommy Ettinger on 4/2/2016. 017 */ 018@Beta 019public class ModularMapGenerator { 020 public DungeonUtility utility; 021 protected int height, width; 022 public StatefulRNG rng; 023 protected long rebuildSeed; 024 protected boolean seedFixed = false; 025 026 protected char[][] map = null; 027 protected int[][] environment = null; 028 //public RegionMap<MapModule> layout, modules, inverseModules; 029 public RegionMap<MapModule> layout; 030 public LinkedHashMap<Integer, ArrayList<MapModule>> modules; 031 public LinkedHashMap<Coord, MapModule> displacement; 032 033 private void putModule(short[] module) { 034 char[][] unp = CoordPacker.unpackChar(module, '.', '#'); 035 MapModule mm = new MapModule(GwtCompatibility.insert2D(unp, 036 GwtCompatibility.fill2D('#', unp.length + 2, unp[0].length + 2), 1, 1)); 037 //short[] b = CoordPacker.rectangle(1 + mm.max.x, 1 + mm.max.y); 038 //modules.put(b, mm); 039 //inverseModules.put(CoordPacker.negatePacked(b), mm); 040 ArrayList<MapModule> mms = modules.get(mm.category); 041 if (mms == null) { 042 mms = new ArrayList<>(16); 043 mms.add(mm); 044 modules.put(mm.category, mms); 045 } else 046 mms.add(mm); 047 } 048 049 private void putRectangle(int width, int height, float multiplier) { 050 putModule(CoordPacker.rectangle(Math.round(width * multiplier), Math.round(height * multiplier))); 051 } 052 053 private void putCircle(int radius, float multiplier) { 054 putModule(CoordPacker.circle(Coord.get(Math.round(radius * multiplier + 1), Math.round(radius * multiplier + 1)), 055 Math.round(radius * multiplier), 056 Math.round((radius + 1) * 2 * multiplier + 1), Math.round((radius + 1) * 2 * multiplier + 1))); 057 } 058 059 private void initModules() { 060 layout = new RegionMap<>(64); 061 //modules = new RegionMap<>(64); 062 //inverseModules = new RegionMap<>(64); 063 modules = new LinkedHashMap<>(64); 064 for (int i = 1; i <= 64; i <<= 1) { 065 ArrayList<MapModule> mms = new ArrayList<>(16); 066 modules.put(i, mms); 067 } 068 displacement = new LinkedHashMap<>(64); 069 float multiplier = 1;//(float) Math.sqrt(Math.max(1f, Math.min(width, height) / 24f)); 070 putRectangle(2, 2, multiplier); 071 putRectangle(3, 3, multiplier); 072 putRectangle(4, 4, multiplier); 073 putRectangle(4, 2, multiplier); 074 putRectangle(2, 4, multiplier); 075 putRectangle(6, 6, multiplier); 076 putRectangle(6, 3, multiplier); 077 putRectangle(3, 6, multiplier); 078 putCircle(2, multiplier); 079 080 putRectangle(8, 8, multiplier); 081 putRectangle(6, 12, multiplier); 082 putRectangle(12, 6, multiplier); 083 putCircle(4, multiplier); 084 085 putRectangle(14, 14, multiplier); 086 putRectangle(9, 18, multiplier); 087 putRectangle(18, 9, multiplier); 088 putRectangle(14, 18, multiplier); 089 putRectangle(18, 14, multiplier); 090 putCircle(7, multiplier); 091 } 092 093 /** 094 * Make a ModularMapGenerator with a StatefulRNG (backed by LightRNG) using a random seed, height 30, and width 60. 095 */ 096 public ModularMapGenerator() { 097 this(60, 30); 098 } 099 100 /** 101 * Make a ModularMapGenerator with the given height and width; the RNG used for generating a dungeon and 102 * adding features will be a StatefulRNG (backed by LightRNG) using a random seed. 103 * 104 * @param width The width of the dungeon in cells 105 * @param height The height of the dungeon in cells 106 */ 107 public ModularMapGenerator(int width, int height) { 108 this(width, height, new StatefulRNG()); 109 } 110 111 /** 112 * Make a ModularMapGenerator with the given height, width, and RNG. Use this if you want to seed the RNG. 113 * 114 * @param width The width of the dungeon in cells 115 * @param height The height of the dungeon in cells 116 * @param rng The RNG to use for all purposes in this class; if it is a StatefulRNG, then it will be used as-is, 117 * but if it is not a StatefulRNG, a new StatefulRNG will be used, randomly seeded by this parameter 118 */ 119 public ModularMapGenerator(int width, int height, RNG rng) { 120 this.rng = (rng instanceof StatefulRNG) ? (StatefulRNG) rng : new StatefulRNG(rng.nextLong()); 121 utility = new DungeonUtility(this.rng); 122 rebuildSeed = this.rng.getState(); 123 this.height = height; 124 this.width = width; 125 map = new char[width][height]; 126 environment = new int[width][height]; 127 for (int x = 0; x < this.width; x++) { 128 Arrays.fill(map[x], '#'); 129 } 130 initModules(); 131 } 132 133 /** 134 * Copies all fields from copying and makes a new DungeonGenerator. 135 * 136 * @param copying the DungeonGenerator to copy 137 */ 138 public ModularMapGenerator(ModularMapGenerator copying) { 139 rng = new StatefulRNG(copying.rng.getState()); 140 utility = new DungeonUtility(rng); 141 rebuildSeed = rng.getState(); 142 height = copying.height; 143 width = copying.width; 144 map = GwtCompatibility.copy2D(copying.map); 145 environment = GwtCompatibility.copy2D(copying.environment); 146 layout = new RegionMap<>(copying.layout); 147 modules = new LinkedHashMap<>(copying.modules); 148 } 149 150 /** 151 * Get the most recently generated char[][] map out of this class. The 152 * map may be null if generate() or setMap() have not been called. 153 * 154 * @return a char[][] map, or null. 155 */ 156 public char[][] getMap() { 157 return map; 158 } 159 160 /** 161 * Get the most recently generated char[][] map out of this class without any chars other than '#' or '.', for 162 * walls and floors respectively. The map may be null if generate() or setMap() have not been called. 163 * 164 * @return a char[][] map with only '#' for walls and '.' for floors, or null. 165 */ 166 public char[][] getBareMap() { 167 return DungeonUtility.simplifyDungeon(map); 168 } 169 170 public char[][] generate() { 171 MapModule mm, mm2; 172 int xPos, yPos, categorySize = 32, alteredSize = (categorySize * 3) >>> 1, bits = 5, ctr; 173 Coord[][] grid = new Coord[1][1]; 174 // find biggest category and drop down as many modules as we can fit 175 for (; categorySize >= 4; categorySize >>= 1, alteredSize = (categorySize * 3) >>> 1, bits--) { 176 if (width / alteredSize <= 0 || height / alteredSize <= 0) 177 continue; 178 grid = new Coord[width / alteredSize][height / alteredSize]; 179 ctr = 0; 180 for (int xLimit = alteredSize - 1, x = 0; xLimit < width; xLimit += alteredSize, x += alteredSize) { 181 for (int yLimit = alteredSize - 1, y = 0; yLimit < height; yLimit += alteredSize, y += alteredSize) { 182 if (layout.allAt(x + alteredSize / 2, y + alteredSize / 2).isEmpty()) // && (bits <= 3 || rng.nextInt(5) < bits) 183 { 184 if (rng.between(2, grid.length * grid[0].length + 3) == ctr++) 185 continue; 186 mm = rng.getRandomElement(modules.get(categorySize)); 187 if (mm == null) break; 188 mm = mm.rotate(rng.nextInt(4)); 189 xPos = rng.nextInt(3) << (bits - 2); 190 yPos = rng.nextInt(3) << (bits - 2); 191 for (int px = 0; px <= mm.max.x; px++) { 192 System.arraycopy(mm.map[px], 0, map[px + x + xPos], y + yPos, mm.max.y + 1); 193 System.arraycopy(mm.environment[px], 0, environment[px + x + xPos], y + yPos, mm.max.y + 1); 194 } 195 layout.put(CoordPacker.rectangle(x + xPos, y + yPos, categorySize, categorySize), mm); 196 displacement.put(Coord.get(x + xPos, y + yPos), mm); 197 grid[x / alteredSize][y / alteredSize] = Coord.get(x + xPos, y + yPos); 198 } 199 } 200 } 201 if (layout.size > 0) 202 break; 203 } 204 Coord a, b; 205 int gw = grid.length; 206 if (gw > 0) { 207 int gh = grid[0].length; 208 for (int w = 0; w < gw; w++) { 209 for (int h = 0; h < gh; h++) { 210 a = grid[w][h]; 211 if (a == null) 212 continue; 213 int connectors = rng.nextInt(16) | rng.nextInt(16); 214 if ((connectors & 1) == 1 && w > 0 && grid[w - 1][h] != null) { 215 b = grid[w - 1][h]; 216 connectLeftRight(displacement.get(b), b.x, b.y, displacement.get(a), a.x, a.y); 217 } 218 if ((connectors & 2) == 2 && w < gw - 1 && grid[w + 1][h] != null) { 219 b = grid[w + 1][h]; 220 connectLeftRight(displacement.get(a), a.x, a.y, displacement.get(b), b.x, b.y); 221 } 222 if ((connectors & 4) == 4 && h > 0 && grid[w][h - 1] != null) { 223 b = grid[w][h - 1]; 224 connectTopBottom(displacement.get(b), b.x, b.y, displacement.get(a), a.x, a.y); 225 } 226 if ((connectors & 8) == 8 && h < gh - 1 && grid[w][h + 1] != null) { 227 b = grid[w][h + 1]; 228 connectTopBottom(displacement.get(a), a.x, a.y, displacement.get(b), b.x, b.y); 229 } 230 } 231 } 232 } 233 Coord begin; 234 short[] packed; 235 for (Map.Entry<Coord, MapModule> dmm : displacement.entrySet()) { 236 begin = dmm.getKey(); 237 mm = dmm.getValue(); 238 //int newCat = mm.category; 239 //if(newCat >= 16) newCat >>>= 1; 240 //if(newCat >= 8) newCat >>>= 1; 241 //mm2 = rng.getRandomElement(modules.get(newCat)); 242 int shiftsX = begin.x - (mm.category * 3 / 2) * ((begin.x * 2) / (3 * mm.category)), 243 shiftsY = begin.y - (mm.category * 3 / 2) * ((begin.y * 2) / (3 * mm.category)), 244 leftSize = Integer.highestOneBit(shiftsX), 245 rightSize = Integer.highestOneBit((mm.category >>> 1) - shiftsX), 246 topSize = Integer.highestOneBit(shiftsY), 247 bottomSize = Integer.highestOneBit((mm.category >>> 1) - shiftsY); 248 if (leftSize >= 4 && !mm.leftDoors.isEmpty()) { 249 mm2 = rng.getRandomElement(modules.get(leftSize)); 250 if (mm2 == null) continue; 251 if (mm2.rightDoors.isEmpty()) { 252 if (!mm2.topDoors.isEmpty()) 253 mm2 = mm2.rotate(1); 254 else if (!mm2.leftDoors.isEmpty()) 255 mm2 = mm2.flip(true, false); 256 else if (!mm2.bottomDoors.isEmpty()) 257 mm2 = mm2.rotate(3); 258 else continue; 259 } 260 for (int i = 0; i < 4; i++) { 261 packed = CoordPacker.rectangle(begin.x - shiftsX, begin.y + i * mm.category / 4, leftSize, leftSize); 262 if (layout.containsRegion(packed)) 263 continue; 264 for (int px = 0; px <= mm2.max.x; px++) { 265 System.arraycopy(mm2.map[px], 0, map[px + begin.x - shiftsX], begin.y + i * mm.category / 4, mm2.max.y + 1); 266 System.arraycopy(mm2.environment[px], 0, environment[px + begin.x - shiftsX], begin.y + i * mm.category / 4, mm2.max.y + 1); 267 } 268 layout.put(packed, mm2); 269 connectLeftRight(mm2, begin.x - shiftsX, begin.y + i * mm.category / 4, mm, begin.x, begin.y); 270 } 271 } 272 if (rightSize >= 4 && !mm.rightDoors.isEmpty()) { 273 mm2 = rng.getRandomElement(modules.get(rightSize)); 274 if (mm2 == null) continue; 275 if (mm2.leftDoors.isEmpty()) { 276 if (!mm2.bottomDoors.isEmpty()) 277 mm2 = mm2.rotate(1); 278 else if (!mm2.rightDoors.isEmpty()) 279 mm2 = mm2.flip(true, false); 280 else if (!mm2.topDoors.isEmpty()) 281 mm2 = mm2.rotate(3); 282 else continue; 283 } 284 for (int i = 0; i < 4; i++) { 285 packed = CoordPacker.rectangle(begin.x + mm.category, begin.y + i * mm.category / 4, rightSize, rightSize); 286 if (layout.containsRegion(packed)) 287 continue; 288 for (int px = 0; px <= mm2.max.x; px++) { 289 System.arraycopy(mm2.map[px], 0, map[px + begin.x + mm.category], begin.y + i * mm.category / 4, mm2.max.y + 1); 290 System.arraycopy(mm2.environment[px], 0, environment[px + begin.x + mm.category], begin.y + i * mm.category / 4, mm2.max.y + 1); 291 } 292 layout.put(packed, mm2); 293 connectLeftRight(mm, begin.x, begin.y, mm2, begin.x + mm.category, begin.y + i * mm.category / 4); 294 } 295 } 296 if (topSize >= 4 && !mm.topDoors.isEmpty()) { 297 mm2 = rng.getRandomElement(modules.get(topSize)); 298 if (mm2 == null) continue; 299 if (mm2.bottomDoors.isEmpty()) { 300 if (!mm2.leftDoors.isEmpty()) 301 mm2 = mm2.rotate(3); 302 else if (!mm2.topDoors.isEmpty()) 303 mm2 = mm2.flip(false, true); 304 else if (!mm2.rightDoors.isEmpty()) 305 mm2 = mm2.rotate(1); 306 else continue; 307 } 308 for (int i = 0; i < 4; i++) { 309 packed = CoordPacker.rectangle(begin.x + i * mm.category / 4, begin.y - shiftsY, topSize, topSize); 310 if (layout.containsRegion(packed)) 311 continue; 312 for (int px = 0; px <= mm2.max.x; px++) { 313 System.arraycopy(mm2.map[px], 0, map[px + begin.x + i * mm.category / 4], begin.y - shiftsY, mm2.max.y + 1); 314 System.arraycopy(mm2.environment[px], 0, environment[px + begin.x + i * mm.category / 4], begin.y - shiftsY, mm2.max.y + 1); 315 } 316 layout.put(packed, mm2); 317 connectTopBottom(mm2, begin.x + i * mm.category / 4, begin.y - shiftsY, mm, begin.x, begin.y); 318 } 319 } 320 if (bottomSize >= 4 && !mm.bottomDoors.isEmpty()) { 321 mm2 = rng.getRandomElement(modules.get(bottomSize)); 322 if (mm2 == null) continue; 323 if (mm2.topDoors.isEmpty()) { 324 if (!mm2.rightDoors.isEmpty()) 325 mm2 = mm2.rotate(1); 326 else if (!mm2.topDoors.isEmpty()) 327 mm2 = mm2.flip(false, true); 328 else if (!mm2.leftDoors.isEmpty()) 329 mm2 = mm2.rotate(3); 330 else continue; 331 } 332 for (int i = 0; i < 4; i++) { 333 packed = CoordPacker.rectangle(begin.x + i * mm.category / 4, begin.y + mm.category, bottomSize, bottomSize); 334 if (layout.containsRegion(packed)) 335 continue; 336 for (int px = 0; px <= mm2.max.x; px++) { 337 System.arraycopy(mm2.map[px], 0, map[px + begin.x + i * mm.category / 4], begin.y + mm.category, mm2.max.y + 1); 338 System.arraycopy(mm2.environment[px], 0, environment[px + begin.x + i * mm.category / 4], begin.y + mm.category, mm2.max.y + 1); 339 } 340 layout.put(packed, mm2); 341 connectTopBottom(mm, begin.x, begin.y, mm2, begin.x + i * mm.category / 4, begin.y + mm.category); 342 } 343 } 344 } 345 return map; 346 } 347 348 /** 349 * Change the underlying char[][]; only affects the toString method, and of course getMap 350 * 351 * @param map a char[][], probably produced by an earlier call to this class and then modified. 352 */ 353 public void setMap(char[][] map) { 354 this.map = map; 355 if (map == null) { 356 width = 0; 357 height = 0; 358 return; 359 } 360 width = map.length; 361 if (width > 0) 362 height = map[0].length; 363 } 364 365 /** 366 * Height of the map in cells. 367 * 368 * @return Height of the map in cells. 369 */ 370 public int getHeight() { 371 return height; 372 } 373 374 /** 375 * Width of the map in cells. 376 * 377 * @return Width of the map in cells. 378 */ 379 public int getWidth() { 380 return width; 381 } 382 383 /** 384 * Gets the environment int 2D array for use with classes like RoomFinder. 385 * 386 * @return the environment int 2D array 387 */ 388 public int[][] getEnvironment() { 389 return environment; 390 } 391 392 /** 393 * Sets the environment int 2D array. 394 * 395 * @param environment a 2D array of int, where each int corresponds to a constant in MixedGenerator. 396 */ 397 public void setEnvironment(int[][] environment) { 398 this.environment = environment; 399 } 400 401 private void connectLeftRight(MapModule left, int leftX, int leftY, MapModule right, int rightX, int rightY) { 402 if (left.rightDoors == null || left.rightDoors.isEmpty() 403 || right.leftDoors == null || right.leftDoors.isEmpty()) 404 return; 405 List<Coord> line = new ArrayList<>(1), temp; 406 int best = 1024; 407 Coord tl, tr, twl, twr, wl = null, wr = null; 408 for (Coord l : left.rightDoors) { 409 tl = twl = l.translate(leftX, leftY); 410 if (tl.x > 0 && tl.x < width - 1 && map[tl.x - 1][tl.y] != '#') 411 tl = Coord.get(tl.x + 1, tl.y); 412 else if (tl.x > 0 && tl.x < width - 1 && map[tl.x + 1][tl.y] != '#') 413 tl = Coord.get(tl.x - 1, tl.y); 414 else if (tl.y > 0 && tl.y < height - 1 && map[tl.x][tl.y - 1] != '#') 415 tl = Coord.get(tl.x, tl.y + 1); 416 else if (tl.y > 0 && tl.y < height - 1 && map[tl.x][tl.y + 1] != '#') 417 tl = Coord.get(tl.x, tl.y - 1); 418 else 419 continue; 420 421 for (Coord r : right.leftDoors) { 422 tr = twr = r.translate(rightX, rightY); 423 if (tr.x > 0 && tr.x < width - 1 && map[tr.x - 1][tr.y] != '#') 424 tr = Coord.get(tr.x + 1, tr.y); 425 else if (tr.x > 0 && tr.x < width - 1 && map[tr.x + 1][tr.y] != '#') 426 tr = Coord.get(tr.x - 1, tr.y); 427 else if (tr.y > 0 && tr.y < height - 1 && map[tr.x][tr.y - 1] != '#') 428 tr = Coord.get(tr.x, tr.y + 1); 429 else if (tr.y > 0 && tr.y < height - 1 && map[tr.x][tr.y + 1] != '#') 430 tr = Coord.get(tr.x, tr.y - 1); 431 else 432 continue; 433 temp = OrthoLine.line(tl, tr); 434 if (temp.size() < best) { 435 line = temp; 436 best = line.size(); 437 wl = twl; 438 wr = twr; 439 } 440 } 441 } 442 temp = new ArrayList<>(line.size()); 443 for (Coord c : line) { 444 if (map[c.x][c.y] == '#') { 445 map[c.x][c.y] = '.'; 446 environment[c.x][c.y] = MixedGenerator.CORRIDOR_FLOOR; 447 temp.add(c); 448 } 449 } 450 if (wl != null && map[wl.x][wl.y] == '#') { 451 //if(line.isEmpty()) 452 map[wl.x][wl.y] = '.'; 453 environment[wl.x][wl.y] = MixedGenerator.ROOM_FLOOR; 454 //else 455 // map[wl.x][wl.y] = '+'; 456 } 457 if (wr != null && map[wr.x][wr.y] == '#') { 458 //if(line.isEmpty()) 459 map[wr.x][wr.y] = '.'; 460 environment[wr.x][wr.y] = MixedGenerator.ROOM_FLOOR; 461 //else 462 // map[wr.x][wr.y] = '+'; 463 } 464 layout.put(CoordPacker.packSeveral(temp), null); 465 466 } 467 468 private void connectTopBottom(MapModule top, int topX, int topY, MapModule bottom, int bottomX, int bottomY) { 469 if (top.bottomDoors == null || top.bottomDoors.isEmpty() 470 || bottom.topDoors == null || bottom.topDoors.isEmpty()) 471 return; 472 List<Coord> line = new ArrayList<>(1), temp; 473 int best = 1024; 474 Coord tt, tb, twt, twb, wt = null, wb = null; 475 for (Coord l : top.bottomDoors) { 476 tt = twt = l.translate(topX, topY); 477 if (tt.y > 0 && tt.y < height - 1 && map[tt.x][tt.y - 1] != '#') 478 tt = Coord.get(tt.x, tt.y + 1); 479 else if (tt.y > 0 && tt.y < height - 1 && map[tt.x][tt.y + 1] != '#') 480 tt = Coord.get(tt.x, tt.y - 1); 481 else if (tt.x > 0 && tt.x < width - 1 && map[tt.x - 1][tt.y] != '#') 482 tt = Coord.get(tt.x + 1, tt.y); 483 else if (tt.x > 0 && tt.x < width - 1 && map[tt.x + 1][tt.y] != '#') 484 tt = Coord.get(tt.x - 1, tt.y); 485 else 486 continue; 487 488 for (Coord r : bottom.topDoors) { 489 tb = twb = r.translate(bottomX, bottomY); 490 if (tb.y > 0 && tb.y < height - 1 && map[tb.x][tb.y - 1] != '#') 491 tb = Coord.get(tb.x, tb.y + 1); 492 else if (tb.y > 0 && tb.y < height - 1 && map[tb.x][tb.y + 1] != '#') 493 tb = Coord.get(tb.x, tb.y - 1); 494 else if (tb.x > 0 && tb.x < width - 1 && map[tb.x - 1][tb.y] != '#') 495 tb = Coord.get(tb.x + 1, tb.y); 496 else if (tb.x > 0 && tb.x < width - 1 && map[tb.x + 1][tb.y] != '#') 497 tb = Coord.get(tb.x - 1, tb.y); 498 else 499 continue; 500 temp = OrthoLine.line(tt, tb); 501 if (temp.size() < best) { 502 line = temp; 503 best = line.size(); 504 wt = twt; 505 wb = twb; 506 } 507 } 508 } 509 temp = new ArrayList<>(line.size()); 510 for (Coord c : line) { 511 if (map[c.x][c.y] == '#') { 512 map[c.x][c.y] = '.'; 513 environment[c.x][c.y] = MixedGenerator.CORRIDOR_FLOOR; 514 temp.add(c); 515 } 516 } 517 if (wt != null && map[wt.x][wt.y] == '#') { 518 //if(line.isEmpty()) 519 map[wt.x][wt.y] = '.'; 520 environment[wt.x][wt.y] = MixedGenerator.ROOM_FLOOR; 521 //else 522 // map[wl.x][wl.y] = '+'; 523 524 } 525 if (wb != null && map[wb.x][wb.y] == '#') { 526 //if(line.isEmpty()) 527 map[wb.x][wb.y] = '.'; 528 environment[wb.x][wb.y] = MixedGenerator.ROOM_FLOOR; 529 //else 530 // map[wb.x][wb.y] = '+'; 531 } 532 layout.put(CoordPacker.packSeveral(temp), null); 533 } 534}