001package squidpony.squidgrid.mapping;
002
003import squidpony.GwtCompatibility;
004import squidpony.squidmath.Coord;
005import squidpony.squidmath.RegionMap;
006
007import java.util.ArrayList;
008import java.util.Arrays;
009import java.util.LinkedHashSet;
010import java.util.List;
011
012import static squidpony.squidmath.CoordPacker.*;
013
014/**
015 * A small class that can analyze a dungeon or other map and identify areas as being "room" or "corridor" based on how
016 * thick the walkable areas are (corridors are at most 2 cells wide at their widest, rooms are anything else). Most
017 * methods of this class return 2D char arrays or Lists thereof, with the subset of the map that is in a specific region
018 * kept the same, but everything else replaced with '#'.
019 * Created by Tommy Ettinger on 2/3/2016.
020 * 
021 * @see RectangleRoomFinder A simpler but faster alternative
022 */
023public class RoomFinder {
024    /**
025     * A copy of the dungeon map, however it was passed to the constructor.
026     */
027    public char[][] map,
028    /**
029     * A simplified version of the dungeon map, using '#' for walls and '.' for floors.
030     */
031    basic;
032    /**
033     * Not likely to be used directly, but there may be things you can do with these that are cumbersome using only
034     * RoomFinder's simpler API.
035     */
036    public RegionMap<List<short[]>> rooms,
037    /**
038     * Not likely to be used directly, but there may be things you can do with these that are cumbersome using only
039     * RoomFinder's simpler API.
040     */
041    corridors,
042    /**
043     * Not likely to be used directly, but there may be things you can do with these that are cumbersome using only
044     * RoomFinder's simpler API. Won't be assigned a value if this class is constructed with a 2D char array; it needs
045     * the two-arg constructor using the environment produced by a MixedGenerator, SerpentMapGenerator, or similar.
046     */
047    caves;
048    /**
049     * When a RoomFinder is constructed, it stores all points of rooms that are adjacent to another region here.
050     */
051    public Coord[] connections,
052    /**
053     * Potential doorways, where a room is adjacent to a corridor.
054     */
055    doorways,
056    /**
057     * Cave mouths, where a cave is adjacent to another type of terrain.
058     */
059    mouths;
060    public int width, height;
061
062    /**
063     * Constructs a RoomFinder given a dungeon map, and finds rooms, corridors, and their connections on the map. Does
064     * not find caves; if a collection of caves is requested from this, it will be non-null but empty.
065     * @param dungeon a 2D char array that uses '#' for walls.
066     */
067    public RoomFinder(char[][] dungeon)
068    {
069        if(dungeon.length <= 0)
070            return;
071        width = dungeon.length;
072        height = dungeon[0].length;
073        map = new char[width][height];
074        for (int i = 0; i < width; i++) {
075            System.arraycopy(dungeon[i], 0, map[i], 0, height);
076        }
077        rooms = new RegionMap<>(32);
078        corridors = new RegionMap<>(32);
079        caves = new RegionMap<>(8);
080        basic = DungeonUtility.simplifyDungeon(map);
081        short[] floors = pack(basic, '.'),
082                r = flood(floors, retract(floors, 1, width, height, true), 2, false),
083                c = differencePacked(floors, r),
084                d = intersectPacked(r, fringe(c, 1, width, height, false));
085        connections = doorways = allPacked(d);
086        mouths = new Coord[0];
087        List<short[]> rs = split(r), cs = split(c);
088
089        short[][] ra = rs.toArray(new short[rs.size()][]),
090                ca = cs.toArray(new short[cs.size()][]);
091
092        for (short[] sep : cs) {
093            short[] someDoors = intersectPacked(r, fringe(sep, 1, width, height, false));
094            short[] doors = allPackedHilbert(someDoors);
095            List<short[]> near = new ArrayList<short[]>(4);
096            for (int j = 0; j < doors.length; j++) {
097                near.addAll(findManyPackedHilbert(doors[j], ra));
098            }
099            corridors.put(sep, near);
100        }
101
102        for (short[] sep : rs) {
103            List<short[]> near = new ArrayList<short[]>(10);
104            short[] aroundDoors = intersectPacked(c, fringe(sep, 1, width, height, false));
105            short[] doors = allPackedHilbert(aroundDoors);
106            for (int j = 0; j < doors.length; j++) {
107                near.addAll(findManyPackedHilbert(doors[j], ca));
108            }
109            rooms.put(sep, near);
110        }
111    }
112
113    public RoomFinder(char[][] dungeon, int environmentKind)
114    {
115        if(dungeon.length <= 0)
116            return;
117        width = dungeon.length;
118        height = dungeon[0].length;
119        map = new char[width][height];
120        for (int i = 0; i < width; i++) {
121            System.arraycopy(dungeon[i], 0, map[i], 0, height);
122        }
123        rooms = new RegionMap<>(32);
124        corridors = new RegionMap<>(32);
125        caves = new RegionMap<>(8);
126        basic = DungeonUtility.simplifyDungeon(map);
127
128        if(environmentKind == MixedGenerator.ROOM_FLOOR) {
129            short[] floors = pack(basic, '.'),
130                    r = flood(floors, retract(floors, 1, width, height, true), 2, false),
131                    c = differencePacked(floors, r),
132                    d = intersectPacked(r, fringe(c, 1, width, height, false));
133            connections = doorways = allPacked(d);
134            mouths = new Coord[0];
135            List<short[]> rs = split(r), cs = split(c);
136
137            short[][] ra = rs.toArray(new short[rs.size()][]),
138                    ca = cs.toArray(new short[cs.size()][]);
139
140            for (short[] sep : cs) {
141                short[] someDoors = intersectPacked(r, fringe(sep, 1, width, height, false));
142                short[] doors = allPackedHilbert(someDoors);
143                List<short[]> near = new ArrayList<short[]>(4);
144                for (int j = 0; j < doors.length; j++) {
145                    near.addAll(findManyPackedHilbert(doors[j], ra));
146                }
147                corridors.put(sep, near);
148            }
149
150            for (short[] sep : rs) {
151                List<short[]> near = new ArrayList<short[]>(10);
152                short[] aroundDoors = intersectPacked(c, fringe(sep, 1, width, height, false));
153                short[] doors = allPackedHilbert(aroundDoors);
154                for (int j = 0; j < doors.length; j++) {
155                    near.addAll(findManyPackedHilbert(doors[j], ca));
156                }
157                rooms.put(sep, near);
158            }
159        }
160        else
161        {
162            short[] floors = pack(basic, '.');
163            caves.put(floors, new ArrayList<short[]>());
164            connections = mouths = allPacked(retract(
165                    differencePacked(floors, retract(floors, 1, width, height, true)),
166                    1, width, height, false));
167            doorways = new Coord[0];
168        }
169    }
170
171    /**
172     * Constructs a RoomFinder given a dungeon map and an environment map (which currently is only produced by
173     * MixedGenerator by the getEnvironment() method after generate() is called, but other classes that use
174     * MixedGenerator may also expose that environment, such as SerpentMapGenerator.getEnvironment()), and finds rooms,
175     * corridors, caves, and their connections on the map.
176     * @param dungeon a 2D char array that uses '#' for walls.
177     * @param environment a 2D int array using constants from MixedGenerator; typically produced by a call to
178     *                    getEnvironment() in MixedGenerator or SerpentMapGenerator after dungeon generation.
179     */
180    public RoomFinder(char[][] dungeon, int[][] environment)
181    {
182        if(dungeon.length <= 0)
183            return;
184        width = dungeon.length;
185        height = dungeon[0].length;
186        map = new char[width][height];
187        for (int i = 0; i < width; i++) {
188            System.arraycopy(dungeon[i], 0, map[i], 0, height);
189        }
190        rooms = new RegionMap<>(32);
191        corridors = new RegionMap<>(32);
192        caves = new RegionMap<>(32);
193
194        basic = DungeonUtility.simplifyDungeon(map);
195        short[] r = pack(environment, MixedGenerator.ROOM_FLOOR),
196                c = pack(environment, MixedGenerator.CORRIDOR_FLOOR),
197                v = pack(environment, MixedGenerator.CAVE_FLOOR),
198                rc = unionPacked(r, c),
199                d = intersectPacked(r, fringe(c, 1, width, height, false)),
200                m = intersectPacked(rc, fringe(v, 1, width, height, false));
201        doorways = allPacked(d);
202        mouths = allPacked(m);
203        connections = new Coord[doorways.length + mouths.length];
204        System.arraycopy(doorways, 0, connections, 0, doorways.length);
205        System.arraycopy(mouths, 0, connections, doorways.length, mouths.length);
206
207        List<short[]> rs = split(r), cs = split(c), vs = split(v);
208        short[][] ra = rs.toArray(new short[rs.size()][]),
209                ca = cs.toArray(new short[cs.size()][]),
210                va = vs.toArray(new short[vs.size()][]);
211
212        for (short[] sep : cs) {
213            short[] someDoors = intersectPacked(r, fringe(sep, 1, width, height, false));
214            short[] doors = allPackedHilbert(someDoors);
215            List<short[]> near = new ArrayList<short[]>(16);
216            for (int j = 0; j < doors.length; j++) {
217                near.addAll(findManyPackedHilbert(doors[j], ra));
218            }
219            someDoors = intersectPacked(v, fringe(sep, 1, width, height, false));
220            doors = allPackedHilbert(someDoors);
221            for (int j = 0; j < doors.length; j++) {
222                near.addAll(findManyPackedHilbert(doors[j], va));
223            }
224            corridors.put(sep, near);
225        }
226
227        for (short[] sep : rs) {
228            List<short[]> near = new ArrayList<short[]>(32);
229            short[] aroundDoors = intersectPacked(c, fringe(sep, 1, width, height, false));
230            short[] doors = allPackedHilbert(aroundDoors);
231            for (int j = 0; j < doors.length; j++) {
232                near.addAll(findManyPackedHilbert(doors[j], ca));
233            }
234            aroundDoors = intersectPacked(v, fringe(sep, 1, width, height, false));
235            doors = allPackedHilbert(aroundDoors);
236            for (int j = 0; j < doors.length; j++) {
237                near.addAll(findManyPackedHilbert(doors[j], va));
238            }
239            rooms.put(sep, near);
240        }
241
242        for (short[] sep : vs) {
243            List<short[]> near = new ArrayList<short[]>(48);
244            short[] aroundMouths = intersectPacked(c, fringe(sep, 1, width, height, false));
245            short[] maws = allPackedHilbert(aroundMouths);
246            for (int j = 0; j < maws.length; j++) {
247                near.addAll(findManyPackedHilbert(maws[j], ca));
248            }
249            aroundMouths = intersectPacked(r, fringe(sep, 1, width, height, false));
250            maws = allPackedHilbert(aroundMouths);
251            for (int j = 0; j < maws.length; j++) {
252                near.addAll(findManyPackedHilbert(maws[j], ra));
253            }
254            caves.put(sep, near);
255        }
256
257    }
258
259    /**
260     * Gets all the rooms this found during construction, returning them as an ArrayList of 2D char arrays, where an
261     * individual room is "masked" so only its contents have normal map chars and the rest have only '#'.
262     * @return an ArrayList of 2D char arrays representing rooms.
263     */
264    public ArrayList<char[][]> findRooms()
265    {
266        ArrayList<char[][]> rs = new ArrayList<char[][]>(rooms.size);
267        for(short[] r : rooms.keys())
268        {
269            rs.add(mask(map, r, '#'));
270        }
271        return rs;
272    }
273
274    /**
275     * Gets all the corridors this found during construction, returning them as an ArrayList of 2D char arrays, where an
276     * individual corridor is "masked" so only its contents have normal map chars and the rest have only '#'.
277     * @return an ArrayList of 2D char arrays representing corridors.
278     */
279    public ArrayList<char[][]> findCorridors()
280    {
281        ArrayList<char[][]> cs = new ArrayList<char[][]>(corridors.size);
282        for(short[] c : corridors.keys())
283        {
284            cs.add(mask(map, c, '#'));
285        }
286        return cs;
287    }
288
289    /**
290     * Gets all the caves this found during construction, returning them as an ArrayList of 2D char arrays, where an
291     * individual room is "masked" so only its contents have normal map chars and the rest have only '#'. Will only
292     * return a non-empty collection if the two-arg constructor was used and the environment contains caves.
293     * @return an ArrayList of 2D char arrays representing caves.
294     */
295    public ArrayList<char[][]> findCaves()
296    {
297        ArrayList<char[][]> vs = new ArrayList<char[][]>(caves.size);
298        for(short[] v : caves.keys())
299        {
300            vs.add(mask(map, v, '#'));
301        }
302        return vs;
303    }
304    /**
305     * Gets all the rooms, corridors, and caves this found during construction, returning them as an ArrayList of 2D
306     * char arrays, where an individual room or corridor is "masked" so only its contents have normal map chars and the
307     * rest have only '#'.
308     * @return an ArrayList of 2D char arrays representing rooms, corridors, or caves.
309     */
310    public ArrayList<char[][]> findRegions()
311    {
312        ArrayList<char[][]> rs = new ArrayList<char[][]>(rooms.size + corridors.size + caves.size);
313        for(short[] r : rooms.keys())
314        {
315            rs.add(mask(map, r, '#'));
316        }
317        for(short[] r : corridors.keys()) {
318            rs.add(mask(map, r, '#'));
319        }
320        for(short[] r : caves.keys()) {
321            rs.add(mask(map, r, '#'));
322        }
323        return rs;
324    }
325    protected static char[][] defaultFill(int width, int height)
326    {
327        char[][] d = new char[width][height];
328        for (int x = 0; x < width; x++) {
329            Arrays.fill(d[x], '#');
330        }
331        return d;
332    }
333
334    /**
335     * Merges multiple 2D char arrays where the '#' character means "no value", and combines them so all cells with
336     * value are on one map, with '#' filling any other cells. If regions is empty, this uses width and height to
337     * construct a blank map, all '#'. It will also use width and height for the size of the returned 2D array.
338     * @param regions An ArrayList of 2D char array regions, where '#' is an empty value and all others will be merged
339     * @param width the width of any map this returns
340     * @param height the height of any map this returns
341     * @return a 2D char array that merges all non-'#' areas in regions, and fills the rest with '#'
342     */
343    public static char[][] merge(ArrayList<char[][]> regions, int width, int height)
344    {
345        if(regions == null || regions.isEmpty())
346            return defaultFill(width, height);
347        char[][] first = regions.get(0);
348        char[][] dungeon = new char[first.length][first[0].length];
349        for (int x = 0; x < first.length; x++) {
350            Arrays.fill(dungeon[x], '#');
351        }
352        for(char[][] region : regions)
353        {
354            for (int x = 0; x < width; x++) {
355                for (int y = 0; y < height; y++) {
356                    if(region[x][y] != '#')
357                        dungeon[x][y] = region[x][y];
358                }
359            }
360        }
361        return dungeon;
362    }
363
364    /**
365     * Takes an x, y position and finds the room, corridor, or cave at that position, if there is one, returning the
366     * same 2D char array format as the other methods.
367     * @param x the x coordinate of a position that should be in a room or corridor
368     * @param y the y coordinate of a position that should be in a room or corridor
369     * @return a masked 2D char array where anything not in the current region is '#'
370     */
371    public char[][] regionAt(int x, int y)
372    {
373        LinkedHashSet<short[]> regions = rooms.regionsContaining(x, y);
374        regions.addAll(corridors.regionsContaining(x, y));
375        regions.addAll(caves.regionsContaining(x, y));
376        short[] found;
377        if(regions.isEmpty())
378            found = ALL_WALL;
379        else
380            found = GwtCompatibility.first(regions);
381        return mask(map, found, '#');
382    }
383
384    /**
385     * Takes an x, y position and finds the room or corridor at that position and the rooms, corridors or caves that it
386     * directly connects to, and returns the group as one merged 2D char array.
387     * @param x the x coordinate of a position that should be in a room or corridor
388     * @param y the y coordinate of a position that should be in a room or corridor
389     * @return a masked 2D char array where anything not in the current region or one nearby is '#'
390     */
391    public char[][] regionsNear(int x, int y)
392    {
393        LinkedHashSet<short[]> regions = rooms.regionsContaining(x, y);
394        regions.addAll(corridors.regionsContaining(x, y));
395        regions.addAll(caves.regionsContaining(x, y));
396        short[] found;
397        if(regions.isEmpty())
398            found = ALL_WALL;
399        else
400        {
401            found = GwtCompatibility.first(regions);
402            LinkedHashSet<List<short[]>> near = rooms.allAt(x, y);
403            for (List<short[]> links : near) {
404                for(short[] n : links)
405                {
406                    found = unionPacked(found, n);
407                }
408            }
409            near = corridors.allAt(x, y);
410            for (List<short[]> links : near) {
411                for(short[] n : links)
412                {
413                    found = unionPacked(found, n);
414                }
415            }
416            near = caves.allAt(x, y);
417            for (List<short[]> links : near) {
418                for(short[] n : links)
419                {
420                    found = unionPacked(found, n);
421                }
422            }
423        }
424        return mask(map, found, '#');
425    }
426
427    /**
428     * Takes an x, y position and finds the rooms or corridors that are directly connected to the room, corridor or cave
429     * at that position, and returns the group as an ArrayList of 2D char arrays, one per connecting region.
430     * @param x the x coordinate of a position that should be in a room or corridor
431     * @param y the y coordinate of a position that should be in a room or corridor
432     * @return an ArrayList of masked 2D char arrays where anything not in a connected region is '#'
433     */
434    public ArrayList<char[][]> regionsConnected(int x, int y)
435    {
436        ArrayList<char[][]> regions = new ArrayList<>(10);
437        LinkedHashSet<List<short[]>> near = rooms.allAt(x, y);
438        for (List<short[]> links : near) {
439            for(short[] n : links)
440            {
441                regions.add(mask(map, n, '#'));
442            }
443        }
444        near = corridors.allAt(x, y);
445        for (List<short[]> links : near) {
446            for (short[] n : links) {
447                regions.add(mask(map, n, '#'));
448            }
449        }
450        near = caves.allAt(x, y);
451        for (List<short[]> links : near) {
452            for (short[] n : links) {
453                regions.add(mask(map, n, '#'));
454            }
455        }
456
457        return regions;
458    }
459}