001package squidpony.squidgrid.mapping;
002
003import squidpony.squidgrid.Direction;
004import squidpony.squidgrid.iterator.SquidIterators;
005import squidpony.squidmath.Coord;
006
007import java.util.*;
008
009/**
010 * An algorithm to find rectangle areas in dungeons. It is a simpler and faster
011 * alternative to {@link RoomFinder}. You can execute
012 * {@code RectangleRoomsFinderTest} to see how it performs.
013 * 
014 * @author smelC
015 * 
016 * @see RoomFinder A fancier room finder
017 */
018public class RectangleRoomFinder {
019
020        protected final char[][] dungeon;
021        protected final int dungeonWidth;
022        protected final int dungeonHeight;
023
024        protected final Set<Character> floors;
025
026        /**
027         * The minimum number of cells that the diagonal of a room must have. Having
028         * 3 here means that, by default, only rooms at most 3x3 are considered.
029         */
030        public int minimumDiagonal = 3;
031
032        /** {@code true} to restrict {@code this} to find square rooms */
033        public boolean onlySquareRooms;
034
035        public RectangleRoomFinder(char[][] dungeon) {
036                this.dungeon = dungeon;
037                this.dungeonWidth = dungeon.length;
038                this.dungeonHeight = dungeonWidth == 0 ? 0 : dungeon[0].length;
039                this.floors = new HashSet<>();
040                this.floors.add('.');
041        }
042
043        /**
044         * Adds a character considered as a floor.
045         * 
046         * @param c
047         * @return {@code true} if {@code c} wasn't a floor character.
048         */
049        public boolean addFloorCharacter(char c) {
050                return floors.add(c);
051        }
052
053        /**
054         * Removes a character from being considered as a floor.
055         * 
056         * @param c
057         * @return {@code true} if {@code c} was a floor character.
058         */
059        public boolean removeFloorCharacter(char c) {
060                return floors.remove(c);
061        }
062
063        /**
064         * @return The rectangles of the dungeon given at creation time.
065         */
066        public List<Rectangle> findRectangles() {
067                final List<Rectangle> result = new ArrayList<>();
068
069                /*
070                 * Every cell containing true indicates that this cell is included in an
071                 * already-found room.
072                 */
073                final boolean[][] assigneds = new boolean[dungeonWidth][dungeonHeight];
074
075                final Iterator<Coord> it = new SquidIterators.BottomLeftToTopRight(dungeonWidth, dungeonHeight);
076
077                nextBottomLeft: while (it.hasNext()) {
078                        final Coord c = it.next();
079                        /*
080                         * Try to find the room's diagonal, from its bottom left to its top
081                         * right
082                         */
083                        Coord current = c;
084                        int steps = 0;
085                        while (!assigneds[c.x][c.y] && isFloor(dungeon[current.x][current.y])) {
086                                current = current.translate(Direction.UP_RIGHT);
087                                steps++;
088                        }
089                        if (steps < minimumDiagonal)
090                                continue;
091                        /*
092                         * We have the diagonal. Let's check that this tentative room only
093                         * contains (room-unassigned) floors.
094                         */
095                        Rectangle r = new Rectangle.Impl(c, steps, steps);
096                        Iterator<Coord> cells = Rectangle.Utils.cells(r);
097                        while (cells.hasNext()) {
098                                final Coord inr = cells.next();
099                                assert isInDungeon(inr);
100                                if (!isFloor(dungeon[inr.x][inr.y]) || assigneds[inr.x][inr.y])
101                                        continue nextBottomLeft;
102                        }
103                        if (!onlySquareRooms) {
104                                /* Try to extend it */
105                                r = extendRoom(assigneds, r, Direction.LEFT);
106                                r = extendRoom(assigneds, r, Direction.RIGHT);
107                                r = extendRoom(assigneds, r, Direction.UP);
108                                r = extendRoom(assigneds, r, Direction.DOWN);
109                        }
110                        /* Found a room! Let's record the cells. */
111                        result.add(r);
112                        cells = Rectangle.Utils.cells(r);
113                        while (cells.hasNext()) {
114                                final Coord inr = cells.next();
115                                assigneds[inr.x][inr.y] = true;
116                        }
117                }
118
119                return result;
120        }
121
122        /**
123         * @param assigneds
124         *            Cells already in a room.
125         * @param d
126         *            A cardinal direction.
127         * @return A variant of {@code r} extended to the direction {@code d}, if
128         *         possible. {@code r} itself if unaffected.
129         */
130        protected Rectangle extendRoom(boolean[][] assigneds, Rectangle r, Direction d) {
131                assert !d.isDiagonal();
132                Rectangle result = r;
133                while (true) {
134                        Rectangle next = extendRoomOnce(assigneds, result, d);
135                        if (next == result)
136                                /* No change */
137                                break;
138                        else
139                                result = next;
140                }
141                return result;
142        }
143
144        /**
145         * @param assigneds
146         *            Cells already in a room. This array is muted by this call.
147         */
148        protected Rectangle extendRoomOnce(boolean[][] assigneds, Rectangle r, Direction d) {
149                final Coord bl = r.getBottomLeft();
150                Coord first = null;
151                Direction way = null;
152                int steps = -1;
153                switch (d) {
154                case DOWN_LEFT:
155                case DOWN_RIGHT:
156                case NONE:
157                case UP_LEFT:
158                case UP_RIGHT:
159                        throw new IllegalStateException(
160                                        "Unexpected direction in " + getClass().getSimpleName() + "::extendRoomOnce: " + d);
161                case DOWN:
162                        first = bl.translate(Direction.DOWN);
163                        way = Direction.RIGHT;
164                        steps = r.getWidth();
165                        break;
166                case LEFT:
167                        first = bl.translate(Direction.LEFT);
168                        way = Direction.UP;
169                        steps = r.getHeight();
170                        break;
171                case RIGHT:
172                        first = bl.translate(r.getWidth() - 1, 0).translate(Direction.RIGHT);
173                        way = Direction.UP;
174                        steps = r.getHeight();
175                        break;
176                case UP:
177                        first = bl.translate(0, -r.getHeight() + 1).translate(Direction.UP);
178                        way = Direction.RIGHT;
179                        steps = r.getWidth();
180                        break;
181                }
182
183                assert first != null;
184
185                Coord current = first;
186
187                assert 0 <= steps;
188
189                while (0 < steps) {
190                        if (!isInDungeon(current) || !isFloor(dungeon[current.x][current.y])
191                                        || assigneds[current.x][current.y])
192                                /* Cannot extend */
193                                return r;
194                        current = current.translate(way);
195                        steps--;
196                }
197
198                final Rectangle result = Rectangle.Utils.extend(r, d);
199                assert validRoomCells(Rectangle.Utils.cells(result));
200                return result;
201        }
202
203        protected boolean isFloor(char c) {
204                return floors.contains(c);
205        }
206
207        protected boolean isInDungeon(Coord c) {
208                return 0 <= c.x && c.x < dungeonWidth && 0 <= c.y && c.y < dungeonHeight;
209        }
210
211        private boolean validRoomCells(Iterator<? extends Coord> cs) {
212                while (cs.hasNext()) {
213                        final Coord c = cs.next();
214                        if (!isInDungeon(c) || !isFloor(dungeon[c.x][c.y]))
215                                return false;
216                }
217                return true;
218        }
219}