001package squidpony.squidgrid.mapping; 002 003import squidpony.squidai.DijkstraMap; 004import squidpony.squidgrid.FOV; 005import squidpony.squidmath.Coord; 006import squidpony.squidmath.CoordPacker; 007import squidpony.squidmath.GreasedRegion; 008import squidpony.squidmath.IRNG; 009import squidpony.squidmath.IStatefulRNG; 010import squidpony.squidmath.OrthoLine; 011import squidpony.squidmath.StatefulRNG; 012 013import java.util.ArrayList; 014import java.util.Arrays; 015import java.util.List; 016import java.util.Map; 017import java.util.Set; 018 019/** 020 * A static class that can be used to modify the char[][] dungeons that other generators produce. 021 * Includes various utilities for random floor-finding, but also provides ways to take dungeons that use '#' 022 * for walls and make a copy that uses unicode box drawing characters. 023 * 024 * @author Tommy Ettinger - https://github.com/tommyettinger 025 * @see DungeonGenerator DungeonGenerator uses this class a fair amount 026 * Created by Tommy Ettinger on 4/1/2015. 027 */ 028public class DungeonUtility { 029 030 /** 031 * Constant for environment tiles that are not near a cave, room, or corridor. Value is 0. 032 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 033 */ 034 public static final int UNTOUCHED = 0; 035 /** 036 * Constant for environment tiles that are floors for a room. Value is 1. 037 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 038 */ 039 public static final int ROOM_FLOOR = 1; 040 /** 041 * Constant for environment tiles that are walls near a room. Value is 2. 042 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 043 */ 044 public static final int ROOM_WALL = 2; 045 /** 046 * Constant for environment tiles that are floors for a cave. Value is 3. 047 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 048 */ 049 public static final int CAVE_FLOOR = 3; 050 /** 051 * Constant for environment tiles that are walls near a cave. Value is 4. 052 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 053 */ 054 public static final int CAVE_WALL = 4; 055 /** 056 * Constant for environment tiles that are floors for a corridor. Value is 5. 057 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 058 */ 059 public static final int CORRIDOR_FLOOR = 5; 060 /** 061 * Constant for environment tiles that are walls near a corridor. Value is 6. 062 * Used by several classes that distinguish types of dungeon environment, like {@link SectionDungeonGenerator}. 063 */ 064 public static final int CORRIDOR_WALL = 6; 065 066 public DungeonUtility() { 067 rng = new StatefulRNG(); 068 } 069 070 public DungeonUtility(IStatefulRNG rng) { 071 this.rng = rng; 072 } 073 074 public DungeonUtility(IRNG rng) { 075 this.rng = new StatefulRNG(rng.nextLong()); 076 } 077 078 /** 079 * The random number generator that will be used for all methods in this class with a random component. 080 */ 081 public IStatefulRNG rng; 082 083 084 /** 085 * Finds a random Coord where the x and y match up to a [x][y] location on map that has '.' as a value. 086 * Uses this class' rng field for pseudo-random number generation. May fail if there are very few floor tiles; 087 * use {@link #randomCell(short[])} given {@link #packedFloors(char[][])} to get a floor cell guaranteed if there is 088 * at least one, or better still, make a {@link GreasedRegion#GreasedRegion(char[][], char)} and get a single Coord 089 * from it with {@link GreasedRegion#singleRandom(IRNG)}. You can reuse a GreasedRegion with modifications, like 090 * removing cells you already picked, but using packedFloors() needs to make new short arrays each time. 091 * 092 * @param map a char[][] that should contain a '.' floor tile 093 * @return a Coord that corresponds to a '.' in map, or null if a '.' cannot be found or if map is too small 094 */ 095 public Coord randomFloor(char[][] map) { 096 int width = map.length; 097 int height = map[0].length; 098 if (width < 3 || height < 3) 099 return null; 100 int x = rng.nextInt(width - 2) + 1, y = rng.nextInt(height - 2) + 1; 101 for (int i = 0; i < 20; i++) { 102 if (map[x][y] == '.') { 103 return Coord.get(x, y); 104 } else { 105 x = rng.nextInt(width - 2) + 1; 106 y = rng.nextInt(height - 2) + 1; 107 } 108 } 109 x = 1; 110 y = 1; 111 if (map[x][y] == '.') 112 return Coord.get(x, y); 113 114 while (map[x][y] != '.') { 115 x += 1; 116 if (x >= width - 1) { 117 x = 1; 118 y += 1; 119 } 120 if (y >= height - 1) 121 return null; 122 } 123 return Coord.get(x, y); 124 } 125 126 /** 127 * Finds a random Coord where the x and y match up to a [x][y] location that is encoded as "on" in packed. 128 * This is useful when you have used {@code DungeonUtility.packedFloors(char[][] map)} to encode all floors in map, 129 * or {@code CoordPacker.pack(char[][] map, char... yes)} to encode all cells in a char[][] map that match a 130 * particular type, like '.' for floors or '~' for deep water, and want to efficiently get one randomly-chosen tile 131 * from it. Calling pack() is likely slightly less efficient than using randomFloor(), but it only needs to be done 132 * once per map and cell type, and this method should be substantially more efficient when the type of cell is 133 * uncommon on the map. 134 * Uses this class' rng field for pseudo-random number generation. 135 * 136 * @param packed a packed array produced by CoordPacker encoding the cells to choose from as "on" 137 * @return a Coord that corresponds to a '.' in map, or (-1, -1) if a '.' cannot be found or if map is too small 138 */ 139 public Coord randomCell(short[] packed) { 140 CoordPacker.init(); 141 return CoordPacker.singleRandom(packed, rng); 142 } 143 144 /** 145 * A convenience wrapper for getting a packed-data representation of all floors ('.') in map, for randomCell(). 146 * If you want other chars or more chars than just the period, you can use CoordPacker.pack() with a char[][] map 147 * and one or more chars to find as the parameters. This is the same as calling {@code CoordPacker.pack(map, '.')}. 148 * 149 * @param map a char[][] that uses '.' to represent floors 150 * @return all floors in map in packed data format (a special short array) that can be given to randomCell() 151 */ 152 public static short[] packedFloors(char[][] map) { 153 CoordPacker.init(); 154 return CoordPacker.pack(map, '.'); 155 } 156 157 /** 158 * Finds a random Coord where the x and y match up to a [x][y] location on map that has the same value as the 159 * parameter tile. Uses this class' rng field for pseudo-random number generation. 160 * 161 * @param map a char[][] that should contain the desired tile 162 * @param tile the char to search for 163 * @return a Coord that corresponds to a map element equal to tile, or null if tile cannot be found or if map is too small. 164 */ 165 public Coord randomMatchingTile(char[][] map, char tile) { 166 int width = map.length; 167 int height = map[0].length; 168 if (width < 3 || height < 3) 169 return null; 170 int x = rng.nextInt(width - 2) + 1, y = rng.nextInt(height - 2) + 1; 171 for (int i = 0; i < 30; i++) { 172 if (map[x][y] == tile) { 173 return Coord.get(x, y); 174 } else { 175 x = rng.nextInt(width - 2) + 1; 176 y = rng.nextInt(height - 2) + 1; 177 } 178 } 179 x = 1; 180 y = 1; 181 if (map[x][y] == tile) 182 return Coord.get(x, y); 183 184 while (map[x][y] != tile) { 185 x += 1; 186 if (x >= width - 1) { 187 x = 1; 188 y += 1; 189 } 190 if (y >= height - 1) 191 return null; 192 } 193 return Coord.get(x, y); 194 } 195 196 /** 197 * Gets a random Coord that is adjacent to start, validating whether the position can exist on the given map. 198 * Adjacency defaults to four-way cardinal directions unless eightWay is true, in which case it uses Chebyshev. 199 * This can step into walls, and should NOT be used for movement. It is meant for things like sound that can 200 * exist in walls, or for assigning decor to floors or walls that are adjacent to floors. 201 * 202 * @param map a char[][] map that this will only use for its width and height; contents are ignored 203 * @param start the starting position 204 * @param eightWay true to choose a random orthogonal or diagonal direction; false to only choose from orthogonal 205 * @return a Coord that is adjacent to start on the map, or null if start is off the map or the map is very small 206 */ 207 public Coord randomStep(char[][] map, Coord start, boolean eightWay) { 208 int width = map.length; 209 int height = map[0].length; 210 if (width < 3 || height < 3 || start.x < 0 || start.y < 0 || start.x > width - 1 || start.y > height - 1) 211 return null; 212 Coord stepped = Coord.get(start.x, start.y); 213 214 if (eightWay) { 215 int mv = rng.nextInt(9); 216 return Coord.get(Math.min(Math.max(0, stepped.x + (mv % 3) - 1), height - 1), 217 Math.min(Math.max(0, stepped.y + (mv / 3) - 1), height - 1)); 218 } else { 219 int mv = rng.nextInt(5); 220 switch (mv) { 221 case 0: 222 return Coord.get(Math.min(Math.max(0, stepped.x - 1), height - 1), 223 stepped.y); 224 case 1: 225 return Coord.get(Math.min(Math.max(0, stepped.x + 1), height - 1), 226 stepped.y); 227 case 2: 228 return Coord.get(stepped.x, 229 Math.min(Math.max(0, stepped.y - 1), height - 1)); 230 case 3: 231 return Coord.get(stepped.x, 232 Math.min(Math.max(0, stepped.y + 1), height - 1)); 233 default: 234 return stepped; 235 } 236 } 237 } 238 239 /** 240 * Finds a random Coord where the x and y match up to a [x][y] location on map that has '.' as a value, 241 * and a square of cells extending in the positive x and y directions with a side length of size must also have 242 * '.' as their values. 243 * Uses this class' rng field for pseudo-random number generation. 244 * 245 * @param map a char[][] that should contain at least one floor represented by '.' 246 * @param size the side length of a square that must be completely filled with floors for this to return it 247 * @return a Coord that corresponds to a '.' in map, or null if a '.' cannot be found or if map is too small. 248 */ 249 public Coord randomFloorLarge(char[][] map, int size) { 250 int width = map.length; 251 int height = map[0].length; 252 if (width < size + 2 || height < size + 2) 253 return null; 254 int x = rng.nextInt(width - size), y = rng.nextInt(height - size); 255 CELL: 256 for (int i = 0; i < 20; i++, x = rng.nextInt(width - size), y = rng.nextInt(height - size)) { 257 if (map[x][y] == '.') { 258 for (int j = 0; j < size; j++) { 259 for (int k = 0; k < size; k++) { 260 if (map[x + j][y + k] != '.') 261 continue CELL; 262 } 263 } 264 return Coord.get(x, y); 265 } 266 } 267 x = 1; 268 y = 1; 269 270 SLOW: 271 while (true) { 272 x += 1; 273 if (x >= width - size) { 274 x = 1; 275 y += 1; 276 } 277 if (y >= height - size) 278 return null; 279 if (map[x][y] == '.') { 280 for (int j = 0; j < size; j++) { 281 for (int k = 0; k < size; k++) { 282 if (map[x + j][y + k] != '.') 283 continue SLOW; 284 } 285 } 286 return Coord.get(x, y); 287 } 288 } 289 } 290 291 /** 292 * Takes a char[][] dungeon map that uses '#' to represent walls, and returns a new char[][] that uses unicode box 293 * drawing characters to draw straight, continuous lines for walls, filling regions between walls (that were 294 * filled with more walls before) with space characters, ' '. If the lines "point the wrong way," such as having 295 * multiple horizontally adjacent vertical lines where there should be horizontal lines, call transposeLines() on 296 * the returned map, which will keep the dimensions of the map the same and only change the line chars. You will 297 * also need to call transposeLines if you call hashesToLines on a map that already has "correct" line-drawing 298 * characters, which means hashesToLines should only be called on maps that use '#' for walls. If you have a 299 * jumbled map that contains two or more of the following: "correct" line-drawing characters, "incorrect" 300 * line-drawing characters, and '#' characters for walls, you can reset by calling linesToHashes() and then 301 * potentially calling hashesToLines() again. 302 * 303 * @param map a 2D char array indexed with x,y that uses '#' for walls 304 * @return a copy of the map passed as an argument with box-drawing characters replacing '#' walls 305 */ 306 public static char[][] hashesToLines(char[][] map) { 307 return hashesToLines(map, false); 308 } 309 310 private static final char[] wallLookup = new char[] 311 { 312 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼', 313 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼', 314 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼', 315 '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '┴', '┐', '┤', '┬', '┤', 316 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼', 317 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼', 318 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '─', '┴', 319 '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '┴', '┐', '┤', '─', '┘', 320 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼', 321 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '─', '┐', '┤', '┬', '┬', 322 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼', 323 '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '─', '┐', '┤', '┬', '┐', 324 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '│', '┬', '├', 325 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '─', '┐', '│', '┬', '┌', 326 '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '│', '─', '└', 327 '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '─', '┐', '│', '─', '\1' 328 }; 329 330 /** 331 * Takes a char[][] dungeon map that uses '#' to represent walls, and returns a new char[][] that uses unicode box 332 * drawing characters to draw straight, continuous lines for walls, filling regions between walls (that were 333 * filled with more walls before) with space characters, ' '. If keepSingleHashes is true, then '#' will be used if 334 * a wall has no orthogonal wall neighbors; if it is false, then a horizontal line will be used for stand-alone 335 * wall cells. If the lines "point the wrong way," such as having multiple horizontally adjacent vertical lines 336 * where there should be horizontal lines, call transposeLines() on the returned map, which will keep the dimensions 337 * of the map the same and only change the line chars. You will also need to call transposeLines if you call 338 * hashesToLines on a map that already has "correct" line-drawing characters, which means hashesToLines should only 339 * be called on maps that use '#' for walls. If you have a jumbled map that contains two or more of the following: 340 * "correct" line-drawing characters, "incorrect" line-drawing characters, and '#' characters for walls, you can 341 * reset by calling linesToHashes() and then potentially calling hashesToLines() again. 342 * 343 * @param map a 2D char array indexed with x,y that uses '#' for walls 344 * @param keepSingleHashes true if walls that are not orthogonally adjacent to other walls should stay as '#' 345 * @return a copy of the map passed as an argument with box-drawing characters replacing '#' walls 346 */ 347 public static char[][] hashesToLines(char[][] map, boolean keepSingleHashes) { 348 int width = map.length + 2; 349 int height = map[0].length + 2; 350 351 char[][] dungeon = new char[width][height]; 352 for (int i = 1; i < width - 1; i++) { 353 System.arraycopy(map[i - 1], 0, dungeon[i], 1, height - 2); 354 } 355 for (int i = 0; i < width; i++) { 356 dungeon[i][0] = '\1'; 357 dungeon[i][height - 1] = '\1'; 358 } 359 for (int i = 0; i < height; i++) { 360 dungeon[0][i] = '\1'; 361 dungeon[width - 1][i] = '\1'; 362 } 363 for (int x = 1; x < width - 1; x++) { 364 for (int y = 1; y < height - 1; y++) { 365 if (map[x - 1][y - 1] == '#') { 366 int q = 0; 367 q |= (y <= 1 || map[x - 1][y - 2] == '#' || map[x - 1][y - 2] == '+' || map[x - 1][y - 2] == '/') ? 1 : 0; 368 q |= (x >= width - 2 || map[x][y - 1] == '#' || map[x][y - 1] == '+' || map[x][y - 1] == '/') ? 2 : 0; 369 q |= (y >= height - 2 || map[x - 1][y] == '#' || map[x - 1][y] == '+' || map[x - 1][y] == '/') ? 4 : 0; 370 q |= (x <= 1 || map[x - 2][y - 1] == '#' || map[x - 2][y - 1] == '+' || map[x - 2][y - 1] == '/') ? 8 : 0; 371 372 q |= (y <= 1 || x >= width - 2 || map[x][y - 2] == '#' || map[x][y - 2] == '+' || map[x][y - 2] == '/') ? 16 : 0; 373 q |= (y >= height - 2 || x >= width - 2 || map[x][y] == '#' || map[x][y] == '+' || map[x][y] == '/') ? 32 : 0; 374 q |= (y >= height - 2 || x <= 1 || map[x - 2][y] == '#' || map[x - 2][y] == '+' || map[x - 2][y] == '/') ? 64 : 0; 375 q |= (y <= 1 || x <= 1 || map[x - 2][y - 2] == '#' || map[x - 2][y - 2] == '+' || map[x - 2][y - 2] == '/') ? 128 : 0; 376 if (!keepSingleHashes && wallLookup[q] == '#') { 377 dungeon[x][y] = '─'; 378 } else { 379 dungeon[x][y] = wallLookup[q]; 380 } 381 } 382 } 383 } 384 char[][] portion = new char[width - 2][height - 2]; 385 for (int i = 1; i < width - 1; i++) { 386 for (int j = 1; j < height - 1; j++) { 387 if (dungeon[i][j] == '\1') { 388 portion[i - 1][j - 1] = ' '; 389 } else { 390 // ┼┌┘ 391 portion[i - 1][j - 1] = dungeon[i][j]; 392 } 393 } 394 } 395 return portion; 396 } 397 398 /** 399 * Reverses most of the effects of hashesToLines(). The only things that will not be reversed are the placement of 400 * space characters in unreachable wall-cells-behind-wall-cells, which remain as spaces. This is useful if you 401 * have a modified map that contains wall characters of conflicting varieties, as described in hashesToLines(). 402 * 403 * @param map a 2D char array indexed with x,y that uses box-drawing characters for walls 404 * @return a copy of the map passed as an argument with '#' replacing box-drawing characters for walls 405 */ 406 public static char[][] linesToHashes(char[][] map) { 407 408 int width = map.length; 409 int height = map[0].length; 410 char[][] portion = new char[width][height]; 411 for (int i = 0; i < width; i++) { 412 for (int j = 0; j < height; j++) { 413 switch (map[i][j]) { 414 case '\1': 415 case '├': 416 case '┤': 417 case '┴': 418 case '┬': 419 case '┌': 420 case '┐': 421 case '└': 422 case '┘': 423 case '│': 424 case '─': 425 case '┼': 426 portion[i][j] = '#'; 427 break; 428 default: 429 portion[i][j] = map[i][j]; 430 } 431 } 432 } 433 return portion; 434 } 435 436 /** 437 * If you call hashesToLines() on a map that uses [y][x] conventions instead of [x][y], it will have the lines not 438 * connect as you expect. Use this function to change the directions of the box-drawing characters only, without 439 * altering the dimensions in any way. This returns a new char[][], instead of modifying the parameter in place. 440 * transposeLines is also needed if the lines in a map have become transposed when they were already correct; 441 * calling this method on an incorrectly transposed map will change the directions on all of its lines. 442 * 443 * @param map a 2D char array indexed with y,x that uses box-drawing characters for walls 444 * @return a copy of map that uses box-drawing characters for walls that will be correct when indexed with x,y 445 */ 446 public static char[][] transposeLines(char[][] map) { 447 448 int width = map[0].length; 449 int height = map.length; 450 char[][] portion = new char[height][width]; 451 for (int i = 0; i < height; i++) { 452 for (int j = 0; j < width; j++) { 453 switch (map[i][j]) { 454 case '\1': 455 portion[i][j] = ' '; 456 break; 457 case '├': 458 portion[i][j] = '┬'; 459 break; 460 case '┤': 461 portion[i][j] = '┴'; 462 break; 463 case '┴': 464 portion[i][j] = '┤'; 465 break; 466 case '┬': 467 portion[i][j] = '├'; 468 break; 469 case '┐': 470 portion[i][j] = '└'; 471 break; 472 case '└': 473 portion[i][j] = '┐'; 474 break; 475 case '│': 476 portion[i][j] = '─'; 477 break; 478 case '─': 479 portion[i][j] = '│'; 480 break; 481 default: //applies to ┼┌┘ and any non-box-drawing 482 portion[i][j] = map[i][j]; 483 } 484 } 485 } 486 return portion; 487 } 488 // case '├ ┤ ┴ ┬ ┌ ┐ └ ┘ │ ─': 489 /** 490 * When a map is generated by DungeonGenerator with addDoors enabled, different chars are used for vertical and 491 * horizontal doors ('+' for vertical and '/' for horizontal). This makes all doors '+', which is useful if you 492 * want '/' to be used for a different purpose and/or to distinguish open and closed doors. 493 * 494 * @param map a char[][] that may have both '+' and '/' for doors 495 * @return a char[][] that only uses '+' for all doors 496 */ 497 public static char[][] closeDoors(char[][] map) { 498 499 int width = map.length; 500 int height = map[0].length; 501 char[][] portion = new char[width][height]; 502 for (int i = 0; i < width; i++) { 503 for (int j = 0; j < height; j++) { 504 if (map[i][j] == '/') portion[i][j] = '+'; 505 else portion[i][j] = map[i][j]; 506 507 } 508 } 509 return portion; 510 } 511 512 /** 513 * When a map is generated by DungeonGenerator with addDoors enabled, different chars are used for vertical and 514 * horizontal doors ('+' for vertical and '/' for horizontal). This makes all doors '/', which is useful if you 515 * want '+' to be used for a different purpose and/or to distinguish open and closed doors. 516 * 517 * @param map a char[][] that may have both '+' and '/' for doors 518 * @return a char[][] that only uses '/' for all doors 519 */ 520 public static char[][] openDoors(char[][] map) { 521 522 int width = map.length; 523 int height = map[0].length; 524 char[][] portion = new char[width][height]; 525 for (int i = 0; i < width; i++) { 526 for (int j = 0; j < height; j++) { 527 if (map[i][j] == '+') portion[i][j] = '/'; 528 else portion[i][j] = map[i][j]; 529 } 530 } 531 return portion; 532 } 533 534 535 /** 536 * Takes a char[][] dungeon map and returns a copy with all box drawing chars, special placeholder chars, or '#' 537 * chars changed to '#' and everything else changed to '.' . 538 * 539 * @param map a char[][] with different characters that can be simplified to "wall" or "floor" 540 * @return a copy of map with all box-drawing, placeholder, wall or space characters as '#' and everything else '.' 541 */ 542 public static char[][] simplifyDungeon(char[][] map) { 543 544 int width = map.length; 545 int height = map[0].length; 546 char[][] portion = new char[width][height]; 547 for (int i = 0; i < width; i++) { 548 for (int j = 0; j < height; j++) { 549 switch (map[i][j]) { 550 case '\1': 551 case '├': 552 case '┤': 553 case '┴': 554 case '┬': 555 case '┌': 556 case '┐': 557 case '└': 558 case '┘': 559 case '│': 560 case '─': 561 case '┼': 562 case ' ': 563 case '#': 564 portion[i][j] = '#'; 565 break; 566 default: 567 portion[i][j] = '.'; 568 } 569 } 570 } 571 return portion; 572 } 573 574 /** 575 * Takes a dungeon map with either '#' as the only wall character or the unicode box drawing characters used by 576 * hashesToLines(), and returns a new char[][] dungeon map with two characters per cell, mostly filling the spaces 577 * next to non-walls with space characters, and only doing anything different if a box-drawing character would 578 * continue into an adjacent cell, or if a '#' wall needs another '#' wall next to it. The recommended approach is 579 * to keep both the original non-double-width map and the newly-returned double-width map, since the single-width 580 * maps can be used more easily for pathfinding. If you need to undo this function, call unDoubleWidth(). 581 * 582 * @param map a char[][] that uses either '#' or box-drawing characters for walls, but one per cell 583 * @return a widened copy of map that uses two characters for every cell, connecting box-drawing chars correctly 584 */ 585 public static char[][] doubleWidth(char[][] map) { 586 int width = map.length; 587 int height = map[0].length; 588 char[][] paired = new char[width * 2][height]; 589 for (int y = 0; y < height; y++) { 590 for (int x = 0, px = 0; x < width; x++, px += 2) { 591 paired[px][y] = map[x][y]; 592 switch (paired[px][y]) { 593 // case '┼ ├ ┤ ┴ ┬ ┌ ┐ └ ┘ │ ─' 594 case '┼': 595 case '├': 596 case '┴': 597 case '┬': 598 case '┌': 599 case '└': 600 case '─': 601 paired[px + 1][y] = '─'; 602 break; 603 case '#': 604 paired[px + 1][y] = '#'; 605 break; 606 607 default: 608 paired[px + 1][y] = ' '; 609 break; 610 /* 611 case '.': 612 case '┤': 613 case '┐': 614 case '┘': 615 case '│': 616 */ 617 } 618 } 619 } 620 return paired; 621 } 622 623 /** 624 * Takes a dungeon map that uses two characters per cell, and condenses it to use only the left (lower index) 625 * character in each cell. This should (probably) only be called on the result of doubleWidth(), and will throw an 626 * exception if called on a map with an odd number of characters for width, such as "#...#" . 627 * 628 * @param map a char[][] that has been widened by doubleWidth() 629 * @return a copy of map that uses only one char per cell 630 */ 631 public static char[][] unDoubleWidth(char[][] map) { 632 int width = map.length; 633 int height = map[0].length; 634 if (width % 2 != 0) 635 throw new IllegalArgumentException("Argument must be a char[width][height] with an even width."); 636 char[][] unpaired = new char[width / 2][height]; 637 for (int y = 0; y < height; y++) { 638 for (int x = 0, px = 0; px < width; x++, px += 2) { 639 unpaired[x][y] = map[px][y]; 640 } 641 } 642 return unpaired; 643 } 644 645 646 /** 647 * Given a char[][] for the map, produces a double[][] that can be used with FOV.calculateFOV(). It expects any 648 * doors to be represented by '+' if closed or '/' if open (which can be caused by calling 649 * DungeonUtility.closeDoors() ), any walls to be '#' or box drawing characters, and it doesn't care what other 650 * chars are used (only doors, including open ones, and walls obscure light and thus have a resistance by default). 651 * <br> 652 * This is here for backwards-compatibility; this method delegates to {@link FOV#generateResistances(char[][])}. 653 * 654 * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() 655 * @return a resistance map suitable for use with the FOV class, with clear cells assigned 0.0 and blocked ones 1.0 656 */ 657 public static double[][] generateResistances(char[][] map) { 658 return FOV.generateResistances(map); 659 } 660 661 /** 662 * Given a char[][] for the map that should use box drawing characters (as produced by 663 * {@link #hashesToLines(char[][], boolean)}), produces a double[][] with triple width and triple height that can be 664 * used with FOV.calculateFOV() in classes that use subcell lighting. Importantly, this only considers a "thin line" 665 * of wall to be blocking (matching the box drawing character), instead of the whole 3x3 area. This expects any 666 * doors to be represented by '+' if closed or '/' if open (which can be caused by calling 667 * {@link #closeDoors(char[][])}), thick vegetation or other concealing obstructions to be '"', any normal walls to 668 * be box drawing characters, any cells that block all subcells to be '#', and it doesn't care what other chars are 669 * used (only doors, including open ones, vegetation, and walls obscure light and thus have a resistance normally). 670 * <br> 671 * This is here for backwards-compatibility; this method delegates to {@link FOV#generateResistances3x3(char[][])} 672 * 673 * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() 674 * @return a resistance map suitable for use with the FOV class and subcell lighting, with triple width/height 675 */ 676 public static double[][] generateResistances3x3(char[][] map) { 677 return FOV.generateResistances3x3(map); 678 } 679 680 /** 681 * Given a char[][] for the map, produces a double[][] that can be used with FOV.calculateFOV(), but does not treat 682 * any cells as partly transparent, only fully-blocking or fully-permitting light. This is mainly useful if you 683 * expect the FOV radius to be very high or (effectively) infinite, since anything less than complete blockage would 684 * be passed through by infinite-radius FOV. This expects any doors to be represented by '+' if closed or '/' if 685 * open (most door placement defaults to a mix of '+' and '/', so by calling 686 * {@link DungeonUtility#closeDoors(char[][])} you can close all doors at the start), and any walls to be '#' or 687 * box drawing characters. This will assign 1.0 resistance to walls and closed doors or 0.0 for any other cell. 688 * <br> 689 * This is here for backwards-compatibility; this method delegates to {@link FOV#generateSimpleResistances(char[][])}. 690 * 691 * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() 692 * @return a resistance map suitable for use with the FOV class, but with no partially transparent cells 693 */ 694 public static double[][] generateSimpleResistances(char[][] map) { 695 return FOV.generateSimpleResistances(map); 696 } 697 698 /** 699 * Given a char[][] for the map that should use box drawing characters (as produced by 700 * {@link #hashesToLines(char[][], boolean)}), produces a double[][] with triple width and triple height that can be 701 * used with FOV.calculateFOV() in classes that use subcell lighting. This expects any doors to be represented by 702 * '+' if closed or '/' if open (most door placement defaults to a mix of '+' and '/', so by calling 703 * {@link DungeonUtility#closeDoors(char[][])} you can close all doors at the start), any walls to be box drawing 704 * characters, and any cells that block all subcells within their area to be '#'. This will assign 1.0 resistance to 705 * walls and closed doors where a line of the box drawing char would block light, or 0.0 for any other subcell. 706 * <br> 707 * This is here for backwards-compatibility; this method delegates to {@link FOV#generateSimpleResistances3x3(char[][])}. 708 * 709 * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() 710 * @return a resistance map suitable for use with the FOV class and subcell lighting, with triple width/height 711 */ 712 public static double[][] generateSimpleResistances3x3(char[][] map) { 713 return FOV.generateSimpleResistances3x3(map); 714 } 715 716 /** 717 * Given a char[][] for the map, a Map of Character keys to Double values that will be used to determine costs, and 718 * a double value for unhandled characters, produces a double[][] that can be used as a costMap by DijkstraMap. It 719 * expects any doors to be represented by '+' if closed or '/' if open (which can be caused by calling 720 * DungeonUtility.closeDoors() ) and any walls to be '#' or box drawing characters. In the parameter costs, there 721 * does not need to be an entry for '#' or any box drawing characters, but if one is present for '#' it will apply 722 * that cost to both '#' and all box drawing characters, and if one is not present it will default to a very high 723 * number. For any other entry in costs, a char in the 2D char array that matches the key will correspond 724 * (at the same x,y position in the returned 2D double array) to that key's value in costs. If a char is used in the 725 * map but does not have a corresponding key in costs, it will be given the value of the parameter defaultValue. 726 * <p/> 727 * The values in costs are multipliers, so should not be negative, should only be 0.0 in cases where you want 728 * infinite movement across all adjacent squares of that kind, should be higher than 1.0 for difficult terrain (2.0 729 * and 3.0 are reasonable), should be between 0.0 and 1.0 for easy terrain, and should be 1.0 for normal terrain. 730 * If a cell should not be possible to enter for this character, 999.0 should be a reasonable value for a cost. 731 * <p/> 732 * An example use for this would be to make a creature unable to enter any non-water cell (like a fish), 733 * unable to enter doorways (like some mythological versions of vampires), or to make a wheeled vehicle take more 734 * time to move across rubble or rough terrain. 735 * <p/> 736 * A potentially common case that needs to be addressed is NPC movement onto staircases in games that have them; 737 * some games may find it desirable for NPCs to block staircases and others may not, but in either case you should 738 * give both '>' and '<', the standard characters for staircases, the same value in costs. 739 * 740 * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() . 741 * @param costs a Map of Character keys representing possible elements in map, and Double values for their cost. 742 * @param defaultValue a double that will be used as the cost for any characters that don't have a key in costs. 743 * @return a cost map suitable for use with DijkstraMap 744 */ 745 public static double[][] generateCostMap(char[][] map, Map<Character, Double> costs, double defaultValue) { 746 int width = map.length; 747 int height = map[0].length; 748 double[][] portion = new double[width][height]; 749 char current; 750 for (int i = 0; i < width; i++) { 751 for (int j = 0; j < height; j++) { 752 current = map[i][j]; 753 if (costs.containsKey(current)) { 754 portion[i][j] = costs.get(current); 755 } else { 756 switch (current) { 757 case '\1': 758 case '├': 759 case '┤': 760 case '┴': 761 case '┬': 762 case '┌': 763 case '┐': 764 case '└': 765 case '┘': 766 case '│': 767 case '─': 768 case '┼': 769 case '#': 770 portion[i][j] = (costs.containsKey('#')) 771 ? costs.get('#') 772 : squidpony.squidai.DijkstraMap.WALL; 773 break; 774 default: 775 portion[i][j] = defaultValue; 776 } 777 } 778 } 779 } 780 return portion; 781 } 782 783 /** 784 * Given a char[][] for the map, produces a double[][] that can be used as a map by AStarSearch. It 785 * expects any doors to be represented by '+' if closed or '/' if open (which can be ensured by calling 786 * {@link #closeDoors(char[][])}) and any walls to be '#' or box drawing characters. Any wall or closed door will be 787 * assigned a negative number, meaning it is impassable for AStarSearch, and all other chars will be assigned 1.0, 788 * giving them a normal cost. 789 * 790 * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() . 791 * @return a cost map suitable for use with AStarSearch 792 */ 793 public static double[][] generateAStarCostMap(char[][] map) { 794 int width = map.length; 795 int height = map[0].length; 796 double[][] portion = new double[width][height]; 797 for (int i = 0; i < width; i++) { 798 for (int j = 0; j < height; j++) { 799 switch (map[i][j]) { 800 case '\1': 801 case '├': 802 case '┤': 803 case '┴': 804 case '┬': 805 case '┌': 806 case '┐': 807 case '└': 808 case '┘': 809 case '│': 810 case '─': 811 case '┼': 812 case '#': 813 case '+': 814 portion[i][j] = -1; 815 break; 816 default: 817 portion[i][j] = 1; 818 } 819 } 820 } 821 return portion; 822 } 823 824 /** 825 * Given a char[][] for the map, a Map of Character keys to Double values that will be used to determine costs, and 826 * a double value for unhandled characters, produces a double[][] that can be used as a map by AStarSearch. It 827 * expects any doors to be represented by '+' if closed or '/' if open (which can be caused by calling 828 * DungeonUtility.closeDoors() ) and any walls to be '#' or box drawing characters. In the parameter costs, there 829 * does not need to be an entry for '#' or any box drawing characters, but if one is present for '#' it will apply 830 * that cost to both '#' and all box drawing characters, and if one is not present it will default to a negative 831 * number, meaning it is impassable for AStarSearch. For any other entry in costs, a char in the 2D char array that 832 * matches the key will correspond (at the same x,y position in the returned 2D double array) to that key's value in 833 * costs. If a char is used in the map but does not have a corresponding key in costs, it will be given the value of 834 * the parameter defaultValue, which is typically 1 unless a creature is limited to only moving in some terrain. 835 * <p/> 836 * The values in costs are different from those expected for DijkstraMap; negative numbers are impassable, 1 is the 837 * cost for a normal walkable tile, and higher numbers are harder to enter. 838 * <p/> 839 * An example use for this would be to make a creature unable to enter any non-water cell (like a fish), 840 * unable to enter doorways (like some mythological versions of vampires), or to make a wheeled vehicle take more 841 * time to move across rubble or rough terrain. 842 * <p/> 843 * A potentially common case that needs to be addressed is NPC movement onto staircases in games that have them; 844 * some games may find it desirable for NPCs to block staircases and others may not, but in either case you should 845 * give both '>' and '<', the standard characters for staircases, the same value in costs. 846 * 847 * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() . 848 * @param costs a Map of Character keys representing possible elements in map, and Double values for their cost. 849 * @param defaultValue a double that will be used as the cost for any characters that don't have a key in costs. 850 * @return a cost map suitable for use with AStarSearch 851 */ 852 public static double[][] generateAStarCostMap(char[][] map, Map<Character, Double> costs, double defaultValue) { 853 int width = map.length; 854 int height = map[0].length; 855 double[][] portion = new double[width][height]; 856 char current; 857 for (int i = 0; i < width; i++) { 858 for (int j = 0; j < height; j++) { 859 current = map[i][j]; 860 if (costs.containsKey(current)) { 861 portion[i][j] = costs.get(current); 862 } else { 863 switch (current) { 864 case '\1': 865 case '├': 866 case '┤': 867 case '┴': 868 case '┬': 869 case '┌': 870 case '┐': 871 case '└': 872 case '┘': 873 case '│': 874 case '─': 875 case '┼': 876 case '#': 877 portion[i][j] = (costs.containsKey('#')) 878 ? costs.get('#') 879 : -1; 880 break; 881 default: 882 portion[i][j] = defaultValue; 883 } 884 } 885 } 886 } 887 return portion; 888 } 889 890 public static double[][] translateAStarToDijkstra(double[][] astar) { 891 if (astar == null) return null; 892 if (astar.length <= 0 || astar[0].length <= 0) 893 return new double[0][0]; 894 double[][] dijkstra = new double[astar.length][astar[0].length]; 895 for (int x = 0; x < astar.length; x++) { 896 for (int y = 0; y < astar[x].length; y++) { 897 if (astar[x][y] <= 0) 898 dijkstra[x][y] = DijkstraMap.WALL; 899 else 900 dijkstra[x][y] = DijkstraMap.FLOOR; 901 } 902 } 903 return dijkstra; 904 } 905 906 public static double[][] translateDijkstraToAStar(double[][] dijkstra) { 907 if (dijkstra == null) return null; 908 if (dijkstra.length <= 0 || dijkstra[0].length <= 0) 909 return new double[0][0]; 910 double[][] astar = new double[dijkstra.length][dijkstra[0].length]; 911 for (int x = 0; x < dijkstra.length; x++) { 912 for (int y = 0; y < dijkstra[x].length; y++) { 913 if (dijkstra[x][y] > DijkstraMap.FLOOR) 914 astar[x][y] = -1; 915 else 916 astar[x][y] = 1; 917 } 918 } 919 return astar; 920 } 921 922 /** 923 * @param rng 924 * @param map 925 * @param acceptable 926 * @param frustration The number of trials that this method can do. Usually 16 or 927 * 32. 928 * @return A random cell in {@code map} whose symbol is in 929 * {@code acceptable}. Or {@code null} if not found. 930 */ 931 public static /* @Nullable */Coord getRandomCell(IRNG rng, char[][] map, Set<Character> acceptable, 932 int frustration) { 933 if (frustration < 0) 934 throw new IllegalStateException("Frustration should not be negative"); 935 final int width = map.length; 936 final int height = width == 0 ? 0 : map[0].length; 937 if (width == 0 || height == 0) 938 throw new IllegalStateException("Map must be non-empty to get a cell from it"); 939 int i = 0; 940 while (i < frustration) { 941 final int x = rng.nextInt(width); 942 final int y = rng.nextInt(height); 943 if (acceptable.contains(map[x][y])) 944 return Coord.get(x, y); 945 i++; 946 } 947 return null; 948 } 949 950 /** 951 * @param level dungeon/map level as 2D char array. x,y indexed 952 * @param c Coord to check 953 * @return {@code true} if {@code c} is valid in {@code level}, {@code false} otherwise. 954 */ 955 public static boolean inLevel(char[][] level, Coord c) { 956 return inLevel(level, c.x, c.y); 957 } 958 959 /** 960 * @param level dungeon/map level as 2D char array. x,y indexed 961 * @param x x coordinate to check 962 * @param y y coordinate to check 963 * @return {@code true} if {@code c} is valid in {@code level}, {@code false} otherwise. 964 */ 965 public static boolean inLevel(char[][] level, int x, int y) { 966 return 0 <= x && x < level.length && 0 <= y && y < level[x].length; 967 } 968 969 /** 970 * @param level dungeon/map level as 2D double array. x,y indexed 971 * @param c Coord to check 972 * @return {@code true} if {@code c} is valid in {@code level}, {@code false} otherwise. 973 */ 974 public static boolean inLevel(double[][] level, Coord c) { 975 return inLevel(level, c.x, c.y); 976 } 977 978 /** 979 * @param level dungeon/map level as 2D double array. x,y indexed 980 * @param x x coordinate to check 981 * @param y y coordinate to check 982 * @return {@code true} if {@code c} is valid in {@code level}, {@code false} otherwise. 983 */ 984 public static boolean inLevel(double[][] level, int x, int y) { 985 return 0 <= x && x < level.length && 0 <= y && y < level[x].length; 986 } 987 988 /** 989 * @param level a dungeon/map level as 2D array. x,y indexed 990 * @param c Coord to check 991 * @return {@code true} if {@code c} is valid in {@code level}, {@code false} otherwise. 992 */ 993 public static <T> boolean inLevel(T[][] level, Coord c) { 994 return inLevel(level, c.x, c.y); 995 } 996 997 /** 998 * @param level a dungeon/map level as 2D array. x,y indexed 999 * @param x x coordinate to check 1000 * @param y y coordinate to check 1001 * @return {@code true} if {@code c} is valid in {@code level}, {@code false} otherwise. 1002 */ 1003 public static <T> boolean inLevel(T[][] level, int x, int y) { 1004 return 0 <= x && x < level.length && 0 <= y && y < level[x].length; 1005 } 1006 1007 /** 1008 * Quickly counts the number of char elements in level that are equal to match. 1009 * 1010 * @param level the 2D char array to count cells in 1011 * @param match the char to search for 1012 * @return the number of cells that matched 1013 */ 1014 public static int countCells(char[][] level, char match) { 1015 if (level == null || level.length == 0) 1016 return 0; 1017 int counter = 0; 1018 for (int x = 0; x < level.length; x++) { 1019 for (int y = 0; y < level[x].length; y++) { 1020 if (level[x][y] == match) counter++; 1021 } 1022 } 1023 return counter; 1024 } 1025 1026 /** 1027 * For when you want to print a 2D char array. Prints on multiple lines, with a trailing newline. 1028 * 1029 * @param level a 2D char array to print with a trailing newline 1030 */ 1031 public static void debugPrint(char[][] level) { 1032 if (level == null || level.length == 0 || level[0].length == 0) 1033 System.out.println("INVALID DUNGEON LEVEL"); 1034 else { 1035 for (int y = 0; y < level[0].length; y++) { 1036 for (int x = 0; x < level.length; x++) { 1037 System.out.print(level[x][y]); 1038 } 1039 System.out.println(); 1040 1041 } 1042 } 1043 } 1044 1045 /** 1046 * Changes the outer edge of a char[][] to the wall char, '#'. 1047 * 1048 * @param map A char[][] that stores map data; will be modified in place 1049 * @return the modified-in-place map with its edge replaced with '#' 1050 */ 1051 public static char[][] wallWrap(char[][] map) { 1052 int upperY = map[0].length - 1; 1053 int upperX = map.length - 1; 1054 for (int i = 0; i < map.length; i++) { 1055 map[i][0] = '#'; 1056 map[i][upperY] = '#'; 1057 } 1058 for (int i = 0; i < map[0].length; i++) { 1059 map[0][i] = '#'; 1060 map[upperX][i] = '#'; 1061 } 1062 return map; 1063 } 1064 public static ArrayList<Coord> pointPath(int width, int height, IRNG rng) { 1065 if (width <= 2 || height <= 2) 1066 throw new IllegalArgumentException("width and height must be greater than 2"); 1067 CoordPacker.init(); 1068 long columnAlterations = (rng.nextLong() & 0xFFFFFFFFFFFFL); 1069 float columnBase = width / (Long.bitCount(columnAlterations) + 48.0f); 1070 long rowAlterations = (rng.nextLong() & 0xFFFFFFFFFFFFL); 1071 float rowBase = height / (Long.bitCount(rowAlterations) + 48.0f); 1072 1073 int[] columns = new int[16], rows = new int[16]; 1074 int csum = 0, rsum = 0; 1075 long b = 7; 1076 for (int i = 0; i < 16; i++, b <<= 3) { 1077 columns[i] = csum + (int) (columnBase * 0.5f * (3 + Long.bitCount(columnAlterations & b))); 1078 csum += (int) (columnBase * (3 + Long.bitCount(columnAlterations & b))); 1079 rows[i] = rsum + (int) (rowBase * 0.5f * (3 + Long.bitCount(rowAlterations & b))); 1080 rsum += (int) (rowBase * (3 + Long.bitCount(rowAlterations & b))); 1081 } 1082 int cs = width - csum; 1083 int rs = height - rsum; 1084 int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs; 1085 for (int i = 0; i <= 7; i++) { 1086 cs2 = 0; 1087 rs2 = 0; 1088 columns[i] -= cs2; 1089 rows[i] -= rs2; 1090 } 1091 for (int i = 15; i >= 8; i--) { 1092 cs3 = cs3 * (i - 8) >> 3; 1093 rs3 = rs3 * (i - 8) >> 3; 1094 columns[i] += cs3; 1095 rows[i] += rs3; 1096 } 1097 1098 ArrayList<Coord> points = new ArrayList<>(80); 1099 int m = rng.nextInt(64); 1100 Coord temp = CoordPacker.mooreToCoord(m), next; 1101 temp = Coord.get(columns[temp.x], rows[temp.y]); 1102 for (int i = 0, r; i < 256; r = rng.between(4, 12), i += r, m += r) { 1103 next = CoordPacker.mooreToCoord(m); 1104 next = Coord.get(columns[next.x], rows[next.y]); 1105 points.addAll(OrthoLine.line(temp, next)); 1106 temp = next; 1107 } 1108 points.add(points.get(0)); 1109 return points; 1110 } 1111 1112 /** 1113 * Ensures a path exists in a rough ring around the map by first creating the path (using 1114 * {@link #pointPath(int, int, IRNG)} with the given IRNG), then finding chars in blocking that are on that path and 1115 * replacing them with replacement. Modifies map in-place (!) and returns an ArrayList of Coord points that will 1116 * always be on the path. 1117 * 1118 * @param map a 2D char array, x then y, etc. that will be modified directly; this is the "returned map" 1119 * @param rng used for random factors in the path choice 1120 * @param replacement the char that will fill be used where a path needs to be carved out; usually '.' 1121 * @param blocking an array or vararg of char that are considered blocking for the path and will be replaced if 1122 * they are in the way 1123 * @return the ArrayList of Coord points that are on the carved path, including existing non-blocking cells; will be empty if any parameters are invalid 1124 */ 1125 public static ArrayList<Coord> ensurePath(char[][] map, IRNG rng, char replacement, char... blocking) { 1126 if (map == null || map.length <= 0 || blocking == null || blocking.length <= 0) 1127 return new ArrayList<Coord>(0); 1128 int width = map.length, height = map[0].length; 1129 ArrayList<Coord> points = pointPath(width, height, rng); 1130 char[] blocks = new char[blocking.length]; 1131 System.arraycopy(blocking, 0, blocks, 0, blocking.length); 1132 Arrays.sort(blocks); 1133 for (Coord c : points) { 1134 if (c.x >= 0 && c.x < width && c.y >= 0 && c.y < height && Arrays.binarySearch(blocks, map[c.x][c.y]) >= 0) { 1135 map[c.x][c.y] = replacement; 1136 } 1137 } 1138 return points; 1139 } 1140 1141 public static ArrayList<Coord> allMatching(char[][] map, char... matching) { 1142 if (map == null || map.length <= 0 || matching == null || matching.length <= 0) 1143 return new ArrayList<Coord>(0); 1144 int width = map.length, height = map[0].length; 1145 char[] matches = new char[matching.length]; 1146 System.arraycopy(matching, 0, matches, 0, matching.length); 1147 Arrays.sort(matches); 1148 ArrayList<Coord> points = new ArrayList<Coord>(map.length * 4); 1149 for (int x = 0; x < width; x++) { 1150 for (int y = 0; y < height; y++) { 1151 if (Arrays.binarySearch(matches, map[x][y]) >= 0) 1152 points.add(Coord.get(x, y)); 1153 } 1154 } 1155 return points; 1156 } 1157 1158 /** 1159 * Gets a List of Coord that are within radius distance of (x,y), and appends them to buf if it is non-null or makes 1160 * a fresh List to append to otherwise. Returns buf if non-null, else the fresh List of Coord. May produce Coord 1161 * values that are not within the boundaries of a map, such as (-5,-4), if the center is too close to the edge or 1162 * radius is too high. You can use {@link squidpony.squidgrid.Radius#inCircle(int, int, int, boolean, int, int, List)} 1163 * with surpassEdges as false if you want to limit Coords to within the map, or the more general 1164 * {@link squidpony.squidgrid.Radius#pointsInside(int, int, int, boolean, int, int, List)} on a Radius.SQUARE or 1165 * Radius.DIAMOND enum value if you want a square or diamond shape. 1166 * 1167 * @param x center x of the circle 1168 * @param y center y of the circle 1169 * @param radius inclusive radius to extend from the center; radius 0 gives just the center 1170 * @param buf Where to add the coordinates, or null for this method to 1171 * allocate a fresh list. 1172 * @return The coordinates of a circle centered {@code (x, y)}, whose 1173 * diameter is {@code (radius * 2) + 1}. 1174 * @see squidpony.squidgrid.Radius#inCircle(int, int, int, boolean, int, int, List) if you want to keep the Coords within the bounds of the map 1175 */ 1176 public static List<Coord> circle(int x, int y, int radius, /* @Nullable */ List<Coord> buf) { 1177 final List<Coord> result = buf == null ? new ArrayList<Coord>() : buf; 1178 radius = Math.max(0, radius); 1179 for (int dx = -radius; dx <= radius; ++dx) { 1180 final int high = (int) Math.floor(Math.sqrt(radius * radius - dx * dx)); 1181 for (int dy = -high; dy <= high; ++dy) { 1182 result.add(Coord.get(x + dx, y + dy)); 1183 } 1184 } 1185 return result; 1186 } 1187}