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.ArrayList;
009import java.util.Collections;
010import java.util.EnumMap;
011import java.util.LinkedHashSet;
012
013import static squidpony.squidmath.CoordPacker.*;
014
015/**
016 * The primary way to create a more-complete dungeon, layering different effects and modifications on top of
017 * a DungeonBoneGen's dungeon or another dungeon without such effects. Also ensures only connected regions of the map
018 * are used by filling unreachable areas with walls, and can find far-apart staircase positions if generate() is used or
019 * can keep existing staircases in a map 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(). Some of these take different parameters, like addDoors() which need to know if it should check openings
024 * that are two cells wide to add a door and a wall to, or whether it should only add doors to single-cell openings.
025 * Then call generate() to get a char[][] with the desired dungeon map, using a fixed repertoire of chars to represent
026 * the different features. After calling generate(), you can safely get the values from the stairsUp and stairsDown
027 * fields, which are Coords that should be a long distance from each other but connected in the dungeon. You may want
028 * to change those to staircase characters, but there's no requirement to do anything with them. The DungeonUtility
029 * field of this class, utility, is a convenient way of accessing the non-static methods in that class, such as
030 * randomFloor(), without needing to create another DungeonUtility (this class creates one, so you don't have to).
031 * <br>
032 * Previews for the kinds of dungeon this generates, given a certain argument to generate():
033 * <ul>
034 *     <li>Using TilesetType.DEFAULT_DUNGEON (text, click "Raw", may need to zoom out): https://gist.github.com/tommyettinger/a3bd413b903f2e103541</li>
035 *     <li>Using TilesetType.DEFAULT_DUNGEON (graphical, scroll down and to the right): http://tommyettinger.github.io/home/PixVoxel/dungeon/dungeon.html</li>
036 *     <li>Using SerpentMapGenerator.generate()  (text, click "Raw", may need to zoom out): https://gist.github.com/tommyettinger/93b47048fc8a209a9712</li>
037 * </ul>
038 * <br>
039 * As of March 6, 2016, the algorithm this uses to place water and grass was swapped for a more precise version. You no
040 * longer need to give this 150% in addWater or addGrass to effectively produce 100% water or grass, and this should be
041 * no more than 1.1% different from the percentage you request for any effects. If you need to reproduce dungeons with
042 * the same seed and get the same (imprecise) results as before this change, you can use a subclass of this,
043 * LegacyDungeonGenerator, which needs the same "150% means 100%, 75% means 50%" adjustments as before. The API should
044 * be identical, and both will return DungeonGenerator values when they return something for chaining.
045 * @see squidpony.squidgrid.mapping.DungeonUtility this class exposes a DungeonUtility member; DungeonUtility also has many useful static methods
046 * @see squidpony.squidgrid.mapping.LegacyDungeonGenerator for the less-precise behavior; at least it's consistent
047 *
048 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
049 * @author Tommy Ettinger - https://github.com/tommyettinger
050 */
051public class DungeonGenerator {
052
053    /**
054     * The effects that can be applied to this dungeon. More may be added in future releases.
055     */
056    public enum FillEffect
057    {
058        /**
059         * Water, represented by '~'
060         */
061        WATER,
062        /**
063         * Doors, represented by '+' for east-to-west connections or '/' for north-to-south ones.
064         */
065        DOORS,
066        /**
067         * Traps, represented by '^'
068         */
069        TRAPS,
070        /**
071         * Grass, represented by '"'
072         */
073        GRASS,
074        /**
075         * Boulders strewn about open areas, represented by '#' and treated as walls
076         */
077        BOULDERS,
078        /**
079         * Islands of ground, '.', surrounded by shallow water, ',', to place in water at evenly spaced points
080         */
081        ISLANDS
082    }
083
084    /**
085     * The effects that will be applied when generate is called. Strongly prefer using addWater, addDoors, addTraps,
086     * and addGrass.
087     */
088    public EnumMap<FillEffect, Integer> fx;
089    protected DungeonBoneGen gen;
090    public DungeonUtility utility;
091    protected int height, width;
092    public Coord stairsUp = null, stairsDown = null;
093    public StatefulRNG rng;
094    protected long rebuildSeed;
095    protected boolean seedFixed = false;
096
097    protected char[][] dungeon = null;
098
099    /**
100     * Get the most recently generated char[][] dungeon out of this class. The
101     * dungeon may be null if generate() or setDungeon() have not been called.
102     * @return a char[][] dungeon, or null.
103     */
104    public char[][] getDungeon() {
105        return dungeon;
106    }
107    /**
108     * Get the most recently generated char[][] dungeon out of this class without any chars other than '#' or '.', for
109     * walls and floors respectively. The dungeon may be null if generate() or setDungeon() have not been called.
110     * @return a char[][] dungeon with only '#' for walls and '.' for floors, or null.
111     */
112    public char[][] getBareDungeon() {
113        return DungeonUtility.simplifyDungeon(dungeon);
114    }
115
116    /**
117     * Change the underlying char[][]; only affects the toString method, and of course getDungeon.
118     * @param dungeon a char[][], probably produced by an earlier call to this class and then modified.
119     */
120    public void setDungeon(char[][] dungeon) {
121        this.dungeon = dungeon;
122        if(dungeon == null)
123        {
124            width = 0;
125            height = 0;
126            return;
127        }
128        width = dungeon.length;
129        if(width > 0)
130            height = dungeon[0].length;
131    }
132
133    /**
134     * Height of the dungeon in cells.
135     * @return Height of the dungeon in cells.
136     */
137    public int getHeight() {
138        return height;
139    }
140
141    /**
142     * Width of the dungeon in cells.
143     * @return Width of the dungeon in cells.
144     */
145    public int getWidth() {
146        return width;
147    }
148
149
150    /**
151     * Make a DungeonGenerator with a LightRNG using a random seed, height 40, and width 40.
152     */
153    public DungeonGenerator()
154    {
155        rng = new StatefulRNG();
156        gen = new DungeonBoneGen(rng);
157        utility = new DungeonUtility(rng);
158        rebuildSeed = rng.getState();
159        height = 40;
160        width = 40;
161        fx = new EnumMap<>(FillEffect.class);
162    }
163
164    /**
165     * Make a DungeonGenerator with the given height and width; the RNG used for generating a dungeon and
166     * adding features will be a LightRNG using a random seed.
167     * @param width The width of the dungeon in cells
168     * @param height The height of the dungeon in cells
169     */
170    public DungeonGenerator(int width, int height)
171    {
172        this(width, height, new RNG(new LightRNG()));
173    }
174
175    /**
176     * Make a DungeonGenerator with the given height, width, and RNG. Use this if you want to seed the RNG.
177     * @param width The width of the dungeon in cells
178     * @param height The height of the dungeon in cells
179     * @param rng The RNG to use for all purposes in this class; if it is a StatefulRNG, then it will be used as-is,
180     *            but if it is not a StatefulRNG, a new StatefulRNG will be used, randomly seeded by this parameter
181     */
182    public DungeonGenerator(int width, int height, RNG rng)
183    {
184        this.rng = (rng instanceof StatefulRNG) ? (StatefulRNG) rng : new StatefulRNG(rng.nextLong());
185        gen = new DungeonBoneGen(this.rng);
186        utility = new DungeonUtility(this.rng);
187        rebuildSeed = this.rng.getState();
188        this.height = height;
189        this.width = width;
190        fx = new EnumMap<>(FillEffect.class);
191    }
192
193    /**
194     * Copies all fields from copying and makes a new DungeonGenerator.
195     * @param copying the DungeonGenerator to copy
196     */
197    public DungeonGenerator(DungeonGenerator copying)
198    {
199        rng = new StatefulRNG(copying.rng.getState());
200        gen = new DungeonBoneGen(rng);
201        utility = new DungeonUtility(rng);
202        rebuildSeed = rng.getState();
203        height = copying.height;
204        width = copying.width;
205        fx = new EnumMap<>(copying.fx);
206        dungeon = copying.dungeon;
207    }
208
209    /**
210     * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be
211     * clustered into a random number of pools, with more appearing if needed to fill the percentage.
212     * Each pool will have randomized volume that should fill or get very close to filling the requested
213     * percentage, unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater
214     * called, the latest call will take precedence. No islands will be placed with this variant, but the edge of the
215     * water will be shallow, represented by ','.
216     * @param percentage the percentage of floor cells to fill with water
217     * @return this DungeonGenerator; can be chained
218     */
219    public DungeonGenerator addWater(int percentage)
220    {
221        if(percentage < 0) percentage = 0;
222        if(percentage > 100) percentage = 100;
223        if(fx.containsKey(FillEffect.WATER)) fx.remove(FillEffect.WATER);
224        fx.put(FillEffect.WATER, percentage);
225        return this;
226    }
227    /**
228     * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be
229     * clustered into a random number of pools, with more appearing if needed to fill the percentage. Each pool will
230     * have randomized volume that should fill or get very close to filling the requested percentage,
231     * unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater called, the
232     * latest call will take precedence. If islandSpacing is greater than 1, then this will place islands of floor, '.',
233     * surrounded by shallow water, ',', at about the specified distance with Euclidean measurement.
234     * @param percentage the percentage of floor cells to fill with water
235     * @param islandSpacing if greater than 1, islands will be placed randomly this many cells apart.
236     * @return this DungeonGenerator; can be chained
237     */
238    public DungeonGenerator addWater(int percentage, int islandSpacing)
239    {
240        if(percentage < 0) percentage = 0;
241        if(percentage > 100) percentage = 100;
242        if(fx.containsKey(FillEffect.WATER)) fx.remove(FillEffect.WATER);
243        fx.put(FillEffect.WATER, percentage);
244        if(fx.containsKey(FillEffect.ISLANDS)) fx.remove(FillEffect.ISLANDS);
245        if(islandSpacing > 1)
246            fx.put(FillEffect.ISLANDS, islandSpacing);
247        return this;
248    }
249
250    /**
251     * Turns the majority of the given percentage of floor cells into grass cells, represented by '"'. Grass will be
252     * clustered into a random number of patches, with more appearing if needed to fill the percentage. Each area will
253     * have randomized volume that should fill or get very close to filling the requested percentage,
254     * unless the patches encounter too much tight space. If this DungeonGenerator previously had addGrass called, the
255     * latest call will take precedence.
256     * @param percentage the percentage of floor cells to fill with grass
257     * @return this DungeonGenerator; can be chained
258     */
259    public DungeonGenerator addGrass(int percentage)
260    {
261        if(percentage < 0) percentage = 0;
262        if(percentage > 100) percentage = 100;
263        if(fx.containsKey(FillEffect.GRASS)) fx.remove(FillEffect.GRASS);
264        fx.put(FillEffect.GRASS, percentage);
265        return this;
266    }
267    /**
268     * Turns the given percentage of floor cells not already adjacent to walls into wall cells, represented by '#'.
269     * If this DungeonGenerator previously had addBoulders called, the latest call will take precedence.
270     * @param percentage the percentage of floor cells not adjacent to walls to fill with boulders.
271     * @return this DungeonGenerator; can be chained
272     */
273    public DungeonGenerator addBoulders(int percentage)
274    {
275        if(percentage < 0) percentage = 0;
276        if(percentage > 100) percentage = 100;
277        if(fx.containsKey(FillEffect.BOULDERS)) fx.remove(FillEffect.BOULDERS);
278        fx.put(FillEffect.BOULDERS, percentage);
279        return this;
280    }
281    /**
282     * Turns the given percentage of viable doorways into doors, represented by '+' for doors that allow travel along
283     * the x-axis and '/' for doors that allow travel along the y-axis. If doubleDoors is true,
284     * 2-cell-wide openings will be considered viable doorways and will fill one cell with a wall, the other a door.
285     * If this DungeonGenerator previously had addDoors called, the latest call will take precedence.
286     * @param percentage the percentage of valid openings to corridors to fill with doors; should be between 10 and
287     *                   20 if you want doors to appear more than a few times, but not fill every possible opening.
288     * @param doubleDoors true if you want two-cell-wide openings to receive a door and a wall; false if only
289     *                    one-cell-wide openings should receive doors. Usually, this should be true.
290     * @return this DungeonGenerator; can be chained
291     */
292    public DungeonGenerator addDoors(int percentage, boolean doubleDoors)
293    {
294        if(percentage < 0) percentage = 0;
295        if(percentage > 100) percentage = 100;
296        if(doubleDoors) percentage *= -1;
297        if(fx.containsKey(FillEffect.DOORS)) fx.remove(FillEffect.DOORS);
298        fx.put(FillEffect.DOORS, percentage);
299        return this;
300    }
301
302    /**
303     * Turns the given percentage of open area floor cells into trap cells, represented by '^'. Corridors that have no
304     * possible way to move around a trap will not receive traps, ever. If this DungeonGenerator previously had
305     * addTraps called, the latest call will take precedence.
306     * @param percentage the percentage of valid cells to fill with traps; should be no higher than 5 unless
307     *                   the dungeon floor is meant to be a kill screen or minefield.
308     * @return this DungeonGenerator; can be chained
309     */
310    public DungeonGenerator addTraps(int percentage)
311    {
312        if(percentage < 0) percentage = 0;
313        if(percentage > 100) percentage = 100;
314        if(fx.containsKey(FillEffect.TRAPS)) fx.remove(FillEffect.TRAPS);
315        fx.put(FillEffect.TRAPS, percentage);
316        return this;
317    }
318
319    /**
320     * Removes any door, water, or trap insertion effects that this DungeonGenerator would put in future dungeons.
321     * @return this DungeonGenerator, with all effects removed. Can be chained.
322     */
323    public DungeonGenerator clearEffects()
324    {
325        fx.clear();
326        return this;
327    }
328
329    protected LinkedHashSet<Coord> removeAdjacent(LinkedHashSet<Coord> coll, Coord pt)
330    {
331        for(Coord temp : new Coord[]{Coord.get(pt.x + 1, pt.y), Coord.get(pt.x - 1, pt.y),
332                Coord.get(pt.x, pt.y + 1), Coord.get(pt.x, pt.y - 1)})
333        {
334            if(coll.contains(temp) && !(temp.x == pt.x && temp.y == pt.y))
335                coll.remove(temp);
336        }
337
338        return coll;
339    }
340    protected LinkedHashSet<Coord> removeAdjacent(LinkedHashSet<Coord> coll, Coord pt1, Coord pt2)
341    {
342
343        for(Coord temp : new Coord[]{Coord.get(pt1.x + 1, pt1.y), Coord.get(pt1.x - 1, pt1.y),
344                Coord.get(pt1.x, pt1.y + 1), Coord.get(pt1.x, pt1.y - 1),
345                Coord.get(pt2.x + 1, pt2.y), Coord.get(pt2.x - 1, pt2.y),
346                Coord.get(pt2.x, pt2.y + 1), Coord.get(pt2.x, pt2.y - 1),})
347        {
348            if(coll.contains(temp) && !(temp.x == pt1.x && temp.y == pt1.y) && !(temp.x == pt2.x && temp.y == pt2.y))
349                coll.remove(temp);
350        }
351
352        return coll;
353    }
354
355    protected LinkedHashSet<Coord> viableDoorways(boolean doubleDoors, char[][] map)
356    {
357        LinkedHashSet<Coord> doors = new LinkedHashSet<>();
358        for(int x = 1; x < map.length - 1; x++) {
359            for (int y = 1; y < map[x].length - 1; y++) {
360                if(map[x][y] == '#')
361                    continue;
362                if (doubleDoors) {
363                    if (x >= map.length - 2 || y >= map[x].length - 2)
364                        continue;
365                    else {
366                        if (map[x+1][y] != '#' &&
367                                map[x + 2][y] == '#' && map[x - 1][y] == '#'
368                                && map[x][y + 1] != '#' && map[x][y - 1] != '#'
369                                && map[x+1][y + 1] != '#' && map[x+1][y - 1] != '#') {
370                            if (map[x + 2][y + 1] != '#' || map[x - 1][y + 1] != '#' || map[x + 2][y - 1] != '#' || map[x - 1][y - 1] != '#') {
371                                doors.add(Coord.get(x, y));
372                                doors.add(Coord.get(x + 1, y));
373                                doors = removeAdjacent(doors, Coord.get(x, y), Coord.get(x + 1, y));
374                                continue;
375                            }
376                        } else if (map[x][y+1] != '#' &&
377                                map[x][y + 2] == '#' && map[x][y - 1] == '#'
378                                && map[x + 1][y] != '#' && map[x - 1][y] != '#'
379                                && map[x + 1][y+1] != '#' && map[x - 1][y+1] != '#') {
380                            if (map[x + 1][y + 2] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y + 2] != '#' || map[x - 1][y - 1] != '#') {
381                                doors.add(Coord.get(x, y));
382                                doors.add(Coord.get(x, y + 1));
383                                doors = removeAdjacent(doors, Coord.get(x, y), Coord.get(x, y + 1));
384                                continue;
385                            }
386                        }
387                    }
388                }
389                if (map[x + 1][y] == '#' && map[x - 1][y] == '#' && map[x][y + 1] != '#' && map[x][y - 1] != '#') {
390                    if (map[x + 1][y + 1] != '#' || map[x - 1][y + 1] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y - 1] != '#') {
391                        doors.add(Coord.get(x, y));
392                        doors = removeAdjacent(doors, Coord.get(x, y));
393                    }
394                } else if (map[x][y + 1] == '#' && map[x][y - 1] == '#' && map[x + 1][y] != '#' && map[x - 1][y] != '#') {
395                    if (map[x + 1][y + 1] != '#' || map[x + 1][y - 1] != '#' || map[x - 1][y + 1] != '#' || map[x - 1][y - 1] != '#') {
396                        doors.add(Coord.get(x, y));
397                        doors = removeAdjacent(doors, Coord.get(x, y));
398                    }
399                }
400
401            }
402        }
403
404
405        return doors;
406    }
407
408    /**
409     * Generate a char[][] dungeon using TilesetType.DEFAULT_DUNGEON; this produces a dungeon appropriate for a level
410     * of ruins or a partially constructed dungeon. This uses '#' for walls, '.' for floors, '~' for deep water, ',' for
411     * shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that provide
412     * vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in
413     * the generated map.
414     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
415     * @return a char[][] dungeon
416     */
417    public char[][] generate() {
418        return generate(TilesetType.DEFAULT_DUNGEON);
419    }
420
421    /**
422     * Generate a char[][] dungeon given a TilesetType; the comments in that class provide some opinions on what
423     * each TilesetType value could be used for in a game. This uses '#' for walls, '.' for floors, '~' for deep water,
424     * ',' for shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that
425     * provide vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request
426     * these in the generated map.
427     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
428     * @see squidpony.squidgrid.mapping.styled.TilesetType
429     * @param kind a TilesetType enum value, such as TilesetType.DEFAULT_DUNGEON
430     * @return a char[][] dungeon
431     */
432    public char[][] generate(TilesetType kind)
433    {
434        seedFixed = true;
435        rebuildSeed = rng.getState();
436        return generate(gen.generate(kind, width, height));
437    }
438
439    /**
440     * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated.
441     * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method
442     * is meant for adding features like water and doors to existing simple maps.
443     * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors
444     * that provide horizontal passage, and '/' for doors that provide vertical passage.
445     * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map.
446     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
447     * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors; may be modified in-place
448     * @return a char[][] dungeon
449     */
450    public char[][] generate(char[][] baseDungeon)
451    {
452        if(!seedFixed)
453        {
454            rebuildSeed = rng.getState();
455        }
456        seedFixed = false;
457        char[][] map = DungeonUtility.wallWrap(baseDungeon);
458        width = map.length;
459        height = map[0].length;
460        DijkstraMap dijkstra = new DijkstraMap(map);
461        int frustrated = 0;
462        do {
463            dijkstra.clearGoals();
464            stairsUp = utility.randomFloor(map);
465            dijkstra.setGoal(stairsUp);
466            dijkstra.scan(null);
467            frustrated++;
468        }while (dijkstra.getMappedCount() < width + height && frustrated < 15);
469        double maxDijkstra = 0.0;
470        for (int i = 0; i < width; i++) {
471            for (int j = 0; j < height; j++) {
472                if(dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) {
473                    map[i][j] = '#';
474                }
475                else if(dijkstra.gradientMap[i][j] > maxDijkstra) {
476                    maxDijkstra = dijkstra.gradientMap[i][j];
477                }
478            }
479        }
480        stairsDown = singleRandom(pack(dijkstra.gradientMap, maxDijkstra * 0.7,
481                DijkstraMap.FLOOR), rng);
482
483        return innerGenerate(map);
484    }
485
486    /**
487     * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated, and that
488     * already has staircases represented by greater than and less than signs.
489     * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method
490     * is meant for adding features like water and doors to existing simple maps.
491     * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors
492     * that provide horizontal passage, and '/' for doors that provide vertical passage.
493     * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map.
494     * Also sets the fields stairsUp and stairsDown to null, and expects stairs to be already handled.
495     * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors, with stairs already in;
496     *                    may be modified in-place
497     * @return a char[][] dungeon
498     */
499    public char[][] generateRespectingStairs(char[][] baseDungeon) {
500        if(!seedFixed)
501        {
502            rebuildSeed = rng.getState();
503        }
504        seedFixed = false;
505        char[][] map = DungeonUtility.wallWrap(baseDungeon);
506        DijkstraMap dijkstra = new DijkstraMap(map);
507        stairsUp = null;
508        stairsDown = null;
509
510        dijkstra.clearGoals();
511        Coord[] stairs = allPacked(pack(map, '<', '>'));
512        for (Coord s : stairs) {
513            dijkstra.setGoal(s);
514        }
515        dijkstra.scan(null);
516        for (int i = 0; i < width; i++) {
517            for (int j = 0; j < height; j++) {
518                if (dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) {
519                    map[i][j] = '#';
520                }
521            }
522        }
523        return innerGenerate(map);
524    }
525
526
527
528
529    private char[][] innerGenerate(char[][] map)
530    {
531        LinkedHashSet<Coord> doorways;
532        LinkedHashSet<Coord> hazards = new LinkedHashSet<>();
533        Coord temp;
534        boolean doubleDoors = false;
535        int floorCount = DungeonUtility.countCells(map, '.'),
536                doorFill = 0,
537                waterFill = 0,
538                grassFill = 0,
539                trapFill = 0,
540                boulderFill = 0,
541                islandSpacing = 0;
542        if(fx.containsKey(FillEffect.DOORS))
543        {
544            doorFill = fx.get(FillEffect.DOORS);
545            if(doorFill < 0)
546            {
547                doubleDoors = true;
548                doorFill *= -1;
549            }
550        }
551        if(fx.containsKey(FillEffect.GRASS)) {
552            grassFill = fx.get(FillEffect.GRASS);
553        }
554        if(fx.containsKey(FillEffect.WATER)) {
555            waterFill = fx.get(FillEffect.WATER);
556        }
557        if(fx.containsKey(FillEffect.BOULDERS)) {
558            boulderFill = fx.get(FillEffect.BOULDERS) * floorCount / 100;
559        }
560        if(fx.containsKey(FillEffect.ISLANDS)) {
561            islandSpacing = fx.get(FillEffect.ISLANDS);
562        }
563        if(fx.containsKey(FillEffect.TRAPS)) {
564            trapFill = fx.get(FillEffect.TRAPS);
565        }
566
567        doorways = viableDoorways(doubleDoors, map);
568
569        LinkedHashSet<Coord> obstacles = new LinkedHashSet<>(doorways.size() * doorFill / 100);
570        if(doorFill > 0)
571        {
572            int total = doorways.size() * doorFill / 100;
573
574            BigLoop:
575            for(int i = 0; i < total; i++)
576            {
577                Coord entry = rng.getRandomElement(doorways);
578                if(map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '>')
579                    continue;
580                if(map[entry.x - 1][entry.y] != '#' && map[entry.x + 1][entry.y] != '#')
581                {
582                    map[entry.x][entry.y] = '+';
583                }
584                else {
585                    map[entry.x][entry.y] = '/';
586                }
587                obstacles.add(entry);
588                Coord[] adj = new Coord[]{Coord.get(entry.x + 1, entry.y), Coord.get(entry.x - 1, entry.y),
589                        Coord.get(entry.x, entry.y + 1), Coord.get(entry.x, entry.y - 1)};
590                for(Coord near : adj) {
591                    if (doorways.contains(near)) {
592                        map[near.x][near.y] = '#';
593                        obstacles.add(near);
594                        doorways.remove(near);
595                        i++;
596                        doorways.remove(entry);
597                        continue BigLoop;
598                    }
599                }
600                doorways.remove(entry);
601            }
602        }
603        if (boulderFill > 0.0) {
604            short[] floor = pack(map, '.');
605            short[] viable = retract(floor, 1, width, height, true);
606            ArrayList<Coord> boulders = randomPortion(viable, boulderFill, rng);
607            for (Coord boulder : boulders) {
608                map[boulder.x][boulder.y] = '#';
609            }
610        }
611
612
613        if(trapFill > 0) {
614            for (int x = 1; x < map.length - 1; x++) {
615                for (int y = 1; y < map[x].length - 1; y++) {
616                    temp = Coord.get(x, y);
617                    if (map[x][y] == '.' && !obstacles.contains(temp)) {
618                        int ctr = 0;
619                        if (map[x + 1][y] != '#') ++ctr;
620                        if (map[x - 1][y] != '#') ++ctr;
621                        if (map[x][y + 1] != '#') ++ctr;
622                        if (map[x][y - 1] != '#') ++ctr;
623                        if (map[x + 1][y + 1] != '#') ++ctr;
624                        if (map[x - 1][y + 1] != '#') ++ctr;
625                        if (map[x + 1][y - 1] != '#') ++ctr;
626                        if (map[x - 1][y - 1] != '#') ++ctr;
627                        if (ctr >= 5) hazards.add(Coord.get(x, y));
628                    }
629                }
630            }
631        }
632        short[] floors = pack(map, '.'), working;
633        floorCount = count(floors);
634        float waterRate = waterFill / 100.0f, grassRate = grassFill / 100.0f;
635        if(waterRate + grassRate > 1.0f)
636        {
637            waterRate /= (waterFill + grassFill) / 100.0f;
638            grassRate /= (waterFill + grassFill) / 100.0f;
639        }
640        int targetWater = Math.round(floorCount * waterRate),
641                targetGrass = Math.round(floorCount * grassRate),
642                sizeWaterPools = targetWater / rng.between(3, 6),
643                sizeGrassPools = targetGrass / rng.between(2, 5);
644
645        Coord[] scatter;
646        int remainingWater = targetWater, remainingGrass = targetGrass;
647        if(targetWater > 0) {
648            scatter = fractionPacked(floors, 7);
649            scatter = rng.shuffle(scatter, new Coord[scatter.length]);
650            ArrayList<Coord> allWater = new ArrayList<>(targetWater);
651            for (int i = 0; i < scatter.length; i++) {
652                if (remainingWater > 5) //remainingWater >= targetWater * 0.02 &&
653                {
654                    if(!queryPacked(floors, scatter[i].x, scatter[i].y))
655                        continue;
656                    working = spill(floors, packOne(scatter[i]), rng.between(4, Math.min(remainingWater, sizeWaterPools)), rng);
657
658                    floors = differencePacked(floors, working);
659                    Coord[] pts = allPacked(working);
660                    remainingWater -= pts.length;
661                    Collections.addAll(allWater, pts);
662                } else
663                    break;
664            }
665
666            for (Coord pt : allWater) {
667                hazards.remove(pt);
668                //obstacles.add(pt);
669                if (map[pt.x][pt.y] != '<' && map[pt.x][pt.y] != '>')
670                    map[pt.x][pt.y] = '~';
671            }
672            for (Coord pt : allWater) {
673                if (map[pt.x][pt.y] != '<' && map[pt.x][pt.y] != '>' &&
674                        (map[pt.x - 1][pt.y] == '.' || map[pt.x + 1][pt.y] == '.' ||
675                                map[pt.x][pt.y - 1] == '.' || map[pt.x][pt.y + 1] == '.'))
676                    map[pt.x][pt.y] = ',';
677            }
678        }
679        if(targetGrass > 0) {
680            scatter = fractionPacked(floors, 7);
681            scatter = rng.shuffle(scatter, new Coord[scatter.length]);
682            Coord p;
683            for (int i = 0; i < scatter.length; i++) {
684                if (remainingGrass > 5) //remainingGrass >= targetGrass * 0.02 &&
685                {
686                    working = spill(floors, packOne(scatter[i]), rng.between(4, Math.min(remainingGrass, sizeGrassPools)), rng);
687                    if (working.length == 0)
688                        continue;
689                    floors = differencePacked(floors, working);
690                    Coord[] pts = allPacked(working);
691                    remainingGrass -= pts.length;
692                    for (int c = 0; c < pts.length; c++) {
693                        p = pts[c];
694                        map[p.x][p.y] = '"';
695                    }
696                } else
697                    break;
698            }
699        }
700
701        if(islandSpacing > 1 && targetWater > 0) {
702            ArrayList<Coord> islands = PoissonDisk.sampleMap(map, 1f * islandSpacing, rng, '#', '.', '"', '+', '/', '^', '<', '>');
703            for (Coord c : islands) {
704                map[c.x][c.y] = '.';
705                if (map[c.x - 1][c.y] != '#' && map[c.x - 1][c.y] != '<' && map[c.x - 1][c.y] != '>')
706                    map[c.x - 1][c.y] = ',';
707                if (map[c.x + 1][c.y] != '#' && map[c.x + 1][c.y] != '<' && map[c.x + 1][c.y] != '>')
708                    map[c.x + 1][c.y] = ',';
709                if (map[c.x][c.y - 1] != '#' && map[c.x][c.y - 1] != '<' && map[c.x][c.y - 1] != '>')
710                    map[c.x][c.y - 1] = ',';
711                if (map[c.x][c.y + 1] != '#' && map[c.x][c.y + 1] != '<' && map[c.x][c.y + 1] != '>')
712                    map[c.x][c.y + 1] = ',';
713            }
714        }
715
716        if(trapFill > 0)
717        {
718            int total = hazards.size() * trapFill / 100;
719
720            for(int i = 0; i < total; i++)
721            {
722                Coord entry = rng.getRandomElement(hazards);
723                if(map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '<')
724                    continue;
725                map[entry.x][entry.y] = '^';
726                hazards.remove(entry);
727            }
728        }
729
730        dungeon = map;
731        return map;
732
733    }
734
735
736    /**
737     * Gets the seed that can be used to rebuild an identical dungeon to the latest one generated (or the seed that
738     * will be used to generate the first dungeon if none has been made yet). You can pass the long this returns to
739     * the setState() method on this class' rng field, which assuming all other calls to generate a dungeon are
740     * identical, will ensure generate() or generateRespectingStairs() will produce the same dungeon output as the
741     * dungeon originally generated with the seed this returned.
742     * <br>
743     * You can also call getState() on the rng field yourself immediately before generating a dungeon, but this method
744     * handles some complexities of when the state is actually used to generate a dungeon; since StatefulRNG objects can
745     * be shared between different classes that use random numbers, the state could change between when you call
746     * getState() and when this class generates a dungeon. Using getRebuildSeed() eliminates that confusion.
747     * @return a seed as a long that can be passed to setState() on this class' rng field to recreate a dungeon
748     */
749    public long getRebuildSeed() {
750        return rebuildSeed;
751    }
752
753    /**
754     * Provides a string representation of the latest generated dungeon.
755     *
756     * @return a printable string version of the latest generated dungeon.
757     */
758    @Override
759        public String toString() {
760        char[][] trans = new char[height][width];
761        for (int x = 0; x < width; x++) {
762            for (int y = 0; y < height; y++) {
763                trans[y][x] = dungeon[x][y];
764            }
765        }
766        StringBuffer sb = new StringBuffer();
767        for (int row = 0; row < height; row++) {
768            sb.append(trans[row]);
769            sb.append('\n');
770        }
771        return sb.toString();
772    }
773
774}