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.