001package squidpony.squidgrid.mapping;
002
003import squidpony.ArrayTools;
004
005import squidpony.squidmath.GWTRNG;
006import squidpony.squidmath.GreasedRegion;
007import squidpony.squidmath.IRNG;
008import squidpony.squidmath.IntIntOrderedMap;
009import squidpony.squidmath.IntVLA;
010
011/**
012 * A room placing algorithm developed by Rayvolution for his game Fail To Hero, this was simple to implement but
013 * delivers complex connectivity. It is meant to ensure all rooms are connected, but usually not directly, and many
014 * routes need to wind throughout the map to get to a goal.
015 * <br>
016 * <pre>{@code
017 * ┌────────────────────────────┐┌────────┐┌────────┐┌────────┐
018 * │............................││........││........││........│
019 * │............................││........││........││........│
020 * │............................││........││........││........│
021 * │...┌──────────┐...┌─────┐...││...┌┐...│└────┐...││...┌────┘
022 * │...│┌───┐┌────┘...│┌────┘...└┘...││...└────┐│...││...└────┐
023 * │...││...││........││.............││........││...││........│
024 * │...││...││........││.............││........││...││........│
025 * │...││...││........││.......<.....││........││...││........│
026 * └───┘│...││...┌────┘│...┌─────────┘└────────┘│...│└────┐...│
027 * ┌────┘...││...└────┐│...│┌───────────────────┘...└─────┘...│
028 * │........││........││...││.................................│
029 * │.......>││........││...││.................................│
030 * │........││........││...││.................................│
031 * │...┌────┘└────┐...│└───┘│...┌─────────────────────────────┘
032 * │...│┌────────┐│...└─────┘...└────┐┌───┐┌────────┐┌────────┐
033 * │...││........││..................││...││........││........│
034 * │...││........││..................││...││........││........│
035 * │...││........││..................││...││........││........│
036 * │...││...┌┐...│└────┐...┌─────────┘│...│└────┐...│└────┐...│
037 * │...││...││...└─────┘...│┌────────┐│...└────┐│...└─────┘...│
038 * │...││...││.............││........││........││.............│
039 * │...││...││.............││........││........││.............│
040 * │...││...││.............││........││........││.............│
041 * │...││...││...┌─────────┘│...┌┐...││...┌────┘│...┌─────┐...│
042 * │...└┘...││...└──────────┘...││...└┘...└─────┘...│┌────┘...│
043 * │........││..................││..................││........│
044 * │........││..................││..................││........│
045 * │........││..................││..................││........│
046 * └────────┘└──────────────────┘└──────────────────┘└────────┘
047 * }</pre>
048 * <br>
049 * <pre>{@code
050 * ┌───────────────┬─┬───────────┬─────┬───┬─────────┬─┬───┬─┐
051 * │...............│.│...........│.....│...│.........│.│...│.│
052 * │.┌──────────.┌─┘.│.┌──.────┬─┤.┌───┤.│.│.──┐.──┐.│.│.│.│.│
053 * │.│...........│.....│.......│.│.│...│.│.....│...│.│...│...│
054 * ├─┘.┌────.┌─┐.└─────┘.┌──.│.│.│.│.┌─┘.│.│.──┼───┤.└─┬─┘.│.│
055 * │...│.....│.│.........│...│.│...│.│...│.│...│...│...│...│.│
056 * │.┌─┴───┬─┘.│.┌──.┌───┤.──┤.│.┌─┤.│.┌─┴─┼─┐.│.│.└───┤.│.└─┤
057 * │.│.....│...│.│...│...│...│.│.│.│...│...│.│...│.....│.│...│
058 * ├─┤.│.│.│.──┘.│.│.└─┐.├───┤.│.│.│.──┤.│.│.│.──┤.│.│.│.└─┐.│
059 * │.│.│.│.......│.│...│.│...│.│.......│.│...│...│.│.│.│...│.│
060 * │.│.└─┼────.┌─┘.└───┘.│.│.└─┴─┬─┬──.├─┤.──┴───┼─┤.├─┴─┐.└─┤
061 * │.│...│>....│.........│.│.....│.│...│.│.......│.│.│...│...│
062 * │.└─┐.│.┌───┴────.│.│.│.└─┬───┘.│.┌─┘.├───┐.┌─┘.├─┘.│.│.│<│
063 * │...│.│.│.........│.│.....│.......│...│...│.│...│...│...│.│
064 * ├──.├─┼─┴──.│.│.┌─┘.├───┐.└──.──┬─┘.┌─┘.│.│.│.┌─┘.──┴───┤.│
065 * │...│.│.....│.│.│...│...│.......│...│...│...│.│.........│.│
066 * ├─┐.│.│.──┬─┘.├─┘.┌─┤.──┼───┐.│.│.│.└──.└───┤.│.│.┌─┐.│.│.│
067 * │.│...│...│...│...│.│...│...│.│.│.│.........│.│.│.│.│.│.│.│
068 * │.│.│.└─┬─┴─┬─┴─┬─┤.├──.│.──┘.│.│.├──────.│.│.└─┤.│.│.└─┤.│
069 * │...│...│...│...│.│.│.........│...│.......│.....│.│.│...│.│
070 * │.┌─┤.│.│.│.│.│.│.│.│.──┐.──┐.├──.└───────┴─────┘.│.├──.├─┤
071 * │.│.│.│.│.│.│.│...│.│...│...│.│...................│.│...│.│
072 * │.│.├─┘.│.│.│.├──.│.└───┴─┐.│.└───────┐.──┐.──┬─┐.│.│.──┘.│
073 * │.│.│.....│.│.│...│.......│.│.........│...│...│.│...│.....│
074 * ├─┘.│.┌──.│.└─┘.┌─┴────.│.│.├───────┐.└─┐.├──.│.└─┬─┘.┌──.│
075 * │.....│...│.....│.......│...│.......│...│.│.......│...│...│
076 * │.────┴─┐.├────.│.│.────┤.──┘.┌────.├───┘.│.┌────.├──.│.──┤
077 * │.......│.│.......│.....│.....│.....│.....│.│.....│...│...│
078 * └───────┴─┴───────┴─────┴─────┴─────┴─────┴─┴─────┴───┴───┘
079 * }</pre>
080 * <br>
081 * Created by Tommy Ettinger on 5/7/2019.
082 */
083public class ConnectingMapGenerator implements IDungeonGenerator {
084    
085    public int width;
086    public int height;
087    public int roomWidth;
088    public int roomHeight;
089    public int wallThickness;
090    public char[][] dungeon;
091    public int[][] environment;
092    public GreasedRegion region;
093    private final transient GreasedRegion tempRegion;
094    public IRNG rng;
095
096    /**
097     * Calls {@link #ConnectingMapGenerator(int, int, int, int, IRNG, int)} with width 80, height 80, roomWidth 8,
098     * roomHeight 8, a new {@link GWTRNG} for random, and wallThickness 2.
099     */
100    public ConnectingMapGenerator()
101    {
102        this(80, 80, 8, 8, new GWTRNG(), 2);
103    }
104    /**
105     * Determines room width and room height by dividing width or height by 10; wallThickness is 2. 
106     * @param width total width of the map, in cells
107     * @param height total height of the map, in cells
108     * @param random an IRNG to make random choices for connecting rooms
109     */
110
111    public ConnectingMapGenerator(int width, int height, IRNG random)
112    {
113        this(width, height, width / 10, height / 10, random, 2);
114    }
115    /**
116     * Exactly like {@link #ConnectingMapGenerator(int, int, int, int, IRNG, int)} with wallThickness 2.
117     * @param width total width of the map, in cells
118     * @param height total height of the map, in cells
119     * @param roomWidth target width of each room, in cells; only counts the center floor area of a room
120     * @param roomHeight target height of each room, in cells; only counts the center floor area of a room
121     * @param random an IRNG to make random choices for connecting rooms
122     */
123    public ConnectingMapGenerator(int width, int height, int roomWidth, int roomHeight, IRNG random)
124    {
125        this(width, height, roomWidth, roomHeight, random, 2);
126    }
127
128    /**
129     * 
130     * @param width total width of the map, in cells
131     * @param height total height of the map, in cells
132     * @param roomWidth target width of each room, in cells; only counts the center floor area of a room
133     * @param roomHeight target height of each room, in cells; only counts the center floor area of a room
134     * @param random an IRNG to make random choices for connecting rooms
135     * @param wallThickness how thick a wall between two rooms should be, in cells; 1 is minimum, and this usually
136     *                      shouldn't be much more than roomWidth or roomHeight
137     */
138    public ConnectingMapGenerator(int width, int height, int roomWidth, int roomHeight, IRNG random, int wallThickness)
139    {
140        this.width = Math.max(1, width);
141        this.height = Math.max(1, height);
142        this.region = new GreasedRegion(this.width, this.height);
143        tempRegion = new GreasedRegion(this.width, this.height);
144        this.roomWidth = Math.max(1, roomWidth);
145        this.roomHeight = Math.max(1, roomHeight);
146        this.wallThickness = Math.max(1, wallThickness);
147        dungeon = ArrayTools.fill(' ', this.width, this.height);
148        environment = new int[this.width][this.height];
149        rng = random;
150    }
151    /**
152     * Generates a dungeon or other map as a 2D char array. Uses the convention of '#' representing a wall and '.'
153     * representing a bare floor, and also fills {@link #environment} with appropriate constants from DungeonUtility,
154     * like {@link DungeonUtility#ROOM_FLOOR} and {@link DungeonUtility#ROOM_WALL}.
155     * 
156     * @return a 2D char array representing a room-based map, using standard conventions for walls/floors
157     */
158    @Override
159    public char[][] generate() {
160        int gridWidth = (width + wallThickness - 2) / (roomWidth + wallThickness), gridHeight = (height + wallThickness - 2) / (roomHeight + wallThickness), gridMax = gridWidth * gridHeight;
161        if(gridWidth <= 0 || gridHeight <= 0)
162            return dungeon;
163        ArrayTools.fill(dungeon, '#');
164        ArrayTools.fill(environment, DungeonUtility.UNTOUCHED);
165        region.resizeAndEmpty(width, height);
166        IntIntOrderedMap links = new IntIntOrderedMap(gridMax), surface = new IntIntOrderedMap(gridMax);
167        IntVLA choices = new IntVLA(4);
168        int dx = rng.nextSignedInt(gridWidth), dy = rng.nextSignedInt(gridHeight),
169                d = dy << 16 | dx;
170        links.put(d, 0);
171        surface.put(d, 0);
172        for (int i = 0; i < 15 && links.size() < gridMax && !surface.isEmpty(); i++) {
173            choices.clear();
174            if (dx < gridWidth - 1 && !links.containsKey(d + 1)) choices.add(1);
175            if (dy < gridHeight - 1 && !links.containsKey(d + 0x10000)) choices.add(2);
176            if (dx > 0 && !links.containsKey(d - 1)) choices.add(4);
177            if (dy > 0 && !links.containsKey(d - 0x10000)) choices.add(8);
178            if (choices.isEmpty()) {
179                surface.remove(d);
180                break;
181            }
182            int choice = choices.getRandomElement(rng);
183            links.replace(d, links.get(d) | choice);
184            if (choices.size == 1)
185                surface.remove(d);
186            switch (choice) {
187                case 1:
188                    d += 1;
189                    links.put(d, 4);
190                    surface.put(d, 4);
191                    break;
192                case 2:
193                    d += 0x10000;
194                    links.put(d, 8);
195                    surface.put(d, 8);
196                    break;
197                case 4:
198                    d -= 1;
199                    links.put(d, 1);
200                    surface.put(d, 1);
201                    break;
202                default:
203                    d -= 0x10000;
204                    links.put(d, 2);
205                    surface.put(d, 2);
206                    break;
207            }
208            dx = d & 0xFFFF;
209            dy = d >>> 16;
210        }
211        while(links.size() < gridMax)
212        {
213            d = surface.randomKey(rng);
214            dx = d & 0xFFFF;
215            dy = d >>> 16;
216            for (int i = 0; i < 5 && links.size() < gridMax && !surface.isEmpty(); i++) {
217                choices.clear();
218                if (dx < gridWidth - 1 && !links.containsKey(d + 1)) choices.add(1);
219                if (dy < gridHeight - 1 && !links.containsKey(d + 0x10000)) choices.add(2);
220                if (dx > 0 && !links.containsKey(d - 1)) choices.add(4);
221                if (dy > 0 && !links.containsKey(d - 0x10000)) choices.add(8);
222                if (choices.isEmpty()) {
223                    surface.remove(d);
224                    break;
225                }
226                int choice = choices.getRandomElement(rng);
227                links.replace(d, links.get(d) | choice);
228                if (choices.size == 1)
229                    surface.remove(d);
230                switch (choice) {
231                    case 1:
232                        d += 1;
233                        links.put(d, 4);
234                        surface.put(d, 4);
235                        break;
236                    case 2:
237                        d += 0x10000;
238                        links.put(d, 8);
239                        surface.put(d, 8);
240                        break;
241                    case 4:
242                        d -= 1;
243                        links.put(d, 1);
244                        surface.put(d, 1);
245                        break;
246                    default:
247                        d -= 0x10000;
248                        links.put(d, 2);
249                        surface.put(d, 2);
250                        break;
251                }
252                dx = d & 0xFFFF;
253                dy = d >>> 16;
254            }
255        }
256        for (int i = 0; i < links.size(); i++) {
257            d = links.keyAt(i);
258            dx = d & 0xFFFF;
259            dy = d >>> 16;
260            int conn = links.getAt(i);
261            
262            region.insertRectangle(1 + dx * (roomWidth + wallThickness), 1 + dy * (roomHeight + wallThickness), roomWidth, roomHeight);
263            if((conn & 1) != 0)
264                region.insertRectangle(1 + dx * (roomWidth + wallThickness) + roomWidth, 1 + dy * (roomHeight + wallThickness), wallThickness, roomHeight);
265            if((conn & 2) != 0)
266                region.insertRectangle(1 + dx * (roomWidth + wallThickness), 1 + dy * (roomHeight + wallThickness) + roomHeight, roomWidth, wallThickness);
267            if((conn & 4) != 0)
268                region.insertRectangle(1 + dx * (roomWidth + wallThickness) - wallThickness, 1 + dy * (roomHeight + wallThickness), wallThickness, roomHeight);
269            if((conn & 8) != 0)
270                region.insertRectangle(1 + dx * (roomWidth + wallThickness), 1 + dy * (roomHeight + wallThickness) - wallThickness, roomWidth, wallThickness);
271        }
272        region.writeCharsInto(dungeon, '.');
273        region.writeIntsInto(environment, DungeonUtility.ROOM_FLOOR);
274        tempRegion.remake(region).fringe8way().writeIntsInto(environment, DungeonUtility.ROOM_WALL);
275        return dungeon;
276    }
277
278    /**
279     * Gets the most recently-produced dungeon as a 2D char array, usually produced by calling {@link #generate()} or
280     * some similar method present in a specific implementation. This normally passes a direct reference and not a copy,
281     * so you can normally modify the returned array to propagate changes back into this IDungeonGenerator.
282     *
283     * @return the most recently-produced dungeon/map as a 2D char array
284     */
285    @Override
286    public char[][] getDungeon() {
287        return dungeon;
288    }
289    /**
290     * Gets a 2D array of int constants, each representing a type of environment corresponding to a static field of
291     * DungeonUtility. This array will have the same size as the last char 2D array produced by generate(); the value
292     * of this method if called before generate() is undefined, but probably will be a 2D array of all 0 (UNTOUCHED).
293     * <ul>
294     * <li>DungeonUtility.UNTOUCHED, equal to 0, is used for any cells that aren't near a floor.</li>
295     * <li>DungeonUtility.ROOM_FLOOR, equal to 1, is used for floor cells inside wide room areas.</li>
296     * <li>DungeonUtility.ROOM_WALL, equal to 2, is used for wall cells around wide room areas.</li>
297     * <li>DungeonUtility.CAVE_FLOOR, equal to 3, is used for floor cells inside rough cave areas.</li>
298     * <li>DungeonUtility.CAVE_WALL, equal to 4, is used for wall cells around rough cave areas.</li>
299     * <li>DungeonUtility.CORRIDOR_FLOOR, equal to 5, is used for floor cells inside narrow corridor areas.</li>
300     * <li>DungeonUtility.CORRIDOR_WALL, equal to 6, is used for wall cells around narrow corridor areas.</li>
301     * </ul>
302     *
303     * @return a 2D int array where each element is an environment type constant in DungeonUtility
304     */
305    public int[][] getEnvironment() {
306        return environment;
307    }
308
309}