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