001package squidpony.squidgrid.mapping;
002
003
004import squidpony.squidgrid.Direction;
005import squidpony.squidmath.Coord;
006import squidpony.squidmath.RNG;
007
008import java.util.Arrays;
009import java.util.LinkedList;
010import java.util.List;
011
012/**
013 * Creates a dungeon in the style of the original Rogue game. It will always
014 * make a grid style of rooms where there are a certain number horizontally and
015 * vertically and it will link them only next to each other.
016 *
017 * This dungeon generator is based on a port of the rot.js version.
018 *
019 * @author hyakugei
020 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
021 */
022public class ClassicRogueMapGenerator {
023
024    /**
025     * Holds the information needed to track rooms in the classic rogue
026     * generation algorithm.
027     */
028    private class ClassicRogueRoom {
029
030        private int x, y, width, height, cellx, celly;
031        private final List<ClassicRogueRoom> connections = new LinkedList<>();
032
033        ClassicRogueRoom(int x, int y, int width, int height, int cellx, int celly) {
034            this.x = x;
035            this.y = y;
036            this.width = width;
037            this.height = height;
038            this.cellx = cellx;
039            this.celly = celly;
040        }
041
042        @Override
043        public int hashCode() {
044            int hash = 5;
045            hash = 89 * hash + cellx;
046            hash = 89 * hash + celly;
047            return hash;
048        }
049
050        @Override
051        public boolean equals(Object obj) {
052            if (obj == null) {
053                return false;
054            }
055            if (getClass() != obj.getClass()) {
056                return false;
057            }
058            final ClassicRogueRoom other = (ClassicRogueRoom) obj;
059            if (cellx != other.cellx) {
060                return false;
061            }
062            return celly == other.celly;
063        }
064    }
065
066    private RNG rng;
067
068    private int horizontalRooms, verticalRooms, dungeonWidth, dungeonHeight,
069            minRoomWidth, maxRoomWidth, minRoomHeight, maxRoomHeight;
070    private ClassicRogueRoom[][] rooms;
071    private Terrain[][] map;
072
073    /**
074     * Initializes the generator to turn out random dungeons within the specific
075     * parameters.
076     *
077     * Will size down the room width and height parameters if needed to ensure
078     * the desired number of rooms will fit both horizontally and vertically.
079     *
080     * @param horizontalRooms How many rooms will be made horizontally
081     * @param verticalRooms How many rooms will be made vertically
082     * @param dungeonWidth How wide the total dungeon will be
083     * @param dungeonHeight How high the total dungeon will be
084     * @param minRoomWidth The minimum width a room can be
085     * @param maxRoomWidth The maximum width a room can be
086     * @param minRoomHeight The minimum height a room can be
087     * @param maxRoomHeight The maximum height a room can be
088     */
089    public ClassicRogueMapGenerator(int horizontalRooms, int verticalRooms, int dungeonWidth, int dungeonHeight,
090                                    int minRoomWidth, int maxRoomWidth, int minRoomHeight, int maxRoomHeight) {
091        this(horizontalRooms, verticalRooms, dungeonWidth, dungeonHeight, minRoomWidth, maxRoomWidth, minRoomHeight, maxRoomHeight, new RNG());
092    }
093
094    /**
095     * Initializes the generator to turn out random dungeons within the specific
096     * parameters.
097     *
098     * Will size down the room width and height parameters if needed to ensure
099     * the desired number of rooms will fit both horizontally and vertically.
100     *
101     * @param horizontalRooms How many rooms will be made horizontally
102     * @param verticalRooms How many rooms will be made vertically
103     * @param dungeonWidth How wide the total dungeon will be
104     * @param dungeonHeight How high the total dungeon will be
105     * @param minRoomWidth The minimum width a room can be
106     * @param maxRoomWidth The maximum width a room can be
107     * @param minRoomHeight The minimum height a room can be
108     * @param maxRoomHeight The maximum height a room can be
109     */
110    public ClassicRogueMapGenerator(int horizontalRooms, int verticalRooms, int dungeonWidth, int dungeonHeight,
111                                    int minRoomWidth, int maxRoomWidth, int minRoomHeight, int maxRoomHeight, RNG rng)
112    {
113        this.rng = rng;
114        this.horizontalRooms = horizontalRooms;
115        this.verticalRooms = verticalRooms;
116        this.dungeonWidth = dungeonWidth;
117        this.dungeonHeight = dungeonHeight;
118        this.minRoomWidth = minRoomWidth;
119        this.maxRoomWidth = maxRoomWidth;
120        this.minRoomHeight = minRoomHeight;
121        this.maxRoomHeight = maxRoomHeight;
122
123        sanitizeRoomDimensions();
124    }
125
126    private void sanitizeRoomDimensions() {
127        int test = (dungeonWidth - 3 * horizontalRooms) / horizontalRooms;//have to leave space for hallways
128        maxRoomWidth = Math.min(test, maxRoomWidth);
129        minRoomWidth = Math.max(minRoomWidth, 2);
130        minRoomWidth = Math.min(minRoomWidth, maxRoomWidth);
131
132        test = (dungeonHeight - 3 * verticalRooms) / (verticalRooms);//have to leave space for hallways
133        maxRoomHeight = Math.min(test, maxRoomHeight);
134        minRoomHeight = Math.max(minRoomHeight, 2);
135        minRoomHeight = Math.min(minRoomHeight, maxRoomHeight);
136    }
137
138    /**
139     * Builds and returns a map in the Classic Rogue style.
140     * <br>
141     * Only includes rooms, corridors and doors.
142     * <br>
143     * There is also a generate method that produces a 2D char array, which may be more suitable.
144     * @return a 2D array of Terrain objects
145     */
146    public Terrain[][] create() {
147        initRooms();
148        connectRooms();
149        connectUnconnectedRooms();
150        fullyConnect();
151        createRooms();
152        createCorridors();
153        return map;
154    }
155    /**
156     * Builds and returns a map in the Classic Rogue style, returned as a 2D char array.
157     *
158     * Only includes rooms ('.' for floor and '#' for walls), corridors (using the same chars as rooms) and doors ('+'
159     * for closed doors, does not generate open doors).
160     * <br>
161     * There is also a create method that produces a 2D array of Terrain objects, which could (maybe) be what you want.
162     * More methods in SquidLib expect char 2D arrays than Terrain anything, particularly in DungeonUtility.
163     * @return a 2D char array version of the map
164     */
165    public char[][] generate()
166    {
167        create();
168        if(map.length <= 0)
169            return new char[0][0];
170        char[][] gen = new char[map.length][map[0].length];
171        for (int x = 0; x < map.length; x++) {
172            for (int y = 0; y < map[x].length; y++) {
173                gen[x][y] = map[x][y].symbol();
174            }
175        }
176        return gen;
177    }
178
179    private void initRooms() {
180        rooms = new ClassicRogueRoom[horizontalRooms][verticalRooms];
181        map = new Terrain[dungeonWidth][dungeonHeight];
182        for (int x = 0; x < horizontalRooms; x++) {
183            for (int y = 0; y < verticalRooms; y++) {
184                rooms[x][y] = new ClassicRogueRoom(0, 0, 0, 0, x, y);
185            }
186        }
187        for (int x = 0; x < dungeonWidth; x++) {
188            for (int y = 0; y < dungeonHeight; y++) {
189                map[x][y] = Terrain.WALL;
190            }
191        }
192    }
193
194    private void connectRooms() {
195        List<ClassicRogueRoom> unconnected = new LinkedList<>();
196        for (int x = 0; x < horizontalRooms; x++) {
197            for (int y = 0; y < verticalRooms; y++) {
198                unconnected.add(rooms[x][y]);
199            }
200        }
201        unconnected = rng.shuffle(unconnected);
202
203        Direction[]  dirToCheck = new Direction[4];
204        for (ClassicRogueRoom room : unconnected) {
205            rng.shuffle(Direction.CARDINALS, dirToCheck);
206            for (Direction dir : dirToCheck) {
207                int nextX = room.x + dir.deltaX;
208                int nextY = room.y + dir.deltaY;
209                if (nextX < 0 || nextX >= horizontalRooms || nextY < 0 || nextY >= verticalRooms) {
210                    continue;
211                }
212                ClassicRogueRoom otherRoom = rooms[nextX][nextY];
213
214                if (room.connections.contains(otherRoom)) {
215                    break;//already connected to this room
216                }
217
218                if (!otherRoom.connections.isEmpty()) {
219                    room.connections.add(otherRoom);
220                    break;
221                }
222            }
223        }
224    }
225
226    private void connectUnconnectedRooms() {
227        for (int x = 0; x < horizontalRooms; x++) {
228            for (int y = 0; y < verticalRooms; y++) {
229                ClassicRogueRoom room = rooms[x][y];
230
231                if (room.connections.isEmpty()) {
232                    List<Direction> dirToCheck = Arrays.asList(Direction.CARDINALS);
233                    dirToCheck = rng.shuffle(dirToCheck);
234
235                    boolean validRoom = false;
236                    ClassicRogueRoom otherRoom = null;
237
238                    do {
239                        Direction dir = dirToCheck.remove(0);
240
241                        int nextX = x + dir.deltaX;
242                        if (nextX < 0 || nextX >= horizontalRooms) {
243                            continue;
244                        }
245                        int nextY = y + dir.deltaY;
246                        if (nextY < 0 || nextY >= verticalRooms) {
247                            continue;
248                        }
249
250                        otherRoom = rooms[nextX][nextY];
251                        validRoom = true;
252
253                        if (otherRoom.connections.contains(room)) {
254                            validRoom = false;
255                        }
256                        else {
257                            break;
258                        }
259                    } while (!dirToCheck.isEmpty());
260
261                    if (validRoom) {
262                        room.connections.add(otherRoom);
263                    }
264                }
265            }
266        }
267    }
268
269    private void fullyConnect() {
270        boolean allGood;
271        do {
272            LinkedList<ClassicRogueRoom> deq = new LinkedList<>();
273            for (int x = 0; x < horizontalRooms; x++) {
274                for (int y = 0; y < verticalRooms; y++) {
275                    deq.offer(rooms[x][y]);
276                }
277            }
278            LinkedList<ClassicRogueRoom> connected = new LinkedList<>();
279            connected.add(deq.removeFirst());
280            boolean changed = true;
281            testing:
282            while (changed) {
283                changed = false;
284                for (ClassicRogueRoom test : deq) {
285                    for (ClassicRogueRoom r : connected) {
286                        if (test.connections.contains(r) || r.connections.contains(test)) {
287                            connected.offer(test);
288                            deq.remove(test);
289                            changed = true;
290                            continue testing;
291                        }
292                    }
293                }
294            }
295
296            allGood = true;
297            if (!deq.isEmpty()) {
298                testing:
299                for (ClassicRogueRoom room : deq) {
300                    for (Direction dir : Direction.CARDINALS) {
301                        int x = room.cellx + dir.deltaX;
302                        int y = room.celly + dir.deltaY;
303                        if (x >= 0 && y >= 0 && x < horizontalRooms && y < verticalRooms) {
304                            ClassicRogueRoom otherRoom = rooms[x][y];
305                            if (connected.contains(otherRoom)) {
306                                room.connections.add(otherRoom);
307                                allGood = false;
308                                break testing;
309                            }
310                        }
311                    }
312                }
313            }
314
315        } while (!allGood);
316    }
317
318    private void createRooms() {
319        int cwp = dungeonWidth / horizontalRooms;
320        int chp = dungeonHeight / verticalRooms;
321
322        ClassicRogueRoom otherRoom;
323
324        for (int x = 0; x < horizontalRooms; x++) {
325            for (int y = 0; y < verticalRooms; y++) {
326                int sx = cwp * x;
327                int sy = chp * y;
328
329                sx = Math.max(sx, 2);
330                sy = Math.max(sy, 2);
331
332                int roomw = rng.between(minRoomWidth, maxRoomWidth + 1);
333                int roomh = rng.between(minRoomHeight, maxRoomHeight + 1);
334
335                if (y > 0) {
336                    otherRoom = rooms[x][y - 1];
337                    while (sy - (otherRoom.y + otherRoom.height) < 3) {
338                        sy++;
339                    }
340                }
341
342                if (x > 0) {
343                    otherRoom = rooms[x - 1][y];
344                    while (sx - (otherRoom.x + otherRoom.width) < 3) {
345                        sx++;
346                    }
347                }
348
349                int sxOffset = Math.round(rng.nextInt(cwp - roomw) / 2);
350                int syOffset = Math.round(rng.nextInt(chp - roomh) / 2);
351
352                while (sx + sxOffset + roomw >= dungeonWidth) {
353                    if (sxOffset > 0) {
354                        sxOffset--;
355                    } else {
356                        roomw--;
357                    }
358                }
359                while (sy + syOffset + roomh >= dungeonHeight) {
360                    if (syOffset > 0) {
361                        syOffset--;
362                    } else {
363                        roomh--;
364                    }
365                }
366
367                sx += sxOffset;
368                sy += syOffset;
369
370                ClassicRogueRoom r = rooms[x][y];
371                r.x = sx;
372                r.y = sy;
373                r.width = roomw;
374                r.height = roomh;
375
376                for (int xx = sx; xx < sx + roomw; xx++) {
377                    for (int yy = sy; yy < sy + roomh; yy++) {
378                        map[xx][yy] = Terrain.FLOOR;
379                    }
380                }
381            }
382        }
383    }
384
385    private Coord randomWallPosition(ClassicRogueRoom room, Direction dir) {
386        int x, y;
387        Coord p = null;
388
389        switch (dir) {
390            case LEFT:
391                y = rng.between(room.y + 1, room.y + room.height);
392                x = room.x - 1;
393                map[x][y] = Terrain.CLOSED_DOOR;
394                p = Coord.get(x - 1, y);
395                break;
396            case RIGHT:
397                y = rng.between(room.y + 1, room.y + room.height);
398                x = room.x + room.width;
399                map[x][y] = Terrain.CLOSED_DOOR;
400                p = Coord.get(x + 1, y);
401                break;
402            case UP:
403                x = rng.between(room.x + 1, room.x + room.width);
404                y = room.y - 1;
405                map[x][y] = Terrain.CLOSED_DOOR;
406                p = Coord.get(x, y - 1);
407                break;
408            case DOWN:
409                x = rng.between(room.x + 1, room.x + room.width);
410                y = room.y + room.height;
411                map[x][y] = Terrain.CLOSED_DOOR;
412                p = Coord.get(x, y + 1);
413                break;
414        case NONE:
415                break;
416                case DOWN_LEFT:
417                case DOWN_RIGHT:
418                case UP_LEFT:
419                case UP_RIGHT:
420                        throw new IllegalStateException("There should only be cardinal positions here");
421        }
422
423        return p;
424    }
425
426    /**
427     * Draws a corridor between the two points with a zig-zag in between.
428     *
429     * @param start
430     * @param end
431     */
432    private void digPath(Coord start, Coord end) {
433        int xOffset = end.x - start.x;
434        int yOffset = end.y - start.y;
435        int xpos = start.x;
436        int ypos = start.y;
437
438        List<Magnitude> moves = new LinkedList<>();
439
440        int xAbs = Math.abs(xOffset);
441        int yAbs = Math.abs(yOffset);
442
443        double firstHalf = rng.nextDouble();
444        double secondHalf = 1 - firstHalf;
445
446        Direction xDir = xOffset < 0 ? Direction.LEFT : Direction.RIGHT;
447        Direction yDir = yOffset > 0 ? Direction.DOWN : Direction.UP;
448
449        if (xAbs < yAbs) {
450            int tempDist = (int) Math.ceil(yAbs * firstHalf);
451            moves.add(new Magnitude(yDir, tempDist));
452            moves.add(new Magnitude(xDir, xAbs));
453            tempDist = (int) Math.floor(yAbs * secondHalf);
454            moves.add(new Magnitude(yDir, tempDist));
455        } else {
456            int tempDist = (int) Math.ceil(xAbs * firstHalf);
457            moves.add(new Magnitude(xDir, tempDist));
458            moves.add(new Magnitude(yDir, yAbs));
459            tempDist = (int) Math.floor(xAbs * secondHalf);
460            moves.add(new Magnitude(xDir, tempDist));
461        }
462
463        map[xpos][ypos] = Terrain.FLOOR;
464
465        while (!moves.isEmpty()) {
466            Magnitude move = moves.remove(0);
467            Direction dir = move.dir;
468            int dist = move.distance;
469            while (dist > 0) {
470                xpos += dir.deltaX;
471                ypos += dir.deltaY;
472                map[xpos][ypos] = Terrain.FLOOR;
473                dist--;
474            }
475        }
476    }
477
478    private void createCorridors() {
479        for (int x = 0; x < horizontalRooms; x++) {
480            for (int y = 0; y < verticalRooms; y++) {
481                ClassicRogueRoom room = rooms[x][y];
482                for (ClassicRogueRoom otherRoom : room.connections) {
483                    Direction dir = Direction.getCardinalDirection(otherRoom.cellx - room.cellx, otherRoom.celly - room.celly);
484                    digPath(randomWallPosition(room, dir), randomWallPosition(otherRoom, dir.opposite()));
485                }
486            }
487        }
488    }
489
490    private class Magnitude {
491
492        public Direction dir;
493        public int distance;
494
495        public Magnitude(Direction dir, int distance) {
496            this.dir = dir;
497            this.distance = distance;
498        }
499    }
500}