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}