001package squidpony.squidgrid.mapping;
002
003import squidpony.squidai.DijkstraMap;
004import squidpony.squidgrid.mapping.styled.DungeonBoneGen;
005import squidpony.squidgrid.mapping.styled.TilesetType;
006import squidpony.squidmath.*;
007
008import java.util.*;
009
010import static squidpony.squidmath.CoordPacker.*;
011
012/**
013 * A good way to create a more-complete dungeon, layering different effects and modifications on top of a dungeon
014 * produced by DungeonBoneGen or another dungeon without such effects. Unlike DungeonGenerator, this class uses
015 * environment information for the dungeons it is given (or quickly generates such information if using DungeonBoneGen),
016 * and uses that information to only place effects like grass or water where you specify, like "only in caves", or
017 * "doors should never be in caves". Ensures only connected regions of the map are used by filling unreachable areas
018 * with walls, and can find far-apart staircase positions if generate() is used or can keep existing staircases in a map
019 * if generateRespectingStairs() is used.
020 * <br>
021 * The main technique for using this is simple: Construct a DungeonGenerator, usually with the desired width and height,
022 * then call any feature adding methods that you want in the dungeon, like addWater(), addTraps, addGrass(), or
023 * addDoors(). All of these methods except addDoors() take an int argument that corresponds to a constant in this class,
024 * CAVE, CORRIDOR, or ROOM, or ALL, and they will only cause the requested feature to show up in that environment. Some
025 * of these take different parameters, like addDoors() which needs to know if it should check openings that are two
026 * cells wide to add a door and a wall to, or whether it should only add doors to single-cell openings. In the case of
027 * addDoors(), it doesn't take an environment argument since doors almost always are between environments (rooms and
028 * corridors), so placing them only within one or the other doesn't make sense. This class, unlike the normal
029 * DungeonGenerator, also has an addLake() method, which, like addDoors(), doesn't take an environment parameter. It can
030 * be used to turn a large section of what would otherwise be walls into a lake (of some character for deep lake cells
031 * and some character for shallow lake cells), and corridors that cross the lake become bridges, shown as ':'. It should
032 * be noted that because the lake fills walls, it doesn't change the connectivity of the map unless you can cross the
033 * lake. Once you've added any features to the generator's effects list, call generate() to get a char[][] with the
034 * desired dungeon map, using a fixed repertoire of chars to represent the different features, with the exception of the
035 * customization that can be requested from addLake(). If you use the libGDX text-based display module, you can change
036 * what chars are shown by using addSwap() in TextCellFactory. After calling generate(), you can safely get the values
037 * from the stairsUp and stairsDown fields, which are Coords that should be a long distance from each other but
038 * connected in the dungeon. You may want to change those to staircase characters, but there's no requirement to do
039 * anything with them. The DungeonUtility field of this class, utility, is a convenient way of accessing the non-static
040 * methods in that class, such as randomFloor(), without needing to create another DungeonUtility (this class creates
041 * one, so you don't have to).
042 * <br>
043 * Example map with a custom-representation lake: https://gist.github.com/tommyettinger/0055075f9de59c452d25
044 * @see DungeonUtility this class exposes a DungeonUtility member; DungeonUtility also has many useful static methods
045 * @see DungeonGenerator for a slightly simpler alternative that does not recognize different sections of dungeon
046 *
047 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
048 * @author Tommy Ettinger - https://github.com/tommyettinger
049 */
050public class SectionDungeonGenerator {
051
052    /**
053     * The effects that can be applied to this dungeon. More may be added in future releases.
054     */
055    public enum FillEffect
056    {
057        /**
058         * Water, represented by '~'
059         */
060        WATER,
061        /**
062         * Traps, represented by '^'
063         */
064        TRAPS,
065        /**
066         * Grass, represented by '"'
067         */
068        GRASS,
069        /**
070         * Boulders strewn about open areas, represented by '#' and treated as walls
071         */
072        BOULDERS,
073        /**
074         * Islands of ground, '.', surrounded by shallow water, ',', to place in water at evenly spaced points
075         */
076        ISLANDS
077    }
078
079    /**
080     * Constant for features being added to all environment types.
081     */
082    public static final int ALL = 0,
083    /**
084     * Constant for features being added only to rooms.
085     */
086    ROOM = 1,
087    /**
088     * Constant for features being added only to corridors.
089     */
090    CORRIDOR = 2,
091    /**
092     * Constant for features being added only to caves.
093     */
094    CAVE = 3;
095
096    /**
097     * The effects that will be applied when generate is called. Strongly prefer using addWater, addDoors, addTraps,
098     * and addGrass.
099     */
100    public EnumMap<FillEffect, Integer> roomFX, corridorFX, caveFX;
101
102    /**
103     * Percentage of viable positions to fill with doors, represented by '+' for east-to-west connections or '/' for
104     * north-to-south ones; this number will be negative if filling two-cell wide positions but will be made positive
105     * when needed.
106     */
107    public int doorFX = 0;
108    /**
109     * The char to use for deep lake cells.
110     */
111    public char deepLakeGlyph = '~';
112    /**
113     * The char to use for shallow lake cells.
114     */
115    public char shallowLakeGlyph = ',';
116    /**
117     * The approximate percentage of non-room, non-cave, non-edge-of-map wall cells to try to fill with lake. Corridors
118     * that are covered by a lake will become bridges, the glyph ':'.
119     */
120    public int lakeFX = 0;
121    /**
122     * The approximate percentage of non-room, non-cave, non-edge-of-map wall cells to try to fill with maze. Corridors
123     * that are covered by a maze will become part of its layout.
124     */
125    public int mazeFX = 0;
126    public DungeonUtility utility;
127    protected int height, width;
128    public Coord stairsUp = null, stairsDown = null;
129    public StatefulRNG rng;
130    protected long rebuildSeed;
131    protected boolean seedFixed = false;
132    protected int environmentType = 1;
133
134    protected char[][] dungeon = null;
135    public RoomFinder finder;
136    public Placement placement;
137
138    /**
139     * Get the most recently generated char[][] dungeon out of this class. The
140     * dungeon may be null if generate() or setDungeon() have not been called.
141     * @return a char[][] dungeon, or null.
142     */
143    public char[][] getDungeon() {
144        return dungeon;
145    }
146    /**
147     * Get the most recently generated char[][] dungeon out of this class without any chars other than '#' or '.', for
148     * walls and floors respectively. The dungeon may be null if generate() or setDungeon() have not been called.
149     * @return a char[][] dungeon with only '#' for walls and '.' for floors, or null.
150     */
151    public char[][] getBareDungeon() {
152        return DungeonUtility.simplifyDungeon(dungeon);
153    }
154
155    /**
156     * Change the underlying char[][]; only affects the toString method, and of course getDungeon.
157     * @param dungeon a char[][], probably produced by an earlier call to this class and then modified.
158     */
159    public void setDungeon(char[][] dungeon) {
160        this.dungeon = dungeon;
161        if(dungeon == null)
162        {
163            width = 0;
164            height = 0;
165            return;
166        }
167        width = dungeon.length;
168        if(width > 0)
169            height = dungeon[0].length;
170    }
171
172    /**
173     * Height of the dungeon in cells.
174     * @return Height of the dungeon in cells.
175     */
176    public int getHeight() {
177        return height;
178    }
179
180    /**
181     * Width of the dungeon in cells.
182     * @return Width of the dungeon in cells.
183     */
184    public int getWidth() {
185        return width;
186    }
187
188
189    /**
190     * Make a DungeonGenerator with a LightRNG using a random seed, height 40, and width 40.
191     */
192    public SectionDungeonGenerator()
193    {
194        rng = new StatefulRNG();
195        utility = new DungeonUtility(rng);
196        rebuildSeed = rng.getState();
197        height = 40;
198        width = 40;
199        roomFX = new EnumMap<>(FillEffect.class);
200        corridorFX = new EnumMap<>(FillEffect.class);
201        caveFX = new EnumMap<>(FillEffect.class);
202    }
203
204    /**
205     * Make a DungeonGenerator with the given height and width; the RNG used for generating a dungeon and
206     * adding features will be a LightRNG using a random seed.
207     * @param width The width of the dungeon in cells
208     * @param height The height of the dungeon in cells
209     */
210    public SectionDungeonGenerator(int width, int height)
211    {
212        this(width, height, new RNG(new LightRNG()));
213    }
214
215    /**
216     * Make a DungeonGenerator with the given height, width, and RNG. Use this if you want to seed the RNG.
217     * @param width The width of the dungeon in cells
218     * @param height The height of the dungeon in cells
219     * @param rng The RNG to use for all purposes in this class; if it is a StatefulRNG, then it will be used as-is,
220     *            but if it is not a StatefulRNG, a new StatefulRNG will be used, randomly seeded by this parameter
221     */
222    public SectionDungeonGenerator(int width, int height, RNG rng)
223    {
224        this.rng = (rng instanceof StatefulRNG) ? (StatefulRNG) rng : new StatefulRNG(rng.nextLong());
225        utility = new DungeonUtility(this.rng);
226        rebuildSeed = this.rng.getState();
227        this.height = height;
228        this.width = width;
229        roomFX = new EnumMap<>(FillEffect.class);
230        corridorFX = new EnumMap<>(FillEffect.class);
231        caveFX = new EnumMap<>(FillEffect.class);
232    }
233
234    /**
235     * Copies all fields from copying and makes a new DungeonGenerator.
236     * @param copying the DungeonGenerator to copy
237     */
238    public SectionDungeonGenerator(SectionDungeonGenerator copying)
239    {
240        rng = new StatefulRNG(copying.rng.getState());
241        utility = new DungeonUtility(rng);
242        rebuildSeed = rng.getState();
243        height = copying.height;
244        width = copying.width;
245        roomFX = new EnumMap<>(copying.roomFX);
246        corridorFX = new EnumMap<>(copying.corridorFX);
247        caveFX = new EnumMap<>(copying.caveFX);
248        doorFX = copying.doorFX;
249        lakeFX = copying.lakeFX;
250        deepLakeGlyph = copying.deepLakeGlyph;
251        shallowLakeGlyph = copying.shallowLakeGlyph;
252        dungeon = copying.dungeon;
253    }
254
255    /**
256     * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be
257     * clustered into a random number of pools, with more appearing if needed to fill the percentage.
258     * Each pool will have randomized volume that should fill or get very close to filling the requested
259     * percentage, unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater
260     * called, the latest call will take precedence. No islands will be placed with this variant, but the edge of the
261     * water will be shallow, represented by ','.
262     * @param env the environment to apply this to
263     * @param percentage the percentage of floor cells to fill with water
264     * @return this DungeonGenerator; can be chained
265     */
266    public SectionDungeonGenerator addWater(int env, int percentage)
267    {
268        if(percentage < 0) percentage = 0;
269        if(percentage > 100) percentage = 100;
270        switch (env)
271        {
272            case ROOM:
273                if(roomFX.containsKey(FillEffect.WATER)) roomFX.remove(FillEffect.WATER);
274                roomFX.put(FillEffect.WATER, percentage);
275                break;
276            case CORRIDOR:
277                if(corridorFX.containsKey(FillEffect.WATER)) corridorFX.remove(FillEffect.WATER);
278                corridorFX.put(FillEffect.WATER, percentage);
279                break;
280            case CAVE:
281                if(caveFX.containsKey(FillEffect.WATER)) caveFX.remove(FillEffect.WATER);
282                caveFX.put(FillEffect.WATER, percentage);
283                break;
284            default:
285                if(roomFX.containsKey(FillEffect.WATER))
286                    roomFX.put(FillEffect.WATER, Math.min(100, roomFX.get(FillEffect.WATER) + percentage));
287                else
288                    roomFX.put(FillEffect.WATER, percentage);
289                if(corridorFX.containsKey(FillEffect.WATER))
290                    corridorFX.put(FillEffect.WATER, Math.min(100, corridorFX.get(FillEffect.WATER) + percentage));
291                else
292                    corridorFX.put(FillEffect.WATER, percentage);
293                if(caveFX.containsKey(FillEffect.WATER))
294                    caveFX.put(FillEffect.WATER, Math.min(100, caveFX.get(FillEffect.WATER) + percentage));
295                else
296                    caveFX.put(FillEffect.WATER, percentage);
297        }
298        return this;
299    }
300    /**
301     * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be
302     * clustered into a random number of pools, with more appearing if needed to fill the percentage. Each pool will
303     * have randomized volume that should fill or get very close to filling the requested percentage,
304     * unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater called, the
305     * latest call will take precedence. If islandSpacing is greater than 1, then this will place islands of floor, '.',
306     * surrounded by shallow water, ',', at about the specified distance with Euclidean measurement.
307     * @param env the environment to apply this to
308     * @param percentage the percentage of floor cells to fill with water
309     * @param islandSpacing if greater than 1, islands will be placed randomly this many cells apart.
310     * @return this DungeonGenerator; can be chained
311     */
312    public SectionDungeonGenerator addWater(int env, int percentage, int islandSpacing)
313    {
314        addWater(env, percentage);
315
316        if(percentage < 0) percentage = 0;
317        if(percentage > 100) percentage = 100;
318        switch (env) {
319            case ROOM:
320                if (roomFX.containsKey(FillEffect.ISLANDS)) roomFX.remove(FillEffect.ISLANDS);
321                if(islandSpacing > 1)
322                    roomFX.put(FillEffect.ISLANDS, percentage);
323                break;
324            case CORRIDOR:
325                if (corridorFX.containsKey(FillEffect.ISLANDS)) corridorFX.remove(FillEffect.ISLANDS);
326                if(islandSpacing > 1)
327                    corridorFX.put(FillEffect.ISLANDS, percentage);
328                break;
329            case CAVE:
330                if (caveFX.containsKey(FillEffect.ISLANDS)) caveFX.remove(FillEffect.ISLANDS);
331                if(islandSpacing > 1)
332                    caveFX.put(FillEffect.ISLANDS, percentage);
333                break;
334            default:
335                if (roomFX.containsKey(FillEffect.ISLANDS)) roomFX.remove(FillEffect.ISLANDS);
336                if(islandSpacing > 1)
337                    roomFX.put(FillEffect.ISLANDS, percentage);
338                if (corridorFX.containsKey(FillEffect.ISLANDS)) corridorFX.remove(FillEffect.ISLANDS);
339                if(islandSpacing > 1)
340                    corridorFX.put(FillEffect.ISLANDS, percentage);
341                if (caveFX.containsKey(FillEffect.ISLANDS)) caveFX.remove(FillEffect.ISLANDS);
342                if(islandSpacing > 1)
343                    caveFX.put(FillEffect.ISLANDS, percentage);
344        }
345
346        return this;
347    }
348
349    /**
350     * Turns the majority of the given percentage of floor cells into grass cells, represented by '"'. Grass will be
351     * clustered into a random number of patches, with more appearing if needed to fill the percentage. Each area will
352     * have randomized volume that should fill or get very close to filling (two thirds of) the requested percentage,
353     * unless the patches encounter too much tight space. If this DungeonGenerator previously had addGrass called, the
354     * latest call will take precedence.
355     * @param env the environment to apply this to
356     * @param percentage the percentage of floor cells to fill with grass; this can vary quite a lot. It may be
357     *                   difficult to fill very high (over 66%) percentages of map with grass, though you can do this by
358     *                   giving a percentage of between 100 and 150.
359     * @return this DungeonGenerator; can be chained
360     */
361    public SectionDungeonGenerator addGrass(int env, int percentage)
362    {
363        if(percentage < 0) percentage = 0;
364        if(percentage > 100) percentage = 100;
365        switch (env)
366        {
367            case ROOM:
368                if(roomFX.containsKey(FillEffect.GRASS)) roomFX.remove(FillEffect.GRASS);
369                roomFX.put(FillEffect.GRASS, percentage);
370                break;
371            case CORRIDOR:
372                if(corridorFX.containsKey(FillEffect.GRASS)) corridorFX.remove(FillEffect.GRASS);
373                corridorFX.put(FillEffect.GRASS, percentage);
374                break;
375            case CAVE:
376                if(caveFX.containsKey(FillEffect.GRASS)) caveFX.remove(FillEffect.GRASS);
377                caveFX.put(FillEffect.GRASS, percentage);
378                break;
379            default:
380                if(roomFX.containsKey(FillEffect.GRASS))
381                    roomFX.put(FillEffect.GRASS, Math.min(100, roomFX.get(FillEffect.GRASS) + percentage));
382                else
383                    roomFX.put(FillEffect.GRASS, percentage);
384                if(corridorFX.containsKey(FillEffect.GRASS))
385                    corridorFX.put(FillEffect.GRASS, Math.min(100, corridorFX.get(FillEffect.GRASS) + percentage));
386                else
387                    corridorFX.put(FillEffect.GRASS, percentage);
388                if(caveFX.containsKey(FillEffect.GRASS))
389                    caveFX.put(FillEffect.GRASS, Math.min(100, caveFX.get(FillEffect.GRASS) + percentage));
390                else
391                    caveFX.put(FillEffect.GRASS, percentage);
392        }
393        return this;
394    }
395    /**
396     * Turns the given percentage of floor cells not already adjacent to walls into wall cells, represented by '#'.
397     * If this DungeonGenerator previously had addBoulders called, the latest call will take precedence.
398     * @param env the environment to apply this to
399     * @param percentage the percentage of floor cells not adjacent to walls to fill with boulders.
400     * @return this DungeonGenerator; can be chained
401     */
402    public SectionDungeonGenerator addBoulders(int env, int percentage)
403    {
404        if(percentage < 0) percentage = 0;
405        if(percentage > 100) percentage = 100;
406        switch (env)
407        {
408            case ROOM:
409                if(roomFX.containsKey(FillEffect.BOULDERS)) roomFX.remove(FillEffect.BOULDERS);
410                roomFX.put(FillEffect.BOULDERS, percentage);
411                break;
412            case CORRIDOR:
413                if(corridorFX.containsKey(FillEffect.BOULDERS)) corridorFX.remove(FillEffect.BOULDERS);
414                corridorFX.put(FillEffect.BOULDERS, percentage);
415                break;
416            case CAVE:
417                if(caveFX.containsKey(FillEffect.BOULDERS)) caveFX.remove(FillEffect.BOULDERS);
418                caveFX.put(FillEffect.BOULDERS, percentage);
419                break;
420            default:
421                if(roomFX.containsKey(FillEffect.BOULDERS))
422                    roomFX.put(FillEffect.BOULDERS, Math.min(100, roomFX.get(FillEffect.BOULDERS) + percentage));
423                else
424                    roomFX.put(FillEffect.BOULDERS, percentage);
425                if(corridorFX.containsKey(FillEffect.BOULDERS))
426                    corridorFX.put(FillEffect.BOULDERS, Math.min(100, corridorFX.get(FillEffect.BOULDERS) + percentage));
427                else
428                    corridorFX.put(FillEffect.BOULDERS, percentage);
429                if(caveFX.containsKey(FillEffect.BOULDERS))
430                    caveFX.put(FillEffect.BOULDERS, Math.min(100, caveFX.get(FillEffect.BOULDERS) + percentage));
431                else
432                    caveFX.put(FillEffect.BOULDERS, percentage);
433        }
434        return this;
435    }
436    /**
437     * Turns the given percentage of viable doorways into doors, represented by '+' for doors that allow travel along
438     * the x-axis and '/' for doors that allow travel along the y-axis. If doubleDoors is true,
439     * 2-cell-wide openings will be considered viable doorways and will fill one cell with a wall, the other a door.
440     * If this DungeonGenerator previously had addDoors called, the latest call will take precedence.
441     * @param percentage the percentage of valid openings to corridors to fill with doors; should be between 10 and
442     *                   20 if you want doors to appear more than a few times, but not fill every possible opening.
443     * @param doubleDoors true if you want two-cell-wide openings to receive a door and a wall; false if only
444     *                    one-cell-wide openings should receive doors. Usually, this should be true.
445     * @return this DungeonGenerator; can be chained
446     */
447    public SectionDungeonGenerator addDoors(int percentage, boolean doubleDoors)
448    {
449        if(percentage < 0) percentage = 0;
450        if(percentage > 100) percentage = 100;
451        if(doubleDoors) percentage *= -1;
452        doorFX = percentage;
453        return this;
454    }
455
456    /**
457     * Instructs the generator to add a winding section of corridors into a large area that can be filled without
458     * overwriting rooms, caves, or the edge of the map; wall cells will become either '#' or '.' and corridors will be
459     * overwritten. If the percentage is too high (40% is probably too high to adequately fill), this will fill less than
460     * the requested percentage rather than fill multiple mazes.
461     * @param percentage The percentage of non-room, non-cave, non-edge-of-map wall cells to try to fill with maze.
462     * @return this for chaining
463     */
464    public SectionDungeonGenerator addMaze(int percentage)
465    {
466
467        if(percentage < 0) percentage = 0;
468        if(percentage > 100) percentage = 100;
469        mazeFX = percentage;
470        return this;
471    }
472
473    /**
474     * Instructs the generator to add a lake (here, of water) into a large area that can be filled without overwriting
475     * rooms, caves, or the edge of the map; wall cells will become the deep lake glyph (here, '~'), unless they are
476     * close to an existing room or cave, in which case they become the shallow lake glyph (here, ','), and corridors
477     * that are "covered" by a lake will become bridges, the glyph ':'. If the percentage is too high (40% is probably
478     * too high to adequately fill), this will fill less than the requested percentage rather than fill multiple lakes.
479     * @param percentage The percentage of non-room, non-cave, non-edge-of-map wall cells to try to fill with lake.
480     * @return this for chaining
481     */
482    public SectionDungeonGenerator addLake(int percentage)
483    {
484        return addLake(percentage, '~', ',');
485    }
486
487    /**
488     * Instructs the generator to add a lake into a large area that can be filled without overwriting rooms, caves, or
489     * the edge of the map; wall cells will become the char deepLake, unless they are close to an existing room or cave,
490     * in which case they become the char shallowLake, and corridors that are "covered" by a lake will become bridges,
491     * the glyph ':'. If the percentage is too high (40% is probably too high to adequately fill), this will fill less
492     * than the requested percentage rather than fill multiple lakes.
493     * @param percentage The percentage of non-room, non-cave, non-edge-of-map wall cells to try to fill with lake.
494     * @param deepLake the char to use for deep lake cells, such as '~'
495     * @param shallowLake the char to use for shallow lake cells, such as ','
496     * @return this for chaining
497     */
498    public SectionDungeonGenerator addLake(int percentage, char deepLake, char shallowLake)
499    {
500        if(percentage < 0) percentage = 0;
501        if(percentage > 100) percentage = 100;
502        lakeFX = percentage;
503        deepLakeGlyph = deepLake;
504        shallowLakeGlyph = shallowLake;
505        return this;
506    }
507
508    /**
509     * Turns the given percentage of open area floor cells into trap cells, represented by '^'. Corridors that have no
510     * possible way to move around a trap will not receive traps, ever. If this DungeonGenerator previously had
511     * addTraps called, the latest call will take precedence.
512     * @param env the environment to apply this to
513     * @param percentage the percentage of valid cells to fill with traps; should be no higher than 5 unless
514     *                   the dungeon floor is meant to be a kill screen or minefield.
515     * @return this DungeonGenerator; can be chained
516     */
517    public SectionDungeonGenerator addTraps(int env, int percentage)
518    {
519        if(percentage < 0) percentage = 0;
520        if(percentage > 100) percentage = 100;
521        switch (env)
522        {
523            case ROOM:
524                if(roomFX.containsKey(FillEffect.TRAPS)) roomFX.remove(FillEffect.TRAPS);
525                roomFX.put(FillEffect.TRAPS, percentage);
526                break;
527            case CORRIDOR:
528                if(corridorFX.containsKey(FillEffect.TRAPS)) corridorFX.remove(FillEffect.TRAPS);
529                corridorFX.put(FillEffect.TRAPS, percentage);
530                break;
531            case CAVE:
532                if(caveFX.containsKey(FillEffect.TRAPS)) caveFX.remove(FillEffect.TRAPS);
533                caveFX.put(FillEffect.TRAPS, percentage);
534                break;
535            default:
536                if(roomFX.containsKey(FillEffect.TRAPS))
537                    roomFX.put(FillEffect.TRAPS, Math.min(100, roomFX.get(FillEffect.TRAPS) + percentage));
538                else
539                    roomFX.put(FillEffect.TRAPS, percentage);
540                if(corridorFX.containsKey(FillEffect.TRAPS))
541                    corridorFX.put(FillEffect.TRAPS, Math.min(100, corridorFX.get(FillEffect.TRAPS) + percentage));
542                else
543                    corridorFX.put(FillEffect.TRAPS, percentage);
544                if(caveFX.containsKey(FillEffect.TRAPS))
545                    caveFX.put(FillEffect.TRAPS, Math.min(100, caveFX.get(FillEffect.TRAPS) + percentage));
546                else
547                    caveFX.put(FillEffect.TRAPS, percentage);
548        }
549        return this;
550    }
551
552    /**
553     * Removes any door, water, or trap insertion effects that this DungeonGenerator would put in future dungeons.
554     * @return this DungeonGenerator, with all effects removed. Can be chained.
555     */
556    public SectionDungeonGenerator clearEffects()
557    {
558        roomFX.clear();
559        corridorFX.clear();
560        caveFX.clear();
561        lakeFX = 0;
562        mazeFX = 0;
563        doorFX = 0;
564        return this;
565    }
566
567    protected LinkedHashSet<Coord> removeAdjacent(LinkedHashSet<Coord> coll, Coord pt)
568    {
569        for(Coord temp : new Coord[]{Coord.get(pt.x + 1, pt.y), Coord.get(pt.x - 1, pt.y),
570                Coord.get(pt.x, pt.y + 1), Coord.get(pt.x, pt.y - 1)})
571        {
572            if(coll.contains(temp) && !(temp.x == pt.x && temp.y == pt.y))
573                coll.remove(temp);
574        }
575
576        return coll;
577    }
578    protected LinkedHashSet<Coord> removeAdjacent(LinkedHashSet<Coord> coll, Coord pt1, Coord pt2)
579    {
580
581        for(Coord temp : new Coord[]{Coord.get(pt1.x + 1, pt1.y), Coord.get(pt1.x - 1, pt1.y),
582                Coord.get(pt1.x, pt1.y + 1), Coord.get(pt1.x, pt1.y - 1),
583                Coord.get(pt2.x + 1, pt2.y), Coord.get(pt2.x - 1, pt2.y),
584                Coord.get(pt2.x, pt2.y + 1), Coord.get(pt2.x, pt2.y - 1),})
585        {
586            if(coll.contains(temp) && !(temp.x == pt1.x && temp.y == pt1.y) && !(temp.x == pt2.x && temp.y == pt2.y))
587                coll.remove(temp);
588        }
589
590        return coll;
591    }
592    protected LinkedHashSet<Coord> removeNearby(LinkedHashSet<Coord> coll, char[][] disallowed)
593    {
594        if(coll == null || disallowed == null || disallowed.length == 0 || disallowed[0].length == 0)
595            return new LinkedHashSet<>();
596        LinkedHashSet<Coord> next = new LinkedHashSet<>(coll.size());
597        int width = disallowed.length, height = disallowed[0].length;
598        COORD_WISE:
599        for(Coord c : coll)
600        {
601            for (int x = Math.max(0, c.x - 1); x <= Math.min(width - 1, c.x + 1); x++) {
602
603                for (int y = Math.max(0, c.y - 1); y <= Math.min(height - 1, c.y + 1); y++) {
604                    if(disallowed[x][y] != '#')
605                        continue COORD_WISE;
606                }
607            }
608            next.add(c);
609        }
610
611        return next;
612    }
613
614
615    protected LinkedHashSet<Coord> viableDoorways(boolean doubleDoors, char[][] map, char[][] allCaves,
616                                                  char[][] allCorridors)
617    {
618        LinkedHashSet<Coord> doors = new LinkedHashSet<>();
619        for(int x = 1; x < map.length - 1; x++) {
620            for (int y = 1; y < map[x].length - 1; y++) {
621                if(map[x][y] == '#' || allCorridors[x][y] != '#')
622                    continue;
623                if (doubleDoors) {
624                    if (x >= map.length - 2 || y >= map[x].length - 2)
625                        continue;
626                    else {
627                        if (map[x+1][y] != '#' &&
628                                map[x + 2][y] == '#' && map[x - 1][y] == '#'
629                                && map[x][y + 1] != '#' && map[x][y - 1] != '#'
630                                && map[x+1][y + 1] != '#' && map[x+1][y - 1] != '#') {
631                            if (map[x + 2][y + 1] != '#' || map[x - 1][y + 1] != '#' || map[x + 2][y - 1] != '#' || map[x - 1][y - 1] != '#') {
632                                doors.add(Coord.get(x, y));
633                                doors.add(Coord.get(x + 1, y));
634                                doors = removeAdjacent(doors, Coord.get(x, y), Coord.get(x + 1, y));
635                                continue;
636                            }
637                        } else if (map[x][y+1] != '#' &&
638                                map[x][y + 2] == '#' && map[x][y - 1] == '#'
639                                && map[x + 1][y] != '#' && map[x - 1][y] != '#'
640                                && map[x + 1][y+1] != '#' && map[x - 1][y+1] != '#') {
641                            if (map[x + 1][y + 2] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y + 2] != '#' || map[x - 1][y - 1] != '#') {
642                                doors.add(Coord.get(x, y));
643                                doors.add(Coord.get(x, y + 1));
644                                doors = removeAdjacent(doors, Coord.get(x, y), Coord.get(x, y + 1));
645                                continue;
646                            }
647                        }
648                    }
649                }
650                if (map[x + 1][y] == '#' && map[x - 1][y] == '#' && map[x][y + 1] != '#' && map[x][y - 1] != '#') {
651                    if (map[x + 1][y + 1] != '#' || map[x - 1][y + 1] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y - 1] != '#') {
652                        doors.add(Coord.get(x, y));
653                        doors = removeAdjacent(doors, Coord.get(x, y));
654                    }
655                } else if (map[x][y + 1] == '#' && map[x][y - 1] == '#' && map[x + 1][y] != '#' && map[x - 1][y] != '#') {
656                    if (map[x + 1][y + 1] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y + 1] != '#' || map[x - 1][y - 1] != '#') {
657                        doors.add(Coord.get(x, y));
658                        doors = removeAdjacent(doors, Coord.get(x, y));
659                    }
660                }
661
662            }
663        }
664
665        return removeNearby(doors, allCaves);
666    }
667
668    /**
669     * Generate a char[][] dungeon using TilesetType.DEFAULT_DUNGEON; this produces a dungeon appropriate for a level
670     * of ruins or a partially constructed dungeon. This uses '#' for walls, '.' for floors, '~' for deep water, ',' for
671     * shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that provide
672     * vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in
673     * the generated map.
674     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
675     * @return a char[][] dungeon
676     */
677    public char[][] generate() {
678        return generate(TilesetType.DEFAULT_DUNGEON);
679    }
680
681    /**
682     * Generate a char[][] dungeon given a TilesetType; the comments in that class provide some opinions on what
683     * each TilesetType value could be used for in a game. This uses '#' for walls, '.' for floors, '~' for deep water,
684     * ',' for shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that
685     * provide vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request
686     * these in the generated map.
687     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
688     * @see TilesetType
689     * @param kind a TilesetType enum value, such as TilesetType.DEFAULT_DUNGEON
690     * @return a char[][] dungeon
691     */
692    public char[][] generate(TilesetType kind)
693    {
694        rebuildSeed = rng.getState();
695        environmentType = kind.environment();
696        DungeonBoneGen gen = new DungeonBoneGen(rng);
697        char[][] map = DungeonUtility.wallWrap(gen.generate(kind, width, height));
698
699        seedFixed = false;
700        DijkstraMap dijkstra = new DijkstraMap(map);
701        int frustrated = 0;
702        do {
703            dijkstra.clearGoals();
704            stairsUp = utility.randomFloor(map);
705            dijkstra.setGoal(stairsUp);
706            dijkstra.scan(null);
707            frustrated++;
708        }while (dijkstra.getMappedCount() < width + height && frustrated < 15);
709        double maxDijkstra = 0.0;
710        for (int i = 0; i < width; i++) {
711            for (int j = 0; j < height; j++) {
712                if(dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) {
713                    map[i][j] = '#';
714                }
715                else if(dijkstra.gradientMap[i][j] > maxDijkstra) {
716                    maxDijkstra = dijkstra.gradientMap[i][j];
717                }
718            }
719        }
720        stairsDown = singleRandom(pack(dijkstra.gradientMap, maxDijkstra * 0.7,
721                DijkstraMap.FLOOR), rng);
722        finder = new RoomFinder(map, environmentType);
723        return innerGenerate();
724    }
725
726    /**
727     * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated and an
728     * environment as an int[][], which can often be obtained from MixedGenerator or classes that use it, like
729     * SerpentMapGenerator, with their getEnvironment method.
730     * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method
731     * is meant for adding features like water and doors to existing maps while avoiding placing incongruous features in
732     * areas where they don't fit, like a door in a cave or moss in a room.
733     * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors
734     * that provide horizontal passage, and '/' for doors that provide vertical passage.
735     * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map.
736     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
737     * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors; may be modified in-place
738     * @param environment stores whether a cell is room, corridor, or cave; getEnvironment() typically gives this
739     * @return a char[][] dungeon
740     */
741    public char[][] generate(char[][] baseDungeon, int[][] environment)
742    {
743        if(!seedFixed)
744        {
745            rebuildSeed = rng.getState();
746        }
747        seedFixed = false;
748        char[][] map = DungeonUtility.wallWrap(baseDungeon);
749        width = map.length;
750        height = map[0].length;
751        int[][] env2 = new int[width][height];
752        for (int x = 0; x < width; x++) {
753            System.arraycopy(environment[x], 0, env2[x], 0, height);
754        }
755
756        DijkstraMap dijkstra = new DijkstraMap();
757        dijkstra.measurement = DijkstraMap.Measurement.MANHATTAN;
758        int frustrated = 0;
759        do {
760            dijkstra.initialize(map);
761            dijkstra.clearGoals();
762            stairsUp = utility.randomFloor(map);
763            dijkstra.setGoal(stairsUp);
764            dijkstra.scan(null);
765            frustrated++;
766        }while (dijkstra.getMappedCount() < width + height && frustrated < 15);
767        double maxDijkstra = 0.0;
768        for (int i = 0; i < width; i++) {
769            for (int j = 0; j < height; j++) {
770                if(dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) {
771                    map[i][j] = '#';
772                    env2[i][j] = MixedGenerator.UNTOUCHED;
773                }
774                else if(dijkstra.gradientMap[i][j] > maxDijkstra) {
775                    maxDijkstra = dijkstra.gradientMap[i][j];
776                }
777            }
778        }
779        if(maxDijkstra < 16)
780            return generate(baseDungeon, environment);
781        stairsDown = singleRandom(pack(dijkstra.gradientMap, maxDijkstra * 0.7,
782                DijkstraMap.FLOOR), rng);
783        finder = new RoomFinder(map, env2);
784        return innerGenerate();
785    }
786
787    /**
788     * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated, with
789     * staircases represented by greater than and less than signs, and an environment as an int[][], which can often be
790     * obtained from MixedGenerator or classes that use it, like SerpentMapGenerator, with their getEnvironment method.
791     * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method
792     * is meant for adding features like water and doors to existing maps while avoiding placing incongruous features in
793     * areas where they don't fit, like a door in a cave or moss in a room.
794     * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors
795     * that provide horizontal passage, and '/' for doors that provide vertical passage.
796     * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map.
797     * Also sets the fields stairsUp and stairsDown to null, and expects stairs to be already handled.
798     * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors, with stairs already in;
799     *                    may be modified in-place
800     * @param environment stores whether a cell is room, corridor, or cave; getEnvironment() typically gives this
801     * @return a char[][] dungeon
802     */
803    public char[][] generateRespectingStairs(char[][] baseDungeon, int[][] environment) {
804        if(!seedFixed)
805        {
806            rebuildSeed = rng.getState();
807        }
808        seedFixed = false;
809        char[][] map = DungeonUtility.wallWrap(baseDungeon);
810        int[][] env2 = new int[width][height];
811        for (int x = 0; x < width; x++) {
812            System.arraycopy(environment[x], 0, env2[x], 0, height);
813        }
814        DijkstraMap dijkstra = new DijkstraMap(map);
815        stairsUp = null;
816        stairsDown = null;
817
818        dijkstra.clearGoals();
819        Coord[] stairs = allPacked(pack(map, '<', '>'));
820        for (Coord s : stairs) {
821            dijkstra.setGoal(s);
822        }
823        dijkstra.scan(null);
824        for (int i = 0; i < width; i++) {
825            for (int j = 0; j < height; j++) {
826                if (dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) {
827                    map[i][j] = '#';
828                    env2[i][j] = MixedGenerator.UNTOUCHED;
829                }
830            }
831        }
832        finder = new RoomFinder(map, env2);
833        return innerGenerate();
834    }
835
836
837
838    private char[][] innerGenerate() {
839        dungeon = new char[width][height];
840        for (int x = 0; x < width; x++) {
841            Arrays.fill(dungeon[x], '#');
842        }
843        ArrayList<char[][]> rm = finder.findRooms(),
844                cr = finder.findCorridors(),
845                cv = finder.findCaves();
846        char[][] roomMap = innerGenerate(RoomFinder.merge(rm, width, height), roomFX),
847                allCorridors = RoomFinder.merge(cr, width, height),
848                corridorMap = innerGenerate(allCorridors, corridorFX),
849                allCaves = RoomFinder.merge(cv, width, height),
850                caveMap = innerGenerate(allCaves, caveFX),
851                doorMap = makeDoors(rm, cr, allCaves, allCorridors);
852        char[][][] lakesAndMazes = makeLake(rm, cv);
853        for (int x = 0; x < width; x++) {
854            for (int y = 0; y < height; y++) {
855                if(corridorMap[x][y] != '#' && lakesAndMazes[0][x][y] != '#')
856                    dungeon[x][y] = ':';
857                else if(doorMap[x][y] == '+' || doorMap[x][y] == '/')
858                    dungeon[x][y] = doorMap[x][y];
859                else if(doorMap[x][y] == '*')
860                    dungeon[x][y] = '#';
861                else if(roomMap[x][y] != '#')
862                    dungeon[x][y] = roomMap[x][y];
863                else if(lakesAndMazes[1][x][y] != '#')
864                    dungeon[x][y] = lakesAndMazes[1][x][y];
865                else if(corridorMap[x][y] != '#')
866                    dungeon[x][y] = corridorMap[x][y];
867                else if(caveMap[x][y] != '#')
868                    dungeon[x][y] = caveMap[x][y];
869                else if(lakesAndMazes[0][x][y] != '#')
870                    dungeon[x][y] = lakesAndMazes[0][x][y];
871            }
872        }
873        placement = new Placement(finder);
874        return dungeon;
875
876    }
877    private char[][] makeDoors(ArrayList<char[][]> rooms, ArrayList<char[][]> corridors, char[][] allCaves,
878                               char[][] allCorridors)
879    {
880        char[][] map = new char[width][height];
881        for (int x = 0; x < width; x++) {
882            Arrays.fill(map[x], '#');
883        }
884        if(doorFX == 0 || (rooms.isEmpty() && corridors.isEmpty()))
885            return map;
886        boolean doubleDoors = false;
887        int doorFill = doorFX;
888        if(doorFill < 0)
889        {
890            doubleDoors = true;
891            doorFill *= -1;
892        }
893        ArrayList<char[][]> fused = new ArrayList<>(rooms.size() + corridors.size());
894        fused.addAll(rooms);
895        fused.addAll(corridors);
896
897        map = RoomFinder.merge(fused, width, height);
898
899        LinkedHashSet<Coord> doorways = viableDoorways(doubleDoors, map, allCaves, allCorridors);
900
901
902        int total = doorways.size() * doorFill / 100;
903
904        BigLoop:
905        for(int i = 0; i < total; i++) {
906            Coord entry = rng.getRandomElement(doorways);
907            if (map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '>')
908                continue;
909            if (map[entry.x - 1][entry.y] != '#' && map[entry.x + 1][entry.y] != '#' &&
910                    map[entry.x - 1][entry.y] != '*' && map[entry.x + 1][entry.y] != '*') {
911                map[entry.x][entry.y] = '+';
912            } else {
913                map[entry.x][entry.y] = '/';
914            }
915            Coord[] adj = new Coord[]{Coord.get(entry.x + 1, entry.y), Coord.get(entry.x - 1, entry.y),
916                    Coord.get(entry.x, entry.y + 1), Coord.get(entry.x, entry.y - 1)};
917            for (Coord near : adj) {
918                if (doorways.contains(near)) {
919                    map[near.x][near.y] = '*';
920                    doorways.remove(near);
921                    i++;
922                    doorways.remove(entry);
923                    continue BigLoop;
924                }
925            }
926            doorways.remove(entry);
927        }
928        return map;
929
930    }
931    private char[][][] makeLake(ArrayList<char[][]> rooms, ArrayList<char[][]> caves)
932    {
933        char[][][] maps = new char[2][width][height];
934        char[][] fusedMap;
935        for (int x = 0; x < width; x++) {
936            Arrays.fill(maps[0][x], '#');
937            Arrays.fill(maps[1][x], '#');
938        }
939        if((lakeFX == 0 && mazeFX == 0) || (rooms.isEmpty() && caves.isEmpty()))
940            return maps;
941        int lakeFill = lakeFX, mazeFill = mazeFX;
942        if(lakeFX + mazeFX > 100)
943        {
944            lakeFill -= (lakeFX + mazeFX - 100) / 2;
945            mazeFill -= (lakeFX + mazeFX - 99) / 2;
946        }
947
948        ArrayList<char[][]> fused = new ArrayList<>(rooms.size() + caves.size());
949        fused.addAll(rooms);
950        fused.addAll(caves);
951
952        fusedMap = RoomFinder.merge(fused, width, height);
953        short[] limit = rectangle(1, 1, width - 2, height - 2),
954                potential = intersectPacked(limit, pack(fusedMap, '#'));
955        int ctr = count(potential), potentialMazeSize = ctr * mazeFill / 100, potentialLakeSize = ctr * lakeFill / 100;
956        ArrayList<short[]> viable;
957        short[] chosen;
958        int minSize;
959        Coord center;
960        short[] flooded;
961        boolean[][] deep;
962        if(potentialMazeSize > 0) {
963            viable = split(potential);
964            if (viable.isEmpty())
965                return maps;
966
967            chosen = viable.get(0);
968            minSize = count(chosen);
969            for (short[] sa : viable) {
970                int sz = count(sa);
971                if (sz > minSize) {
972                    chosen = sa;
973                    minSize = sz;
974                }
975            }
976            PacMazeGenerator pac = new PacMazeGenerator(width - width % 3, height - height % 3, rng);
977            char[][] pacMap = pac.generate();
978            center = singleRandom(chosen, rng);
979            flooded = intersectPacked(limit, spill(chosen, packOne(center), potentialMazeSize, rng));
980            short[] pacEnv = removeIsolated(
981                    intersectPacked(
982                            flooded,
983                            translate(
984                                    pack(pacMap, '.'),
985                                    1, 1, width, height)));
986            deep = unpack(pacEnv, width, height);
987
988            for (int x = 1; x < width - 1; x++) {
989                for (int y = 1; y < height - 1; y++) {
990                    if (deep[x][y])
991                        maps[1][x][y] = pacMap[x-1][y-1];
992                }
993            }
994            finder.corridors.put(pacEnv, new ArrayList<short[]>());
995            potential = differencePacked(potential, flooded);
996        }
997        if(potentialLakeSize > 0) {
998            viable = split(potential);
999            if (viable.isEmpty())
1000                return maps;
1001            chosen = viable.get(0);
1002            minSize = count(chosen);
1003            for (short[] sa : viable) {
1004                int sz = count(sa);
1005                if (sz > minSize) {
1006                    chosen = sa;
1007                    minSize = sz;
1008                }
1009            }
1010            center = singleRandom(chosen, rng);
1011            flooded = intersectPacked(limit, spill(chosen, packOne(center), potentialLakeSize, rng));
1012
1013            deep = unpack(flooded, width, height);
1014
1015            short[] shore = intersectPacked(limit,
1016                    flood(fringe(pack(fusedMap, '.'), 3, width, height, true, true),
1017                            flooded, 3, false)),
1018                    lake = unionPacked(flooded, shore);
1019
1020            boolean[][] shallow = unpack(shore, width, height);
1021
1022            for (int x = 0; x < width; x++) {
1023                for (int y = 0; y < height; y++) {
1024                    if (deep[x][y])
1025                        maps[0][x][y] = deepLakeGlyph;
1026                    else if (shallow[x][y])
1027                        maps[0][x][y] = shallowLakeGlyph;
1028                }
1029            }
1030            ArrayList<short[]> change = new ArrayList<>();
1031            for (short[] room : finder.rooms.keys()) {
1032                if (intersects(lake, expand(room, 1, width, height)))
1033                    change.add(room);
1034            }
1035            for (short[] region : change) {
1036                finder.caves.put(region, finder.rooms.remove(region));
1037            }
1038            //finder.caves.put(lake, new ArrayList<short[]>());
1039        }
1040        return maps;
1041    }
1042
1043    private char[][] innerGenerate(char[][] map, EnumMap<FillEffect, Integer> fx)
1044    {
1045        LinkedHashSet<Coord> hazards = new LinkedHashSet<>();
1046        int floorCount = DungeonUtility.countCells(map, '.'),
1047                doorFill = 0,
1048                waterFill = 0,
1049                grassFill = 0,
1050                trapFill = 0,
1051                boulderFill = 0,
1052                islandSpacing = 0;
1053
1054        if(fx.containsKey(FillEffect.GRASS)) {
1055            grassFill = fx.get(FillEffect.GRASS);
1056        }
1057        if(fx.containsKey(FillEffect.WATER)) {
1058            waterFill = fx.get(FillEffect.WATER);
1059        }
1060        if(fx.containsKey(FillEffect.BOULDERS)) {
1061            boulderFill = fx.get(FillEffect.BOULDERS) * floorCount / 100;
1062        }
1063        if(fx.containsKey(FillEffect.ISLANDS)) {
1064            islandSpacing = fx.get(FillEffect.ISLANDS);
1065        }
1066        if(fx.containsKey(FillEffect.TRAPS)) {
1067            trapFill = fx.get(FillEffect.TRAPS);
1068        }
1069        if (boulderFill > 0.0) {
1070            short[] floor = pack(map, '.');
1071            short[] viable = retract(floor, 1, width, height, true);
1072            ArrayList<Coord> boulders = randomPortion(viable, boulderFill, rng);
1073            for (Coord boulder : boulders) {
1074                map[boulder.x][boulder.y] = '#';
1075            }
1076        }
1077
1078
1079        if(trapFill > 0) {
1080            for (int x = 1; x < map.length - 1; x++) {
1081                for (int y = 1; y < map[x].length - 1; y++) {
1082                    if (map[x][y] == '.') {
1083                        int ctr = 0;
1084                        if (map[x + 1][y] != '#') ++ctr;
1085                        if (map[x - 1][y] != '#') ++ctr;
1086                        if (map[x][y + 1] != '#') ++ctr;
1087                        if (map[x][y - 1] != '#') ++ctr;
1088                        if (map[x + 1][y + 1] != '#') ++ctr;
1089                        if (map[x - 1][y + 1] != '#') ++ctr;
1090                        if (map[x + 1][y - 1] != '#') ++ctr;
1091                        if (map[x - 1][y - 1] != '#') ++ctr;
1092                        if (ctr >= 5) hazards.add(Coord.get(x, y));
1093                    }
1094                }
1095            }
1096        }
1097        short[] floors = pack(map, '.'), working;
1098        floorCount = count(floors);
1099        float waterRate = waterFill / 100.0f, grassRate = grassFill / 100.0f;
1100        if(waterRate + grassRate > 1.0f)
1101        {
1102            waterRate /= (waterFill + grassFill) / 100.0f;
1103            grassRate /= (waterFill + grassFill) / 100.0f;
1104        }
1105        int targetWater = Math.round(floorCount * waterRate),
1106                targetGrass = Math.round(floorCount * grassRate),
1107                sizeWaterPools = targetWater / rng.between(3, 6),
1108                sizeGrassPools = targetGrass / rng.between(2, 5);
1109
1110        Coord[] scatter;
1111        int remainingWater = targetWater, remainingGrass = targetGrass;
1112        if(targetWater > 0) {
1113            scatter = fractionPacked(floors, 7);
1114            scatter = rng.shuffle(scatter, new Coord[scatter.length]);
1115            ArrayList<Coord> allWater = new ArrayList<>(targetWater);
1116            for (int i = 0; i < scatter.length; i++) {
1117                if (remainingWater > 5) //remainingWater >= targetWater * 0.02 &&
1118                {
1119                    if(!queryPacked(floors, scatter[i].x, scatter[i].y))
1120                        continue;
1121                    working = spill(floors, packOne(scatter[i]), rng.between(4, Math.min(remainingWater, sizeWaterPools)), rng);
1122
1123                    floors = differencePacked(floors, working);
1124                    Coord[] pts = allPacked(working);
1125                    remainingWater -= pts.length;
1126                    Collections.addAll(allWater, pts);
1127                } else
1128                    break;
1129            }
1130
1131            for (Coord pt : allWater) {
1132                hazards.remove(pt);
1133                //obstacles.add(pt);
1134                if (map[pt.x][pt.y] != '<' && map[pt.x][pt.y] != '>')
1135                    map[pt.x][pt.y] = '~';
1136            }
1137            for (Coord pt : allWater) {
1138                if (map[pt.x][pt.y] != '<' && map[pt.x][pt.y] != '>' &&
1139                        (map[pt.x - 1][pt.y] == '.' || map[pt.x + 1][pt.y] == '.' ||
1140                                map[pt.x][pt.y - 1] == '.' || map[pt.x][pt.y + 1] == '.'))
1141                    map[pt.x][pt.y] = ',';
1142            }
1143        }
1144        if(targetGrass > 0) {
1145            scatter = fractionPacked(floors, 7);
1146            scatter = rng.shuffle(scatter, new Coord[scatter.length]);
1147            Coord p;
1148            for (int i = 0; i < scatter.length; i++) {
1149                if (remainingGrass > 5) //remainingGrass >= targetGrass * 0.02 &&
1150                {
1151                    working = spill(floors, packOne(scatter[i]), rng.between(4, Math.min(remainingGrass, sizeGrassPools)), rng);
1152                    if (working.length == 0)
1153                        continue;
1154                    floors = differencePacked(floors, working);
1155                    Coord[] pts = allPacked(working);
1156                    remainingGrass -= pts.length;
1157                    for (int c = 0; c < pts.length; c++) {
1158                        p = pts[c];
1159                        map[p.x][p.y] = '"';
1160                    }
1161                } else
1162                    break;
1163            }
1164        }
1165
1166        if(islandSpacing > 1 && targetWater > 0) {
1167            ArrayList<Coord> islands = PoissonDisk.sampleMap(map, 1f * islandSpacing, rng, '#', '.', '"', '+', '/', '^', '<', '>');
1168            for (Coord c : islands) {
1169                map[c.x][c.y] = '.';
1170                if (map[c.x - 1][c.y] != '#' && map[c.x - 1][c.y] != '<' && map[c.x - 1][c.y] != '>')
1171                    map[c.x - 1][c.y] = ',';
1172                if (map[c.x + 1][c.y] != '#' && map[c.x + 1][c.y] != '<' && map[c.x + 1][c.y] != '>')
1173                    map[c.x + 1][c.y] = ',';
1174                if (map[c.x][c.y - 1] != '#' && map[c.x][c.y - 1] != '<' && map[c.x][c.y - 1] != '>')
1175                    map[c.x][c.y - 1] = ',';
1176                if (map[c.x][c.y + 1] != '#' && map[c.x][c.y + 1] != '<' && map[c.x][c.y + 1] != '>')
1177                    map[c.x][c.y + 1] = ',';
1178            }
1179        }
1180
1181        if(trapFill > 0)
1182        {
1183            int total = hazards.size() * trapFill / 100;
1184
1185            for(int i = 0; i < total; i++)
1186            {
1187                Coord entry = rng.getRandomElement(hazards);
1188                if(map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '<')
1189                    continue;
1190                map[entry.x][entry.y] = '^';
1191                hazards.remove(entry);
1192            }
1193        }
1194
1195        return map;
1196
1197    }
1198
1199    /**
1200     * Gets the seed that can be used to rebuild an identical dungeon to the latest one generated (or the seed that
1201     * will be used to generate the first dungeon if none has been made yet). You can pass the long this returns to
1202     * the setState() method on this class' rng field, which assuming all other calls to generate a dungeon are
1203     * identical, will ensure generate() or generateRespectingStairs() will produce the same dungeon output as the
1204     * dungeon originally generated with the seed this returned.
1205     * <br>
1206     * You can also call getState() on the rng field yourself immediately before generating a dungeon, but this method
1207     * handles some complexities of when the state is actually used to generate a dungeon; since StatefulRNG objects can
1208     * be shared between different classes that use random numbers, the state could change between when you call
1209     * getState() and when this class generates a dungeon. Using getRebuildSeed() eliminates that confusion.
1210     * @return a seed as a long that can be passed to setState() on this class' rng field to recreate a dungeon
1211     */
1212    public long getRebuildSeed() {
1213        return rebuildSeed;
1214    }
1215
1216    /**
1217     * Provides a string representation of the latest generated dungeon.
1218     *
1219     * @return a printable string version of the latest generated dungeon.
1220     */
1221    @Override
1222        public String toString() {
1223        char[][] trans = new char[height][width];
1224        for (int x = 0; x < width; x++) {
1225            for (int y = 0; y < height; y++) {
1226                trans[y][x] = dungeon[x][y];
1227            }
1228        }
1229        StringBuffer sb = new StringBuffer();
1230        for (int row = 0; row < height; row++) {
1231            sb.append(trans[row]);
1232            sb.append('\n');
1233        }
1234        return sb.toString();
1235    }
1236
1237}