001package squidpony.squidgrid.mapping;
002
003import squidpony.squidmath.Coord;
004import squidpony.squidmath.CoordPacker;
005import squidpony.squidmath.DDALine;
006import squidpony.squidmath.RNG;
007
008import java.util.ArrayList;
009import java.util.LinkedHashMap;
010import java.util.List;
011
012/**
013 * Generate dungeons with between 1 and 3 primary "lanes" going from the upper left "base" to the bottom right "base"
014 * (and vice versa, since this is symmetrical). Also fills the area not covered by lanes with "jungle" (random, but
015 * symmetrical, room or cave connections). Dungeons are produced by MixedGenerator, like those SerpentMapGenerator
016 * makes, but include the wide lanes going from corner to corner. You can call different methods like putCaveCarvers(),
017 * putBoxRoomCarvers(), putWalledRoundRoomCarvers(), etc. to affect the "jungle", which defaults to caves unless one or
018 * more of the putXXXCarvers methods was called. The lanes are always 5 floor cells wide, measured 8-way. This supports
019 * the getEnvironment() method, which can be used in conjunction with RoomFinder to find where separate room, corridor,
020 * and cave areas have been placed.
021 * <br>
022 * A preview can be seen here https://gist.github.com/tommyettinger/4f57cff23eead11b17bf , with dungeons created with
023 * one, two, and three lanes, and only using box-shaped rooms for "jungle." Currently, the two-lane dungeon seems to be
024 * ideal for maps that aren't incredibly large; the samples are 80x80, but larger maps may have better jungle layout
025 * with three lanes than those three-lane maps can manage on smaller sizes. Another potential advantage of the two-lane
026 * approach is that it can be used to generate a "ring" of wide paths around a central "core" of jungle, which wasn't
027 * originally intended as a use of this generator but could be very useful for games that, for instance, want guards
028 * patrolling an obvious ring, while the player, monsters, and/or other prisoners start in the jungle.
029 * Created by Tommy Ettinger on 10/24/2015.
030 */
031public class LanesMapGenerator {
032    protected SymmetryDungeonGenerator mix;
033    protected int[] columns, rows;
034    protected RNG random;
035    protected int lanes;
036    /**
037     * This prepares a map generator that will generate a map with the given width and height, using the given RNG.
038     * The dungeon will have the specified number of wide lanes going from upper left to lower right, possibly taking a
039     * longer path to approach the other corners.  You call the different carver-adding methods to affect what the
040     * non-lane portion of the dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(),
041     * defaulting to only caves if none are called. You call generate() after adding carvers, which returns a char[][]
042     * for a map.
043     * @param width the width of the final map in cells
044     * @param height the height of the final map in cells
045     * @param rng an RNG object to use for random choices; this make a lot of random choices.
046     * @param lanes between 1 and 3; the number of wide paths to generate going from upper left to lower right.
047     * @see MixedGenerator
048     */
049    public LanesMapGenerator(int width, int height, RNG rng, int lanes)
050    {
051        if(width <= 8 || height <= 8)
052            throw new IllegalArgumentException("width and height must be greater than 8");
053        this.lanes = (lanes < 1 || lanes > 3) ? 1 : lanes;
054        random = rng;
055        /*
056        long columnAlterations = random.nextLong();
057        float columnBase = width / (Long.bitCount(columnAlterations) + 16.0f);
058        long rowAlterations = random.nextLong();
059        float rowBase = height / (Long.bitCount(rowAlterations) + 16.0f);
060
061        columns = new int[32];
062        rows = new int[32];
063        int csum = 0, rsum = 0;
064        long b = 3;
065        for (int i = 0; i < 32; i++, b <<= 2) {
066            columns[i] = csum + (int)(columnBase * 0.5f * (1 + Long.bitCount(columnAlterations & b)));
067            csum += (int)(columnBase * (1 + Long.bitCount(columnAlterations & b)));
068            rows[i] = rsum + (int)(rowBase * 0.5f * (1 + Long.bitCount(rowAlterations & b)));
069            rsum += (int)(rowBase * (1 + Long.bitCount(rowAlterations & b)));
070        }
071        int cs = (width - csum);
072        int rs = (height - rsum);
073        int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs;
074        for (int i = 15; i >= 0; i--) {
075            cs2= cs2 * i / 15;
076            rs2 = rs2 * i / 15;
077            columns[i] -= cs2;
078            rows[i] -= rs2;
079        }
080        for (int i = 15; i >= 16; i--) {
081            cs3 = cs3 * (i - 16) / 16;
082            rs3 = rs3 * (i - 16) / 16;
083            columns[i] += cs3;
084            rows[i] += rs3;
085        }
086        */
087        long columnAlterations = random.nextLong(0x1000000000000L);
088        float columnBase = width / (Long.bitCount(columnAlterations) + 48.0f);
089        long rowAlterations = random.nextLong(0x1000000000000L);
090        float rowBase = height / (Long.bitCount(rowAlterations) + 48.0f);
091
092        columns = new int[16];
093        rows = new int[16];
094        int csum = 0, rsum = 0;
095        long b = 7;
096        for (int i = 0; i < 16; i++, b <<= 3) {
097            columns[i] = csum + (int)(columnBase * 0.5f * (3 + Long.bitCount(columnAlterations & b)));
098            csum += (int)(columnBase * (3 + Long.bitCount(columnAlterations & b)));
099            rows[i] = rsum + (int)(rowBase * 0.5f * (3 + Long.bitCount(rowAlterations & b)));
100            rsum += (int)(rowBase * (3 + Long.bitCount(rowAlterations & b)));
101        }
102        int cs = (width - csum);
103        int rs = (height - rsum);
104        int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs;
105        for (int i = 0; i <= 7; i++) {
106            cs2= cs2 * i / 7;
107            rs2 = rs2 * i / 7;
108            columns[i] -= cs2;
109            rows[i] -= rs2;
110        }
111        for (int i = 15; i >= 8; i--) {
112            cs3 = cs3 * (i - 8) / 8;
113            rs3 = rs3 * (i - 8) / 8;
114            columns[i] += cs3;
115            rows[i] += rs3;
116        }
117
118
119        LinkedHashMap<Coord, List<Coord>> connections = new LinkedHashMap<>(80);
120        Coord temp, t;
121        int m = random.nextInt(32), r = random.between(8, 24);
122        temp = CoordPacker.hilbertToCoord(m);
123        Coord starter = CoordPacker.hilbertToCoord(m);
124        m += r;
125        for (int i = r; i < 256 && m < 256 - 9; i += r, m += r) {
126            List<Coord> cl = new ArrayList<>(4);
127            cl.add(Coord.get(columns[temp.x], rows[temp.y]));
128            temp = CoordPacker.hilbertToCoord(m);
129            r = random.between(8, 24);
130            for (int j = 0, p = r - 1;
131                 j < 3 && p > 2 && Math.min(random.nextDouble(), random.nextDouble()) < 0.2;
132                 j++, p -= random.between(1, p)) {
133                t = CoordPacker.hilbertToCoord(m + p);
134                cl.add(Coord.get(columns[t.x], rows[t.y]));
135            }
136            connections.put(Coord.get(columns[temp.x], rows[temp.y]), cl);
137        }
138        connections.get(Coord.get(columns[temp.x], rows[temp.y])).add(
139                Coord.get(columns[starter.x], rows[starter.y]));
140        mix = new SymmetryDungeonGenerator(width, height, random, connections, 0.6f);
141        boolean[][] fixed = new boolean[width][height];
142
143        if(lanes != 2)
144        {
145            List<Coord> path = DDALine.line(3, 3, width - 4, height - 4);
146            for(Coord c : path)
147            {
148                for (int x = c.x - 2; x <= c.x + 2; x++) {
149                    for (int y = c.y - 2; y <= c.y + 2; y++) {
150                        fixed[x][y] = true;
151                    }
152                }
153            }
154        }
155        if(lanes > 1)
156        {
157            List<Coord> path = DDALine.line(3, 3, 3, height - 4);
158            path.addAll(DDALine.line(3, 3, width - 4, 3));
159            for(Coord c : path)
160            {
161                for (int x = c.x - 2; x <= c.x + 2; x++) {
162                    for (int y = c.y - 2; y <= c.y + 2; y++) {
163                        fixed[x][y] = true;
164                    }
165                }
166            }
167        }
168        mix.setFixedRooms(fixed);
169    }
170
171
172    /**
173     * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves
174     * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make
175     * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically
176     * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10
177     * between the count of putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers() is reasonable.
178     * @see MixedGenerator
179     * @param count the number of carvers making caves between rooms; only matters in relation to other carvers
180     */
181    public void putCaveCarvers(int count)
182    {
183        mix.putCaveCarvers(count);
184    }
185    /**
186     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
187     * 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
188     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
189     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
190     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
191     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
192     * and putRoundRoomCarvers() is reasonable.
193     * @see MixedGenerator
194     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
195     *              to other carvers
196     */
197    public void putBoxRoomCarvers(int count)
198    {
199        mix.putBoxRoomCarvers(count);
200    }
201    /**
202     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
203     * 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
204     * ensures walls will be placed around the room, only allowing corridors and small cave openings to pass. If count
205     * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher
206     * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then
207     * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
208     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
209     * and putRoundRoomCarvers() is reasonable.
210     * @see MixedGenerator
211     * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation
212     *              to other carvers
213     */
214    public void putWalledBoxRoomCarvers(int count)
215    {
216        mix.putWalledBoxRoomCarvers(count);
217    }
218    /**
219     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
220     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
221     * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
222     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
223     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
224     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
225     * and putRoundRoomCarvers() is reasonable.
226     * @see MixedGenerator
227     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
228     *              to other carvers
229     */
230    public void putRoundRoomCarvers(int count)
231    {
232        mix.putRoundRoomCarvers(count);
233    }
234
235    /**
236     * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms
237     * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is
238     * one. This also ensures walls will be placed around the room, only allowing corridors and small cave openings to
239     * pass. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible,
240     * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used,
241     * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver
242     * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(),
243     * and putRoundRoomCarvers() is reasonable.
244     * @see MixedGenerator
245     * @param count the number of carvers making circular rooms and corridors between them; only matters in relation
246     *              to other carvers
247     */
248    public void putWalledRoundRoomCarvers(int count)
249    {
250        mix.putWalledRoundRoomCarvers(count);
251    }
252
253    /**
254     * This generates a new map by stretching a 16x16 grid of potential rooms to fit the width and height passed to the
255     * constructor, randomly expanding columns and rows before contracting the whole to fit perfectly. This uses the
256     * Moore Curve, a space-filling curve that loops around on itself, to guarantee that the rooms will always have a
257     * long path through the dungeon that, if followed completely, will take you back to your starting room. Some small
258     * branches are possible, and large rooms may merge with other rooms nearby. This uses MixedGenerator.
259     * @see MixedGenerator
260     * @return a char[][] where '#' is a wall and '.' is a floor or corridor; x first y second
261     */
262    public char[][] generate()
263    {
264        return mix.generate();
265    }
266
267    /**
268     * Gets a 2D array of int constants, each representing a type of environment corresponding to a static field of
269     * MixedGenerator. This array will have the same size as the last char 2D array prduced by generate(), and the value
270     * of this method if called before generate() is undefined, but probably will be a 2D array of all 0 (UNTOUCHED).
271     * <ul>
272     *     <li>MixedGenerator.UNTOUCHED, equal to 0, is used for any cells that aren't near a floor.</li>
273     *     <li>MixedGenerator.ROOM_FLOOR, equal to 1, is used for floor cells inside wide room areas.</li>
274     *     <li>MixedGenerator.ROOM_WALL, equal to 2, is used for wall cells around wide room areas.</li>
275     *     <li>MixedGenerator.CAVE_FLOOR, equal to 3, is used for floor cells inside rough cave areas.</li>
276     *     <li>MixedGenerator.CAVE_WALL, equal to 4, is used for wall cells around rough cave areas.</li>
277     *     <li>MixedGenerator.CORRIDOR_FLOOR, equal to 5, is used for floor cells inside narrow corridor areas.</li>
278     *     <li>MixedGenerator.CORRIDOR_WALL, equal to 6, is used for wall cells around narrow corridor areas.</li>
279     * </ul>
280     * @return a 2D int array where each element is an environment type constant in MixedGenerator
281     */
282    public int[][] getEnvironment()
283    {
284        return mix.getEnvironment();
285    }
286}