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