001package squidpony.squidgrid.mapping;
002
003import squidpony.squidmath.Coord;
004import squidpony.squidmath.CoordPacker;
005import squidpony.squidmath.RNG;
006
007import java.util.ArrayList;
008import java.util.LinkedHashMap;
009import java.util.List;
010
011/**
012 * Generate dungeons based on a random, winding, looping path through 2D space. Uses techniques from MixedGenerator.
013 * Uses a Moore Curve, which is related to Hilbert Curves but loops back to its starting point, and stretches and
014 * distorts the grid to make sure a visual correlation isn't obvious. This supports the getEnvironment() method, which
015 * can be used in conjunction with RoomFinder to find where separate room, corridor, and cave areas have been placed.
016 * <br>
017 * To get a sense of what kinds of map this generates, you can look at a sample map on
018 * https://gist.github.com/tommyettinger/93b47048fc8a209a9712 , which also includes a snippet of Java code that can
019 * generate that map.
020 * <br>
021 * The name comes from a vivid dream I had about gigantic, multi-colored snakes that completely occupied a roguelike
022 * dungeon. Shortly after, I made the connection to the Australian mythology I'd heard about the Rainbow Serpent, which
023 * in some stories dug water-holes and was similarly gigantic.
024 * Created by Tommy Ettinger on 10/24/2015.
025 */
026public class SerpentMapGenerator {
027    private MixedGenerator mix;
028    private int[] columns, rows;
029    private RNG random;
030    /**
031     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
032     * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing
033     * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the
034     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
035     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
036     * @param width the width of the final map in cells
037     * @param height the height of the final map in cells
038     * @param rng an RNG object to use for random choices; this make a lot of random choices.
039     * @see MixedGenerator
040     */
041    public SerpentMapGenerator(int width, int height, RNG rng)
042    {
043        this(width, height, rng, false);
044    }
045    /**
046     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
047     * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing
048     * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the
049     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
050     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
051     * @param width the width of the final map in cells
052     * @param height the height of the final map in cells
053     * @param rng an RNG object to use for random choices; this make a lot of random choices.
054     * @param symmetrical true if this should generate a bi-radially symmetric map, false for a typical map
055     * @see MixedGenerator
056     */
057    public SerpentMapGenerator(int width, int height, RNG rng, boolean symmetrical)
058    {
059        if(width <= 2 || height <= 2)
060            throw new IllegalArgumentException("width and height must be greater than 2");
061        random = rng;
062        long columnAlterations = random.nextLong(0x1000000000000L);
063        float columnBase = width / (Long.bitCount(columnAlterations) + 48.0f);
064        long rowAlterations = random.nextLong(0x1000000000000L);
065        float rowBase = height / (Long.bitCount(rowAlterations) + 48.0f);
066
067        columns = new int[16];
068        rows = new int[16];
069        int csum = 0, rsum = 0;
070        long b = 7;
071        for (int i = 0; i < 16; i++, b <<= 3) {
072            columns[i] = csum + (int)(columnBase * 0.5f * (3 + Long.bitCount(columnAlterations & b)));
073            csum += (int)(columnBase * (3 + Long.bitCount(columnAlterations & b)));
074            rows[i] = rsum + (int)(rowBase * 0.5f * (3 + Long.bitCount(rowAlterations & b)));
075            rsum += (int)(rowBase * (3 + Long.bitCount(rowAlterations & b)));
076        }
077        int cs = (width - csum);
078        int rs = (height - rsum);
079        int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs;
080        for (int i = 0; i <= 7; i++) {
081            cs2= cs2 * i / 7;
082            rs2 = rs2 * i / 7;
083            columns[i] -= cs2;
084            rows[i] -= rs2;
085        }
086        for (int i = 15; i >= 8; i--) {
087            cs3 = cs3 * (i - 8) / 8;
088            rs3 = rs3 * (i - 8) / 8;
089            columns[i] += cs3;
090            rows[i] += rs3;
091        }
092
093        List<Coord> points = new ArrayList<>(80);
094        Coord temp;
095        for (int i = 0, m = random.nextInt(64), r; i < 256; r = random.between(4, 12), i += r, m += r) {
096            temp = CoordPacker.mooreToCoord(m);
097            points.add(Coord.get(columns[temp.x], rows[temp.y]));
098        }
099        points.add(points.get(0));
100        if(symmetrical) {
101            mix = new SymmetryDungeonGenerator(width, height, random,
102                    SymmetryDungeonGenerator.removeSomeOverlap(width, height, points));
103        }
104        else
105            mix = new MixedGenerator(width, height, random, points);
106    }
107
108    /**
109     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
110     * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing
111     * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the
112     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
113     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
114     * @param width the width of the final map in cells
115     * @param height the height of the final map in cells
116     * @param rng an RNG object to use for random choices; this make a lot of random choices.
117     * @param branchingChance the chance from 0.0 to 1.0 that each room will branch at least once
118     * @see MixedGenerator
119     */
120    public SerpentMapGenerator(int width, int height, RNG rng, double branchingChance)
121    {
122        this(width, height, rng, branchingChance, false);
123    }
124    /**
125     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
126     * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing
127     * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the
128     * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only
129     * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map.
130     * @param width the width of the final map in cells
131     * @param height the height of the final map in cells
132     * @param rng an RNG object to use for random choices; this make a lot of random choices.
133     * @param branchingChance the chance from 0.0 to 1.0 that each room will branch at least once
134     * @param symmetrical true if this should generate a bi-radially symmetric map, false for a typical map
135     * @see MixedGenerator
136     */
137    public SerpentMapGenerator(int width, int height, RNG rng, double branchingChance, boolean symmetrical)
138    {
139        if(width <= 2 || height <= 2)
140            throw new IllegalArgumentException("width and height must be greater than 2");
141        random = rng;
142        long columnAlterations = random.nextLong(0x1000000000000L);
143        float columnBase = width / (Long.bitCount(columnAlterations) + 48.0f);
144        long rowAlterations = random.nextLong(0x1000000000000L);
145        float rowBase = height / (Long.bitCount(rowAlterations) + 48.0f);
146
147        columns = new int[16];
148        rows = new int[16];
149        int csum = 0, rsum = 0;
150        long b = 7;
151        for (int i = 0; i < 16; i++, b <<= 3) {
152            columns[i] = csum + (int)(columnBase * 0.5f * (3 + Long.bitCount(columnAlterations & b)));
153            csum += (int)(columnBase * (3 + Long.bitCount(columnAlterations & b)));
154            rows[i] = rsum + (int)(rowBase * 0.5f * (3 + Long.bitCount(rowAlterations & b)));
155            rsum += (int)(rowBase * (3 + Long.bitCount(rowAlterations & b)));
156        }
157        int cs = (width - csum);
158        int rs = (height - rsum);
159        int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs;
160        for (int i = 0; i <= 7; i++) {
161            cs2= cs2 * i / 7;
162            rs2 = rs2 * i / 7;
163            columns[i] -= cs2;
164            rows[i] -= rs2;
165        }
166        for (int i = 15; i >= 8; i--) {
167            cs3 = cs3 * (i - 8) / 8;
168            rs3 = rs3 * (i - 8) / 8;
169            columns[i] += cs3;
170            rows[i] += rs3;
171        }
172
173        LinkedHashMap<Coord, List<Coord>> connections = new LinkedHashMap<>(80);
174        Coord temp, t;
175        int m = random.nextInt(64), r = random.between(4, 12);
176        temp = CoordPacker.mooreToCoord(m);
177        Coord starter = CoordPacker.mooreToCoord(m);
178        m += r;
179        for (int i = r; i < 256; i += r, m += r) {
180            List<Coord> cl = new ArrayList<>(4);
181            cl.add(Coord.get(columns[temp.x], rows[temp.y]));
182            temp = CoordPacker.mooreToCoord(m);
183            r = random.between(4, 12);
184            for (int j = 0, p = r - 1;
185                 j < 3 && p > 2 && Math.min(random.nextDouble(), random.nextDouble()) < branchingChance;
186                 j++, p -= random.between(1, p)) {
187                t = CoordPacker.mooreToCoord(m + p);
188                cl.add(Coord.get(columns[t.x], rows[t.y]));
189            }
190            connections.put(Coord.get(columns[temp.x], rows[temp.y]), cl);
191        }
192        connections.get(Coord.get(columns[temp.x], rows[temp.y])).add(
193                Coord.get(columns[starter.x], rows[starter.y]));
194        if(symmetrical) {
195            mix = new SymmetryDungeonGenerator(width, height, random,
196                    SymmetryDungeonGenerator.removeSomeOverlap(width, height, connections));
197        }
198        else
199            mix = new MixedGenerator(width, height, random, connections);
200
201    }
202
203    /**
204     * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves
205     * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make
206     * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically
207     * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10
208     * between the count of putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers() is reasonable.
209     * @see MixedGenerator
210     * @param count the number of carvers making caves between rooms; only matters in relation to other carvers
211     */
212    public void putCaveCarvers(int count)
213    {
214        mix.putCaveCarvers(count);
215    }
216    /**
217     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
218     * 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
219     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
220     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
221     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
222     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
223     * and putRoundRoomCarvers() is reasonable.
224     * @see MixedGenerator
225     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
226     *              to other carvers
227     */
228    public void putBoxRoomCarvers(int count)
229    {
230        mix.putBoxRoomCarvers(count);
231    }
232    /**
233     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
234     * with a random size in a box shape at the start and end, and a small room at the corner if there is one. This also
235     * ensures walls will be placed around the room, only allowing corridors and small cave openings to pass. If count
236     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
237     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
238     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
239     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
240     * and putRoundRoomCarvers() is reasonable.
241     * @see MixedGenerator
242     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
243     *              to other carvers
244     */
245    public void putWalledBoxRoomCarvers(int count)
246    {
247        mix.putWalledBoxRoomCarvers(count);
248    }
249    /**
250     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
251     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
252     * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
253     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
254     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
255     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
256     * and putRoundRoomCarvers() is reasonable.
257     * @see MixedGenerator
258     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
259     *              to other carvers
260     */
261    public void putRoundRoomCarvers(int count)
262    {
263        mix.putRoundRoomCarvers(count);
264    }
265
266    /**
267     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
268     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
269     * one. This also ensures walls will be placed around the room, only allowing corridors and small cave openings to
270     * pass. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
271     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
272     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
273     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
274     * and putRoundRoomCarvers() is reasonable.
275     * @see MixedGenerator
276     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
277     *              to other carvers
278     */
279    public void putWalledRoundRoomCarvers(int count)
280    {
281        mix.putWalledRoundRoomCarvers(count);
282    }
283
284    /**
285     * This generates a new map by stretching a 16x16 grid of potential rooms to fit the width and height passed to the
286     * constructor, randomly expanding columns and rows before contracting the whole to fit perfectly. This uses the
287     * Moore Curve, a space-filling curve that loops around on itself, to guarantee that the rooms will always have a
288     * long path through the dungeon that, if followed completely, will take you back to your starting room. Some small
289     * branches are possible, and large rooms may merge with other rooms nearby. This uses MixedGenerator.
290     * @see MixedGenerator
291     * @return a char[][] where '#' is a wall and '.' is a floor or corridor; x first y second
292     */
293    public char[][] generate()
294    {
295        return mix.generate();
296    }
297
298    /**
299     * Gets a 2D array of int constants, each representing a type of environment corresponding to a static field of
300     * MixedGenerator. This array will have the same size as the last char 2D array produced by generate(); the value
301     * of this method if called before generate() is undefined, but probably will be a 2D array of all 0 (UNTOUCHED).
302     * <ul>
303     *     <li>MixedGenerator.UNTOUCHED, equal to 0, is used for any cells that aren't near a floor.</li>
304     *     <li>MixedGenerator.ROOM_FLOOR, equal to 1, is used for floor cells inside wide room areas.</li>
305     *     <li>MixedGenerator.ROOM_WALL, equal to 2, is used for wall cells around wide room areas.</li>
306     *     <li>MixedGenerator.CAVE_FLOOR, equal to 3, is used for floor cells inside rough cave areas.</li>
307     *     <li>MixedGenerator.CAVE_WALL, equal to 4, is used for wall cells around rough cave areas.</li>
308     *     <li>MixedGenerator.CORRIDOR_FLOOR, equal to 5, is used for floor cells inside narrow corridor areas.</li>
309     *     <li>MixedGenerator.CORRIDOR_WALL, equal to 6, is used for wall cells around narrow corridor areas.</li>
310     * </ul>
311     * @return a 2D int array where each element is an environment type constant in MixedGenerator
312     */
313    public int[][] getEnvironment()
314    {
315        return mix.getEnvironment();
316    }
317}