001package squidpony.squidgrid; 002 003import squidpony.squidgrid.Spill.Measurement; 004import squidpony.squidmath.Coord; 005import squidpony.squidmath.RNG; 006import squidpony.squidmath.StatefulRNG; 007 008import java.util.ArrayList; 009import java.util.LinkedHashMap; 010import java.util.LinkedHashSet; 011import java.util.List; 012import java.util.Set; 013 014/** 015 * A randomized flood-fill implementation that can be used for level generation (e.g. filling ponds and lakes), for 016 * gas propagation, or for all sorts of fluid-dynamics-on-the-cheap. 017 * Created by Tommy Ettinger on 4/7/2015. 018 */ 019public class MultiSpill { 020 021 /** 022 * This affects how distance is measured on diagonal directions vs. orthogonal directions. MANHATTAN should form a 023 * diamond shape on a featureless map, while CHEBYSHEV and EUCLIDEAN will form a square. If you only call 024 * Spill.start() once, you should strongly prefer MANHATTAN, even if the rest of the game uses another 025 * measurement, because CHEBYSHEV and EUCLIDEAN can produce odd, gap-filled flood-fills. Any case where you have 026 * too many gaps can be corrected to varying extent by calling start() more than once with slowly increasing values. 027 * Because start() will extend from the existing area of the Spill, holes are likely to be filled after a few calls, 028 * but if the last call to start() tries to fill too many more cells than the previous one, it can cause holes on 029 * the periphery of the Spill area. 030 */ 031 public Measurement measurement = Measurement.MANHATTAN; 032 033 034 /** 035 * Stores which parts of the map are accessible (with a value of true) and which are not (with a value of false, 036 * including both walls and unreachable sections of the map). Should not be changed unless the actual physical 037 * terrain has changed. You should call initialize() with a new map instead of changing this directly. 038 */ 039 public boolean[][] physicalMap; 040 /** 041 * The cells that are filled by the a spiller with index n when it reaches its volume or limits will be equal to n; 042 * others will be -1. 043 */ 044 public short[][] spillMap; 045 046 /** 047 * The cells that are filled by the any spiller will be true, others will be false. 048 */ 049 public boolean[][] anySpillMap; 050 051 /** 052 * Each spiller in the MultiSpill corresponds to a list of points that it will randomly fill, starting with the 053 * initial point for each spiller passed to start(), in order of when they are reached. 054 */ 055 public ArrayList<ArrayList<Coord>> spreadPattern; 056 /** 057 * Height of the map. Exciting stuff. Don't change this, instead call initialize(). 058 */ 059 public int height; 060 /** 061 * Width of the map. Exciting stuff. Don't change this, instead call initialize(). 062 */ 063 public int width; 064 /** 065 * The amount of cells filled by this Spill, which may be less than the volume passed to start() if the boundaries 066 * are reached on all sides and the Spill has no more room to fill. 067 */ 068 public int filled = 0; 069 private ArrayList<LinkedHashSet<Coord>> fresh; 070 /** 071 * The StatefulRNG used to decide how to randomly fill a space; can have its state set and read. 072 */ 073 public StatefulRNG rng; 074 075 private boolean initialized = false; 076 /** 077 * Construct a Spill without a level to actually scan. If you use this constructor, you must call an 078 * initialize() method before using this class. 079 */ 080 public MultiSpill() { 081 rng = new StatefulRNG(); 082 083 fresh = new ArrayList<>(); 084 } 085 /** 086 * Construct a Spill without a level to actually scan. This constructor allows you to specify an RNG, but the actual 087 * RandomnessSource the RNG that this object uses will not be identical to the one passed as random (64 bits will 088 * be requested from the passed RNG, and that will be used to seed this class' RNG). 089 * 090 * If you use this constructor, you must call an initialize() method before using this class. 091 * @param random an RNG that will be converted to a StatefulRNG if it is not one already 092 */ 093 public MultiSpill(RNG random) { 094 rng = new StatefulRNG(random.getRandomness()); 095 096 fresh = new ArrayList<>(); 097 } 098 099 /** 100 * Used to construct a Spill from the output of another. 101 * @param level a short[][] that should have been the spillMap of another MultiSpill 102 */ 103 public MultiSpill(final short[][] level) { 104 rng = new StatefulRNG(); 105 106 initialize(level); 107 } 108 /** 109 * Used to construct a Spill from the output of another, specifying a distance calculation. 110 * @param level a short[][] that should have been the spillMap of another MultiSpill 111 * @param measurement a Spill.Measurement that should usually be MANHATTAN 112 */ 113 public MultiSpill(final short[][] level, Measurement measurement) { 114 rng = new StatefulRNG(); 115 116 this.measurement = measurement; 117 118 initialize(level); 119 } 120 121 /** 122 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 123 * char[][] where '#' means a wall and anything else is a walkable tile. If you only have 124 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 125 * map that can be used here. 126 * 127 * @param level a char[][] that should use '#' for walls and '.' for floors 128 */ 129 public MultiSpill(final char[][] level) { 130 rng = new StatefulRNG(); 131 132 initialize(level); 133 } 134 /** 135 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 136 * char[][] where one char means a wall and anything else is a walkable tile. If you only have 137 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 138 * map that can be used here. You can specify the character used for walls. 139 * 140 * @param level a char[][] that should use alternateWall for walls and '.' for floors 141 * @param alternateWall the char to use for walls 142 */ 143 public MultiSpill(final char[][] level, char alternateWall) { 144 rng = new StatefulRNG(); 145 146 initialize(level, alternateWall); 147 } 148 149 /** 150 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 151 * char[][] where '#' means a wall and anything else is a walkable tile. If you only have 152 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 153 * map that can be used here. This constructor specifies a distance measurement. 154 * 155 * @param level a char[][] that should use '#' for walls and '.' for floors 156 * @param measurement a Spill.Measurement that should usually be MANHATTAN 157 */ 158 public MultiSpill(final char[][] level, Measurement measurement) { 159 rng = new StatefulRNG(); 160 this.measurement = measurement; 161 162 initialize(level); 163 } 164 /** 165 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 166 * char[][] where '#' means a wall and anything else is a walkable tile. If you only have 167 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 168 * map that can be used here. This constructor specifies a distance measurement. 169 * 170 * This constructor allows you to specify an RNG, but the actual RandomnessSource the RNG that this object uses 171 * will not be identical to the one passed as random (64 bits will be requested from the passed RNG, and that will 172 * be used to seed this class' RNG). 173 * 174 * @param level a char[][] that should use '#' for walls and '.' for floors 175 * @param measurement a Spill.Measurement that should usually be MANHATTAN 176 * @param random an RNG that will be converted to a StatefulRNG if it is not one already 177 */ 178 public MultiSpill(final char[][] level, Measurement measurement, RNG random) { 179 rng = new StatefulRNG(random.getRandomness()); 180 this.measurement = measurement; 181 182 initialize(level); 183 } 184 185 /** 186 * Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given 187 * one when it was constructed, or because the contents of the terrain have changed permanently. 188 * @param level a short[][] that should have been the spillMap of another MultiSpill 189 * @return this for chaining 190 */ 191 public MultiSpill initialize(final short[][] level) { 192 fresh = new ArrayList<>(); 193 width = level.length; 194 height = level[0].length; 195 spillMap = new short[width][height]; 196 anySpillMap = new boolean[width][height]; 197 physicalMap = new boolean[width][height]; 198 for (int y = 0; y < height; y++) { 199 for (int x = 0; x < width; x++) { 200 spillMap[x][y] = level[x][y]; 201 anySpillMap[x][y] = level[x][y] > 0; 202 physicalMap[x][y] = level[x][y] >= 0; 203 } 204 } 205 initialized = true; 206 return this; 207 } 208 209 /** 210 * Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given 211 * one when it was constructed, or because the contents of the terrain have changed permanently (not if a 212 * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). 213 * @param level a char[][] that should use '#' for walls and '.' for floors 214 * @return this for chaining 215 */ 216 public MultiSpill initialize(final char[][] level) { 217 fresh = new ArrayList<>(); 218 width = level.length; 219 height = level[0].length; 220 spillMap = new short[width][height]; 221 anySpillMap = new boolean[width][height]; 222 physicalMap = new boolean[width][height]; 223 for (int y = 0; y < height; y++) { 224 for (int x = 0; x < width; x++) { 225 spillMap[x][y] = -1; 226 anySpillMap[x][y] = false; 227 physicalMap[x][y] = (level[x][y] != '#'); 228 } 229 } 230 initialized = true; 231 return this; 232 } 233 234 /** 235 * Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given 236 * one when it was constructed, or because the contents of the terrain have changed permanently (not if a 237 * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). This 238 * initialize() method allows you to specify an alternate wall char other than the default character, '#' . 239 * @param level a char[][] that should use alternateWall for walls and '.' for floors 240 * @param alternateWall the char to use for walls 241 * @return this for chaining 242 */ 243 public MultiSpill initialize(final char[][] level, char alternateWall) { 244 fresh = new ArrayList<>(); 245 width = level.length; 246 height = level[0].length; 247 spillMap = new short[width][height]; 248 anySpillMap = new boolean[width][height]; 249 physicalMap = new boolean[width][height]; 250 for (int y = 0; y < height; y++) { 251 for (int x = 0; x < width; x++) { 252 spillMap[x][y] = -1; 253 anySpillMap[x][y] = false; 254 physicalMap[x][y] = (level[x][y] != alternateWall); 255 } 256 } 257 initialized = true; 258 return this; 259 } 260 261 /** 262 * Resets the spillMap to being empty. 263 */ 264 public void resetMap() { 265 if(!initialized) return; 266 for (int y = 0; y < height; y++) { 267 for (int x = 0; x < width; x++) { 268 spillMap[x][y] = -1; 269 anySpillMap[x][y] = false; 270 } 271 } 272 } 273 274 /** 275 * Resets this Spill to a state with an empty spillMap and an empty spreadPattern. 276 */ 277 public void reset() { 278 resetMap(); 279 spreadPattern.clear(); 280 fresh.clear(); 281 } 282 283 /** 284 * Reverts a cell to an unfilled state (false in spillMap). 285 * @param x 286 * @param y 287 */ 288 public void resetCell(int x, int y) { 289 if(!initialized) return; 290 spillMap[x][y] = -1; 291 anySpillMap[x][y] = false; 292 } 293 294 /** 295 * Reverts a cell to an unfilled state (false in spillMap). 296 * @param pt 297 */ 298 public void resetCell(Coord pt) { 299 if(!initialized) return; 300 spillMap[pt.x][pt.y] = -1; 301 anySpillMap[pt.x][pt.y] = false; 302 } 303 304 protected void setFresh(int idx, int x, int y) { 305 if(!initialized) return; 306 fresh.get(idx).add(Coord.get(x, y)); 307 } 308 309 protected void setFresh(int idx, final Coord pt) { 310 if(!initialized) return; 311 for(LinkedHashSet<Coord> f : fresh) 312 { 313 if(f.contains(pt)) 314 return; 315 } 316 fresh.get(idx).add(pt); 317 } 318 319 /** 320 * Recalculate the spillMap and return the spreadPattern. The cell corresponding to a Coord in entries will be true, 321 * the cells near each of those will be true if chosen at random from all passable cells adjacent to a 322 * filled (true) cell, and all other cells will be false. This takes a total number of cells to attempt 323 * to fill (the volume parameter), which can be negative to simply fill the whole map, and will fill less if it has 324 * completely exhausted all passable cells from all sources in entries. 325 * If the measurement this Spill uses is anything other than MANHATTAN, you can expect many gaps in the first 326 * filled area. Subsequent calls to start() with the same entry and a higher volume will expand the area 327 * of the Spill, and are likely to fill any gaps after a few subsequent calls. Increasing the volume slowly 328 * is the best way to ensure that gaps only exist on the very edge if you use a non-MANHATTAN measurement. 329 * 330 * @param entries the first cell for each spiller to spread from, which should really be passable. 331 * @param volume the total number of cells to attempt to fill; if negative will fill the whole map. 332 * @param impassable a Set of Position keys representing the locations of moving obstacles to a 333 * fill that cannot be moved through; this can be null if there are no such obstacles. 334 * @return an ArrayList of Points that this will enter, in order starting with entry at index 0, until it 335 * reaches its volume or fills its boundaries completely. 336 */ 337 public ArrayList<ArrayList<Coord>> start(List<Coord> entries, int volume, Set<Coord> impassable) { 338 if(!initialized) return null; 339 if(impassable == null) 340 impassable = new LinkedHashSet<>(); 341 if(volume < 0) 342 volume = Integer.MAX_VALUE; 343 ArrayList<Coord> spillers = new ArrayList<>(entries); 344 spreadPattern = new ArrayList<>(spillers.size()); 345 fresh.clear(); 346 for (short i = 0; i < spillers.size(); i++) { 347 spreadPattern.add(new ArrayList<Coord>(128)); 348 fresh.add(new LinkedHashSet<Coord>(128)); 349 Coord c = spillers.get(i); 350 spillMap[c.x][c.y] = i; 351 352 } 353 boolean hasFresh = false; 354 Coord temp; 355 for (int x = 0; x < spillMap.length; x++) { 356 for (int y = 0; y < spillMap[x].length; y++) { 357 temp = Coord.get(x, y); 358 if (spillMap[x][y] >= 0 && !impassable.contains(temp)) { 359 fresh.get(spillMap[x][y]).add(temp); 360 hasFresh = true; 361 } 362 } 363 } 364 Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS; 365 366 while (hasFresh && filled < volume) { 367 hasFresh = false; 368 for (short i = 0; i < spillers.size() && filled < volume; i++) { 369 LinkedHashSet<Coord> currentFresh = fresh.get(i); 370 if(currentFresh.isEmpty()) 371 continue; 372 else 373 hasFresh = true; 374 Coord cell = currentFresh.toArray(new Coord[currentFresh.size()])[rng.nextInt(currentFresh.size())]; 375 376 spreadPattern.get(i).add(cell); 377 spillMap[cell.x][cell.y] = i; 378 filled++; 379 anySpillMap[cell.x][cell.y] = true; 380 381 for (int d = 0; d < dirs.length; d++) { 382 Coord adj = cell.translate(dirs[d].deltaX, dirs[d].deltaY); 383 double h = heuristic(dirs[d]); 384 if (physicalMap[adj.x][adj.y] && !anySpillMap[adj.x][adj.y] && !impassable.contains(adj) && rng.nextDouble() <= 1.0 / h) { 385 setFresh(i, adj); 386 } 387 } 388 currentFresh.remove(cell); 389 } 390 } 391 return spreadPattern; 392 } 393 394 /** 395 * Recalculate the spillMap and return the spreadPattern. The cell corresponding to a key in entries will be true, 396 * the cells near each of those will be true if chosen at random from all passable cells adjacent to a 397 * filled (true) cell, and all other cells will be false. This takes a total number of cells to attempt 398 * to fill (the volume parameter), which can be negative to simply fill the whole map, and will fill less if it has 399 * completely exhausted all passable cells from all sources in entries. It uses the values in entries to determine 400 * whether it should advance from a particular key in that step or not; this choice is pseudo-random. If you have 401 * some values that are at or near 1.0 and some values that are closer to 0.0, you should expect the keys for the 402 * higher values to spread further out than the keys associated with lower values. 403 * <br> 404 * If the measurement this Spill uses is anything other than MANHATTAN, you can expect many gaps in the first 405 * filled area. Subsequent calls to start() with the same entry and a higher volume will expand the area 406 * of the Spill, and are likely to fill any gaps after a few subsequent calls. Increasing the volume slowly 407 * is the best way to ensure that gaps only exist on the very edge if you use a non-MANHATTAN measurement. 408 * <br> 409 * The intended purpose for this method is filling contiguous areas of dungeon with certain terrain features, but it 410 * has plenty of other uses as well. 411 * @param entries key: the first cell for each spiller to spread from. value: the bias toward advancing this key; 412 * 1.0 will always advance, 0.0 will never advance beyond the key, in between will randomly choose 413 * @param volume the total number of cells to attempt to fill; if negative will fill the whole map. 414 * @param impassable a Set of Position keys representing the locations of moving obstacles to a 415 * fill that cannot be moved through; this can be null if there are no such obstacles. 416 * @return an ArrayList of Points that this will enter, in order starting with entry at index 0, until it 417 * reaches its volume or fills its boundaries completely. 418 */ 419 public ArrayList<ArrayList<Coord>> start(LinkedHashMap<Coord, Double> entries, int volume, Set<Coord> impassable) { 420 if(!initialized) return null; 421 if(impassable == null) 422 impassable = new LinkedHashSet<>(); 423 if(volume < 0) 424 volume = Integer.MAX_VALUE; 425 ArrayList<Coord> spillers0 = new ArrayList<>(entries.keySet()), 426 spillers = new ArrayList<>(spillers0.size()); 427 ArrayList<Double> biases0 = new ArrayList<>(entries.values()), 428 biases = new ArrayList<>(biases0.size()); 429 spreadPattern = new ArrayList<>(spillers0.size()); 430 fresh.clear(); 431 for (short i = 0, ctr = 0; i < spillers0.size(); i++, ctr++) { 432 spreadPattern.add(new ArrayList<Coord>(128)); 433 fresh.add(new LinkedHashSet<Coord>(128)); 434 Coord c = spillers0.get(i); 435 spillers.add(c); 436 biases.add(biases0.get(i)); 437 if(biases0.get(i) <= 0.0001) 438 continue; 439 spillMap[c.x][c.y] = ctr; 440 441 } 442 boolean hasFresh = false; 443 Coord temp; 444 for (int x = 0; x < spillMap.length; x++) { 445 for (int y = 0; y < spillMap[x].length; y++) { 446 temp = Coord.get(x, y); 447 if (spillMap[x][y] >= 0 && !impassable.contains(temp)) { 448 fresh.get(spillMap[x][y]).add(temp); 449 hasFresh = true; 450 } 451 } 452 } 453 454 Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS; 455 456 while (hasFresh && filled < volume) { 457 hasFresh = false; 458 for (short i = 0; i < spillers.size() && filled < volume; i++) { 459 LinkedHashSet<Coord> currentFresh = fresh.get(i); 460 if(currentFresh.isEmpty()) 461 continue; 462 else 463 hasFresh = true; 464 Coord cell = currentFresh.toArray(new Coord[currentFresh.size()])[rng.nextInt(currentFresh.size())]; 465 if(rng.nextDouble() < biases.get(i)) { 466 467 spreadPattern.get(i).add(cell); 468 spillMap[cell.x][cell.y] = i; 469 filled++; 470 anySpillMap[cell.x][cell.y] = true; 471 472 473 for (int d = 0; d < dirs.length; d++) { 474 Coord adj = cell.translate(dirs[d].deltaX, dirs[d].deltaY); 475 double h = heuristic(dirs[d]); 476 if (physicalMap[adj.x][adj.y] && !anySpillMap[adj.x][adj.y] && !impassable.contains(adj) 477 && rng.nextDouble() <= 1.0 / h) { 478 setFresh(i, adj); 479 } 480 } 481 currentFresh.remove(cell); 482 } 483 } 484 } 485 return spreadPattern; 486 } 487 488 private static final double root2 = Math.sqrt(2.0); 489 private double heuristic(Direction target) { 490 switch (measurement) { 491 case MANHATTAN: 492 case CHEBYSHEV: 493 return 1.0; 494 case EUCLIDEAN: 495 switch (target) { 496 case DOWN_LEFT: 497 case DOWN_RIGHT: 498 case UP_LEFT: 499 case UP_RIGHT: 500 return root2; 501 default: 502 return 1.0; 503 } 504 } 505 return 1.0; 506 } 507}