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.LinkedHashSet;
010import java.util.List;
011
012/**
013 * Generate dungeons based on a random, winding, looping path through 3D space, requiring a character to move up and
014 * down as well as north/south/east/west to get through the dungeon. Uses techniques from MixedGenerator.
015 * Uses a Moore Curve, which is related to Hilbert Curves but loops back to its starting point, and stretches and
016 * distorts the grid to make sure a visual correlation isn't obvious.
017 * <br>
018 * The name comes from a vivid dream I had about gigantic, multi-colored snakes that completely occupied a roguelike
019 * dungeon. Shortly after, I made the connection to the Australian mythology I'd heard about the Rainbow Serpent, which
020 * in some stories dug water-holes and was similarly gigantic.
021 * Created by Tommy Ettinger on 10/24/2015.
022 */
023public class SerpentDeepMapGenerator {
024    private MixedGenerator[] mix;
025    private int[] columns, rows;
026    private int width, height, depth;
027    private ArrayList<LinkedHashSet<Coord>> linksUp,linksDown;
028    private RNG random;
029
030    /**
031     * This prepares a map generator that will generate a map with the given width, height and depth, using the given
032     * RNG. The intended purpose is to carve a long path that loops through the whole dungeon's 3D space, while
033     * hopefully maximizing the amount of rooms the player encounters. You call the different carver-adding methods to
034     * affect what the dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(),
035     * defaulting to only caves if none are called. You call generate() after adding carvers, which returns a char[][][]
036     * for a map.
037     * @param width the width of the final map in cells
038     * @param height the height of the final map in cells
039     * @param depth the number of levels deep to create
040     * @param rng an RNG object to use for random choices; this make a lot of random choices.
041     * @see MixedGenerator
042     */
043    public SerpentDeepMapGenerator(int width, int height, int depth, RNG rng) {
044        this(width, height, depth, rng, 0.3);
045    }
046    /**
047     * This prepares a map generator that will generate a map with the given width, height and depth, using the given
048     * RNG, and will branch out to other nearby rooms that (probably) do not have staircases between layers.
049     * The intended purpose is to carve a long path that loops through the whole dungeon's 3D space, while
050     * hopefully maximizing the amount of rooms the player encounters. You call the different carver-adding methods to
051     * affect what the dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(),
052     * defaulting to only caves if none are called. You call generate() after adding carvers, which returns a char[][][]
053     * for a map.
054     * @param width the width of the final map in cells
055     * @param height the height of the final map in cells
056     * @param depth the number of levels deep to create
057     * @param rng an RNG object to use for random choices; this make a lot of random choices.
058     * @param branchingChance the odds from 0.0 to 1.0 that a branch will be created near each necessary room.
059     * @see MixedGenerator
060     */
061    public SerpentDeepMapGenerator(int width, int height, int depth, RNG rng, double branchingChance)
062    {
063        if(width <= 2 || height <= 2)
064            throw new IllegalArgumentException("width and height must be greater than 2");
065        if(depth < 1)
066            throw new IllegalArgumentException("depth must be at least 1");
067        random = rng;
068        this.width = width;
069        this.height = height;
070        this.depth = depth;
071        int numLayers = (int)Math.ceil(depth / 4.0f);
072        long columnAlterations = random.nextLong(0x100000000L);
073        float columnBase = width / (Long.bitCount(columnAlterations) + 16.0f);
074        long rowAlterations = random.nextLong(0x100000000L);
075        float rowBase = height / (Long.bitCount(rowAlterations) + 16.0f);
076
077        columns = new int[16];
078        rows = new int[16];
079        linksUp = new ArrayList<>(depth);
080        linksDown = new ArrayList<>(depth);
081        for (int i = 0; i < depth; i++) {
082            linksUp.add(new LinkedHashSet<Coord>(80));
083            linksDown.add(new LinkedHashSet<Coord>(80));
084        }
085        int csum = 0, rsum = 0;
086        long b = 3;
087        for (int i = 0; i < 16; i++, b <<= 2) {
088            columns[i] = csum + (int)(columnBase * 0.5f * (1 + Long.bitCount(columnAlterations & b)));
089            csum += (int)(columnBase * (1 + Long.bitCount(columnAlterations & b)));
090            rows[i] = rsum + (int)(rowBase * 0.5f * (1 + Long.bitCount(rowAlterations & b)));
091            rsum += (int)(rowBase * (1 + Long.bitCount(rowAlterations & b)));
092        }
093        int cs = (width - csum);
094        int rs = (height - rsum);
095        int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs;
096        for (int i = 0; i <= 7; i++) {
097            cs2= cs2 * i / 7;
098            rs2 = rs2 * i / 7;
099            columns[i] -= cs2;
100            rows[i] -= rs2;
101        }
102        for (int i = 15; i >= 8; i--) {
103            cs3 = cs3 * (i - 8) / 8;
104            rs3 = rs3 * (i - 8) / 8;
105            columns[i] += cs3;
106            rows[i] += rs3;
107        }
108
109        List<LinkedHashMap<Coord, List<Coord>>> connections = new ArrayList<>(depth);
110        for (int i = 0; i < depth; i++) {
111            connections.add(new LinkedHashMap<Coord, List<Coord>>(80));
112        }
113        int m = random.nextInt(0x800 * numLayers);
114        int x = CoordPacker.getXMoore3D(m, numLayers), y = CoordPacker.getYMoore3D(m, numLayers),
115                z = (int)Math.floor(CoordPacker.getZMoore3D(m, numLayers) * depth / (8f * numLayers)),
116                sx = x, sy = y, sz = z, tz = z;
117        int r = random.between(12, 33);
118        m += r;
119        for (int i = 0; i < 0x800 * numLayers; r = random.between(12, 33), i += r, m = (m + r) % (0x800 * numLayers)) {
120            tz = z;
121            int tx = x, ty = y;
122            do {
123                List<Coord> cl = new ArrayList<>(4);
124
125                for (int j = 0;
126                     j < 2;
127                     j++) {
128                    int x2 = random.between(Math.max(0, tx - 2), tx);
129                    int x3 = random.between(tx + 1, Math.min(tx + 3, 15));
130                    int y2 = random.between(Math.max(0, ty - 2), ty);
131                    int y3 = random.between(ty + 1, Math.min(ty + 3, 15));
132                    if (x3 < 16 && random.nextBoolean())
133                        x2 = x3;
134                    if (y3 < 16 && random.nextBoolean())
135                        y2 = y3;
136                    cl.add(Coord.get(columns[x2], rows[y2]));
137                    if (random.nextDouble() >= branchingChance)
138                        break;
139                }
140
141                List<Coord> connect = connections.get(tz).get(Coord.get(columns[tx], rows[ty]));
142                if(connect != null)
143                    connections.get(tz).get(Coord.get(columns[tx], rows[ty])).addAll(cl);
144                else
145                    connections.get(tz).put(Coord.get(columns[tx], rows[ty]), new ArrayList<>(cl));
146
147                x = CoordPacker.getXMoore3D(m, numLayers);
148                y = CoordPacker.getYMoore3D(m, numLayers);
149                z = (int)Math.floor(CoordPacker.getZMoore3D(m, numLayers) * depth / (8f * numLayers));
150                if(z != tz)
151                    cl.clear();
152                cl.add(Coord.get(columns[x], rows[y]));
153
154                if (tz == z) {
155                    List<Coord> conn = connections.get(z).get(Coord.get(columns[tx], rows[ty]));
156                    if(conn != null)
157                        connections.get(z).get(Coord.get(columns[tx], rows[ty])).addAll(cl);
158                    else
159                        connections.get(z).put(Coord.get(columns[tx], rows[ty]), new ArrayList<>(cl));
160                    break;
161                }
162                else {
163                    if (z > tz) {
164                        linksDown.get(tz).add(Coord.get(tx, ty));
165                        tz++;
166                        linksUp.get(tz).add(Coord.get(tx, ty));
167                    }
168                    else
169                    {
170                        linksUp.get(tz).add(Coord.get(tx, ty));
171                        tz--;
172                        linksDown.get(tz).add(Coord.get(tx, ty));
173                    }
174                }
175            }while (true);
176        }
177
178        do {
179            List<Coord> cl = new ArrayList<>(4);
180
181            for (int j = 0;
182                 j < 2;
183                 j++) {
184                int x2 = random.between(Math.max(0, x - 2), x);
185                int x3 = random.between(x + 1, Math.min(x + 3, 15));
186                int y2 = random.between(Math.max(0, y - 2), y);
187                int y3 = random.between(y + 1, Math.min(y + 3, 15));
188                if (x3 < 16 && random.nextBoolean())
189                    x2 = x3;
190                if (y3 < 16 && random.nextBoolean())
191                    y2 = y3;
192                cl.add(Coord.get(columns[x2], rows[y2]));
193                if (Math.min(random.nextDouble(), random.nextDouble()) >= branchingChance)
194                    break;
195            }
196
197            List<Coord> connect = connections.get(tz).get(Coord.get(columns[x], rows[y]));
198            if(connect != null)
199                connections.get(tz).get(Coord.get(columns[x], rows[y])).addAll(cl);
200            else
201                connections.get(tz).put(Coord.get(columns[x], rows[y]), new ArrayList<>(cl));
202
203            if(sz != tz)
204                cl.clear();
205            cl.add(Coord.get(columns[x], rows[y]));
206
207            if (tz == sz) {
208                connections.get(sz).get(Coord.get(columns[x], rows[y])).add(
209                        Coord.get(columns[sx], rows[sy]));
210                break;
211            }
212            else {
213                if (sz > tz) {
214                    linksDown.get(tz).add(Coord.get(x, y));
215                    tz++;
216                    linksUp.get(tz).add(Coord.get(x, y));
217                }
218                else
219                {
220                    linksUp.get(tz).add(Coord.get(x, y));
221                    tz--;
222                    linksDown.get(tz).add(Coord.get(x, y));
223                }
224            }
225        }while (true);
226
227        mix = new MixedGenerator[depth];
228        for (int i = 0; i < depth; i++) {
229            mix[i] = new MixedGenerator(width, height, random, connections.get(i), 0.35f);
230        }
231    }
232    /**
233     * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves
234     * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make
235     * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically
236     * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10
237     * between the count of putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers() is reasonable.
238     * @see MixedGenerator
239     * @param count the number of carvers making caves between rooms; only matters in relation to other carvers
240     */
241    public void putCaveCarvers(int count)
242    {
243        for (int i = 0; i < depth; i++) {
244            mix[i].putCaveCarvers(count);
245        }
246    }
247    /**
248     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
249     * 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
250     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
251     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
252     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
253     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
254     * and putRoundRoomCarvers() is reasonable.
255     * @see MixedGenerator
256     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
257     *              to other carvers
258     */
259    public void putBoxRoomCarvers(int count)
260    {
261        for (int i = 0; i < depth; i++) {
262            mix[i].putBoxRoomCarvers(count);
263        }
264    }
265    /**
266     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
267     * 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
268     * ensures walls will be placed around the room, only allowing corridors and small cave openings to pass. If count
269     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
270     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
271     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
272     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
273     * and putRoundRoomCarvers() is reasonable.
274     * @see MixedGenerator
275     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
276     *              to other carvers
277     */
278    public void putWalledBoxRoomCarvers(int count)
279    {
280        for (int i = 0; i < depth; i++) {
281            mix[i].putWalledBoxRoomCarvers(count);
282        }
283    }
284    /**
285     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
286     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
287     * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
288     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
289     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
290     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
291     * and putRoundRoomCarvers() is reasonable.
292     * @see MixedGenerator
293     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
294     *              to other carvers
295     */
296    public void putRoundRoomCarvers(int count)
297    {
298        for (int i = 0; i < depth; i++) {
299            mix[i].putRoundRoomCarvers(count);
300        }
301    }
302
303    /**
304     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
305     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
306     * one. This also ensures walls will be placed around the room, only allowing corridors and small cave openings to
307     * pass. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
308     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
309     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
310     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
311     * and putRoundRoomCarvers() is reasonable.
312     * @see MixedGenerator
313     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
314     *              to other carvers
315     */
316    public void putWalledRoundRoomCarvers(int count)
317    {
318        for (int i = 0; i < depth; i++) {
319            mix[i].putWalledRoundRoomCarvers(count);
320        }
321    }
322
323    /**
324     * This generates a new map by stretching a 32x32x(multiple of 8) grid of potential rooms to fit the width, height,
325     * and depth passed to the constructor, randomly expanding columns and rows before contracting the whole to fit
326     * perfectly. This uses the Moore Curve, a space-filling curve that loops around on itself, to guarantee that the
327     * rooms will always have a long path through the dungeon, going up and down as well as north/south/east/west, that,
328     * if followed completely, will take you back to your starting room. Some small branches are possible, and large
329     * rooms may merge with other rooms nearby. This uses MixedGenerator.
330     * @see MixedGenerator
331     * @return a char[][][] where the outermost array is layers, then inside that are x and y in order (z x y)
332     */
333    public char[][][] generate()
334    {
335        char[][][] dungeon = new char[depth][][];
336        short[][] floors = new short[depth][];
337        int dlimit = (height + width) / 3;
338        for (int i = 0; i < depth; i++) {
339            dungeon[i] = mix[i].generate();
340            floors[i] = CoordPacker.pack(dungeon[i], '.');
341        }
342        //using actual dungeon space per layer, not row/column 3D grid space
343        ArrayList<LinkedHashSet<Coord>> ups = new ArrayList<>(depth),
344                downs = new ArrayList<>(depth);
345        for (int i = 0; i < depth; i++) {
346            ups.add(new LinkedHashSet<Coord>(40));
347            downs.add(new LinkedHashSet<Coord>(40));
348            LinkedHashSet<Coord> above = null;
349            if (i > 0) {
350                above = new LinkedHashSet<>(linksDown.get(i - 1));
351                if(above.size() == 0)
352                    continue;
353                Coord higher = random.getRandomElement(above.toArray(new Coord[above.size()]));
354                while(above.size() > 0)
355                {
356                    short[] nearAbove = CoordPacker.flood(floors[i - 1],
357                            CoordPacker.packOne(columns[higher.x], rows[higher.y]),
358                            dlimit);
359                    short[] near = CoordPacker.intersectPacked(nearAbove, CoordPacker.flood(floors[i],
360                            CoordPacker.packOne(columns[higher.x], rows[higher.y]),
361                            dlimit));
362                    ArrayList<Coord> subLinks = CoordPacker.randomPortion(near, 1, random);
363                    ups.get(i).addAll(subLinks);
364                    downs.get(i-1).addAll(subLinks);
365                    for(Coord abv : linksDown.get(i-1))
366                    {
367                        if(CoordPacker.queryPacked(nearAbove, columns[abv.x], rows[abv.y])) //scannedAbove[columns[abv.x]][rows[abv.y]] <= dlimit
368                            above.remove(abv);
369                    }
370                    if(above.isEmpty())
371                        break;
372                    higher = random.getRandomElement(above.toArray(new Coord[above.size()]));
373                }
374            }
375        }
376
377        for (int i = 0; i < depth; i++) {
378            LinkedHashMap<Coord, Integer> used = new LinkedHashMap<>(128);
379            for(Coord up : ups.get(i))
380            {
381                Integer count = used.get(up);
382                if(count != null && count > 1)
383                    continue;
384                dungeon[i][up.x][up.y] = '<';
385
386                used.put(up, (count == null) ? 1 : count + 1);
387            }
388            used.clear();
389            for(Coord down : downs.get(i))
390            {
391                Integer count = used.get(down);
392                if(count != null && count > 1)
393                    continue;
394                dungeon[i][down.x][down.y] = '>';
395
396                used.put(down, (count == null) ? 1 : count + 1);
397            }
398        }
399        return dungeon;
400    }
401
402    /**
403     * Gets an array (length equals depth) of 2D int arrays representing the environments for levels.
404     * @return an array of 2D int arrays, where each 2D array is a level's environment
405     */
406    public int[][][] getEnvironments()
407    {
408        int[][][] env = new int[depth][][];
409        for (int i = 0; i < depth; i++) {
410            env[i] = mix[i].getEnvironment();
411        }
412        return env;
413    }
414
415    /**
416     * Gets a 2D int array representing the environment for the requested level.
417     * @param level the level to get from the generated dungeon; will be clamped between 0 and depth - 1
418     * @return a 2D int array representing the requested level's environment
419     */
420    public int[][] getEnvironment(int level)
421    {
422        return mix[Math.max(0, Math.min(depth - 1, level))].getEnvironment();
423    }
424}