001package squidpony.squidgrid.mapping.styled; 002 003import squidpony.squidmath.GWTRNG; 004import squidpony.squidmath.GreasedRegion; 005import squidpony.squidmath.IRNG; 006import squidpony.squidmath.RNG; 007 008import java.util.Random; 009 010/** 011 * Generate a dungeon using Sean T. Barrett's Herringbone Wang Tiles method. http://nothings.org/gamedev/herringbone/ 012 * Created by Tommy Ettinger on 3/10/2015. 013 * @author Tommy Ettinger - https://github.com/tommyettinger 014 */ 015public class DungeonBoneGen { 016 017 /** 018 * The current {@link IRNG}, a random number generator that can be seeded initially, and is usually an {@link RNG}. 019 */ 020 public IRNG rng; 021 private int[][] c_color, h_color, v_color; 022 private int wide = 20; 023 private int high = 20; 024 /** 025 * A GreasedRegion that, after {@link #generate(TilesetType, int, int)} has been called, will hold the floor cells 026 * in its data as "on" cells and walls as "off" cells. This can be useful for inter-operating with code that expects 027 * a GreasedRegion, which can be for various reasons. 028 */ 029 public GreasedRegion region = new GreasedRegion(1, 1); 030 /** 031 * Not recommended for general usage; a GreasedRegion that is frequently modified by this generator and is kept 032 * in a field so this and potentially other classes can avoid allocating new GreasedRegions with 033 * {@link GreasedRegion#remake(GreasedRegion)} or the various refill methods in GreasedRegion. 034 */ 035 public transient GreasedRegion workingRegion = new GreasedRegion(1, 1); 036 037 /** 038 * Gets the current RNG. 039 * @return 040 */ 041 public IRNG getRng() { 042 return rng; 043 } 044 045 /** 046 * Sets the current RNG. 047 * @param rng 048 */ 049 public void setRng(IRNG rng) { 050 this.rng = rng; 051 } 052 053 /** 054 * Returns the width, used as the first coordinate in any char[][] in this class. 055 * @return 056 */ 057 public int getWidth() { 058 return wide; 059 } 060 061 /** 062 * Returns the height, used as the second coordinate in any char[][] in this class. 063 * @return 064 */ 065 public int getHeight() { 066 return high; 067 } 068 069 /** 070 * Get the char[][] dungeon that was last returned by generate(), or null if generate() or setDungeon have not been 071 * called. Uses x,y indexing. 072 * @return 073 */ 074 public char[][] getDungeon() { 075 return dungeon; 076 } 077 078 /** 079 * Change the stored char[][] dungeon, using x,y indexing. 080 * @param dungeon 081 */ 082 public void setDungeon(char[][] dungeon) { 083 this.dungeon = dungeon; 084 wide = dungeon.length; 085 high = dungeon[0].length; 086 } 087 088 /** 089 * Gets the char at a given x,y position. 090 * @param x 091 * @param y 092 * @return 093 */ 094 public char get(int x, int y) { 095 return dungeon[x][y]; 096 } 097 098 /** 099 * Sets the char at the given x,y position, storing it in this object. The dungeon this modifies is accessible with 100 * getDungeon() and can be set all at once with setDungeon(). 101 * @param elem 102 * @param x 103 * @param y 104 */ 105 public void put(char elem, int x, int y) { 106 dungeon[x][y] = elem; 107 } 108 109 /** 110 * The latest result of calling this class' generate() method. 111 */ 112 private char[][] dungeon; 113 114 /** 115 * Constructs a DungeonBoneGen that uses the given java.util.Random . 116 * 117 * @param random A Random number generator to be used during the dungeon generation; it will 118 * be used to generate a seed for the internal RNG this class uses. 119 */ 120 public DungeonBoneGen(Random random) { 121 this(new GWTRNG(random.nextInt(), random.nextInt())); 122 } 123 /** 124 * Constructs a DungeonBoneGen that uses the given IRNG. 125 * 126 * @param random An IRNG to be used during the dungeon generation, such as an {@link RNG} or {@link GWTRNG} 127 */ 128 public DungeonBoneGen(IRNG random) { 129 rng = random; 130 c_color = new int[1][1]; 131 h_color = new int[1][1]; 132 v_color = new int[1][1]; 133 } 134 135 /** 136 * Constructs a DungeonBoneGen that uses a default RNG, randomly seeded. 137 */ 138 public DungeonBoneGen() { 139 this(new GWTRNG()); 140 } 141 142 /* 143 private char[][] insert(char[][] mat, String[] items, int coord1, int coord2) { 144 if (mat.length == 0 || items.length == 0 || items[0].length() == 0) 145 return mat; 146 147 for (int i = coord1, i1 = 0; i1 < items.length; i++, i1++) { 148 char[] car = items[i1].toCharArray(); 149 for (int j = coord2, j2 = 0; j2 < car.length; j++, j2++) { 150 if (i < 0 || j < 0 || i >= mat.length || j >= mat[i].length) 151 continue; 152 mat[i][j] = car[j2]; 153 } 154 } 155 return mat; 156 157 } 158 */ 159 private Tile chooseTile(Tile[] list, int numlist, int[] y_positions, int[] x_positions) { 160 int a = c_color[y_positions[0]][x_positions[0]]; 161 int b = c_color[y_positions[1]][x_positions[1]]; 162 int c = c_color[y_positions[2]][x_positions[2]]; 163 int d = c_color[y_positions[3]][x_positions[3]]; 164 int e = c_color[y_positions[4]][x_positions[4]]; 165 int f = c_color[y_positions[5]][x_positions[5]]; 166 int i, n, match = Integer.MAX_VALUE, pass; 167 for (pass = 0; pass < 2; ++pass) { 168 n = 0; 169 // pass #1: 170 // count number of variants that match this partial set of constraints 171 // pass #2: 172 // stop on randomly selected match 173 for (i = 0; i < numlist; ++i) { 174 Tile tile = list[i]; 175 if ((a < 0 || a == tile.a_constraint) && 176 (b < 0 || b == tile.b_constraint) && 177 (c < 0 || c == tile.c_constraint) && 178 (d < 0 || d == tile.d_constraint) && 179 (e < 0 || e == tile.e_constraint) && 180 (f < 0 || f == tile.f_constraint)) { 181 n += 1; 182 if (n > match) { 183 // use list[i] 184 // update constraints to reflect what we placed 185 c_color[y_positions[0]][x_positions[0]] = tile.a_constraint; 186 c_color[y_positions[1]][x_positions[1]] = tile.b_constraint; 187 c_color[y_positions[2]][x_positions[2]] = tile.c_constraint; 188 c_color[y_positions[3]][x_positions[3]] = tile.d_constraint; 189 c_color[y_positions[4]][x_positions[4]] = tile.e_constraint; 190 c_color[y_positions[5]][x_positions[5]] = tile.f_constraint; 191 return tile; 192 } 193 } 194 } 195 if (n == 0) { 196 return null; 197 } 198 match = rng.nextInt(n); 199 } 200 return null; 201 } 202 203 private Tile chooseTile(Tile[] list, int numlist, boolean upright, int[] y_positions, int[] x_positions) { 204 int a, b, c, d, e, f; 205 if (upright) { 206 a = h_color[y_positions[0]][x_positions[0]]; 207 b = v_color[y_positions[1]][x_positions[1]]; 208 c = v_color[y_positions[2]][x_positions[2]]; 209 d = v_color[y_positions[3]][x_positions[3]]; 210 e = v_color[y_positions[4]][x_positions[4]]; 211 f = h_color[y_positions[5]][x_positions[5]]; 212 } else { 213 a = h_color[y_positions[0]][x_positions[0]]; 214 b = h_color[y_positions[1]][x_positions[1]]; 215 c = v_color[y_positions[2]][x_positions[2]]; 216 d = v_color[y_positions[3]][x_positions[3]]; 217 e = h_color[y_positions[4]][x_positions[4]]; 218 f = h_color[y_positions[5]][x_positions[5]]; 219 } 220 int i, n, match = Integer.MAX_VALUE, pass; 221 for (pass = 0; pass < 2; ++pass) { 222 n = 0; 223 // pass #1: 224 // count number of variants that match this partial set of constraints 225 // pass #2: 226 // stop on randomly selected match 227 for (i = 0; i < numlist; ++i) { 228 Tile tile = list[i]; 229 if ((a < 0 || a == tile.a_constraint) && 230 (b < 0 || b == tile.b_constraint) && 231 (c < 0 || c == tile.c_constraint) && 232 (d < 0 || d == tile.d_constraint) && 233 (e < 0 || e == tile.e_constraint) && 234 (f < 0 || f == tile.f_constraint)) { 235 n += 1; 236 if (n > match) { 237 // use list[i] 238 // update constraints to reflect what we placed 239 if (upright) { 240 h_color[y_positions[0]][x_positions[0]] = tile.a_constraint; 241 v_color[y_positions[1]][x_positions[1]] = tile.b_constraint; 242 v_color[y_positions[2]][x_positions[2]] = tile.c_constraint; 243 v_color[y_positions[3]][x_positions[3]] = tile.d_constraint; 244 v_color[y_positions[4]][x_positions[4]] = tile.e_constraint; 245 h_color[y_positions[5]][x_positions[5]] = tile.f_constraint; 246 } else { 247 h_color[y_positions[0]][x_positions[0]] = tile.a_constraint; 248 h_color[y_positions[1]][x_positions[1]] = tile.b_constraint; 249 v_color[y_positions[2]][x_positions[2]] = tile.c_constraint; 250 v_color[y_positions[3]][x_positions[3]] = tile.d_constraint; 251 h_color[y_positions[4]][x_positions[4]] = tile.e_constraint; 252 h_color[y_positions[5]][x_positions[5]] = tile.f_constraint; 253 } 254 return tile; 255 } 256 } 257 } 258 if (n == 0) { 259 return null; 260 } 261 match = rng.nextInt(n); 262 } 263 return null; 264 } 265 266 /** 267 * Generate a dungeon given a TilesetType enum. 268 * The main way of generating dungeons with DungeonBoneGen. 269 * Consider using DungeonBoneGen.wallWrap to surround the edges with walls. 270 * Assigns the returned result to a member of this class, 'dungeon'. 271 * 272 * @param tt A TilesetType enum; try lots of these out to see how they look. 273 * @param w Width of the dungeon to generate in chars. 274 * @param h Height of the dungeon to generate in chars. 275 * @return A row-major char[][] with h rows and w columns; it will be filled with '#' for walls and '.' for floors. 276 */ 277 public char[][] generate(TilesetType tt, int w, int h) { 278 return generate(tt.getTileset(), w, h); 279 } 280 281 /** 282 * Changes the outer edge of a char[][] to the wall char, '#'. 283 * 284 * @param map A char[][] that stores map data. 285 * @return 286 */ 287 public static char[][] wallWrap(char[][] map) { 288 int upperY = map[0].length - 1; 289 int upperX = map.length - 1; 290 for (int i = 0; i < map.length; i++) { 291 map[i][0] = '#'; 292 map[i][upperY] = '#'; 293 } 294 for (int i = 0; i < map[0].length; i++) { 295 map[0][i] = '#'; 296 map[upperX][i] = '#'; 297 } 298 return map; 299 } 300 301 /** 302 * Changes the outer edge of this dungeon to the wall char, '#'. 303 * 304 * @return The modified dungeon, a char[][]. 305 */ 306 public char[][] wallWrap() { 307 int upperY = high - 1; 308 int upperX = wide - 1; 309 for (int i = 0; i < wide; i++) { 310 dungeon[i][0] = '#'; 311 dungeon[i][upperY] = '#'; 312 } 313 for (int i = 0; i < high; i++) { 314 dungeon[0][i] = '#'; 315 dungeon[upperX][i] = '#'; 316 } 317 return dungeon; 318 } 319 320 private boolean matchingAdjacent(int y, int x) 321 { 322 return c_color[y][x] == c_color[y + 1][x + 1]; 323 } 324 325 private int changeColor(int old_color, int num_options) { 326 327 int offset = 1 + rng.nextInt(num_options - 1); 328 return (old_color + offset) % num_options; 329 } 330 331 /** 332 * Generate a dungeon given a Tileset. 333 * If you have your own Tileset gained by parsing your own JSON, use 334 * this to generate a dungeon using it. Consider using DungeonBoneGen.wallWrap 335 * to surround the edges with walls. Assigns the returned result to a member 336 * of this class, 'dungeon'. 337 * 338 * @param ts A Tileset; if you don't have one of these available, use a TilesetType enum instead to select a predefined one. 339 * @param h Height of the dungeon to generate in chars. 340 * @param w Width of the dungeon to generate in chars. 341 * @return A row-major char[][] with h rows and w columns; it will be filled with '#' for walls and '.' for floors. 342 */ 343 public char[][] generate(Tileset ts, int w, int h) { 344 wide = Math.max(1, w); 345 high = Math.max(1, h); 346 region.resizeAndEmpty(wide, high); 347 workingRegion.resizeAndEmpty(wide, high); 348 int sidelen = ts.config.short_side_length; 349 int xmax = (wide / sidelen) + 6; 350 int ymax = (high / sidelen) + 6; 351// if (xmax > 1006) { 352// return null; 353// } 354// if (ymax > 1006) { 355// return null; 356// } 357 if (ts.config.is_corner) { 358 c_color = new int[ymax][xmax]; 359 int i, j, ypos = -sidelen; 360 int[] cc = ts.config.num_colors; 361 362 for (j = 0; j < ymax; ++j) { 363 for (i = 0; i < xmax; ++i) { 364 c_color[j][i] = rng.nextInt(cc[(i - j + 1) & 3]); // select from cc based on corner type 365 } 366 } 367 368 // Repetition reduction 369 // now go back through and make sure we don't have adjacent 3x2 vertices that are identical, 370 // to avoid really obvious repetition (which happens easily with extreme weights) 371 for (j = 0; j < ymax - 3; ++j) { 372 for (i = 0; i < xmax - 3; ++i) { 373 int p; // corner type 374// if (i + 3 >= 1006) { 375// return null; 376// } 377// if (j + 3 >= 1006) { 378// return null; 379// } 380 if (matchingAdjacent(j, i) && matchingAdjacent(j + 1, i) && matchingAdjacent(j + 2, i) 381 && matchingAdjacent(j, i + 1) && matchingAdjacent(j + 1, i + 1) && matchingAdjacent(j + 2, i + 1)) { 382 p = ((i + 1) - (j + 1) + 1) & 3; 383 if (cc[p] > 1) 384 c_color[j + 1][i + 1] = changeColor(c_color[j + 1][i + 1], cc[p]); 385 } 386 387 if (matchingAdjacent(j, i) && matchingAdjacent(j, i + 1) && matchingAdjacent(j, i + 2) 388 && matchingAdjacent(j + 1, i) && matchingAdjacent(j + 1, i + 1) && matchingAdjacent(j + 1, i + 2)) { 389 p = ((i + 2) - (j + 1) + 1) & 3; 390 if (cc[p] > 1) 391 c_color[j + 1][i + 2] = changeColor(c_color[j + 1][i + 2], cc[p]); 392 } 393 } 394 } 395 396 397 for (j = -1; ypos < high; ++j) { 398 // a general herringbone row consists of: 399 // horizontal left block, the bottom of a previous vertical, the top of a new vertical 400 int phase = j & 3; 401 // displace horizontally according to pattern 402 if (phase == 0) { 403 i = 0; 404 } else { 405 i = phase - 4; 406 } 407 for (; ; i += 4) { 408 int xpos = i * sidelen; 409 if (xpos >= wide) 410 break; 411 // horizontal left-block 412 if (xpos + sidelen * 2 >= 0 && ypos >= 0) { 413 Tile t = chooseTile( 414 ts.h_tiles, ts.h_tiles.length, 415 new int[]{j + 2, j + 2, j + 2, j + 3, j + 3, j + 3}, 416 new int[]{i + 2, i + 3, i + 4, i + 2, i + 3, i + 4}); 417 418 if (t == null) 419 return null; 420 421 //trans_output = insert(trans_output, t.data, ypos, xpos); 422 423 ////debug info in case fix on September 13, 2019 isn't complete 424// workingRegion.refill(t.data, t.width, t.height, wide, high); 425// System.out.println("\nhorizontal tile at i="+i+",j="+j); 426// System.out.println(workingRegion); 427// region.or(workingRegion.translate(xpos, ypos)); 428// System.out.println("\nhorizontal tile translated at i="+i+",j="+j+",xPos="+xpos+",yPos="+ypos+",first="+workingRegion.first()); 429// System.out.println(workingRegion); 430 region.or(workingRegion.refill(t.data, t.width, t.height, wide, high).translate(xpos, ypos)); 431 432 } 433 xpos += sidelen * 2; 434 // now we're at the end of a previous vertical one 435 xpos += sidelen; 436 // now we're at the start of a new vertical one 437 if (xpos < wide) { 438 Tile t = chooseTile( 439 ts.v_tiles, ts.v_tiles.length, 440 new int[]{j + 2, j + 3, j + 4, j + 2, j + 3, j + 4}, 441 new int[]{i + 5, i + 5, i + 5, i + 6, i + 6, i + 6}); 442 443 if (t == null) 444 return null; 445 //trans_output = insert(trans_output, t.data, ypos, xpos); 446 447 ////debug info in case fix on September 13, 2019 isn't complete 448// workingRegion.refill(t.data, t.width, t.height, wide, high); 449// System.out.println("\nvertical tile at i="+i+",j="+j); 450// System.out.println(workingRegion); 451// region.or(workingRegion.translate(xpos, ypos)); 452// System.out.println("\nvertical tile translated at i="+i+",j="+j+",xPos="+xpos+",yPos="+ypos+",first="+workingRegion.first()); 453// System.out.println(workingRegion); 454 455 region.or(workingRegion.refill(t.data, t.width, t.height, wide, high).translate(xpos, ypos)); 456 } 457 } 458 ypos += sidelen; 459 } 460 } else { 461 int i, j, ypos; 462 v_color = new int[ymax][xmax]; 463 h_color = new int[ymax][xmax]; 464 for (int yy = 0; yy < ymax; yy++) { 465 for (int xx = 0; xx < xmax; xx++) { 466 v_color[yy][xx] = -1; 467 h_color[yy][xx] = -1; 468 } 469 } 470 471 ypos = -1 * sidelen; 472 for (j = -1; ypos < high; ++j) { 473 // a general herringbone row consists of: 474 // horizontal left block, the bottom of a previous vertical, the top of a new vertical 475 int phase = j & 3; 476 // displace horizontally according to pattern 477 if (phase == 0) { 478 i = 0; 479 } else { 480 i = phase - 4; 481 } 482 for (; ; i += 4) { 483 int xpos = i * sidelen; 484 if (xpos >= wide) 485 break; 486 // horizontal left-block 487 if (xpos + sidelen * 2 >= 0 && ypos >= 0) { 488 Tile t = chooseTile( 489 ts.h_tiles, ts.h_tiles.length, false, 490 new int[]{j + 2, j + 2, j + 2, j + 2, j + 3, j + 3}, 491 new int[]{i + 2, i + 3, i + 2, i + 4, i + 2, i + 3}); 492 493 if (t == null) 494 return null; 495 //trans_output = insert(trans_output, t.data, ypos, xpos); 496 region.or(workingRegion.refill(t.data, t.width, t.height, wide, high).translate(xpos, ypos)); 497 } 498 xpos += sidelen * 2; 499 // now we're at the end of a previous vertical one 500 xpos += sidelen; 501 // now we're at the start of a new vertical one 502 if (xpos < wide) { 503 Tile t = chooseTile( 504 ts.v_tiles, ts.v_tiles.length, true, 505 new int[]{j + 2, j + 2, j + 2, j + 3, j + 3, j + 4}, 506 new int[]{i + 5, i + 5, i + 6, i + 5, i + 6, i + 5}); 507 508 if (t == null) 509 return null; 510 //trans_output = insert(trans_output, t.data, ypos, xpos); 511 region.or(workingRegion.refill(t.data, t.width, t.height, wide, high).translate(xpos, ypos)); 512 } 513 } 514 ypos += sidelen; 515 } 516 } 517 /*for (int x = 0; x < w; x++) { 518 for (int y = 0; y < h; y++) { 519 output[x][y] = trans_output[y][x]; 520 } 521 }*/ 522 dungeon = region.toChars(); 523 return dungeon; 524 } 525 526 /** 527 * Provides a string representation of the latest generated dungeon. 528 * 529 * @return 530 */ 531 @Override 532 public String toString() { 533 char[][] trans = new char[high][wide]; 534 for (int x = 0; x < wide; x++) { 535 for (int y = 0; y < high; y++) { 536 trans[y][x] = dungeon[x][y]; 537 } 538 } 539 StringBuffer sb = new StringBuffer(); 540 for (int row = 0; row < high; row++) { 541 sb.append(trans[row]); 542 sb.append('\n'); 543 } 544 return sb.toString(); 545 } 546 547 /* 548 * Gets an array of all herringbone tiles associated with a TilesetType enum. 549 * 550 * @param tt a TilesetType enum 551 * @return an array of 2D char arrays representing tiles 552 * / 553 public String[][] getTiles(TilesetType tt) { 554 final Tileset ts = tt.getTileset(); 555 556 String[][] result = new String[ts.h_tiles.length + ts.v_tiles.length][]; 557 for (int i = 0; i < ts.h_tiles.length; i++) { 558 result[i] = ts.h_tiles[i].data; 559 } 560 for (int i = 0; i < ts.v_tiles.length; i++) { 561 result[ts.h_tiles.length + i] = ts.v_tiles[i].data; 562 } 563 return result; 564 }*/ 565}