001package squidpony.squidgrid.mapping;
002
003import squidpony.squidgrid.Direction;
004import squidpony.squidmath.Coord;
005import squidpony.squidmath.PoissonDisk;
006import squidpony.squidmath.RNG;
007
008import java.util.*;
009
010/**
011 * A dungeon generator that can use a mix of techniques to have part-cave, part-room dungeons. Not entirely intended for
012 * normal use outside of this library, though it can be very useful when you want to make a dungeon match a specific
013 * path and existing generators that use MixedGenerator aren't sufficient. You may want to use a simpler generator based
014 * on this, like SerpentMapGenerator, which generates a long, winding path that loops around on itself. This supports
015 * the getEnvironment() method, which can be used in conjunction with RoomFinder to find where separate room, corridor,
016 * and cave areas have been placed.
017 * <br>
018 * Based on Michael Patraw's excellent Drunkard's Walk dungeon generator.
019 * http://mpatraw.github.io/libdrunkard/
020 * @see squidpony.squidgrid.mapping.SerpentMapGenerator a normal use for MixedGenerator that makes winding dungeons
021 * @see squidpony.squidgrid.mapping.SerpentDeepMapGenerator uses MixedGenerator as it makes a multi-level dungeon
022 * Created by Tommy Ettinger on 10/22/2015.
023 */
024public class MixedGenerator {
025    public enum CarverType
026    {
027        CAVE,
028        BOX,
029        ROUND,
030        BOX_WALLED,
031        ROUND_WALLED
032    }
033
034    /**
035     * Constant for environment tiles that are not near a cave, room, or corridor. Value is 0.
036     */
037    public static final int UNTOUCHED = 0;
038    /**
039     * Constant for environment tiles that are floors for a room. Value is 1.
040     */
041    public static final int ROOM_FLOOR = 1;
042    /**
043     * Constant for environment tiles that are walls near a room. Value is 2.
044     */
045    public static final int ROOM_WALL = 2;
046    /**
047     * Constant for environment tiles that are floors for a cave. Value is 3.
048     */
049    public static final int CAVE_FLOOR = 3;
050    /**
051     * Constant for environment tiles that are walls near a cave. Value is 4.
052     */
053    public static final int CAVE_WALL = 4;
054    /**
055     * Constant for environment tiles that are floors for a corridor. Value is 5.
056     */
057    public static final int CORRIDOR_FLOOR = 5;
058    /**
059     * Constant for environment tiles that are walls near a corridor. Value is 6.
060     */
061    public static final int CORRIDOR_WALL = 6;
062
063    protected EnumMap<CarverType, Integer> carvers;
064    protected int width, height;
065    protected float roomWidth, roomHeight;
066    public RNG rng;
067    protected char[][] dungeon;
068    protected boolean generated = false;
069    protected int[][] environment;
070    protected boolean[][] marked, walled, fixedRooms;
071    protected List<Long> points;
072    protected int totalPoints;
073
074    /**
075     * Internal use.
076     * @param width dungeon width in cells
077     * @param height dungeon height in cells
078     * @param rng rng to use
079     * @return evenly spaced Coord points in a list made by PoissonDisk, trimmed down so they aren't all used
080     * @see PoissonDisk used to make the list
081     */
082    protected static List<Coord> basicPoints(int width, int height, RNG rng)
083    {
084        return PoissonDisk.sampleRectangle(Coord.get(2, 2), Coord.get(width - 3, height - 3),
085                8.5f * (width + height) / 120f, width, height, 35, rng);
086    }
087
088    /**
089     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
090     * This version of the constructor uses Poisson Disk sampling to generate the points it will draw caves and
091     * corridors between, ensuring a minimum distance between points, but it does not ensure that paths between points
092     * will avoid overlapping with rooms or other paths. You call the different carver-adding methods to affect what the
093     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
094     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
095     * @param width the width of the final map in cells
096     * @param height the height of the final map in cells
097     * @param rng an RNG object to use for random choices; this make a lot of random choices.
098     * @see PoissonDisk used to ensure spacing for the points.
099     */
100    public MixedGenerator(int width, int height, RNG rng) {
101        this(width, height, rng, basicPoints(width, height, rng));
102    }
103
104    /**
105     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
106     * This version of the constructor uses a List of Coord points from some other source to determine the path to add
107     * rooms or caves to and then connect. You call the different carver-adding methods to affect what the
108     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
109     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
110     * @param width the width of the final map in cells
111     * @param height the height of the final map in cells
112     * @param rng an RNG object to use for random choices; this make a lot of random choices.
113     * @param sequence a List of Coord to connect in order; index 0 is the start, index size() - 1 is the end.
114     * @see SerpentMapGenerator a class that uses this technique
115     */
116    public MixedGenerator(int width, int height, RNG rng, List<Coord> sequence) {
117        this.width = width;
118        this.height = height;
119        this.roomWidth = width / 64.0f;
120        this.roomHeight = height / 64.0f;
121        if(width <= 2 || height <= 2)
122            throw new IllegalStateException("width and height must be greater than 2");
123        this.rng = rng;
124        dungeon = new char[width][height];
125        environment = new int[width][height];
126        marked = new boolean[width][height];
127        walled = new boolean[width][height];
128        fixedRooms = new boolean[width][height];
129        Arrays.fill(dungeon[0], '#');
130        Arrays.fill(environment[0], UNTOUCHED);
131        for (int i = 1; i < width; i++) {
132            System.arraycopy(dungeon[0], 0, dungeon[i], 0, height);
133            System.arraycopy(environment[0], 0, environment[i], 0, height);
134        }
135        totalPoints = sequence.size() - 1;
136        points = new ArrayList<>(totalPoints);
137        for (int i = 0; i < totalPoints; i++) {
138            Coord c1 = sequence.get(i), c2 = sequence.get(i + 1);
139            points.add(((c1.x & 0xffL) << 24) | ((c1.y & 0xff) << 16) | ((c2.x & 0xff) << 8) | (c2.y & 0xff));
140        }
141        carvers = new EnumMap<>(CarverType.class);
142    }
143    /**
144     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
145     * This version of the constructor uses a LinkedHashMap with Coord keys and Coord array values to determine a
146     * branching path for the dungeon to take; each key will connect once to each of the Coords in its value, and you
147     * usually don't want to connect in both directions. You call the different carver-adding methods to affect what the
148     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
149     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
150     * @param width the width of the final map in cells
151     * @param height the height of the final map in cells
152     * @param rng an RNG object to use for random choices; this make a lot of random choices.
153     * @param connections a Map of Coord keys to arrays of Coord to connect to next; shouldn't connect both ways
154     * @see SerpentMapGenerator a class that uses this technique
155     */
156    public MixedGenerator(int width, int height, RNG rng, LinkedHashMap<Coord, List<Coord>> connections)
157    {
158        this(width, height, rng, connections, 0.8f);
159    }
160    /**
161     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
162     * This version of the constructor uses a LinkedHashMap with Coord keys and Coord array values to determine a
163     * branching path for the dungeon to take; each key will connect once to each of the Coords in its value, and you
164     * usually don't want to connect in both directions. You call the different carver-adding methods to affect what the
165     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
166     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
167     * @param width the width of the final map in cells
168     * @param height the height of the final map in cells
169     * @param rng an RNG object to use for random choices; this make a lot of random choices.
170     * @param connections a Map of Coord keys to arrays of Coord to connect to next; shouldn't connect both ways
171     * @param roomSizeMultiplier a float multiplier that will be applied to each room's width and height
172     * @see SerpentMapGenerator a class that uses this technique
173     */
174    public MixedGenerator(int width, int height, RNG rng, LinkedHashMap<Coord, List<Coord>> connections,
175                          float roomSizeMultiplier) {
176        this.width = width;
177        this.height = height;
178        this.roomWidth = (width / 64.0f) * roomSizeMultiplier;
179        this.roomHeight = (height / 64.0f) * roomSizeMultiplier;
180        if(width <= 2 || height <= 2)
181            throw new IllegalStateException("width and height must be greater than 2");
182        this.rng = rng;
183        dungeon = new char[width][height];
184        environment = new int[width][height];
185        marked = new boolean[width][height];
186        walled = new boolean[width][height];
187        fixedRooms = new boolean[width][height];
188        Arrays.fill(dungeon[0], '#');
189        Arrays.fill(environment[0], UNTOUCHED);
190        for (int i = 1; i < width; i++) {
191            System.arraycopy(dungeon[0], 0, dungeon[i], 0, height);
192            System.arraycopy(environment[0], 0, environment[i], 0, height);
193        }
194        totalPoints = 0;
195        for(List<Coord> vals : connections.values())
196        {
197            totalPoints += vals.size();
198        }
199        points = new ArrayList<>(totalPoints);
200        for (Map.Entry<Coord, List<Coord>> kv : connections.entrySet()) {
201            Coord c1 = kv.getKey();
202            for (Coord c2 : kv.getValue()) {
203                points.add(((c1.x & 0xffL) << 24) | ((c1.y & 0xff) << 16) | ((c2.x & 0xff) << 8) | (c2.y & 0xff));
204            }
205        }
206        carvers = new EnumMap<>(CarverType.class);
207    }
208
209    /**
210     * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves
211     * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make
212     * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically
213     * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10
214     * between the count of putCaveCarvers(), putBoxRoomCarvers(), putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and
215     * putWalledRoundRoomCarvers() is reasonable.
216     * @param count the number of carvers making caves between rooms; only matters in relation to other carvers
217     */
218    public void putCaveCarvers(int count)
219    {
220        carvers.put(CarverType.CAVE, count);
221    }
222    /**
223     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
224     * with a random size in a box shape at the start and end, and a small room at the corner if there is one. If count
225     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
226     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
227     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
228     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
229     * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable.
230     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
231     *              to other carvers
232     */
233    public void putBoxRoomCarvers(int count)
234    {
235        carvers.put(CarverType.BOX, count);
236    }
237
238    /**
239     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
240     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
241     * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
242     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
243     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
244     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
245     * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable.
246     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
247     *              to other carvers
248     */
249    public void putRoundRoomCarvers(int count)
250    {
251        carvers.put(CarverType.ROUND, count);
252    }
253    /**
254     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
255     * with a random size in a box shape at the start and end, and a small room at the corner if there is one, enforcing
256     * the presence of walls around the rooms even if another room is already there or would be placed there. Corridors
257     * can always pass through enforced walls, but caves will open at most one cell in the wall. If count
258     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
259     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
260     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
261     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
262     * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable.
263     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
264     *              to other carvers
265     */
266    public void putWalledBoxRoomCarvers(int count)
267    {
268        carvers.put(CarverType.BOX_WALLED, count);
269    }
270
271    /**
272     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
273     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
274     * one, enforcing the presence of walls around the rooms even if another room is already there or would be placed
275     * there. Corridors can always pass through enforced walls, but caves will open at most one cell in the wall. If
276     * count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
277     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
278     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
279     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
280     * putRoundRoomCarvers(), putWalledBoxRoomCarvers(), and putWalledRoundRoomCarvers() is reasonable.
281     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
282     *              to other carvers
283     */
284    public void putWalledRoundRoomCarvers(int count)
285    {
286        carvers.put(CarverType.ROUND_WALLED, count);
287    }
288
289    /**
290     * Uses the added carvers (or just makes caves if none were added) to carve from point to point in sequence, if it
291     * was provided by the constructor, or evenly-spaced randomized points if it was not. This will never carve out
292     * cells on the very edge of the map. Uses the numbers of the various kinds of carver that were added relative to
293     * each other to determine how frequently to use a given carver type.
294     * @return a char[][] where '#' is a wall and '.' is a floor or corridor; x first y second
295     */
296    public char[][] generate()
297    {
298        CarverType[] carvings = carvers.keySet().toArray(new CarverType[carvers.size()]);
299        int[] carvingsCounters = new int[carvings.length];
300        int totalLength = 0;
301        for (int i = 0; i < carvings.length; i++) {
302            carvingsCounters[i] = carvers.get(carvings[i]);
303            totalLength += carvingsCounters[i];
304        }
305        CarverType[] allCarvings = new CarverType[totalLength];
306
307        for (int i = 0, c = 0; i < carvings.length; i++) {
308            for (int j = 0; j < carvingsCounters[i]; j++) {
309                allCarvings[c++] = carvings[i];
310            }
311        }
312        if(allCarvings.length == 0)
313        {
314            allCarvings = new CarverType[]{CarverType.CAVE};
315            totalLength = 1;
316        }
317        else
318            allCarvings = rng.shuffle(allCarvings, new CarverType[allCarvings.length]);
319
320        for (int p = 0, c = 0; p < totalPoints; p++, c = (++c) % totalLength) {
321            long pair = points.get(p);
322            Coord start = Coord.get((int)(pair >> 24) & 0xff, (int)(pair >> 16) & 0xff),
323                  end   = Coord.get((int)(pair >> 8) & 0xff, (int)pair & 0xff);
324            CarverType ct = allCarvings[c];
325            Direction dir;
326            switch (ct)
327            {
328                case CAVE:
329                    markPiercing(end);
330                    markEnvironmentCave(end.x, end.y);
331                    store();
332                    double weight = 0.75;
333                    do {
334                        Coord cent = markPlusCave(start);
335                        if(cent != null)
336                        {
337                            markPiercingCave(cent);
338                            markPiercingCave(cent.translate(1, 0));
339                            markPiercingCave(cent.translate(-1, 0));
340                            markPiercingCave(cent.translate(0, 1));
341                            markPiercingCave(cent.translate(0, -1));
342                            weight = 0.95;
343                        }
344                        dir = stepWobbly(start, end, weight);
345                        start = start.translate(dir);
346                    }while (dir != Direction.NONE);
347                    break;
348                case BOX:
349                    markRectangle(end, rng.between(1, 5), rng.between(1, 5));
350                    markRectangle(start, rng.between(1, 4), rng.between(1, 4));
351                    store();
352                    dir = Direction.getDirection(end.x - start.x, (end.y - start.y));
353                    if(dir.isDiagonal())
354                        dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0)
355                                : Direction.getCardinalDirection(0, -dir.deltaY);
356                    while (start.x != end.x && start.y != end.y)
357                    {
358                        markPiercing(start);
359                        markEnvironmentCorridor(start.x, start.y);
360                        start = start.translate(dir);
361                    }
362                    markRectangle(start, 1, 1);
363                    dir = Direction.getCardinalDirection(end.x - start.x, -(end.y - start.y));
364                    while (!(start.x == end.x && start.y == end.y))
365                    {
366                        markPiercing(start);
367                        markEnvironmentCorridor(start.x, start.y);
368                        start = start.translate(dir);
369                    }
370                    break;
371                case BOX_WALLED:
372                    markRectangleWalled(end, rng.between(1, 5), rng.between(1, 5));
373                    markRectangleWalled(start, rng.between(1, 4), rng.between(1, 4));
374                    store();
375                    dir = Direction.getDirection(end.x - start.x, (end.y - start.y));
376                    if(dir.isDiagonal())
377                        dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0)
378                                : Direction.getCardinalDirection(0, -dir.deltaY);
379                    while (start.x != end.x && start.y != end.y)
380                    {
381                        markPiercing(start);
382                        markEnvironmentCorridor(start.x, start.y);
383                        start = start.translate(dir);
384                    }
385                    markRectangleWalled(start, 1, 1);
386                    dir = Direction.getCardinalDirection(end.x - start.x, -(end.y - start.y));
387                    while (!(start.x == end.x && start.y == end.y))
388                    {
389                        markPiercing(start);
390                        markEnvironmentCorridor(start.x, start.y);
391                        start = start.translate(dir);
392                    }
393                    break;
394                case ROUND:
395                    markCircle(end, rng.between(2, 6));
396                    markCircle(start, rng.between(2, 6));
397                    store();
398                    dir = Direction.getDirection(end.x - start.x, (end.y - start.y));
399                    if(dir.isDiagonal())
400                        dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0)
401                                : Direction.getCardinalDirection(0, -dir.deltaY);
402                    while (start.x != end.x && start.y != end.y)
403                    {
404                        markPiercing(start);
405                        markEnvironmentCorridor(start.x, start.y);
406                        start = start.translate(dir);
407                    }
408                    markCircle(start, 2);
409                    dir = Direction.getCardinalDirection(end.x - start.x, -(end.y - start.y));
410                    while (!(start.x == end.x && start.y == end.y))
411                    {
412                        markPiercing(start);
413                        markEnvironmentCorridor(start.x, start.y);
414                        start = start.translate(dir);
415                    }
416                    break;
417                case ROUND_WALLED:
418                    markCircleWalled(end, rng.between(2, 6));
419                    markCircleWalled(start, rng.between(2, 6));
420                    store();
421                    dir = Direction.getDirection(end.x - start.x, (end.y - start.y));
422                    if(dir.isDiagonal())
423                        dir = rng.nextBoolean() ? Direction.getCardinalDirection(dir.deltaX, 0)
424                                : Direction.getCardinalDirection(0, -dir.deltaY);
425                    while (start.x != end.x && start.y != end.y)
426                    {
427                        markPiercing(start);
428                        markEnvironmentCorridor(start.x, start.y);
429                        start = start.translate(dir);
430                    }
431                    markCircleWalled(start, 2);
432                    dir = Direction.getCardinalDirection(end.x - start.x, -(end.y - start.y));
433                    while (!(start.x == end.x && start.y == end.y))
434                    {
435                        markPiercing(start);
436                        markEnvironmentCorridor(start.x, start.y);
437                        start = start.translate(dir);
438                    }
439                    break;
440            }
441            store();
442        }
443        for (int x = 0; x < width; x++) {
444            for (int y = 0; y < height; y++) {
445                if(fixedRooms[x][y])
446                    markPiercingRoom(x, y);
447            }
448        }
449        store();
450        markEnvironmentWalls();
451        generated = true;
452        return dungeon;
453    }
454
455    public int[][] getEnvironment()
456    {
457        return environment;
458    }
459
460    public boolean hasGenerated()
461    {
462        return generated;
463    }
464
465    public boolean[][] getFixedRooms() {
466        return fixedRooms;
467    }
468
469    public void setFixedRooms(boolean[][] fixedRooms) {
470        this.fixedRooms = fixedRooms;
471    }
472
473    /**
474     * Internal use. Takes cells that have been previously marked and permanently stores them as floors in the dungeon.
475     */
476    protected void store()
477    {
478        for (int i = 0; i < width; i++) {
479            for (int j = 0; j < height; j++) {
480                if(marked[i][j])
481                {
482                    dungeon[i][j] = '.';
483                    marked[i][j] = false;
484                }
485            }
486        }
487    }
488
489    /**
490     * Internal use. Finds all floor cells by environment and marks untouched adjacent (8-way) cells as walls, using the
491     * appropriate type for the nearby floor.
492     */
493    protected void markEnvironmentWalls()
494    {
495        for (int i = 0; i < width; i++) {
496            for (int j = 0; j < height; j++) {
497                if(environment[i][j] == UNTOUCHED)
498                {
499                    boolean allWalls = true;
500                    //lowest precedence, also checks for any floors
501                    for (int x = Math.max(0, i - 1); x <= Math.min(width - 1, i + 1); x++) {
502
503                        for (int y = Math.max(0, j - 1); y <= Math.min(height - 1, j + 1); y++) {
504                            if (environment[x][y] == CORRIDOR_FLOOR) {
505                                markEnvironment(i, j, CORRIDOR_WALL);
506                            }
507                            if(dungeon[x][y] == '.')
508                                allWalls = false;
509                        }
510                    }
511                    //if there are no floors we don't need to check twice again.
512                    if(allWalls)
513                        continue;
514                    //more precedence
515                    for (int x = Math.max(0, i - 1); x <= Math.min(width - 1, i + 1); x++) {
516
517                        for (int y = Math.max(0, j - 1); y <= Math.min(height - 1, j + 1); y++) {
518                            if (environment[x][y] == CAVE_FLOOR) {
519                                markEnvironment(i, j, CAVE_WALL);
520                            }
521                        }
522                    }
523                    //highest precedence
524                    for (int x = Math.max(0, i - 1); x <= Math.min(width - 1, i + 1); x++) {
525
526                        for (int y = Math.max(0, j - 1); y <= Math.min(height - 1, j + 1); y++) {
527                            if (environment[x][y] == ROOM_FLOOR) {
528                                markEnvironment(i, j, ROOM_WALL);
529                            }
530                        }
531                    }
532
533                }
534            }
535        }
536    }
537
538    /**
539     * Internal use. Marks a point to be made into floor.
540     * @param x x position to mark
541     * @param y y position to mark
542     * @return false if everything is normal, true if and only if this failed to mark because the position is walled
543     */
544    protected boolean mark(int x, int y) {
545        if (x > 0 && x < width - 1 && y > 0 && y < height - 1 && !walled[x][y]) {
546            marked[x][y] = true;
547            return false;
548        }
549        else return x > 0 && x < width - 1 && y > 0 && y < height - 1 && walled[x][y];
550    }
551
552    /**
553     * Internal use. Marks a point to be made into floor.
554     * @param x x position to mark
555     * @param y y position to mark
556     */
557    protected void markPiercing(int x, int y) {
558        if (x > 0 && x < width - 1 && y > 0 && y < height - 1) {
559            marked[x][y] = true;
560        }
561    }
562    /**
563     * Internal use. Marks a point's environment type as the appropriate kind of environment.
564     * @param x x position to mark
565     * @param y y position to mark
566     * @param kind an int that should be one of the constants in MixedGenerator for environment types.
567     */
568    protected void markEnvironment(int x, int y, int kind) {
569        environment[x][y] = kind;
570    }
571
572    /**
573     * Internal use. Marks a point's environment type as a corridor floor.
574     * @param x x position to mark
575     * @param y y position to mark
576     */
577    protected void markEnvironmentCorridor(int x, int y) {
578        if (x > 0 && x < width - 1 && y > 0 && y < height - 1 && environment[x][y] != ROOM_FLOOR && environment[x][y] != CAVE_FLOOR) {
579            markEnvironment(x, y, CORRIDOR_FLOOR);
580        }
581    }
582
583    /**
584     * Internal use. Marks a point's environment type as a room floor.
585     * @param x x position to mark
586     * @param y y position to mark
587     */
588    protected void markEnvironmentRoom(int x, int y) {
589        if (x > 0 && x < width - 1 && y > 0 && y < height - 1) {
590            markEnvironment(x, y, ROOM_FLOOR);
591        }
592    }
593
594    /**
595     * Internal use. Marks a point's environment type as a cave floor.
596     * @param x x position to mark
597     * @param y y position to mark
598     */
599    protected void markEnvironmentCave(int x, int y) {
600        if (x > 0 && x < width - 1 && y > 0 && y < height - 1 && environment[x][y] != ROOM_FLOOR) {
601            markEnvironment(x, y, CAVE_FLOOR);
602        }
603    }
604    /**
605     * Internal use. Marks a point to be made into floor.
606     * @param x x position to mark
607     * @param y y position to mark
608     */
609    protected void wallOff(int x, int y) {
610        if (x > 0 && x < width - 1 && y > 0 && y < height - 1) {
611            walled[x][y] = true;
612        }
613    }
614
615    /**
616     * Internal use. Marks a point to be made into floor.
617     * @param pos position to mark
618     * @return false if everything is normal, true if and only if this failed to mark because the position is walled
619     */
620    protected boolean mark(Coord pos)
621    {
622        return mark(pos.x, pos.y);
623    }
624
625    /**
626     * Internal use. Marks a point to be made into floor, piercing walls.
627     * @param pos position to mark
628     */
629    protected void markPiercing(Coord pos)
630    {
631        markPiercing(pos.x, pos.y);
632    }
633    /**
634     * Internal use. Marks a point to be made into floor, piercing walls, and also marks the point as a cave floor.
635     * @param pos position to mark
636     */
637    protected void markPiercingCave(Coord pos)
638    {
639        markPiercing(pos.x, pos.y);
640        markEnvironmentCave(pos.x, pos.y);
641    }
642    /**
643     * Internal use. Marks a point to be made into floor, piercing walls, and also marks the point as a room floor.
644     * @param x x coordinate of position to mark
645     * @param y y coordinate of position to mark
646     */
647    protected void markPiercingRoom(int x, int y)
648    {
649        markPiercing(x, y);
650        markEnvironmentCave(x, y);
651    }
652
653    /**
654     * Internal use. Marks a point and the four cells orthogonally adjacent to it.
655     * @param pos center position to mark
656     * @return null if the center of the plus shape wasn't blocked by wall, otherwise the Coord of the center
657     */
658    private Coord markPlus(Coord pos) {
659        Coord block = null;
660        if (mark(pos.x, pos.y))
661            block = pos;
662        mark(pos.x + 1, pos.y);
663        mark(pos.x - 1, pos.y);
664        mark(pos.x, pos.y + 1);
665        mark(pos.x, pos.y - 1);
666        return block;
667    }
668
669    /**
670     * Internal use. Marks a point and the four cells orthogonally adjacent to it, and also marks any cells that weren't
671     * blocked as cave floors.
672     * @param pos center position to mark
673     * @return null if the center of the plus shape wasn't blocked by wall, otherwise the Coord of the center
674     */
675    private Coord markPlusCave(Coord pos) {
676        Coord block = null;
677        if (mark(pos.x, pos.y))
678            block = pos;
679        else
680            markEnvironmentCave(pos.x, pos.y);
681        if(!mark(pos.x + 1, pos.y))
682            markEnvironmentCave(pos.x + 1, pos.y);
683        if(!mark(pos.x - 1, pos.y))
684            markEnvironmentCave(pos.x - 1, pos.y);
685        if(!mark(pos.x, pos.y + 1))
686            markEnvironmentCave(pos.x, pos.y + 1);
687        if(!mark(pos.x, pos.y - 1))
688            markEnvironmentCave(pos.x, pos.y - 1);
689        return block;
690    }
691    /**
692     * Internal use. Marks a rectangle of points centered on pos, extending halfWidth in both x directions and
693     * halfHeight in both vertical directions. Marks all cells in the rectangle as room floors.
694     * @param pos center position to mark
695     * @param halfWidth the distance from the center to extend horizontally
696     * @param halfHeight the distance from the center to extend vertically
697     * @return null if no points in the rectangle were blocked by walls, otherwise a Coord blocked by a wall
698     */
699    private Coord markRectangle(Coord pos, int halfWidth, int halfHeight)
700    {
701        halfWidth = Math.max(1, Math.round(halfWidth * roomWidth));
702        halfHeight = Math.max(1, Math.round(halfHeight * roomHeight));
703        Coord block = null;
704        for (int i = pos.x - halfWidth; i <= pos.x + halfWidth; i++) {
705            for (int j = pos.y - halfHeight; j <= pos.y + halfHeight; j++) {
706                if(mark(i, j))
707                    block = Coord.get(i, j);
708                else
709                    markEnvironmentRoom(i, j);
710            }
711        }
712        return block;
713    }
714    /**
715     * Internal use. Marks a rectangle of points centered on pos, extending halfWidth in both x directions and
716     * halfHeight in both vertical directions. Also considers the area just beyond each wall, but not corners, to be
717     * a blocking wall that can only be passed by corridors and small cave openings. Marks all cells in the rectangle as
718     * room floors.
719     * @param pos center position to mark
720     * @param halfWidth the distance from the center to extend horizontally
721     * @param halfHeight the distance from the center to extend vertically
722     * @return null if no points in the rectangle were blocked by walls, otherwise a Coord blocked by a wall
723     */
724    private Coord markRectangleWalled(Coord pos, int halfWidth, int halfHeight)
725    {
726        halfWidth = Math.max(1, Math.round(halfWidth * roomWidth));
727        halfHeight = Math.max(1, Math.round(halfHeight * roomHeight));
728        Coord block = null;
729        for (int i = pos.x - halfWidth; i <= pos.x + halfWidth; i++) {
730            for (int j = pos.y - halfHeight; j <= pos.y + halfHeight; j++) {
731                if(mark(i, j))
732                    block = Coord.get(i, j);
733                else
734                    markEnvironmentRoom(i, j);
735            }
736        }
737        for (int i = Math.max(0, pos.x - halfWidth - 1); i <= Math.min(width - 1, pos.x + halfWidth + 1); i++) {
738            for (int j = Math.max(0, pos.y - halfHeight - 1); j <= Math.min(height - 1, pos.y + halfHeight + 1); j++)
739            {
740                wallOff(i, j);
741            }
742        }
743        return block;
744    }
745
746    /**
747     * Internal use. Marks a circle of points centered on pos, extending out to radius in Euclidean measurement. Marks
748     * all cells in the circle as room floors.
749     * @param pos center position to mark
750     * @param radius radius to extend in all directions from center
751     * @return null if no points in the circle were blocked by walls, otherwise a Coord blocked by a wall
752     */
753    private Coord markCircle(Coord pos, int radius)
754    {
755        Coord block = null;
756        int high;
757        radius = Math.max(1, Math.round(radius * Math.min(roomWidth, roomHeight)));
758        for (int dx = -radius; dx <= radius; ++dx)
759        {
760            high = (int)Math.floor(Math.sqrt(radius * radius - dx * dx));
761            for (int dy = -high; dy <= high; ++dy)
762            {
763                if(mark(pos.x + dx, pos.y + dy))
764                    block = pos.translate(dx, dy);
765                else
766                    markEnvironmentRoom(pos.x + dx, pos.y + dy);
767            }
768        }
769        return block;
770    }
771    /**
772     * Internal use. Marks a circle of points centered on pos, extending out to radius in Euclidean measurement.
773     * Also considers the area just beyond each wall, but not corners, to be a blocking wall that can only be passed by
774     * corridors and small cave openings. Marks all cells in the circle as room floors.
775     * @param pos center position to mark
776     * @param radius radius to extend in all directions from center
777     * @return null if no points in the circle were blocked by walls, otherwise a Coord blocked by a wall
778     */
779    private Coord markCircleWalled(Coord pos, int radius)
780    {
781        Coord block = null;
782        int high;
783        radius = Math.max(1, Math.round(radius * Math.min(roomWidth, roomHeight)));
784        for (int dx = -radius; dx <= radius; ++dx)
785        {
786            high = (int)Math.floor(Math.sqrt(radius * radius - dx * dx));
787            for (int dy = -high; dy <= high; ++dy)
788            {
789                if(mark(pos.x + dx, pos.y + dy))
790                    block = pos.translate(dx, dy);
791                else
792                    markEnvironmentRoom(pos.x + dx, pos.y + dy);
793            }
794        }
795        for (int dx = -radius; dx <= radius; ++dx)
796        {
797            high = (int)Math.floor(Math.sqrt(radius * radius - dx * dx));
798            int dx2 = Math.max(1, Math.min(pos.x + dx, width - 2));
799            for (int dy = -high; dy <= high; ++dy)
800            {
801                int dy2 = Math.max(1, Math.min(pos.y + dy, height - 2));
802
803                wallOff(dx2, dy2-1);
804                wallOff(dx2+1, dy2-1);
805                wallOff(dx2-1, dy2-1);
806                wallOff(dx2, dy2);
807                wallOff(dx2+1, dy2);
808                wallOff(dx2-1, dy2);
809                wallOff(dx2, dy2+1);
810                wallOff(dx2+1, dy2+1);
811                wallOff(dx2-1, dy2+1);
812
813            }
814        }
815        return block;
816    }
817
818    /**
819     * Internal use. Drunkard's walk algorithm, single step. Based on Michael Patraw's C code, used for cave carving.
820     * http://mpatraw.github.io/libdrunkard/
821     * @param current the current point
822     * @param target the point to wobble towards
823     * @param weight between 0.5 and 1.0, usually. 0.6 makes very random caves, 0.9 is almost a straight line.
824     * @return a Direction, either UP, DOWN, LEFT, or RIGHT if we should move, or NONE if we have reached our target
825     */
826    private Direction stepWobbly(Coord current, Coord target, double weight)
827    {
828        int dx = target.x - current.x;
829        int dy = target.y - current.y;
830
831        if (dx >  1) dx = 1;
832        if (dx < -1) dx = -1;
833        if (dy >  1) dy = 1;
834        if (dy < -1) dy = -1;
835
836        double r = rng.nextDouble();
837        Direction dir;
838        if (dx == 0 && dy == 0)
839        {
840            return Direction.NONE;
841        }
842        else if (dx == 0 || dy == 0)
843        {
844            int dx2 = (dx == 0) ? dx : dy, dy2 = (dx == 0) ? dy : dx;
845            if (r >= (weight * 0.5))
846            {
847                r -= weight * 0.5;
848                if (r < weight * (1.0 / 6) + (1 - weight) * (1.0 / 3))
849                {
850                    dx2 = -1;
851                    dy2 = 0;
852                }
853                else if (r < weight * (2.0 / 6) + (1 - weight) * (2.0 / 3))
854                {
855                    dx2 = 1;
856                    dy2 = 0;
857                }
858                else
859                {
860                    dx2 = 0;
861                    dy2 *= -1;
862                }
863            }
864            dir = Direction.getCardinalDirection(dx2, -dy2);
865
866        }
867        else
868        {
869            if (r < weight * 0.5)
870            {
871                dy = 0;
872            }
873            else if (r < weight)
874            {
875                dx = 0;
876            }
877            else if (r < weight + (1 - weight) * 0.5)
878            {
879                dx *= -1;
880                dy = 0;
881            }
882            else
883            {
884                dx = 0;
885                dy *= -1;
886            }
887            dir = Direction.getCardinalDirection(dx, -dy);
888        }
889        if(current.x + dir.deltaX <= 0 || current.x + dir.deltaX >= width - 1) {
890            if (current.y < target.y) dir = Direction.DOWN;
891            else if (current.y > target.y) dir = Direction.UP;
892        }
893        else if(current.y + dir.deltaY <= 0 || current.y + dir.deltaY >= height - 1) {
894            if (current.x < target.x) dir = Direction.RIGHT;
895            else if (current.x > target.x) dir = Direction.LEFT;
896        }
897        return dir;
898    }
899
900}