001package squidpony.squidgrid.mapping;
002
003import squidpony.squidai.DijkstraMap;
004import squidpony.squidgrid.MultiSpill;
005import squidpony.squidgrid.Spill;
006import squidpony.squidgrid.mapping.styled.DungeonBoneGen;
007import squidpony.squidgrid.mapping.styled.TilesetType;
008import squidpony.squidmath.Coord;
009import squidpony.squidmath.CoordPacker;
010import squidpony.squidmath.PoissonDisk;
011import squidpony.squidmath.RNG;
012
013import java.util.ArrayList;
014import java.util.LinkedHashMap;
015import java.util.LinkedHashSet;
016
017import static squidpony.squidmath.CoordPacker.*;
018
019/**
020 * A replica of the previous API for DungeonGenerator. DungeonGenerator is the primary way to create a more-complete
021 * dungeon, layering different effects and modifications on top of a DungeonBoneGen's dungeon. This keeps the older API
022 * for DungeonGenerator around for games that relied on its behavior and seeds, but newer work should use the non-legacy
023 * DungeonGenerator class since it is significantly more precise in its results. The only difference between the two API
024 * versions is that LegacyDungeonGenerator uses 2/3 of the value it is given for addWater and addGrass, but is still not
025 * very accurate in how much of that value it uses, while DungeonGenerator gets very close to exactly the value it is
026 * given for those two methods. This class is deprecated in favor of DungeonGenerator.
027 * <br>
028 * The main technique for using this is simple: Construct a DungeonGenerator, usually with the desired width and height,
029 * then call any feature adding methods that you want in the dungeon, like addWater(), addTraps, addGrass(), or
030 * addDoors(). Some of these take different parameters, like addDoors() which need to know if it should check openings
031 * that are two cells wide to add a door and a wall to, or whether it should only add doors to single-cell openings.
032 * Then call generate() to get a char[][] with the desired dungeon map, using a fixed repertoire of chars to represent
033 * the different features. After calling generate(), you can safely get the values from the stairsUp and stairsDown
034 * fields, which are Coords that should be a long distance from each other but connected in the dungeon. You may want
035 * to change those to staircase characters, but there's no requirement to do anything with them. The DungeonUtility
036 * field of this class, utility, is a convenient way of accessing the non-static methods in that class, such as
037 * randomFloor(), without needing to create another DungeonUtility (this class creates one, so you don't have to).
038 *
039 * @see squidpony.squidgrid.mapping.DungeonUtility this class exposes a DungeonUtility member; DungeonUtility also has many useful static methods
040 * @see squidpony.squidgrid.mapping.DungeonGenerator for more-precise behavior
041 *
042 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
043 * @author Tommy Ettinger - https://github.com/tommyettinger
044 * @deprecated Prefer DungeonGenerator with its almost-equivalent API
045 * Created by Tommy Ettinger on 3/5/2016.
046 */
047@Deprecated
048public class LegacyDungeonGenerator extends DungeonGenerator {
049    /**
050     * Get the most recently generated char[][] dungeon out of this class. The
051     * dungeon may be null if generate() or setDungeon() have not been called.
052     *
053     * @return a char[][] dungeon, or null.
054     */
055    @Override
056    public char[][] getDungeon() {
057        return super.getDungeon();
058    }
059
060    /**
061     * Get the most recently generated char[][] dungeon out of this class without any chars other than '#' or '.', for
062     * walls and floors respectively. The dungeon may be null if generate() or setDungeon() have not been called.
063     *
064     * @return a char[][] dungeon with only '#' for walls and '.' for floors, or null.
065     */
066    @Override
067    public char[][] getBareDungeon() {
068        return super.getBareDungeon();
069    }
070
071    /**
072     * Change the underlying char[][]; only affects the toString method, and of course getDungeon.
073     *
074     * @param dungeon a char[][], probably produced by an earlier call to this class and then modified.
075     */
076    @Override
077    public void setDungeon(char[][] dungeon) {
078        super.setDungeon(dungeon);
079    }
080
081    /**
082     * Height of the dungeon in cells.
083     *
084     * @return Height of the dungeon in cells.
085     */
086    @Override
087    public int getHeight() {
088        return super.getHeight();
089    }
090
091    /**
092     * Width of the dungeon in cells.
093     *
094     * @return Width of the dungeon in cells.
095     */
096    @Override
097    public int getWidth() {
098        return super.getWidth();
099    }
100
101    /**
102     * Make a DungeonGenerator with a LightRNG using a random seed, height 40, and width 40.
103     */
104    public LegacyDungeonGenerator() {
105        super();
106    }
107
108    /**
109     * Make a DungeonGenerator with the given height and width; the RNG used for generating a dungeon and
110     * adding features will be a LightRNG using a random seed.
111     *
112     * @param width  The width of the dungeon in cells.
113     * @param height The height of the dungeon in cells.
114     */
115    public LegacyDungeonGenerator(int width, int height) {
116        super(width, height);
117    }
118
119    /**
120     * Make a DungeonGenerator with the given height, width, and RNG. Use this if you want to seed the RNG.
121     *
122     * @param width  The width of the dungeon in cells.
123     * @param height The height of the dungeon in cells.
124     * @param rng    The RNG to use for all purposes in this class; if this has been seeded and you want the same
125     */
126    public LegacyDungeonGenerator(int width, int height, RNG rng) {
127        super(width, height, rng);
128    }
129
130    /**
131     * Copies all fields from copying and makes a new DungeonGenerator.
132     *
133     * @param copying
134     */
135    public LegacyDungeonGenerator(DungeonGenerator copying) {
136        super(copying);
137    }
138    /**
139     * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be
140     * clustered into a random number of pools, with more appearing if needed to fill (two thirds of) the percentage.
141     * Each pool will have randomized volume that should fill or get very close to filling two thirds of the requested
142     * percentage, unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater
143     * called, the latest call will take precedence. No islands will be placed with this variant, but the edge of the
144     * water will be shallow, represented by ','.
145     * @param percentage the percentage of floor cells to fill with water; this can vary quite a lot. It is not
146     *                   intended to allow filling very high (over 66%) percentages of map with water, though you can do
147     *                   this by giving a percentage of between 100 and 150.
148     * @return this DungeonGenerator; can be chained
149     */
150    @Override
151    public DungeonGenerator addWater(int percentage)
152    {
153        if(percentage < 0) percentage = 0;
154        if(percentage > 150) percentage = 150;
155        if(fx.containsKey(FillEffect.WATER)) fx.remove(FillEffect.WATER);
156        fx.put(FillEffect.WATER, percentage);
157        return this;
158    }
159    /**
160     * Turns the majority of the given percentage of floor cells into water cells, represented by '~'. Water will be
161     * clustered into a random number of pools, with more appearing if needed to fill the percentage. Each pool will
162     * have randomized volume that should fill or get very close to filling (two thirds of) the requested percentage,
163     * unless the pools encounter too much tight space. If this DungeonGenerator previously had addWater called, the
164     * latest call will take precedence. If islandSpacing is greater than 1, then this will place islands of floor, '.',
165     * surrounded by shallow water, ',', at about the specified distance with Euclidean measurement.
166     * @param percentage the percentage of floor cells to fill with water; this can vary quite a lot. It may be
167     *                   difficult to fill very high (over 66%) percentages of map with water, though you can do this by
168     *                   giving a percentage of between 100 and 150.
169     * @param islandSpacing if greater than 1, islands will be placed randomly this many cells apart.
170     * @return this DungeonGenerator; can be chained
171     */
172    @Override
173    public DungeonGenerator addWater(int percentage, int islandSpacing)
174    {
175        if(percentage < 0) percentage = 0;
176        if(percentage > 150) percentage = 150;
177        if(fx.containsKey(FillEffect.WATER)) fx.remove(FillEffect.WATER);
178        fx.put(FillEffect.WATER, percentage);
179        if(fx.containsKey(FillEffect.ISLANDS)) fx.remove(FillEffect.ISLANDS);
180        if(islandSpacing > 1)
181            fx.put(FillEffect.ISLANDS, islandSpacing);
182        return this;
183    }
184
185    /**
186     * Turns the majority of the given percentage of floor cells into grass cells, represented by '"'. Grass will be
187     * clustered into a random number of patches, with more appearing if needed to fill the percentage. Each area will
188     * have randomized volume that should fill or get very close to filling (two thirds of) the requested percentage,
189     * unless the patches encounter too much tight space. If this DungeonGenerator previously had addGrass called, the
190     * latest call will take precedence.
191     * @param percentage the percentage of floor cells to fill with grass; this can vary quite a lot. It may be
192     *                   difficult to fill very high (over 66%) percentages of map with grass, though you can do this by
193     *                   giving a percentage of between 100 and 150.
194     * @return this DungeonGenerator; can be chained
195     */
196    @Override
197    public DungeonGenerator addGrass(int percentage)
198    {
199        if(percentage < 0) percentage = 0;
200        if(percentage > 150) percentage = 150;
201        if(fx.containsKey(FillEffect.GRASS)) fx.remove(FillEffect.GRASS);
202        fx.put(FillEffect.GRASS, percentage);
203        return this;
204    }
205    /**
206     * Turns the given percentage of floor cells not already adjacent to walls into wall cells, represented by '#'.
207     * If this DungeonGenerator previously had addBoulders called, the latest call will take precedence.
208     * @param percentage the percentage of floor cells not adjacent to walls to fill with boulders.
209     * @return this DungeonGenerator; can be chained
210     */
211    @Override
212    public DungeonGenerator addBoulders(int percentage)
213    {
214        if(percentage < 0) percentage = 0;
215        if(percentage > 100) percentage = 100;
216        if(fx.containsKey(FillEffect.BOULDERS)) fx.remove(FillEffect.BOULDERS);
217        fx.put(FillEffect.BOULDERS, percentage);
218        return this;
219    }
220    /**
221     * Turns the given percentage of viable doorways into doors, represented by '+' for doors that allow travel along
222     * the x-axis and '/' for doors that allow travel along the y-axis. If doubleDoors is true,
223     * 2-cell-wide openings will be considered viable doorways and will fill one cell with a wall, the other a door.
224     * If this DungeonGenerator previously had addDoors called, the latest call will take precedence.
225     * @param percentage the percentage of valid openings to corridors to fill with doors; should be between 10 and
226     *                   20 if you want doors to appear more than a few times, but not fill every possible opening.
227     * @param doubleDoors true if you want two-cell-wide openings to receive a door and a wall; false if only
228     *                    one-cell-wide openings should receive doors. Usually, this should be true.
229     * @return this DungeonGenerator; can be chained
230     */
231    @Override
232    public DungeonGenerator addDoors(int percentage, boolean doubleDoors)
233    {
234        if(percentage < 0) percentage = 0;
235        if(percentage > 100) percentage = 100;
236        if(doubleDoors) percentage *= -1;
237        if(fx.containsKey(FillEffect.DOORS)) fx.remove(FillEffect.DOORS);
238        fx.put(FillEffect.DOORS, percentage);
239        return this;
240    }
241
242    /**
243     * Turns the given percentage of open area floor cells into trap cells, represented by '^'. Corridors that have no
244     * possible way to move around a trap will not receive traps, ever. If this DungeonGenerator previously had
245     * addTraps called, the latest call will take precedence.
246     * @param percentage the percentage of valid cells to fill with traps; should be no higher than 5 unless
247     *                   the dungeon floor is meant to be a kill screen or minefield.
248     * @return this DungeonGenerator; can be chained
249     */
250    @Override
251    public DungeonGenerator addTraps(int percentage)
252    {
253        if(percentage < 0) percentage = 0;
254        if(percentage > 100) percentage = 100;
255        if(fx.containsKey(FillEffect.TRAPS)) fx.remove(FillEffect.TRAPS);
256        fx.put(FillEffect.TRAPS, percentage);
257        return this;
258    }
259
260
261    /**
262     * Removes any door, water, or trap insertion effects that this DungeonGenerator would put in future dungeons.
263     *
264     * @return this DungeonGenerator, with all effects removed. Can be chained.
265     */
266    @Override
267    public DungeonGenerator clearEffects() {
268        return super.clearEffects();
269    }
270
271    @Override
272    protected LinkedHashSet<Coord> removeAdjacent(LinkedHashSet<Coord> coll, Coord pt) {
273        return super.removeAdjacent(coll, pt);
274    }
275
276    @Override
277    protected LinkedHashSet<Coord> removeAdjacent(LinkedHashSet<Coord> coll, Coord pt1, Coord pt2) {
278        return super.removeAdjacent(coll, pt1, pt2);
279    }
280
281    @Override
282    protected LinkedHashSet<Coord> viableDoorways(boolean doubleDoors, char[][] map) {
283        return super.viableDoorways(doubleDoors, map);
284    }
285
286    /**
287     * Generate a char[][] dungeon using TilesetType.DEFAULT_DUNGEON; this produces a dungeon appropriate for a level
288     * of ruins or a partially constructed dungeon. This uses '#' for walls, '.' for floors, '~' for deep water, ',' for
289     * shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that provide
290     * vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in
291     * the generated map.
292     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
293     * @return a char[][] dungeon
294     */
295    @Override
296    public char[][] generate() {
297        return generate(TilesetType.DEFAULT_DUNGEON);
298    }
299
300    /**
301     * Generate a char[][] dungeon given a TilesetType; the comments in that class provide some opinions on what
302     * each TilesetType value could be used for in a game. This uses '#' for walls, '.' for floors, '~' for deep water,
303     * ',' for shallow water, '^' for traps, '+' for doors that provide horizontal passage, and '/' for doors that
304     * provide vertical passage. Use the addDoors, addWater, addGrass, and addTraps methods of this class to request
305     * these in the generated map.
306     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
307     * @see squidpony.squidgrid.mapping.styled.TilesetType
308     * @param kind a TilesetType enum value, such as TilesetType.DEFAULT_DUNGEON
309     * @return a char[][] dungeon
310     */
311    @Override
312    public char[][] generate(TilesetType kind)
313    {
314        seedFixed = true;
315        rebuildSeed = rng.getState();
316        return generate(gen.generate(kind, width, height));
317    }
318
319    /**
320     * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated.
321     * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method
322     * is meant for adding features like water and doors to existing simple maps.
323     * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors
324     * that provide horizontal passage, and '/' for doors that provide vertical passage.
325     * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map.
326     * Also sets the fields stairsUp and stairsDown to two randomly chosen, distant, connected, walkable cells.
327     * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors
328     * @return a char[][] dungeon
329     */
330    @Override
331    public char[][] generate(char[][] baseDungeon)
332    {
333        if(!seedFixed)
334        {
335            rebuildSeed = rng.getState();
336        }
337        seedFixed = false;
338        char[][] map = DungeonBoneGen.wallWrap(baseDungeon);
339        DijkstraMap dijkstra = new DijkstraMap(map);
340        int frustrated = 0;
341        do {
342            dijkstra.clearGoals();
343            stairsUp = utility.randomFloor(map);
344            dijkstra.setGoal(stairsUp);
345            dijkstra.scan(null);
346            frustrated++;
347        }while (dijkstra.getMappedCount() < width + height && frustrated < 15);
348        double maxDijkstra = 0.0;
349        for (int i = 0; i < width; i++) {
350            for (int j = 0; j < height; j++) {
351                if(dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) {
352                    map[i][j] = '#';
353                }
354                else if(dijkstra.gradientMap[i][j] > maxDijkstra) {
355                    maxDijkstra = dijkstra.gradientMap[i][j];
356                }
357            }
358        }
359        stairsDown = CoordPacker.singleRandom(CoordPacker.pack(dijkstra.gradientMap, maxDijkstra * 0.7,
360                DijkstraMap.FLOOR), rng);
361        /*
362        OUTER_LOOP:
363        for (int i = 0; i < width; i++) {
364            for (int j = 0; j < height; j++) {
365                if (dijkstra.gradientMap[(i + wmod) % width][(j + hmod) % height] < DijkstraMap.FLOOR &&
366                        dijkstra.gradientMap[(i + wmod) % width][(j + hmod) % height] > maxDijkstra * 0.7) {
367                    stairsDown = Coord.get((i + wmod) % width, (j + hmod) % height);
368                    break OUTER_LOOP;
369                }
370            }
371        }*/
372        return innerGenerate(map);
373    }
374
375    /**
376     * Generate a char[][] dungeon with extra features given a baseDungeon that has already been generated, and that
377     * already has staircases represented by greater than and less than signs.
378     * Typically, you want to call generate with a TilesetType or no argument for the easiest generation; this method
379     * is meant for adding features like water and doors to existing simple maps.
380     * This uses '#' for walls, '.' for floors, '~' for deep water, ',' for shallow water, '^' for traps, '+' for doors
381     * that provide horizontal passage, and '/' for doors that provide vertical passage.
382     * Use the addDoors, addWater, addGrass, and addTraps methods of this class to request these in the generated map.
383     * Also sets the fields stairsUp and stairsDown to null, and expects stairs to be already handled.
384     * @param baseDungeon a pre-made dungeon consisting of '#' for walls and '.' for floors, with stairs already in
385     * @return a char[][] dungeon
386     */
387    @Override
388    public char[][] generateRespectingStairs(char[][] baseDungeon) {
389        if(!seedFixed)
390        {
391            rebuildSeed = rng.getState();
392        }
393        seedFixed = false;
394        char[][] map = DungeonBoneGen.wallWrap(baseDungeon);
395        DijkstraMap dijkstra = new DijkstraMap(map);
396        stairsUp = null;
397        stairsDown = null;
398
399        dijkstra.clearGoals();
400        Coord[] stairs = allPacked(unionPacked(pack(map, '<'), pack(map, '>')));
401        for (Coord s : stairs) {
402            dijkstra.setGoal(s);
403        }
404        dijkstra.scan(null);
405        for (int i = 0; i < width; i++) {
406            for (int j = 0; j < height; j++) {
407                if (dijkstra.gradientMap[i][j] >= DijkstraMap.FLOOR) {
408                    map[i][j] = '#';
409                }
410            }
411        }
412        return innerGenerate(map);
413    }
414
415    private char[][] innerGenerate(char[][] map)
416    {
417
418        LinkedHashSet<Coord> floors = new LinkedHashSet<>();
419        LinkedHashSet<Coord> doorways;
420        LinkedHashSet<Coord> hazards = new LinkedHashSet<>();
421        Coord temp;
422        boolean doubleDoors = false;
423        int doorFill = 0;
424        int waterFill = 0;
425        int grassFill = 0;
426        int trapFill = 0;
427        double boulderFill = 0.0;
428        int islandSpacing = 0;
429        if(fx.containsKey(FillEffect.DOORS))
430        {
431            doorFill = fx.get(FillEffect.DOORS);
432            if(doorFill < 0)
433            {
434                doubleDoors = true;
435                doorFill *= -1;
436            }
437        }
438        if(fx.containsKey(FillEffect.GRASS)) {
439            grassFill = fx.get(FillEffect.GRASS);
440        }
441        if(fx.containsKey(FillEffect.WATER)) {
442            waterFill = fx.get(FillEffect.WATER);
443        }
444        if(fx.containsKey(FillEffect.BOULDERS)) {
445            boulderFill = fx.get(FillEffect.BOULDERS) * 0.01;
446        }
447        if(fx.containsKey(FillEffect.ISLANDS)) {
448            islandSpacing = fx.get(FillEffect.ISLANDS);
449        }
450        if(fx.containsKey(FillEffect.TRAPS)) {
451            trapFill = fx.get(FillEffect.TRAPS);
452        }
453
454        double floorRate = 1.0, waterRate = waterFill / 150.0, grassRate = grassFill / 150.0;
455        if(waterRate + grassRate > 1.0)
456        {
457            waterRate /= (waterFill + grassFill) / 100.0;
458            grassRate /= (waterFill + grassFill) / 100.0;
459        }
460        floorRate -= waterRate + grassRate;
461        doorways = viableDoorways(doubleDoors, map);
462
463        LinkedHashSet<Coord> obstacles = new LinkedHashSet<>(doorways.size() * doorFill / 100);
464        if(doorFill > 0)
465        {
466            int total = doorways.size() * doorFill / 100;
467
468            BigLoop:
469            for(int i = 0; i < total; i++)
470            {
471                Coord entry = doorways.toArray(new Coord[doorways.size()])[rng.nextInt(doorways.size())];
472                if(map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '>')
473                    continue;
474                if(map[entry.x - 1][entry.y] != '#' && map[entry.x + 1][entry.y] != '#')
475                {
476                    map[entry.x][entry.y] = '+';
477                }
478                else {
479                    map[entry.x][entry.y] = '/';
480                }
481                obstacles.add(entry);
482                Coord[] adj = new Coord[]{Coord.get(entry.x + 1, entry.y), Coord.get(entry.x - 1, entry.y),
483                        Coord.get(entry.x, entry.y + 1), Coord.get(entry.x, entry.y - 1)};
484                for(Coord near : adj) {
485                    if (doorways.contains(near)) {
486                        map[near.x][near.y] = '#';
487                        obstacles.add(near);
488                        doorways.remove(near);
489                        i++;
490                        doorways.remove(entry);
491                        continue BigLoop;
492                    }
493                }
494                doorways.remove(entry);
495            }
496        }
497        if (boulderFill > 0.0) {
498            short[] walls = unionPacked(unionPacked(pack(map, '>'), pack(map, '<')), pack(map, '#'));
499            short[] more = expand(walls, 1, width, height);
500            short[] rect = rectangle(width, height);
501            short[] viable = differencePacked(rect, more);
502            Coord[] boulders = randomSample(viable, boulderFill, rng);
503            for (int i = 0; i < boulders.length; i++) {
504                map[boulders[i].x][boulders[i].y] = '#';
505            }
506        }
507
508
509        if(trapFill > 0) {
510            for (int x = 1; x < map.length - 1; x++) {
511                for (int y = 1; y < map[x].length - 1; y++) {
512                    temp = Coord.get(x, y);
513                    if (map[x][y] == '.' && !obstacles.contains(temp)) {
514                        floors.add(Coord.get(x, y));
515                        int ctr = 0;
516                        if (map[x + 1][y] != '#') ++ctr;
517                        if (map[x - 1][y] != '#') ++ctr;
518                        if (map[x][y + 1] != '#') ++ctr;
519                        if (map[x][y - 1] != '#') ++ctr;
520                        if (map[x + 1][y + 1] != '#') ++ctr;
521                        if (map[x - 1][y + 1] != '#') ++ctr;
522                        if (map[x + 1][y - 1] != '#') ++ctr;
523                        if (map[x - 1][y - 1] != '#') ++ctr;
524                        if (ctr >= 5) hazards.add(Coord.get(x, y));
525                    }
526                }
527            }
528        }
529
530        MultiSpill ms = new MultiSpill(map, Spill.Measurement.MANHATTAN, rng);
531        LinkedHashMap<Coord, Double> fillers = new LinkedHashMap<>(128);
532        ArrayList<Coord> dots = PoissonDisk.sampleMap(map, Math.min(width, height) / 8f, rng, '#', '+', '/','<', '>');
533        for (int i = 0; i < dots.size(); i++) {
534            switch (i % 3) {
535                case 0:
536                    fillers.put(dots.get(i), floorRate);
537                    break;
538                case 1:
539                    fillers.put(dots.get(i), waterRate);
540                    break;
541                case 2:
542                    fillers.put(dots.get(i), grassRate);
543                    break;
544            }
545        }
546
547        ArrayList<ArrayList<Coord>> fills = ms.start(fillers, -1, null);
548
549        int ctr = 0;
550        for(ArrayList<Coord> pts : fills)
551        {
552            switch (ctr % 3) {
553                case 0:
554                    break;
555                case 1:
556                    floors.removeAll(pts);
557                    hazards.removeAll(pts);
558                    obstacles.addAll(pts);
559                    for (int x = 1; x < width - 1; x++) {
560                        for (int y = 1; y < height - 1; y++) {
561                            if (ms.spillMap[x][y] == ctr && map[x][y] != '<' && map[x][y] != '>') {
562                                map[x][y] = '~';
563                            }
564                        }
565                    }
566                    for (int x = 1; x < width - 1; x++) {
567                        for (int y = 1; y < height - 1; y++) {
568                            if (ms.spillMap[x][y] == ctr) {
569                                if(map[x][y] != '<' && map[x][y] != '>' &&
570                                        (map[x - 1][y] == '.' || map[x + 1][y] == '.' ||
571                                                map[x][y - 1] == '.' || map[x][y + 1] == '.'))
572                                    map[x][y] = ',';
573                            }
574                        }
575                    }
576                    if(islandSpacing > 1) {
577                        ArrayList<Coord> islands = PoissonDisk.sampleMap(map, 1f * islandSpacing, rng, '#', '.', '"', '+', '/', '^', '<', '>');
578                        for (Coord c : islands) {
579                            map[c.x][c.y] = '.';
580                            if (map[c.x - 1][c.y] != '#' && map[c.x - 1][c.y] != '<' && map[c.x - 1][c.y] != '>')
581                                map[c.x - 1][c.y] = ',';
582                            if (map[c.x + 1][c.y] != '#' && map[c.x + 1][c.y] != '<' && map[c.x + 1][c.y] != '>')
583                                map[c.x + 1][c.y] = ',';
584                            if (map[c.x][c.y-1] != '#' && map[c.x][c.y-1] != '<' && map[c.x][c.y-1] != '>')
585                                map[c.x][c.y - 1] = ',';
586                            if (map[c.x][c.y+1] != '#' && map[c.x][c.y+1] != '<' && map[c.x][c.y+1] != '>')
587                                map[c.x][c.y + 1] = ',';
588                        }
589                    }
590
591                    break;
592                case 2:
593                    floors.removeAll(pts);
594                    hazards.removeAll(pts);
595                    obstacles.addAll(pts);
596                    for (int x = 1; x < width - 1; x++) {
597                        for (int y = 1; y < height - 1; y++) {
598                            if (ms.spillMap[x][y] == ctr && map[x][y] == '.') {
599                                map[x][y] = '"';
600                            }
601                        }
602                    }
603                    break;
604            }
605            ctr++;
606        }
607
608        if(trapFill > 0)
609        {
610            int total = hazards.size() * trapFill / 100;
611
612            for(int i = 0; i < total; i++)
613            {
614                Coord entry = hazards.toArray(new Coord[hazards.size()])[rng.nextInt(hazards.size())];
615                if(map[entry.x][entry.y] == '<' || map[entry.x][entry.y] == '<')
616                    continue;
617                map[entry.x][entry.y] = '^';
618                hazards.remove(entry);
619            }
620        }
621
622        dungeon = map;
623        return map;
624
625    }
626
627
628    @SuppressWarnings("unused")
629    private char[][] innerGenerateOld(char[][] map)
630    {
631
632        LinkedHashSet<Coord> floors = new LinkedHashSet<>();
633        LinkedHashSet<Coord> doorways;
634        LinkedHashSet<Coord> hazards = new LinkedHashSet<>();
635        Coord temp;
636        boolean doubleDoors = false;
637        int doorFill = 0;
638        int waterFill = 0;
639        int grassFill = 0;
640        int trapFill = 0;
641        int islandSpacing = 0;
642        if(fx.containsKey(FillEffect.DOORS))
643        {
644            doorFill = fx.get(FillEffect.DOORS);
645            if(doorFill < 0)
646            {
647                doubleDoors = true;
648                doorFill *= -1;
649            }
650        }
651        if(fx.containsKey(FillEffect.GRASS)) {
652            grassFill = fx.get(FillEffect.GRASS);
653        }
654        if(fx.containsKey(FillEffect.WATER)) {
655            waterFill = fx.get(FillEffect.WATER);
656        }
657        if(fx.containsKey(FillEffect.ISLANDS)) {
658            islandSpacing = fx.get(FillEffect.ISLANDS);
659        }
660        if(fx.containsKey(FillEffect.TRAPS)) {
661            trapFill = fx.get(FillEffect.TRAPS);
662        }
663
664        doorways = viableDoorways(doubleDoors, map);
665
666        LinkedHashSet<Coord> obstacles = new LinkedHashSet<>(doorways.size() * doorFill / 100);
667        if(doorFill > 0)
668        {
669            int total = doorways.size() * doorFill / 100;
670
671            BigLoop:
672            for(int i = 0; i < total; i++)
673            {
674                Coord entry = doorways.toArray(new Coord[doorways.size()])[rng.nextInt(doorways.size())];
675                if(map[entry.x - 1][entry.y] != '#' && map[entry.x + 1][entry.y] != '#')
676                {
677                    map[entry.x][entry.y] = '+';
678                }
679                else {
680                    map[entry.x][entry.y] = '/';
681                }
682                obstacles.add(entry);
683                Coord[] adj = new Coord[]{Coord.get(entry.x + 1, entry.y), Coord.get(entry.x - 1, entry.y),
684                        Coord.get(entry.x, entry.y + 1), Coord.get(entry.x, entry.y - 1)};
685                for(Coord near : adj) {
686                    if (doorways.contains(near)) {
687                        map[near.x][near.y] = '#';
688                        obstacles.add(Coord.get(near.x, near.y));
689                        doorways.remove(near);
690                        i++;
691                        doorways.remove(entry);
692                        continue BigLoop;
693                    }
694                }
695                doorways.remove(entry);
696            }
697        }
698
699        for(int x = 1; x < map.length - 1; x++)
700        {
701            for(int y = 1; y < map[x].length - 1; y++)
702            {
703                temp = Coord.get(x, y);
704                if(map[x][y] == '.' && !obstacles.contains(temp))
705                {
706                    floors.add(Coord.get(x, y));
707                    int ctr = 0;
708                    if(map[x+1][y] != '#') ++ctr;
709                    if(map[x-1][y] != '#') ++ctr;
710                    if(map[x][y+1] != '#') ++ctr;
711                    if(map[x][y-1] != '#') ++ctr;
712                    if(map[x+1][y+1] != '#') ++ctr;
713                    if(map[x-1][y+1] != '#') ++ctr;
714                    if(map[x+1][y-1] != '#') ++ctr;
715                    if(map[x-1][y-1] != '#') ++ctr;
716                    if(ctr >= 5) hazards.add(Coord.get(x, y));
717                }
718            }
719        }
720        if(grassFill > 0)
721        {
722            int numPatches = rng.nextInt(8) + 2 + grassFill / 20;
723            int[] volumes = new int[numPatches];
724            int total = floors.size() * grassFill / 100;
725            int error = 0;
726            for(int i = 0; i < numPatches; i++) {
727                volumes[i] = rng.nextInt(total / numPatches);
728                error += volumes[i];
729            }
730            while (error > 0)
731            {
732                int n = rng.nextInt(total - error + 1);
733                volumes[rng.nextInt(volumes.length)] += n;
734                error -= n;
735            }
736            //volumes[0] += total - error;
737            /*
738            for(int i = 0; i < numPatches; i++) {
739                int r = rng.nextInt(volumes[i] / 2) - volumes[i] / 4;
740                volumes[i] += r;
741                volumes[(i + 1) % numPatches] -= r;
742            }
743            */
744            Spill spill = new Spill(map, Spill.Measurement.EUCLIDEAN, rng);
745            int bonusVolume = 0;
746            for(int i = 0; i < numPatches; i++)
747            {
748                floors.removeAll(obstacles);
749                Coord entry = floors.toArray(new Coord[floors.size()])[rng.nextInt(floors.size())];
750                spill.start(entry, volumes[i] / 3, obstacles);
751                spill.start(entry, 2 * volumes[i] / 3, obstacles);
752                ArrayList<Coord> ordered = new ArrayList<>(spill.start(entry, volumes[i], obstacles));
753                floors.removeAll(ordered);
754                hazards.removeAll(ordered);
755                obstacles.addAll(ordered);
756
757                if(spill.filled <= volumes[i])
758                {
759                    bonusVolume += volumes[i] - spill.filled;
760                }
761
762            }
763            for(int x = 1; x < map.length - 1; x++) {
764                for (int y = 1; y < map[x].length - 1; y++) {
765                    if(spill.spillMap[x][y])
766                        map[x][y] = '"';
767                }
768            }
769            int frustration = 0;
770            while (bonusVolume > 0 && frustration < 50)
771            {
772                Coord entry = utility.randomFloor(map);
773                ArrayList<Coord> finisher = spill.start(entry, bonusVolume, obstacles);
774                for(Coord p : finisher)
775                {
776                    map[p.x][p.y] = '"';
777                }
778                bonusVolume -= spill.filled;
779                hazards.removeAll(finisher);
780                frustration++;
781            }
782        }
783
784        if(waterFill > 0)
785        {
786            int numPools = rng.nextInt(4) + 2 + waterFill / 20;
787            int[] volumes = new int[numPools];
788            int total = floors.size() * waterFill / 100;
789            int error = 0;
790            for(int i = 0; i < numPools; i++) {
791                volumes[i] = total / numPools;
792                error += volumes[i];
793            }
794            volumes[0] += total - error;
795
796            for(int i = 0; i < numPools; i++) {
797                int r = rng.nextInt(volumes[i] / 2) - volumes[i] / 4;
798                volumes[i] += r;
799                volumes[(i + 1) % numPools] -= r;
800            }
801            Spill spill = new Spill(map, Spill.Measurement.MANHATTAN, rng);
802            int bonusVolume = 0;
803            for(int i = 0; i < numPools; i++)
804            {
805                floors.removeAll(obstacles);
806                Coord entry = floors.toArray(new Coord[floors.size()])[rng.nextInt(floors.size())];
807//                spill.start(entry, volumes[i] / 3, obstacles);
808//                spill.start(entry, 2 * volumes[i] / 3, obstacles);
809                ArrayList<Coord> ordered = new ArrayList<>(spill.start(entry, volumes[i], obstacles));
810                floors.removeAll(ordered);
811                hazards.removeAll(ordered);
812                obstacles.addAll(ordered);
813
814                if(spill.filled <= volumes[i])
815                {
816                    bonusVolume += volumes[i] - spill.filled;
817                }
818
819            }
820            for(int x = 1; x < map.length - 1; x++) {
821                for (int y = 1; y < map[x].length - 1; y++) {
822                    if (spill.spillMap[x][y]) {
823                        map[x][y] = '~';
824                    }
825                }
826            }
827            int frustration = 0;
828            while (bonusVolume > 0 && frustration < 50)
829            {
830                Coord entry = utility.randomFloor(map);
831                ArrayList<Coord> finisher = spill.start(entry, bonusVolume, obstacles);
832                for(Coord p : finisher)
833                {
834                    map[p.x][p.y] = '~';
835                }
836                bonusVolume -= spill.filled;
837                hazards.removeAll(finisher);
838                frustration++;
839            }
840            for(int x = 1; x < map.length - 1; x++) {
841                for (int y = 1; y < map[x].length - 1; y++) {
842                    if (spill.spillMap[x][y]) {
843                        if(map[x - 1][y] == '.' || map[x + 1][y] == '.' ||
844                                map[x][y - 1] == '.' || map[x][y + 1] == '.')
845                            map[x][y] = ',';
846                    }
847                }
848            }
849            if(islandSpacing > 1) {
850                ArrayList<Coord> islands = PoissonDisk.sampleMap(map, 1f * islandSpacing, rng, '#', '.', '"', '+', '/', '^');
851                for (Coord c : islands) {
852                    map[c.x][c.y] = '.';
853                    if (map[c.x - 1][c.y] != '#')
854                        map[c.x - 1][c.y] = ',';
855                    if (map[c.x + 1][c.y] != '#')
856                        map[c.x + 1][c.y] = ',';
857                    if (map[c.x][c.y - 1] != '#')
858                        map[c.x][c.y - 1] = ',';
859                    if (map[c.x][c.y + 1] != '#')
860                        map[c.x][c.y + 1] = ',';
861                }
862            }
863        }
864
865
866
867        if(trapFill > 0)
868        {
869            int total = hazards.size() * trapFill / 100;
870
871            for(int i = 0; i < total; i++)
872            {
873                Coord entry = hazards.toArray(new Coord[hazards.size()])[rng.nextInt(hazards.size())];
874                map[entry.x][entry.y] = '^';
875                hazards.remove(entry);
876            }
877        }
878
879        dungeon = map;
880        return map;
881
882    }
883
884    /**
885     * Gets the seed that can be used to rebuild an identical dungeon to the latest one generated (or the seed that
886     * will be used to generate the first dungeon if none has been made yet). You can pass the long this returns to
887     * the setState() method on this class' rng field, which assuming all other calls to generate a dungeon are
888     * identical, will ensure generate() or generateRespectingStairs() will produce the same dungeon output as the
889     * dungeon originally generated with the seed this returned.
890     * <br>
891     * You can also call getState() on the rng field yourself immediately before generating a dungeon, but this method
892     * handles some complexities of when the state is actually used to generate a dungeon; since StatefulRNG objects can
893     * be shared between different classes that use random numbers, the state could change between when you call
894     * getState() and when this class generates a dungeon. Using getRebuildSeed() eliminates that confusion.
895     *
896     * @return a seed as a long that can be passed to setState() on this class' rng field to recreate a dungeon
897     */
898    @Override
899    public long getRebuildSeed() {
900        return super.getRebuildSeed();
901    }
902
903    /**
904     * Provides a string representation of the latest generated dungeon.
905     *
906     * @return a printable string version of the latest generated dungeon.
907     */
908    @Override
909    public String toString() {
910        return super.toString();
911    }
912}