001package squidpony.squidgrid.mapping;
002
003import squidpony.GwtCompatibility;
004import squidpony.annotation.Beta;
005import squidpony.squidmath.*;
006
007import java.util.*;
008
009/**
010 * Generator for maps of high-tech areas like space stations or starships, with repeated modules laid out in random ways.
011 * Different from traditional fantasy dungeon generation in that it should seem generally less chaotic in how it's laid
012 * out, and repeated elements with minor tweaks should be especially common. May also be useful in fantasy games for
013 * regimented areas built by well-organized military forces.
014 * <br>
015 * Preview: https://gist.github.com/tommyettinger/c711f8fc83fa9919245d88092444bf7f
016 * Created by Tommy Ettinger on 4/2/2016.
017 */
018@Beta
019public class ModularMapGenerator {
020    public DungeonUtility utility;
021    protected int height, width;
022    public StatefulRNG rng;
023    protected long rebuildSeed;
024    protected boolean seedFixed = false;
025
026    protected char[][] map = null;
027    protected int[][] environment = null;
028    //public RegionMap<MapModule> layout, modules, inverseModules;
029    public RegionMap<MapModule> layout;
030    public LinkedHashMap<Integer, ArrayList<MapModule>> modules;
031    public LinkedHashMap<Coord, MapModule> displacement;
032
033    private void putModule(short[] module) {
034        char[][] unp = CoordPacker.unpackChar(module, '.', '#');
035        MapModule mm = new MapModule(GwtCompatibility.insert2D(unp,
036                GwtCompatibility.fill2D('#', unp.length + 2, unp[0].length + 2), 1, 1));
037        //short[] b = CoordPacker.rectangle(1 + mm.max.x, 1 + mm.max.y);
038        //modules.put(b, mm);
039        //inverseModules.put(CoordPacker.negatePacked(b), mm);
040        ArrayList<MapModule> mms = modules.get(mm.category);
041        if (mms == null) {
042            mms = new ArrayList<>(16);
043            mms.add(mm);
044            modules.put(mm.category, mms);
045        } else
046            mms.add(mm);
047    }
048
049    private void putRectangle(int width, int height, float multiplier) {
050        putModule(CoordPacker.rectangle(Math.round(width * multiplier), Math.round(height * multiplier)));
051    }
052
053    private void putCircle(int radius, float multiplier) {
054        putModule(CoordPacker.circle(Coord.get(Math.round(radius * multiplier + 1), Math.round(radius * multiplier + 1)),
055                Math.round(radius * multiplier),
056                Math.round((radius + 1) * 2 * multiplier + 1), Math.round((radius + 1) * 2 * multiplier + 1)));
057    }
058
059    private void initModules() {
060        layout = new RegionMap<>(64);
061        //modules = new RegionMap<>(64);
062        //inverseModules = new RegionMap<>(64);
063        modules = new LinkedHashMap<>(64);
064        for (int i = 1; i <= 64; i <<= 1) {
065            ArrayList<MapModule> mms = new ArrayList<>(16);
066            modules.put(i, mms);
067        }
068        displacement = new LinkedHashMap<>(64);
069        float multiplier = 1;//(float) Math.sqrt(Math.max(1f, Math.min(width, height) / 24f));
070        putRectangle(2, 2, multiplier);
071        putRectangle(3, 3, multiplier);
072        putRectangle(4, 4, multiplier);
073        putRectangle(4, 2, multiplier);
074        putRectangle(2, 4, multiplier);
075        putRectangle(6, 6, multiplier);
076        putRectangle(6, 3, multiplier);
077        putRectangle(3, 6, multiplier);
078        putCircle(2, multiplier);
079
080        putRectangle(8, 8, multiplier);
081        putRectangle(6, 12, multiplier);
082        putRectangle(12, 6, multiplier);
083        putCircle(4, multiplier);
084
085        putRectangle(14, 14, multiplier);
086        putRectangle(9, 18, multiplier);
087        putRectangle(18, 9, multiplier);
088        putRectangle(14, 18, multiplier);
089        putRectangle(18, 14, multiplier);
090        putCircle(7, multiplier);
091    }
092
093    /**
094     * Make a ModularMapGenerator with a StatefulRNG (backed by LightRNG) using a random seed, height 30, and width 60.
095     */
096    public ModularMapGenerator() {
097        this(60, 30);
098    }
099
100    /**
101     * Make a ModularMapGenerator with the given height and width; the RNG used for generating a dungeon and
102     * adding features will be a StatefulRNG (backed by LightRNG) using a random seed.
103     *
104     * @param width  The width of the dungeon in cells
105     * @param height The height of the dungeon in cells
106     */
107    public ModularMapGenerator(int width, int height) {
108        this(width, height, new StatefulRNG());
109    }
110
111    /**
112     * Make a ModularMapGenerator with the given height, width, and RNG. Use this if you want to seed the RNG.
113     *
114     * @param width  The width of the dungeon in cells
115     * @param height The height of the dungeon in cells
116     * @param rng    The RNG to use for all purposes in this class; if it is a StatefulRNG, then it will be used as-is,
117     *               but if it is not a StatefulRNG, a new StatefulRNG will be used, randomly seeded by this parameter
118     */
119    public ModularMapGenerator(int width, int height, RNG rng) {
120        this.rng = (rng instanceof StatefulRNG) ? (StatefulRNG) rng : new StatefulRNG(rng.nextLong());
121        utility = new DungeonUtility(this.rng);
122        rebuildSeed = this.rng.getState();
123        this.height = height;
124        this.width = width;
125        map = new char[width][height];
126        environment = new int[width][height];
127        for (int x = 0; x < this.width; x++) {
128            Arrays.fill(map[x], '#');
129        }
130        initModules();
131    }
132
133    /**
134     * Copies all fields from copying and makes a new DungeonGenerator.
135     *
136     * @param copying the DungeonGenerator to copy
137     */
138    public ModularMapGenerator(ModularMapGenerator copying) {
139        rng = new StatefulRNG(copying.rng.getState());
140        utility = new DungeonUtility(rng);
141        rebuildSeed = rng.getState();
142        height = copying.height;
143        width = copying.width;
144        map = GwtCompatibility.copy2D(copying.map);
145        environment = GwtCompatibility.copy2D(copying.environment);
146        layout = new RegionMap<>(copying.layout);
147        modules = new LinkedHashMap<>(copying.modules);
148    }
149
150    /**
151     * Get the most recently generated char[][] map out of this class. The
152     * map may be null if generate() or setMap() have not been called.
153     *
154     * @return a char[][] map, or null.
155     */
156    public char[][] getMap() {
157        return map;
158    }
159
160    /**
161     * Get the most recently generated char[][] map out of this class without any chars other than '#' or '.', for
162     * walls and floors respectively. The map may be null if generate() or setMap() have not been called.
163     *
164     * @return a char[][] map with only '#' for walls and '.' for floors, or null.
165     */
166    public char[][] getBareMap() {
167        return DungeonUtility.simplifyDungeon(map);
168    }
169
170    public char[][] generate() {
171        MapModule mm, mm2;
172        int xPos, yPos, categorySize = 32, alteredSize = (categorySize * 3) >>> 1, bits = 5, ctr;
173        Coord[][] grid = new Coord[1][1];
174        // find biggest category and drop down as many modules as we can fit
175        for (; categorySize >= 4; categorySize >>= 1, alteredSize = (categorySize * 3) >>> 1, bits--) {
176            if (width / alteredSize <= 0 || height / alteredSize <= 0)
177                continue;
178            grid = new Coord[width / alteredSize][height / alteredSize];
179            ctr = 0;
180            for (int xLimit = alteredSize - 1, x = 0; xLimit < width; xLimit += alteredSize, x += alteredSize) {
181                for (int yLimit = alteredSize - 1, y = 0; yLimit < height; yLimit += alteredSize, y += alteredSize) {
182                    if (layout.allAt(x + alteredSize / 2, y + alteredSize / 2).isEmpty()) // && (bits <= 3 || rng.nextInt(5) < bits)
183                    {
184                        if (rng.between(2, grid.length * grid[0].length + 3) == ctr++)
185                            continue;
186                        mm = rng.getRandomElement(modules.get(categorySize));
187                        if (mm == null) break;
188                        mm = mm.rotate(rng.nextInt(4));
189                        xPos = rng.nextInt(3) << (bits - 2);
190                        yPos = rng.nextInt(3) << (bits - 2);
191                        for (int px = 0; px <= mm.max.x; px++) {
192                            System.arraycopy(mm.map[px], 0, map[px + x + xPos], y + yPos, mm.max.y + 1);
193                            System.arraycopy(mm.environment[px], 0, environment[px + x + xPos], y + yPos, mm.max.y + 1);
194                        }
195                        layout.put(CoordPacker.rectangle(x + xPos, y + yPos, categorySize, categorySize), mm);
196                        displacement.put(Coord.get(x + xPos, y + yPos), mm);
197                        grid[x / alteredSize][y / alteredSize] = Coord.get(x + xPos, y + yPos);
198                    }
199                }
200            }
201            if (layout.size > 0)
202                break;
203        }
204        Coord a, b;
205        int gw = grid.length;
206        if (gw > 0) {
207            int gh = grid[0].length;
208            for (int w = 0; w < gw; w++) {
209                for (int h = 0; h < gh; h++) {
210                    a = grid[w][h];
211                    if (a == null)
212                        continue;
213                    int connectors = rng.nextInt(16) | rng.nextInt(16);
214                    if ((connectors & 1) == 1 && w > 0 && grid[w - 1][h] != null) {
215                        b = grid[w - 1][h];
216                        connectLeftRight(displacement.get(b), b.x, b.y, displacement.get(a), a.x, a.y);
217                    }
218                    if ((connectors & 2) == 2 && w < gw - 1 && grid[w + 1][h] != null) {
219                        b = grid[w + 1][h];
220                        connectLeftRight(displacement.get(a), a.x, a.y, displacement.get(b), b.x, b.y);
221                    }
222                    if ((connectors & 4) == 4 && h > 0 && grid[w][h - 1] != null) {
223                        b = grid[w][h - 1];
224                        connectTopBottom(displacement.get(b), b.x, b.y, displacement.get(a), a.x, a.y);
225                    }
226                    if ((connectors & 8) == 8 && h < gh - 1 && grid[w][h + 1] != null) {
227                        b = grid[w][h + 1];
228                        connectTopBottom(displacement.get(a), a.x, a.y, displacement.get(b), b.x, b.y);
229                    }
230                }
231            }
232        }
233        Coord begin;
234        short[] packed;
235        for (Map.Entry<Coord, MapModule> dmm : displacement.entrySet()) {
236            begin = dmm.getKey();
237            mm = dmm.getValue();
238            //int newCat = mm.category;
239            //if(newCat >= 16) newCat >>>= 1;
240            //if(newCat >= 8) newCat >>>= 1;
241            //mm2 = rng.getRandomElement(modules.get(newCat));
242            int shiftsX = begin.x - (mm.category * 3 / 2) * ((begin.x * 2) / (3 * mm.category)),
243                    shiftsY = begin.y - (mm.category * 3 / 2) * ((begin.y * 2) / (3 * mm.category)),
244                    leftSize = Integer.highestOneBit(shiftsX),
245                    rightSize = Integer.highestOneBit((mm.category >>> 1) - shiftsX),
246                    topSize = Integer.highestOneBit(shiftsY),
247                    bottomSize = Integer.highestOneBit((mm.category >>> 1) - shiftsY);
248            if (leftSize >= 4 && !mm.leftDoors.isEmpty()) {
249                mm2 = rng.getRandomElement(modules.get(leftSize));
250                if (mm2 == null) continue;
251                if (mm2.rightDoors.isEmpty()) {
252                    if (!mm2.topDoors.isEmpty())
253                        mm2 = mm2.rotate(1);
254                    else if (!mm2.leftDoors.isEmpty())
255                        mm2 = mm2.flip(true, false);
256                    else if (!mm2.bottomDoors.isEmpty())
257                        mm2 = mm2.rotate(3);
258                    else continue;
259                }
260                for (int i = 0; i < 4; i++) {
261                    packed = CoordPacker.rectangle(begin.x - shiftsX, begin.y + i * mm.category / 4, leftSize, leftSize);
262                    if (layout.containsRegion(packed))
263                        continue;
264                    for (int px = 0; px <= mm2.max.x; px++) {
265                        System.arraycopy(mm2.map[px], 0, map[px + begin.x - shiftsX], begin.y + i * mm.category / 4, mm2.max.y + 1);
266                        System.arraycopy(mm2.environment[px], 0, environment[px + begin.x - shiftsX], begin.y + i * mm.category / 4, mm2.max.y + 1);
267                    }
268                    layout.put(packed, mm2);
269                    connectLeftRight(mm2, begin.x - shiftsX, begin.y + i * mm.category / 4, mm, begin.x, begin.y);
270                }
271            }
272            if (rightSize >= 4 && !mm.rightDoors.isEmpty()) {
273                mm2 = rng.getRandomElement(modules.get(rightSize));
274                if (mm2 == null) continue;
275                if (mm2.leftDoors.isEmpty()) {
276                    if (!mm2.bottomDoors.isEmpty())
277                        mm2 = mm2.rotate(1);
278                    else if (!mm2.rightDoors.isEmpty())
279                        mm2 = mm2.flip(true, false);
280                    else if (!mm2.topDoors.isEmpty())
281                        mm2 = mm2.rotate(3);
282                    else continue;
283                }
284                for (int i = 0; i < 4; i++) {
285                    packed = CoordPacker.rectangle(begin.x + mm.category, begin.y + i * mm.category / 4, rightSize, rightSize);
286                    if (layout.containsRegion(packed))
287                        continue;
288                    for (int px = 0; px <= mm2.max.x; px++) {
289                        System.arraycopy(mm2.map[px], 0, map[px + begin.x + mm.category], begin.y + i * mm.category / 4, mm2.max.y + 1);
290                        System.arraycopy(mm2.environment[px], 0, environment[px + begin.x + mm.category], begin.y + i * mm.category / 4, mm2.max.y + 1);
291                    }
292                    layout.put(packed, mm2);
293                    connectLeftRight(mm, begin.x, begin.y, mm2, begin.x + mm.category, begin.y + i * mm.category / 4);
294                }
295            }
296            if (topSize >= 4 && !mm.topDoors.isEmpty()) {
297                mm2 = rng.getRandomElement(modules.get(topSize));
298                if (mm2 == null) continue;
299                if (mm2.bottomDoors.isEmpty()) {
300                    if (!mm2.leftDoors.isEmpty())
301                        mm2 = mm2.rotate(3);
302                    else if (!mm2.topDoors.isEmpty())
303                        mm2 = mm2.flip(false, true);
304                    else if (!mm2.rightDoors.isEmpty())
305                        mm2 = mm2.rotate(1);
306                    else continue;
307                }
308                for (int i = 0; i < 4; i++) {
309                    packed = CoordPacker.rectangle(begin.x + i * mm.category / 4, begin.y - shiftsY, topSize, topSize);
310                    if (layout.containsRegion(packed))
311                        continue;
312                    for (int px = 0; px <= mm2.max.x; px++) {
313                        System.arraycopy(mm2.map[px], 0, map[px + begin.x + i * mm.category / 4], begin.y - shiftsY, mm2.max.y + 1);
314                        System.arraycopy(mm2.environment[px], 0, environment[px + begin.x + i * mm.category / 4], begin.y - shiftsY, mm2.max.y + 1);
315                    }
316                    layout.put(packed, mm2);
317                    connectTopBottom(mm2, begin.x + i * mm.category / 4, begin.y - shiftsY, mm, begin.x, begin.y);
318                }
319            }
320            if (bottomSize >= 4 && !mm.bottomDoors.isEmpty()) {
321                mm2 = rng.getRandomElement(modules.get(bottomSize));
322                if (mm2 == null) continue;
323                if (mm2.topDoors.isEmpty()) {
324                    if (!mm2.rightDoors.isEmpty())
325                        mm2 = mm2.rotate(1);
326                    else if (!mm2.topDoors.isEmpty())
327                        mm2 = mm2.flip(false, true);
328                    else if (!mm2.leftDoors.isEmpty())
329                        mm2 = mm2.rotate(3);
330                    else continue;
331                }
332                for (int i = 0; i < 4; i++) {
333                    packed = CoordPacker.rectangle(begin.x + i * mm.category / 4, begin.y + mm.category, bottomSize, bottomSize);
334                    if (layout.containsRegion(packed))
335                        continue;
336                    for (int px = 0; px <= mm2.max.x; px++) {
337                        System.arraycopy(mm2.map[px], 0, map[px + begin.x + i * mm.category / 4], begin.y + mm.category, mm2.max.y + 1);
338                        System.arraycopy(mm2.environment[px], 0, environment[px + begin.x + i * mm.category / 4], begin.y + mm.category, mm2.max.y + 1);
339                    }
340                    layout.put(packed, mm2);
341                    connectTopBottom(mm, begin.x, begin.y, mm2, begin.x + i * mm.category / 4, begin.y + mm.category);
342                }
343            }
344        }
345        return map;
346    }
347
348    /**
349     * Change the underlying char[][]; only affects the toString method, and of course getMap
350     *
351     * @param map a char[][], probably produced by an earlier call to this class and then modified.
352     */
353    public void setMap(char[][] map) {
354        this.map = map;
355        if (map == null) {
356            width = 0;
357            height = 0;
358            return;
359        }
360        width = map.length;
361        if (width > 0)
362            height = map[0].length;
363    }
364
365    /**
366     * Height of the map in cells.
367     *
368     * @return Height of the map in cells.
369     */
370    public int getHeight() {
371        return height;
372    }
373
374    /**
375     * Width of the map in cells.
376     *
377     * @return Width of the map in cells.
378     */
379    public int getWidth() {
380        return width;
381    }
382
383    /**
384     * Gets the environment int 2D array for use with classes like RoomFinder.
385     *
386     * @return the environment int 2D array
387     */
388    public int[][] getEnvironment() {
389        return environment;
390    }
391
392    /**
393     * Sets the environment int 2D array.
394     *
395     * @param environment a 2D array of int, where each int corresponds to a constant in MixedGenerator.
396     */
397    public void setEnvironment(int[][] environment) {
398        this.environment = environment;
399    }
400
401    private void connectLeftRight(MapModule left, int leftX, int leftY, MapModule right, int rightX, int rightY) {
402        if (left.rightDoors == null || left.rightDoors.isEmpty()
403                || right.leftDoors == null || right.leftDoors.isEmpty())
404            return;
405        List<Coord> line = new ArrayList<>(1), temp;
406        int best = 1024;
407        Coord tl, tr, twl, twr, wl = null, wr = null;
408        for (Coord l : left.rightDoors) {
409            tl = twl = l.translate(leftX, leftY);
410            if (tl.x > 0 && tl.x < width - 1 && map[tl.x - 1][tl.y] != '#')
411                tl = Coord.get(tl.x + 1, tl.y);
412            else if (tl.x > 0 && tl.x < width - 1 && map[tl.x + 1][tl.y] != '#')
413                tl = Coord.get(tl.x - 1, tl.y);
414            else if (tl.y > 0 && tl.y < height - 1 && map[tl.x][tl.y - 1] != '#')
415                tl = Coord.get(tl.x, tl.y + 1);
416            else if (tl.y > 0 && tl.y < height - 1 && map[tl.x][tl.y + 1] != '#')
417                tl = Coord.get(tl.x, tl.y - 1);
418            else
419                continue;
420
421            for (Coord r : right.leftDoors) {
422                tr = twr = r.translate(rightX, rightY);
423                if (tr.x > 0 && tr.x < width - 1 && map[tr.x - 1][tr.y] != '#')
424                    tr = Coord.get(tr.x + 1, tr.y);
425                else if (tr.x > 0 && tr.x < width - 1 && map[tr.x + 1][tr.y] != '#')
426                    tr = Coord.get(tr.x - 1, tr.y);
427                else if (tr.y > 0 && tr.y < height - 1 && map[tr.x][tr.y - 1] != '#')
428                    tr = Coord.get(tr.x, tr.y + 1);
429                else if (tr.y > 0 && tr.y < height - 1 && map[tr.x][tr.y + 1] != '#')
430                    tr = Coord.get(tr.x, tr.y - 1);
431                else
432                    continue;
433                temp = OrthoLine.line(tl, tr);
434                if (temp.size() < best) {
435                    line = temp;
436                    best = line.size();
437                    wl = twl;
438                    wr = twr;
439                }
440            }
441        }
442        temp = new ArrayList<>(line.size());
443        for (Coord c : line) {
444            if (map[c.x][c.y] == '#') {
445                map[c.x][c.y] = '.';
446                environment[c.x][c.y] = MixedGenerator.CORRIDOR_FLOOR;
447                temp.add(c);
448            }
449        }
450        if (wl != null && map[wl.x][wl.y] == '#') {
451            //if(line.isEmpty())
452            map[wl.x][wl.y] = '.';
453            environment[wl.x][wl.y] = MixedGenerator.ROOM_FLOOR;
454            //else
455            //    map[wl.x][wl.y] = '+';
456        }
457        if (wr != null && map[wr.x][wr.y] == '#') {
458            //if(line.isEmpty())
459            map[wr.x][wr.y] = '.';
460            environment[wr.x][wr.y] = MixedGenerator.ROOM_FLOOR;
461            //else
462            //    map[wr.x][wr.y] = '+';
463        }
464        layout.put(CoordPacker.packSeveral(temp), null);
465
466    }
467
468    private void connectTopBottom(MapModule top, int topX, int topY, MapModule bottom, int bottomX, int bottomY) {
469        if (top.bottomDoors == null || top.bottomDoors.isEmpty()
470                || bottom.topDoors == null || bottom.topDoors.isEmpty())
471            return;
472        List<Coord> line = new ArrayList<>(1), temp;
473        int best = 1024;
474        Coord tt, tb, twt, twb, wt = null, wb = null;
475        for (Coord l : top.bottomDoors) {
476            tt = twt = l.translate(topX, topY);
477            if (tt.y > 0 && tt.y < height - 1 && map[tt.x][tt.y - 1] != '#')
478                tt = Coord.get(tt.x, tt.y + 1);
479            else if (tt.y > 0 && tt.y < height - 1 && map[tt.x][tt.y + 1] != '#')
480                tt = Coord.get(tt.x, tt.y - 1);
481            else if (tt.x > 0 && tt.x < width - 1 && map[tt.x - 1][tt.y] != '#')
482                tt = Coord.get(tt.x + 1, tt.y);
483            else if (tt.x > 0 && tt.x < width - 1 && map[tt.x + 1][tt.y] != '#')
484                tt = Coord.get(tt.x - 1, tt.y);
485            else
486                continue;
487
488            for (Coord r : bottom.topDoors) {
489                tb = twb = r.translate(bottomX, bottomY);
490                if (tb.y > 0 && tb.y < height - 1 && map[tb.x][tb.y - 1] != '#')
491                    tb = Coord.get(tb.x, tb.y + 1);
492                else if (tb.y > 0 && tb.y < height - 1 && map[tb.x][tb.y + 1] != '#')
493                    tb = Coord.get(tb.x, tb.y - 1);
494                else if (tb.x > 0 && tb.x < width - 1 && map[tb.x - 1][tb.y] != '#')
495                    tb = Coord.get(tb.x + 1, tb.y);
496                else if (tb.x > 0 && tb.x < width - 1 && map[tb.x + 1][tb.y] != '#')
497                    tb = Coord.get(tb.x - 1, tb.y);
498                else
499                    continue;
500                temp = OrthoLine.line(tt, tb);
501                if (temp.size() < best) {
502                    line = temp;
503                    best = line.size();
504                    wt = twt;
505                    wb = twb;
506                }
507            }
508        }
509        temp = new ArrayList<>(line.size());
510        for (Coord c : line) {
511            if (map[c.x][c.y] == '#') {
512                map[c.x][c.y] = '.';
513                environment[c.x][c.y] = MixedGenerator.CORRIDOR_FLOOR;
514                temp.add(c);
515            }
516        }
517        if (wt != null && map[wt.x][wt.y] == '#') {
518            //if(line.isEmpty())
519            map[wt.x][wt.y] = '.';
520            environment[wt.x][wt.y] = MixedGenerator.ROOM_FLOOR;
521            //else
522            //    map[wl.x][wl.y] = '+';
523
524        }
525        if (wb != null && map[wb.x][wb.y] == '#') {
526            //if(line.isEmpty())
527            map[wb.x][wb.y] = '.';
528            environment[wb.x][wb.y] = MixedGenerator.ROOM_FLOOR;
529            //else
530            //    map[wb.x][wb.y] = '+';
531        }
532        layout.put(CoordPacker.packSeveral(temp), null);
533    }
534}