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}