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