001package squidpony.squidgrid.mapping; 002 003import squidpony.GwtCompatibility; 004import squidpony.squidmath.Coord; 005import squidpony.squidmath.RegionMap; 006 007import java.util.ArrayList; 008import java.util.Arrays; 009import java.util.LinkedHashSet; 010import java.util.List; 011 012import static squidpony.squidmath.CoordPacker.*; 013 014/** 015 * A small class that can analyze a dungeon or other map and identify areas as being "room" or "corridor" based on how 016 * thick the walkable areas are (corridors are at most 2 cells wide at their widest, rooms are anything else). Most 017 * methods of this class return 2D char arrays or Lists thereof, with the subset of the map that is in a specific region 018 * kept the same, but everything else replaced with '#'. 019 * Created by Tommy Ettinger on 2/3/2016. 020 * 021 * @see RectangleRoomFinder A simpler but faster alternative 022 */ 023public class RoomFinder { 024 /** 025 * A copy of the dungeon map, however it was passed to the constructor. 026 */ 027 public char[][] map, 028 /** 029 * A simplified version of the dungeon map, using '#' for walls and '.' for floors. 030 */ 031 basic; 032 /** 033 * Not likely to be used directly, but there may be things you can do with these that are cumbersome using only 034 * RoomFinder's simpler API. 035 */ 036 public RegionMap<List<short[]>> rooms, 037 /** 038 * Not likely to be used directly, but there may be things you can do with these that are cumbersome using only 039 * RoomFinder's simpler API. 040 */ 041 corridors, 042 /** 043 * Not likely to be used directly, but there may be things you can do with these that are cumbersome using only 044 * RoomFinder's simpler API. Won't be assigned a value if this class is constructed with a 2D char array; it needs 045 * the two-arg constructor using the environment produced by a MixedGenerator, SerpentMapGenerator, or similar. 046 */ 047 caves; 048 /** 049 * When a RoomFinder is constructed, it stores all points of rooms that are adjacent to another region here. 050 */ 051 public Coord[] connections, 052 /** 053 * Potential doorways, where a room is adjacent to a corridor. 054 */ 055 doorways, 056 /** 057 * Cave mouths, where a cave is adjacent to another type of terrain. 058 */ 059 mouths; 060 public int width, height; 061 062 /** 063 * Constructs a RoomFinder given a dungeon map, and finds rooms, corridors, and their connections on the map. Does 064 * not find caves; if a collection of caves is requested from this, it will be non-null but empty. 065 * @param dungeon a 2D char array that uses '#' for walls. 066 */ 067 public RoomFinder(char[][] dungeon) 068 { 069 if(dungeon.length <= 0) 070 return; 071 width = dungeon.length; 072 height = dungeon[0].length; 073 map = new char[width][height]; 074 for (int i = 0; i < width; i++) { 075 System.arraycopy(dungeon[i], 0, map[i], 0, height); 076 } 077 rooms = new RegionMap<>(32); 078 corridors = new RegionMap<>(32); 079 caves = new RegionMap<>(8); 080 basic = DungeonUtility.simplifyDungeon(map); 081 short[] floors = pack(basic, '.'), 082 r = flood(floors, retract(floors, 1, width, height, true), 2, false), 083 c = differencePacked(floors, r), 084 d = intersectPacked(r, fringe(c, 1, width, height, false)); 085 connections = doorways = allPacked(d); 086 mouths = new Coord[0]; 087 List<short[]> rs = split(r), cs = split(c); 088 089 short[][] ra = rs.toArray(new short[rs.size()][]), 090 ca = cs.toArray(new short[cs.size()][]); 091 092 for (short[] sep : cs) { 093 short[] someDoors = intersectPacked(r, fringe(sep, 1, width, height, false)); 094 short[] doors = allPackedHilbert(someDoors); 095 List<short[]> near = new ArrayList<short[]>(4); 096 for (int j = 0; j < doors.length; j++) { 097 near.addAll(findManyPackedHilbert(doors[j], ra)); 098 } 099 corridors.put(sep, near); 100 } 101 102 for (short[] sep : rs) { 103 List<short[]> near = new ArrayList<short[]>(10); 104 short[] aroundDoors = intersectPacked(c, fringe(sep, 1, width, height, false)); 105 short[] doors = allPackedHilbert(aroundDoors); 106 for (int j = 0; j < doors.length; j++) { 107 near.addAll(findManyPackedHilbert(doors[j], ca)); 108 } 109 rooms.put(sep, near); 110 } 111 } 112 113 public RoomFinder(char[][] dungeon, int environmentKind) 114 { 115 if(dungeon.length <= 0) 116 return; 117 width = dungeon.length; 118 height = dungeon[0].length; 119 map = new char[width][height]; 120 for (int i = 0; i < width; i++) { 121 System.arraycopy(dungeon[i], 0, map[i], 0, height); 122 } 123 rooms = new RegionMap<>(32); 124 corridors = new RegionMap<>(32); 125 caves = new RegionMap<>(8); 126 basic = DungeonUtility.simplifyDungeon(map); 127 128 if(environmentKind == MixedGenerator.ROOM_FLOOR) { 129 short[] floors = pack(basic, '.'), 130 r = flood(floors, retract(floors, 1, width, height, true), 2, false), 131 c = differencePacked(floors, r), 132 d = intersectPacked(r, fringe(c, 1, width, height, false)); 133 connections = doorways = allPacked(d); 134 mouths = new Coord[0]; 135 List<short[]> rs = split(r), cs = split(c); 136 137 short[][] ra = rs.toArray(new short[rs.size()][]), 138 ca = cs.toArray(new short[cs.size()][]); 139 140 for (short[] sep : cs) { 141 short[] someDoors = intersectPacked(r, fringe(sep, 1, width, height, false)); 142 short[] doors = allPackedHilbert(someDoors); 143 List<short[]> near = new ArrayList<short[]>(4); 144 for (int j = 0; j < doors.length; j++) { 145 near.addAll(findManyPackedHilbert(doors[j], ra)); 146 } 147 corridors.put(sep, near); 148 } 149 150 for (short[] sep : rs) { 151 List<short[]> near = new ArrayList<short[]>(10); 152 short[] aroundDoors = intersectPacked(c, fringe(sep, 1, width, height, false)); 153 short[] doors = allPackedHilbert(aroundDoors); 154 for (int j = 0; j < doors.length; j++) { 155 near.addAll(findManyPackedHilbert(doors[j], ca)); 156 } 157 rooms.put(sep, near); 158 } 159 } 160 else 161 { 162 short[] floors = pack(basic, '.'); 163 caves.put(floors, new ArrayList<short[]>()); 164 connections = mouths = allPacked(retract( 165 differencePacked(floors, retract(floors, 1, width, height, true)), 166 1, width, height, false)); 167 doorways = new Coord[0]; 168 } 169 } 170 171 /** 172 * Constructs a RoomFinder given a dungeon map and an environment map (which currently is only produced by 173 * MixedGenerator by the getEnvironment() method after generate() is called, but other classes that use 174 * MixedGenerator may also expose that environment, such as SerpentMapGenerator.getEnvironment()), and finds rooms, 175 * corridors, caves, and their connections on the map. 176 * @param dungeon a 2D char array that uses '#' for walls. 177 * @param environment a 2D int array using constants from MixedGenerator; typically produced by a call to 178 * getEnvironment() in MixedGenerator or SerpentMapGenerator after dungeon generation. 179 */ 180 public RoomFinder(char[][] dungeon, int[][] environment) 181 { 182 if(dungeon.length <= 0) 183 return; 184 width = dungeon.length; 185 height = dungeon[0].length; 186 map = new char[width][height]; 187 for (int i = 0; i < width; i++) { 188 System.arraycopy(dungeon[i], 0, map[i], 0, height); 189 } 190 rooms = new RegionMap<>(32); 191 corridors = new RegionMap<>(32); 192 caves = new RegionMap<>(32); 193 194 basic = DungeonUtility.simplifyDungeon(map); 195 short[] r = pack(environment, MixedGenerator.ROOM_FLOOR), 196 c = pack(environment, MixedGenerator.CORRIDOR_FLOOR), 197 v = pack(environment, MixedGenerator.CAVE_FLOOR), 198 rc = unionPacked(r, c), 199 d = intersectPacked(r, fringe(c, 1, width, height, false)), 200 m = intersectPacked(rc, fringe(v, 1, width, height, false)); 201 doorways = allPacked(d); 202 mouths = allPacked(m); 203 connections = new Coord[doorways.length + mouths.length]; 204 System.arraycopy(doorways, 0, connections, 0, doorways.length); 205 System.arraycopy(mouths, 0, connections, doorways.length, mouths.length); 206 207 List<short[]> rs = split(r), cs = split(c), vs = split(v); 208 short[][] ra = rs.toArray(new short[rs.size()][]), 209 ca = cs.toArray(new short[cs.size()][]), 210 va = vs.toArray(new short[vs.size()][]); 211 212 for (short[] sep : cs) { 213 short[] someDoors = intersectPacked(r, fringe(sep, 1, width, height, false)); 214 short[] doors = allPackedHilbert(someDoors); 215 List<short[]> near = new ArrayList<short[]>(16); 216 for (int j = 0; j < doors.length; j++) { 217 near.addAll(findManyPackedHilbert(doors[j], ra)); 218 } 219 someDoors = intersectPacked(v, fringe(sep, 1, width, height, false)); 220 doors = allPackedHilbert(someDoors); 221 for (int j = 0; j < doors.length; j++) { 222 near.addAll(findManyPackedHilbert(doors[j], va)); 223 } 224 corridors.put(sep, near); 225 } 226 227 for (short[] sep : rs) { 228 List<short[]> near = new ArrayList<short[]>(32); 229 short[] aroundDoors = intersectPacked(c, fringe(sep, 1, width, height, false)); 230 short[] doors = allPackedHilbert(aroundDoors); 231 for (int j = 0; j < doors.length; j++) { 232 near.addAll(findManyPackedHilbert(doors[j], ca)); 233 } 234 aroundDoors = intersectPacked(v, fringe(sep, 1, width, height, false)); 235 doors = allPackedHilbert(aroundDoors); 236 for (int j = 0; j < doors.length; j++) { 237 near.addAll(findManyPackedHilbert(doors[j], va)); 238 } 239 rooms.put(sep, near); 240 } 241 242 for (short[] sep : vs) { 243 List<short[]> near = new ArrayList<short[]>(48); 244 short[] aroundMouths = intersectPacked(c, fringe(sep, 1, width, height, false)); 245 short[] maws = allPackedHilbert(aroundMouths); 246 for (int j = 0; j < maws.length; j++) { 247 near.addAll(findManyPackedHilbert(maws[j], ca)); 248 } 249 aroundMouths = intersectPacked(r, fringe(sep, 1, width, height, false)); 250 maws = allPackedHilbert(aroundMouths); 251 for (int j = 0; j < maws.length; j++) { 252 near.addAll(findManyPackedHilbert(maws[j], ra)); 253 } 254 caves.put(sep, near); 255 } 256 257 } 258 259 /** 260 * Gets all the rooms this found during construction, returning them as an ArrayList of 2D char arrays, where an 261 * individual room is "masked" so only its contents have normal map chars and the rest have only '#'. 262 * @return an ArrayList of 2D char arrays representing rooms. 263 */ 264 public ArrayList<char[][]> findRooms() 265 { 266 ArrayList<char[][]> rs = new ArrayList<char[][]>(rooms.size); 267 for(short[] r : rooms.keys()) 268 { 269 rs.add(mask(map, r, '#')); 270 } 271 return rs; 272 } 273 274 /** 275 * Gets all the corridors this found during construction, returning them as an ArrayList of 2D char arrays, where an 276 * individual corridor is "masked" so only its contents have normal map chars and the rest have only '#'. 277 * @return an ArrayList of 2D char arrays representing corridors. 278 */ 279 public ArrayList<char[][]> findCorridors() 280 { 281 ArrayList<char[][]> cs = new ArrayList<char[][]>(corridors.size); 282 for(short[] c : corridors.keys()) 283 { 284 cs.add(mask(map, c, '#')); 285 } 286 return cs; 287 } 288 289 /** 290 * Gets all the caves this found during construction, returning them as an ArrayList of 2D char arrays, where an 291 * individual room is "masked" so only its contents have normal map chars and the rest have only '#'. Will only 292 * return a non-empty collection if the two-arg constructor was used and the environment contains caves. 293 * @return an ArrayList of 2D char arrays representing caves. 294 */ 295 public ArrayList<char[][]> findCaves() 296 { 297 ArrayList<char[][]> vs = new ArrayList<char[][]>(caves.size); 298 for(short[] v : caves.keys()) 299 { 300 vs.add(mask(map, v, '#')); 301 } 302 return vs; 303 } 304 /** 305 * Gets all the rooms, corridors, and caves this found during construction, returning them as an ArrayList of 2D 306 * char arrays, where an individual room or corridor is "masked" so only its contents have normal map chars and the 307 * rest have only '#'. 308 * @return an ArrayList of 2D char arrays representing rooms, corridors, or caves. 309 */ 310 public ArrayList<char[][]> findRegions() 311 { 312 ArrayList<char[][]> rs = new ArrayList<char[][]>(rooms.size + corridors.size + caves.size); 313 for(short[] r : rooms.keys()) 314 { 315 rs.add(mask(map, r, '#')); 316 } 317 for(short[] r : corridors.keys()) { 318 rs.add(mask(map, r, '#')); 319 } 320 for(short[] r : caves.keys()) { 321 rs.add(mask(map, r, '#')); 322 } 323 return rs; 324 } 325 protected static char[][] defaultFill(int width, int height) 326 { 327 char[][] d = new char[width][height]; 328 for (int x = 0; x < width; x++) { 329 Arrays.fill(d[x], '#'); 330 } 331 return d; 332 } 333 334 /** 335 * Merges multiple 2D char arrays where the '#' character means "no value", and combines them so all cells with 336 * value are on one map, with '#' filling any other cells. If regions is empty, this uses width and height to 337 * construct a blank map, all '#'. It will also use width and height for the size of the returned 2D array. 338 * @param regions An ArrayList of 2D char array regions, where '#' is an empty value and all others will be merged 339 * @param width the width of any map this returns 340 * @param height the height of any map this returns 341 * @return a 2D char array that merges all non-'#' areas in regions, and fills the rest with '#' 342 */ 343 public static char[][] merge(ArrayList<char[][]> regions, int width, int height) 344 { 345 if(regions == null || regions.isEmpty()) 346 return defaultFill(width, height); 347 char[][] first = regions.get(0); 348 char[][] dungeon = new char[first.length][first[0].length]; 349 for (int x = 0; x < first.length; x++) { 350 Arrays.fill(dungeon[x], '#'); 351 } 352 for(char[][] region : regions) 353 { 354 for (int x = 0; x < width; x++) { 355 for (int y = 0; y < height; y++) { 356 if(region[x][y] != '#') 357 dungeon[x][y] = region[x][y]; 358 } 359 } 360 } 361 return dungeon; 362 } 363 364 /** 365 * Takes an x, y position and finds the room, corridor, or cave at that position, if there is one, returning the 366 * same 2D char array format as the other methods. 367 * @param x the x coordinate of a position that should be in a room or corridor 368 * @param y the y coordinate of a position that should be in a room or corridor 369 * @return a masked 2D char array where anything not in the current region is '#' 370 */ 371 public char[][] regionAt(int x, int y) 372 { 373 LinkedHashSet<short[]> regions = rooms.regionsContaining(x, y); 374 regions.addAll(corridors.regionsContaining(x, y)); 375 regions.addAll(caves.regionsContaining(x, y)); 376 short[] found; 377 if(regions.isEmpty()) 378 found = ALL_WALL; 379 else 380 found = GwtCompatibility.first(regions); 381 return mask(map, found, '#'); 382 } 383 384 /** 385 * Takes an x, y position and finds the room or corridor at that position and the rooms, corridors or caves that it 386 * directly connects to, and returns the group as one merged 2D char array. 387 * @param x the x coordinate of a position that should be in a room or corridor 388 * @param y the y coordinate of a position that should be in a room or corridor 389 * @return a masked 2D char array where anything not in the current region or one nearby is '#' 390 */ 391 public char[][] regionsNear(int x, int y) 392 { 393 LinkedHashSet<short[]> regions = rooms.regionsContaining(x, y); 394 regions.addAll(corridors.regionsContaining(x, y)); 395 regions.addAll(caves.regionsContaining(x, y)); 396 short[] found; 397 if(regions.isEmpty()) 398 found = ALL_WALL; 399 else 400 { 401 found = GwtCompatibility.first(regions); 402 LinkedHashSet<List<short[]>> near = rooms.allAt(x, y); 403 for (List<short[]> links : near) { 404 for(short[] n : links) 405 { 406 found = unionPacked(found, n); 407 } 408 } 409 near = corridors.allAt(x, y); 410 for (List<short[]> links : near) { 411 for(short[] n : links) 412 { 413 found = unionPacked(found, n); 414 } 415 } 416 near = caves.allAt(x, y); 417 for (List<short[]> links : near) { 418 for(short[] n : links) 419 { 420 found = unionPacked(found, n); 421 } 422 } 423 } 424 return mask(map, found, '#'); 425 } 426 427 /** 428 * Takes an x, y position and finds the rooms or corridors that are directly connected to the room, corridor or cave 429 * at that position, and returns the group as an ArrayList of 2D char arrays, one per connecting region. 430 * @param x the x coordinate of a position that should be in a room or corridor 431 * @param y the y coordinate of a position that should be in a room or corridor 432 * @return an ArrayList of masked 2D char arrays where anything not in a connected region is '#' 433 */ 434 public ArrayList<char[][]> regionsConnected(int x, int y) 435 { 436 ArrayList<char[][]> regions = new ArrayList<>(10); 437 LinkedHashSet<List<short[]>> near = rooms.allAt(x, y); 438 for (List<short[]> links : near) { 439 for(short[] n : links) 440 { 441 regions.add(mask(map, n, '#')); 442 } 443 } 444 near = corridors.allAt(x, y); 445 for (List<short[]> links : near) { 446 for (short[] n : links) { 447 regions.add(mask(map, n, '#')); 448 } 449 } 450 near = caves.allAt(x, y); 451 for (List<short[]> links : near) { 452 for (short[] n : links) { 453 regions.add(mask(map, n, '#')); 454 } 455 } 456 457 return regions; 458 } 459}