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