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