Dungeon generation is a fundamental part of roguelike games and procedural content generation. Here are several algorithms for generating dungeons, caves, and other game environments in Java.

Dungeon Generation Algorithms Overview

Common Algorithms

1. Random Walk - Simple but unpredictable
2. Binary Space Partitioning (BSP) - Organized room placement
3. Cellular Automata - Natural-looking cave systems
4. Drunkard's Walk - Organic corridor generation
5. Wave Function Collapse - Pattern-based generation

Basic Random Dungeon Generator

Example 1: Simple Random Room Placement

import java.util.*; import java.awt.Point; public class SimpleDungeonGenerator { private final int width; private final int height; private final char[][] map; private final Random random; // Tile types public static final char WALL = '#'; public static final char FLOOR = '.'; public static final char DOOR = '+'; public static final char CORRIDOR = ','; public static final char WATER = '~'; public static final char EMPTY = ' '; public SimpleDungeonGenerator(int width, int height, long seed) { this.width = width; this.height = height; this.map = new char[height][width]; this.random = new Random(seed); initializeMap(); } private void initializeMap() { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { map[y][x] = WALL; } } } public void generateRandomRooms(int minRooms, int maxRooms, int minRoomSize, int maxRoomSize) { int roomCount = random.nextInt(maxRooms - minRooms + 1) + minRooms; List<Room> rooms = new ArrayList<>(); for (int i = 0; i < roomCount; i++) { int attempts = 0; boolean placed = false; while (attempts < 100 && !placed) { int roomWidth = random.nextInt(maxRoomSize - minRoomSize + 1) + minRoomSize; int roomHeight = random.nextInt(maxRoomSize - minRoomSize + 1) + minRoomSize; int x = random.nextInt(width - roomWidth - 2) + 1; int y = random.nextInt(height - roomHeight - 2) + 1; Room newRoom = new Room(x, y, roomWidth, roomHeight); if (!intersectsAnyRoom(newRoom, rooms)) { carveRoom(newRoom); rooms.add(newRoom); placed = true; } attempts++; } } // Connect rooms with corridors connectRooms(rooms); // Add some water features addWaterFeatures(5); } private boolean intersectsAnyRoom(Room newRoom, List<Room> rooms) { for (Room room : rooms) { if (newRoom.intersects(room, 1)) { // 1 tile padding return true; } } return false; } private void carveRoom(Room room) { for (int y = room.y + 1; y < room.y + room.height - 1; y++) { for (int x = room.x + 1; x < room.x + room.width - 1; x++) { map[y][x] = FLOOR; } } } private void connectRooms(List<Room> rooms) { if (rooms.size() < 2) return; // Connect each room to the next one for (int i = 0; i < rooms.size() - 1; i++) { Room room1 = rooms.get(i); Room room2 = rooms.get(i + 1); Point center1 = room1.getCenter(); Point center2 = room2.getCenter(); // 50% chance to do L-shaped corridor, 50% straight then turn if (random.nextBoolean()) { createLShapedCorridor(center1.x, center1.y, center2.x, center2.y); } else { createCorridor(center1.x, center1.y, center2.x, center2.y); } } // Add some random connections for loops for (int i = 0; i < rooms.size() / 2; i++) { int idx1 = random.nextInt(rooms.size()); int idx2 = random.nextInt(rooms.size()); if (idx1 != idx2) { Room room1 = rooms.get(idx1); Room room2 = rooms.get(idx2); Point center1 = room1.getCenter(); Point center2 = room2.getCenter(); createCorridor(center1.x, center1.y, center2.x, center2.y); } } } private void createCorridor(int x1, int y1, int x2, int y2) { // Horizontal then vertical createHorizontalCorridor(x1, x2, y1); createVerticalCorridor(y1, y2, x2); } private void createLShapedCorridor(int x1, int y1, int x2, int y2) { // Vertical then horizontal createVerticalCorridor(y1, y2, x1); createHorizontalCorridor(x1, x2, y2); } private void createHorizontalCorridor(int x1, int x2, int y) { int start = Math.min(x1, x2); int end = Math.max(x1, x2); for (int x = start; x <= end; x++) { if (map[y][x] == WALL) { map[y][x] = CORRIDOR; } // Add walls above and below if (y > 0 && map[y-1][x] == EMPTY) map[y-1][x] = WALL; if (y < height-1 && map[y+1][x] == EMPTY) map[y+1][x] = WALL; } } private void createVerticalCorridor(int y1, int y2, int x) { int start = Math.min(y1, y2); int end = Math.max(y1, y2); for (int y = start; y <= end; y++) { if (map[y][x] == WALL) { map[y][x] = CORRIDOR; } // Add walls left and right if (x > 0 && map[y][x-1] == EMPTY) map[y][x-1] = WALL; if (x < width-1 && map[y][x+1] == EMPTY) map[y][x+1] = WALL; } } private void addWaterFeatures(int count) { for (int i = 0; i < count; i++) { int x = random.nextInt(width - 4) + 2; int y = random.nextInt(height - 4) + 2; if (map[y][x] == FLOOR || map[y][x] == CORRIDOR) { floodFillWater(x, y, 5 + random.nextInt(10)); } } } private void floodFillWater(int startX, int startY, int maxTiles) { Queue<Point> queue = new LinkedList<>(); Set<Point> visited = new HashSet<>(); queue.add(new Point(startX, startY)); int filled = 0; while (!queue.isEmpty() && filled < maxTiles) { Point p = queue.poll(); if (visited.contains(p)) continue; int x = p.x, y = p.y; if (x < 1 || x >= width-1 || y < 1 || y >= height-1) continue; if (map[y][x] == FLOOR || map[y][x] == CORRIDOR) { map[y][x] = WATER; filled++; visited.add(p); // Add neighbors queue.add(new Point(x+1, y)); queue.add(new Point(x-1, y)); queue.add(new Point(x, y+1)); queue.add(new Point(x, y-1)); } } } public void printMap() { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { System.out.print(map[y][x]); } System.out.println(); } } public char[][] getMap() { return map; } // Room class public static class Room { public final int x, y, width, height; public Room(int x, int y, int width, int height) { this.x = x; this.y = y; this.width = width; this.height = height; } public boolean intersects(Room other, int padding) { return x - padding < other.x + other.width && x + width + padding > other.x && y - padding < other.y + other.height && y + height + padding > other.y; } public Point getCenter() { return new Point(x + width / 2, y + height / 2); } } public static void main(String[] args) { SimpleDungeonGenerator generator = new SimpleDungeonGenerator(80, 40, System.currentTimeMillis()); generator.generateRandomRooms(8, 15, 4, 8); generator.printMap(); } }

Binary Space Partitioning (BSP) Dungeon

Example 2: BSP-Based Dungeon Generator

import java.util.*; import java.awt.Rectangle; public class BSPDungeonGenerator { private final int width; private final int height; private final char[][] map; private final Random random; private List<Room> rooms; private List<Corridor> corridors; public BSPDungeonGenerator(int width, int height, long seed) { this.width = width; this.height = height; this.map = new char[height][width]; this.random = new Random(seed); this.rooms = new ArrayList<>(); this.corridors = new ArrayList<>(); initializeMap(); } private void initializeMap() { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { map[y][x] = SimpleDungeonGenerator.WALL; } } } public void generateBSPDungeon(int minRoomSize, int maxRoomSize, int splitAttempts) { // Start with the entire dungeon as one partition List<Partition> partitions = new ArrayList<>(); partitions.add(new Partition(1, 1, width - 2, height - 2)); // Recursively split partitions for (int i = 0; i < splitAttempts; i++) { List<Partition> newPartitions = new ArrayList<>(); for (Partition partition : partitions) { if (shouldSplit(partition, minRoomSize)) { Partition[] children = splitPartition(partition); if (children != null) { newPartitions.add(children[0]); newPartitions.add(children[1]); } else { newPartitions.add(partition); } } else { newPartitions.add(partition); } } partitions = newPartitions; } // Create rooms in leaf partitions for (Partition partition : partitions) { if (partition.isLeaf()) { Room room = createRoomInPartition(partition, minRoomSize, maxRoomSize); if (room != null) { rooms.add(room); carveRoom(room); } } } // Build BSP tree and connect rooms BSPTree tree = buildBSPTree(partitions); connectBSPRooms(tree); // Add some variety addDoors(); addRandomFeatures(); } private boolean shouldSplit(Partition partition, int minRoomSize) { // Only split if both resulting partitions would be large enough boolean canSplitHorizontal = partition.height > minRoomSize * 2; boolean canSplitVertical = partition.width > minRoomSize * 2; if (!canSplitHorizontal && !canSplitVertical) return false; if (canSplitHorizontal && canSplitVertical) { return random.nextBoolean(); // Random choice } return canSplitHorizontal; } private Partition[] splitPartition(Partition partition) { boolean splitHorizontal = partition.height > partition.width; if (splitHorizontal) { // Split horizontally int splitPoint = random.nextInt(partition.height - 4) + 2; Partition top = new Partition(partition.x, partition.y, partition.width, splitPoint); Partition bottom = new Partition(partition.x, partition.y + splitPoint, partition.width, partition.height - splitPoint); return new Partition[]{top, bottom}; } else { // Split vertically int splitPoint = random.nextInt(partition.width - 4) + 2; Partition left = new Partition(partition.x, partition.y, splitPoint, partition.height); Partition right = new Partition(partition.x + splitPoint, partition.y, partition.width - splitPoint, partition.height); return new Partition[]{left, right}; } } private Room createRoomInPartition(Partition partition, int minSize, int maxSize) { int roomWidth = Math.min(random.nextInt(maxSize - minSize + 1) + minSize, partition.width - 2); int roomHeight = Math.min(random.nextInt(maxSize - minSize + 1) + minSize, partition.height - 2); if (roomWidth < minSize || roomHeight < minSize) return null; int roomX = partition.x + random.nextInt(partition.width - roomWidth); int roomY = partition.y + random.nextInt(partition.height - roomHeight); return new Room(roomX, roomY, roomWidth, roomHeight); } private BSPTree buildBSPTree(List<Partition> partitions) { // This is a simplified version - in practice you'd build the tree during splitting List<BSPTree> trees = new ArrayList<>(); for (Partition partition : partitions) { trees.add(new BSPTree(partition)); } // Combine trees (simplified) while (trees.size() > 1) { BSPTree tree1 = trees.remove(0); BSPTree tree2 = trees.remove(0); BSPTree parent = new BSPTree(new Partition( Math.min(tree1.partition.x, tree2.partition.x), Math.min(tree1.partition.y, tree2.partition.y), Math.max(tree1.partition.x + tree1.partition.width, tree2.partition.x + tree2.partition.width) - Math.min(tree1.partition.x, tree2.partition.x), Math.max(tree1.partition.y + tree1.partition.height, tree2.partition.y + tree2.partition.height) - Math.min(tree1.partition.y, tree2.partition.y) )); parent.left = tree1; parent.right = tree2; trees.add(parent); } return trees.get(0); } private void connectBSPRooms(BSPTree tree) { if (tree == null || tree.isLeaf()) return; connectBSPRooms(tree.left); connectBSPRooms(tree.right); // Connect rooms from left and right subtrees Room leftRoom = findRandomRoomInTree(tree.left); Room rightRoom = findRandomRoomInTree(tree.right); if (leftRoom != null && rightRoom != null) { Point center1 = leftRoom.getCenter(); Point center2 = rightRoom.getCenter(); Corridor corridor = new Corridor(center1, center2); corridors.add(corridor); carveCorridor(corridor); } } private Room findRandomRoomInTree(BSPTree tree) { if (tree == null) return null; if (tree.isLeaf()) { // Find a room in this partition for (Room room : rooms) { if (tree.partition.contains(room.x, room.y, room.width, room.height)) { return room; } } return null; } // Randomly choose left or right subtree return random.nextBoolean() ? findRandomRoomInTree(tree.left) : findRandomRoomInTree(tree.right); } private void carveRoom(Room room) { for (int y = room.y; y < room.y + room.height; y++) { for (int x = room.x; x < room.x + room.width; x++) { if (x >= 0 && x < width && y >= 0 && y < height) { map[y][x] = SimpleDungeonGenerator.FLOOR; } } } } private void carveCorridor(Corridor corridor) { Point start = corridor.start; Point end = corridor.end; // L-shaped corridor if (random.nextBoolean()) { // Horizontal then vertical for (int x = Math.min(start.x, end.x); x <= Math.max(start.x, end.x); x++) { setFloorSafe(x, start.y); } for (int y = Math.min(start.y, end.y); y <= Math.max(start.y, end.y); y++) { setFloorSafe(end.x, y); } } else { // Vertical then horizontal for (int y = Math.min(start.y, end.y); y <= Math.max(start.y, end.y); y++) { setFloorSafe(start.x, y); } for (int x = Math.min(start.x, end.x); x <= Math.max(start.x, end.x); x++) { setFloorSafe(x, end.y); } } } private void setFloorSafe(int x, int y) { if (x >= 0 && x < width && y >= 0 && y < height) { map[y][x] = SimpleDungeonGenerator.CORRIDOR; } } private void addDoors() { for (Corridor corridor : corridors) { // Find where corridor meets rooms and place doors List<Point> potentialDoorLocations = findCorridorEnds(corridor); for (Point doorLoc : potentialDoorLocations) { if (isGoodDoorLocation(doorLoc.x, doorLoc.y)) { map[doorLoc.y][doorLoc.x] = SimpleDungeonGenerator.DOOR; } } } } private List<Point> findCorridorEnds(Corridor corridor) { List<Point> ends = new ArrayList<>(); // Simplified - check points near room boundaries ends.add(corridor.start); ends.add(corridor.end); return ends; } private boolean isGoodDoorLocation(int x, int y) { // Check if this location connects a corridor to a room if (x <= 0 || x >= width-1 || y <= 0 || y >= height-1) return false; int floorCount = 0; int wallCount = 0; for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (dx == 0 && dy == 0) continue; char tile = map[y+dy][x+dx]; if (tile == SimpleDungeonGenerator.FLOOR || tile == SimpleDungeonGenerator.CORRIDOR) { floorCount++; } else if (tile == SimpleDungeonGenerator.WALL) { wallCount++; } } } return floorCount >= 2 && wallCount >= 2; } private void addRandomFeatures() { // Add some water or other features int featureCount = random.nextInt(3) + 1; for (int i = 0; i < featureCount; i++) { int x = random.nextInt(width - 4) + 2; int y = random.nextInt(height - 4) + 2; if (map[y][x] == SimpleDungeonGenerator.FLOOR) { map[y][x] = SimpleDungeonGenerator.WATER; } } } public void printMap() { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { System.out.print(map[y][x]); } System.out.println(); } } // Data classes public static class Partition { public final int x, y, width, height; public Partition(int x, int y, int width, int height) { this.x = x; this.y = y; this.width = width; this.height = height; } public boolean isLeaf() { return true; // Simplified } public boolean contains(int rx, int ry, int rw, int rh) { return x <= rx && y <= ry && x + width >= rx + rw && y + height >= ry + rh; } } public static class BSPTree { public Partition partition; public BSPTree left, right; public BSPTree(Partition partition) { this.partition = partition; } public boolean isLeaf() { return left == null && right == null; } } public static class Corridor { public final Point start, end; public Corridor(Point start, Point end) { this.start = start; this.end = end; } } public static class Room extends SimpleDungeonGenerator.Room { public Room(int x, int y, int width, int height) { super(x, y, width, height); } } public static void main(String[] args) { BSPDungeonGenerator generator = new BSPDungeonGenerator(60, 30, System.currentTimeMillis()); generator.generateBSPDungeon(4, 8, 5); generator.printMap(); } }

Cellular Automata Cave Generator

Example 3: Cave System Generator

import java.util.*; public class CaveGenerator { private final int width; private final int height; private final char[][] map; private final Random random; private static final double INITIAL_WALL_CHANCE = 0.45; private static final int BIRTH_LIMIT = 4; private static final int DEATH_LIMIT = 3; private static final int SMOOTHING_STEPS = 5; public CaveGenerator(int width, int height, long seed) { this.width = width; this.height = height; this.map = new char[height][width]; this.random = new Random(seed); } public void generateCaveSystem() { initializeRandomMap(); // Apply cellular automata rules for (int i = 0; i < SMOOTHING_STEPS; i++) { smoothMap(); } // Remove small isolated caves removeSmallCaves(15); // Ensure connectivity ensureConnectivity(); // Add some variety addCaveFeatures(); } private void initializeRandomMap() { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { // Borders are always walls if (x == 0 || y == 0 || x == width - 1 || y == height - 1) { map[y][x] = SimpleDungeonGenerator.WALL; } else { map[y][x] = random.nextDouble() < INITIAL_WALL_CHANCE ? SimpleDungeonGenerator.WALL : SimpleDungeonGenerator.FLOOR; } } } } private void smoothMap() { char[][] newMap = new char[height][width]; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { int wallNeighbors = countWallNeighbors(x, y); if (map[y][x] == SimpleDungeonGenerator.WALL) { // Wall cell dies if too few wall neighbors newMap[y][x] = (wallNeighbors < DEATH_LIMIT) ? SimpleDungeonGenerator.FLOOR : SimpleDungeonGenerator.WALL; } else { // Floor cell becomes wall if enough wall neighbors newMap[y][x] = (wallNeighbors > BIRTH_LIMIT) ? SimpleDungeonGenerator.WALL : SimpleDungeonGenerator.FLOOR; } } } // Copy new map back for (int y = 0; y < height; y++) { System.arraycopy(newMap[y], 0, map[y], 0, width); } } private int countWallNeighbors(int x, int y) { int wallCount = 0; for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (dx == 0 && dy == 0) continue; int nx = x + dx; int ny = y + dy; if (nx >= 0 && nx < width && ny >= 0 && ny < height) { if (map[ny][nx] == SimpleDungeonGenerator.WALL) { wallCount++; } } else { // Count borders as walls wallCount++; } } } return wallCount; } private void removeSmallCaves(int minCaveSize) { List<Set<Point>> caves = findCaves(); for (Set<Point> cave : caves) { if (cave.size() < minCaveSize) { // Fill small cave with walls for (Point p : cave) { map[p.y][p.x] = SimpleDungeonGenerator.WALL; } } } } private List<Set<Point>> findCaves() { List<Set<Point>> caves = new ArrayList<>(); boolean[][] visited = new boolean[height][width]; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { if (!visited[y][x] && map[y][x] == SimpleDungeonGenerator.FLOOR) { Set<Point> cave = floodFillCave(x, y, visited); caves.add(cave); } } } return caves; } private Set<Point> floodFillCave(int startX, int startY, boolean[][] visited) { Set<Point> cave = new HashSet<>(); Queue<Point> queue = new LinkedList<>(); queue.add(new Point(startX, startY)); while (!queue.isEmpty()) { Point p = queue.poll(); int x = p.x, y = p.y; if (x < 0 || x >= width || y < 0 || y >= height || visited[y][x]) continue; if (map[y][x] != SimpleDungeonGenerator.FLOOR) continue; visited[y][x] = true; cave.add(p); queue.add(new Point(x+1, y)); queue.add(new Point(x-1, y)); queue.add(new Point(x, y+1)); queue.add(new Point(x, y-1)); } return cave; } private void ensureConnectivity() { List<Set<Point>> caves = findCaves(); if (caves.size() <= 1) return; // Already connected or no caves // Find the largest cave Set<Point> mainCave = Collections.max(caves, Comparator.comparing(Set::size)); caves.remove(mainCave); // Connect other caves to main cave for (Set<Point> cave : caves) { connectCaves(mainCave, cave); } } private void connectCaves(Set<Point> cave1, Set<Point> cave2) { // Find closest points between caves Point closest1 = null; Point closest2 = null; double minDistance = Double.MAX_VALUE; for (Point p1 : cave1) { for (Point p2 : cave2) { double distance = Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); if (distance < minDistance) { minDistance = distance; closest1 = p1; closest2 = p2; } } } if (closest1 != null && closest2 != null) { // Create corridor between closest points createCorridor(closest1.x, closest1.y, closest2.x, closest2.y); } } private void createCorridor(int x1, int y1, int x2, int y2) { int currentX = x1; int currentY = y1; while (currentX != x2 || currentY != y2) { if (random.nextBoolean() && currentX != x2) { currentX += (x2 > currentX) ? 1 : -1; } else if (currentY != y2) { currentY += (y2 > currentY) ? 1 : -1; } if (currentX >= 0 && currentX < width && currentY >= 0 && currentY < height) { map[currentY][currentX] = SimpleDungeonGenerator.CORRIDOR; // Add some width to corridor if (random.nextDouble() < 0.3) { for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { int nx = currentX + dx; int ny = currentY + dy; if (nx >= 0 && nx < width && ny >= 0 && ny < height && map[ny][nx] == SimpleDungeonGenerator.WALL) { map[ny][nx] = SimpleDungeonGenerator.CORRIDOR; } } } } } } } private void addCaveFeatures() { addWaterPools(3); addStalactites(10); addTreasureRooms(2); } private void addWaterPools(int count) { for (int i = 0; i < count; i++) { int startX = random.nextInt(width - 4) + 2; int startY = random.nextInt(height - 4) + 2; if (map[startY][startX] == SimpleDungeonGenerator.FLOOR) { floodFillWater(startX, startY, 8 + random.nextInt(15)); } } } private void floodFillWater(int startX, int startY, int maxTiles) { Queue<Point> queue = new LinkedList<>(); Set<Point> visited = new HashSet<>(); queue.add(new Point(startX, startY)); int filled = 0; while (!queue.isEmpty() && filled < maxTiles) { Point p = queue.poll(); if (visited.contains(p)) continue; int x = p.x, y = p.y; if (x < 1 || x >= width-1 || y < 1 || y >= height-1) continue; if (map[y][x] == SimpleDungeonGenerator.FLOOR || map[y][x] == SimpleDungeonGenerator.CORRIDOR) { map[y][x] = SimpleDungeonGenerator.WATER; filled++; visited.add(p); // Add neighbors with some randomness if (random.nextDouble() < 0.7) queue.add(new Point(x+1, y)); if (random.nextDouble() < 0.7) queue.add(new Point(x-1, y)); if (random.nextDouble() < 0.7) queue.add(new Point(x, y+1)); if (random.nextDouble() < 0.7) queue.add(new Point(x, y-1)); } } } private void addStalactites(int count) { for (int i = 0; i < count; i++) { int x = random.nextInt(width - 2) + 1; int y = random.nextInt(height - 2) + 1; // Place stalactite if surrounded by walls (on ceiling) if (map[y][x] == SimpleDungeonGenerator.FLOOR && map[y-1][x] == SimpleDungeonGenerator.WALL) { map[y][x] = '^'; // Stalactite } // Place stalagmite if surrounded by walls (on floor) if (map[y][x] == SimpleDungeonGenerator.FLOOR && map[y+1][x] == SimpleDungeonGenerator.WALL) { map[y][x] = 'v'; // Stalagmite } } } private void addTreasureRooms(int count) { for (int i = 0; i < count; i++) { // Find a dead-end corridor or isolated area Point location = findTreasureLocation(); if (location != null) { map[location.y][location.x] = 'T'; // Treasure // Add some protective walls for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { int nx = location.x + dx; int ny = location.y + dy; if (nx >= 0 && nx < width && ny >= 0 && ny < height && map[ny][nx] == SimpleDungeonGenerator.FLOOR) { map[ny][nx] = SimpleDungeonGenerator.WALL; } } } } } } private Point findTreasureLocation() { // Look for dead ends for (int y = 1; y < height - 1; y++) { for (int x = 1; x < width - 1; x++) { if (map[y][x] == SimpleDungeonGenerator.FLOOR || map[y][x] == SimpleDungeonGenerator.CORRIDOR) { int openNeighbors = 0; for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (dx == 0 && dy == 0) continue; if (Math.abs(dx) + Math.abs(dy) != 1) continue; // Only cardinal directions int nx = x + dx; int ny = y + dy; if (map[ny][nx] == SimpleDungeonGenerator.FLOOR || map[ny][nx] == SimpleDungeonGenerator.CORRIDOR) { openNeighbors++; } } } if (openNeighbors == 1) { // Dead end return new Point(x, y); } } } } return null; } public void printMap() { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { System.out.print(map[y][x]); } System.out.println(); } } public char[][] getMap() { return map; } public static void main(String[] args) { CaveGenerator generator = new CaveGenerator(50, 25, System.currentTimeMillis()); generator.generateCaveSystem(); generator.printMap(); } }

Advanced Dungeon Features

Example 4: Multi-Level Dungeon with Special Features

import java.util.*; public class AdvancedDungeonGenerator { private final int width; private final int height; private final int levels; private final List<char[][]> maps; private final Random random; private final DungeonConfig config; public AdvancedDungeonGenerator(int width, int height, int levels, long seed, DungeonConfig config) { this.width = width; this.height = height; this.levels = levels; this.maps = new ArrayList<>(); this.random = new Random(seed); this.config = config; } public void generateMultiLevelDungeon() { for (int level = 0; level < levels; level++) { char[][] levelMap = new char[height][width]; initializeLevel(levelMap); // Choose generation method based on level if (level == 0) { generateEntranceLevel(levelMap); } else if (level == levels - 1) { generateBossLevel(levelMap); } else if (random.nextDouble() < 0.7) { generateRoomLevel(levelMap); } else { generateCaveLevel(levelMap); } // Add level-specific features addLevelFeatures(levelMap, level); maps.add(levelMap); } // Connect levels with stairs connectLevels(); // Add monsters and treasures populateDungeon(); } private void generateEntranceLevel(char[][] map) { SimpleDungeonGenerator generator = new SimpleDungeonGenerator(width, height, random.nextLong()); generator.generateRandomRooms(3, 6, 5, 8); char[][] generatedMap = generator.getMap(); // Copy to our map for (int y = 0; y < height; y++) { System.arraycopy(generatedMap[y], 0, map[y], 0, width); } // Add entrance addEntrance(map); } private void generateBossLevel(char[][] map) { BSPDungeonGenerator generator = new BSPDungeonGenerator(width, height, random.nextLong()); generator.generateBSPDungeon(6, 12, 4); char[][] generatedMap = generator.getMap(); for (int y = 0; y < height; y++) { System.arraycopy(generatedMap[y], 0, map[y], 0, width); } // Add boss room addBossRoom(map); } private void generateRoomLevel(char[][] map) { SimpleDungeonGenerator generator = new SimpleDungeonGenerator(width, height, random.nextLong()); generator.generateRandomRooms(5, 10, 4, 7); char[][] generatedMap = generator.getMap(); for (int y = 0; y < height; y++) { System.arraycopy(generatedMap[y], 0, map[y], 0, width); } } private void generateCaveLevel(char[][] map) { CaveGenerator generator = new CaveGenerator(width, height, random.nextLong()); generator.generateCaveSystem(); char[][] generatedMap = generator.getMap(); for (int y = 0; y < height; y++) { System.arraycopy(generatedMap[y], 0, map[y], 0, width); } } private void addEntrance(char[][] map) { // Place entrance at top of map for (int x = width / 2 - 2; x <= width / 2 + 2; x++) { map[0][x] = 'E'; // Entrance map[1][x] = SimpleDungeonGenerator.FLOOR; } } private void addBossRoom(char[][] map) { // Create large central room for boss int roomWidth = 10; int roomHeight = 8; int roomX = (width - roomWidth) / 2; int roomY = (height - roomHeight) / 2; // Carve boss room for (int y = roomY; y < roomY + roomHeight; y++) { for (int x = roomX; x < roomX + roomWidth; x++) { if (y >= 0 && y < height && x >= 0 && x < width) { if (y == roomY || y == roomY + roomHeight - 1 || x == roomX || x == roomX + roomWidth - 1) { map[y][x] = SimpleDungeonGenerator.WALL; } else { map[y][x] = SimpleDungeonGenerator.FLOOR; } } } } // Place boss in center map[roomY + roomHeight / 2][roomX + roomWidth / 2] = 'B'; // Add treasure near boss map[roomY + roomHeight / 2][roomX + roomWidth / 2 - 2] = 'T'; map[roomY + roomHeight / 2][roomX + roomWidth / 2 + 2] = 'T'; } private void addLevelFeatures(char[][] map, int level) { // Add stairs addStairs(map, level); // Add water/lava based on depth if (level > levels / 2) { addLavaPools(map, 2 + level / 2); } else { addWaterPools(map, 2); } // Add traps in deeper levels if (level > 1) { addTraps(map, level); } // Add secret rooms occasionally if (random.nextDouble() < 0.3) { addSecretRoom(map); } } private void addStairs(char[][] map, int level) { // Find suitable location for stairs Point stairLocation = findStairLocation(map); if (stairLocation != null) { if (level < levels - 1) { map[stairLocation.y][stairLocation.x] = '>'; // Down stairs } if (level > 0) { // Also add up stairs from previous level char[][] prevMap = maps.get(level - 1); Point upStairLocation = findStairLocation(prevMap); if (upStairLocation != null) { prevMap[upStairLocation.y][upStairLocation.x] = '<'; // Up stairs } } } } private Point findStairLocation(char[][] map) { // Look for a floor tile with only one neighbor (dead end) for (int y = 1; y < height - 1; y++) { for (int x = 1; x < width - 1; x++) { if (map[y][x] == SimpleDungeonGenerator.FLOOR || map[y][x] == SimpleDungeonGenerator.CORRIDOR) { int neighbors = 0; for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (Math.abs(dx) + Math.abs(dy) != 1) continue; if (map[y+dy][x+dx] == SimpleDungeonGenerator.FLOOR || map[y+dy][x+dx] == SimpleDungeonGenerator.CORRIDOR) { neighbors++; } } } if (neighbors == 1) { return new Point(x, y); } } } } // If no dead end found, use any floor tile for (int y = 1; y < height - 1; y++) { for (int x = 1; x < width - 1; x++) { if (map[y][x] == SimpleDungeonGenerator.FLOOR) { return new Point(x, y); } } } return null; } private void addLavaPools(char[][] map, int count) { for (int i = 0; i < count; i++) { int x = random.nextInt(width - 4) + 2; int y = random.nextInt(height - 4) + 2; if (map[y][x] == SimpleDungeonGenerator.FLOOR) { floodFillLava(map, x, y, 5 + random.nextInt(8)); } } } private void floodFillLava(char[][] map, int startX, int startY, int maxTiles) { Queue<Point> queue = new LinkedList<>(); Set<Point> visited = new HashSet<>(); queue.add(new Point(startX, startY)); int filled = 0; while (!queue.isEmpty() && filled < maxTiles) { Point p = queue.poll(); if (visited.contains(p)) continue; int x = p.x, y = p.y; if (x < 1 || x >= width-1 || y < 1 || y >= height-1) continue; if (map[y][x] == SimpleDungeonGenerator.FLOOR || map[y][x] == SimpleDungeonGenerator.CORRIDOR) { map[y][x] = 'L'; // Lava filled++; visited.add(p); if (random.nextDouble() < 0.6) queue.add(new Point(x+1, y)); if (random.nextDouble() < 0.6) queue.add(new Point(x-1, y)); if (random.nextDouble() < 0.6) queue.add(new Point(x, y+1)); if (random.nextDouble() < 0.6) queue.add(new Point(x, y-1)); } } } private void addTraps(char[][] map, int level) { int trapCount = level / 2; for (int i = 0; i < trapCount; i++) { Point trapLocation = findTrapLocation(map); if (trapLocation != null) { map[trapLocation.y][trapLocation.x] = 'X'; // Trap } } } private Point findTrapLocation(char[][] map) { // Place traps in corridors List<Point> corridorTiles = new ArrayList<>(); for (int y = 1; y < height - 1; y++) { for (int x = 1; x < width - 1; x++) { if (map[y][x] == SimpleDungeonGenerator.CORRIDOR) { corridorTiles.add(new Point(x, y)); } } } if (!corridorTiles.isEmpty()) { return corridorTiles.get(random.nextInt(corridorTiles.size())); } return null; } private void addSecretRoom(char[][] map) { // Look for a wall that could hide a secret room for (int y = 2; y < height - 2; y++) { for (int x = 2; x < width - 2; x++) { if (map[y][x] == SimpleDungeonGenerator.WALL && isGoodSecretRoomLocation(map, x, y)) { // Carve secret room carveSecretRoom(map, x, y); return; } } } } private boolean isGoodSecretRoomLocation(char[][] map, int x, int y) { // Check if this wall is between two floor areas boolean hasFloorNeighbor = false; for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (Math.abs(dx) + Math.abs(dy) != 1) continue; if (map[y+dy][x+dx] == SimpleDungeonGenerator.FLOOR) { hasFloorNeighbor = true; break; } } } return hasFloorNeighbor; } private void carveSecretRoom(char[][] map, int x, int y) { int roomSize = 3; // Determine direction to carve for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (Math.abs(dx) + Math.abs(dy) != 1) continue; if (map[y+dy][x+dx] == SimpleDungeonGenerator.FLOOR) { // Carve in opposite direction int carveX = x - dx * roomSize; int carveY = y - dy * roomSize; if (carveX >= 1 && carveX < width-1 && carveY >= 1 && carveY < height-1) { // Carve small room for (int ry = carveY - 1; ry <= carveY + 1; ry++) { for (int rx = carveX - 1; rx <= carveX + 1; rx++) { if (rx >= 0 && rx < width && ry >= 0 && ry < height) { map[ry][rx] = SimpleDungeonGenerator.FLOOR; } } } // Add treasure map[carveY][carveX] = 'T'; // Create hidden door map[y][x] = 'S'; // Secret door return; } } } } } private void connectLevels() { // Stairs are already placed in addLevelFeatures // This method could handle special connections between levels } private void populateDungeon() { for (int level = 0; level < levels; level++) { char[][] map = maps.get(level); populateLevel(map, level); } } private void populateLevel(char[][] map, int level) { int monsterCount = config.baseMonsters + level * 2; int treasureCount = config.baseTreasure + level; // Place monsters for (int i = 0; i < monsterCount; i++) { Point location = findMonsterLocation(map); if (location != null) { char monsterType = getMonsterTypeForLevel(level); map[location.y][location.x] = monsterType; } } // Place treasures for (int i = 0; i < treasureCount; i++) { Point location = findTreasureLocation(map); if (location != null) { map[location.y][location.x] = 'T'; } } } private Point findMonsterLocation(char[][] map) { List<Point> floorTiles = new ArrayList<>(); for (int y = 1; y < height - 1; y++) { for (int x = 1; x < width - 1; x++) { if (map[y][x] == SimpleDungeonGenerator.FLOOR || map[y][x] == SimpleDungeonGenerator.CORRIDOR) { floorTiles.add(new Point(x, y)); } } } if (!floorTiles.isEmpty()) { return floorTiles.get(random.nextInt(floorTiles.size())); } return null; } private Point findTreasureLocation(char[][] map) { // Prefer dead ends for treasure Point deadEnd = findDeadEnd(map); if (deadEnd != null) { return deadEnd; } return findMonsterLocation(map); // Fallback to any floor tile } private Point findDeadEnd(char[][] map) { for (int y = 1; y < height - 1; y++) { for (int x = 1; x < width - 1; x++) { if (map[y][x] == SimpleDungeonGenerator.FLOOR || map[y][x] == SimpleDungeonGenerator.CORRIDOR) { int neighbors = 0; for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { if (Math.abs(dx) + Math.abs(dy) != 1) continue; if (map[y+dy][x+dx] == SimpleDungeonGenerator.FLOOR || map[y+dy][x+dx] == SimpleDungeonGenerator.CORRIDOR) { neighbors++; } } } if (neighbors == 1) { return new Point(x, y); } } } } return null; } private char getMonsterTypeForLevel(int level) { if (level == 0) return 'g'; // Goblin if (level == 1) return 'o'; // Orc if (level == 2) return 't'; // Troll if (level == 3) return 'd'; // Dragon return 'm'; // Generic monster } public void printLevel(int level) { if (level >= 0 && level < maps.size()) { char[][] map = maps.get(level); System.out.println("=== Level " + (level + 1) + " ==="); for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { System.out.print(map[y][x]); } System.out.println(); } } } public static class DungeonConfig { public int baseMonsters = 5; public int baseTreasure = 3; public double secretRoomChance = 0.3; public double trapChance = 0.4; } public static void main(String[] args) { DungeonConfig config = new DungeonConfig(); AdvancedDungeonGenerator generator = new AdvancedDungeonGenerator( 40, 20, 4, System.currentTimeMillis(), config); generator.generateMultiLevelDungeon(); for (int level = 0; level < 4; level++) { generator.printLevel(level); System.out.println(); } } }

Key Features and Best Practices

Algorithm Comparison

Performance Optimization Tips

1. Use efficient data structures for room and corridor tracking
2. Implement spatial partitioning for large dungeons
3. Cache frequently used random numbers
4. Use flood fill algorithms for connectivity checks
5. Limit recursion depth in BSP algorithms

Customization Options

1. Theme Variants: Castle, cave, temple, forest
2. Size Scaling: From small rooms to massive caverns
3. Feature Density: Control room count, corridor length, etc.
4. Biome Mixing: Combine different generation algorithms
5. Procedural Content: Monsters, treasures, traps based on depth

These dungeon generation algorithms provide a solid foundation for creating varied and interesting game environments that can be customized for different game styles and requirements.