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}