- Read the question carefully (twice).
- Break the task into the smallest steps.
- Sketch or write pseudocode before coding.
- Start small — test as you go.
- Check your solution with different cases.
Overview
In this problem set, you will design and implement a procedural dungeon generator that produces 2D roguelike maps. The generator must create a playable dungeon layout that is random, but fair, ensuring key features such as rooms, corridors, walls, and connectivity.
The focus is not just on randomization, but on algorithms, data structures, and problem-solving techniques to generate complex systems.
Learning Objectives
By completing this problem set, you will:
- Practice designing and implementing algorithms for procedural generation.
- Use randomization responsibly to generate diverse but playable outputs.
- Apply graph and grid-based algorithms to ensure dungeon connectivity.
- Explore techniques like BSP (Binary Space Partitioning), cellular automata, and random walk.
- Test outputs for correctness, variability, and fairness.
Requirements
Your dungeon generator must:
- Generate a 2D grid map of size N x M (e.g., 50x50).
- Include:
- Rooms (rectangular or irregular).
- Corridors connecting rooms.
- Walls separating walkable and non-walkable tiles.
- A designated start and exit point.
- Guarantee:
- Every room is reachable from the start.
- The exit is always accessible.
- No isolated spaces (connectivity is required).
- Allow seeded randomness, so the same seed produces the same map.
- Display the dungeon in ASCII or another simple 2D visualization (
#for walls,.for floor,Sfor start,Efor exit). - Optionally (challenge): Add features such as traps, treasures, or monsters.
Part 1: Grid and Representation
- Define a 2D matrix to represent the dungeon.
- Decide how you will encode walls, floors, start, exit, and other entities.
- Implement a function to print the grid in ASCII.
Deliverable:
A function print_map(grid) that shows the dungeon clearly.
Part 2: Room Placement
- Write an algorithm to place non-overlapping rooms on the grid.
- Ensure randomness in size, number, and placement of rooms.
Deliverable:
A dungeon with at least 5 randomly placed rooms visible.
Test Cases:
- A 50x50 grid should display 5–10 rooms.
- Rooms must not overlap.
Part 3: Corridors and Connectivity
- Connect rooms with corridors using algorithms such as:
- Minimum Spanning Tree (MST) on room centers.
- Random walk corridors.
- Guarantee connectivity between all rooms.
Deliverable:
Dungeon with rooms connected by corridors.
Test Cases:
- Confirm that all rooms are reachable from any room (use BFS or DFS to test).
Part 4: Start and Exit Placement
- Place the start point (
S) and exit point (E) in distant locations (e.g., farthest rooms apart). - Verify connectivity.
Deliverable:
A dungeon with start and exit clearly marked.
Part 5: Randomness and Seeds
- Implement seeded randomness.
- Inputting the same seed should always generate the same dungeon.
Deliverable:
Run generator with seed 42 and show that repeated runs produce identical maps.
Part 6: Extra Features (Optional Challenges)
- Add secret rooms or hidden doors.
- Add treasures (
<strong>T</strong>) or traps (X) randomly in the dungeon. - Use cellular automata to generate “cave-like” sections.
- Add a pathfinding function that finds the shortest path from start to exit.
Example Output (ASCII Map)
##################################################
#....................#############################
#....................#..............##############
#....................#..............##############
#######.##############..............##############
S.####################..............##############
#....................#..............##############
#....................#..............##############
#....................#..............##############
#....................######.######################
#...............................................E.
##################################################
##################################################
Evaluation Criteria
- Correctness: Does the generator create valid, playable dungeons?
- Randomness: Are maps varied but still fair?
- Connectivity: Can the player always reach the exit?
- Clarity: Is the output map readable and meaningful?
- Advanced features (optional): Are there extras like treasures, traps, or secret areas?
import random
# Constants for map representation
WALL = "#"
FLOOR = "."
START = "S"
EXIT = "E"
class Dungeon:
def __init__(self, width=50, height=25, seed=None):
self.width = width
self.height = height
self.grid = [[WALL for _ in range(width)] for _ in range(height)]
if seed is not None:
random.seed(seed)
self.rooms = [] # will hold room rectangles: (x, y, w, h)
self.start = None
self.exit = None
def carve_room(self, x, y, w, h):
"""Carve a rectangular room into the grid."""
for i in range(y, y + h):
for j in range(x, x + w):
if 0 < i < self.height - 1 and 0 < j < self.width - 1:
self.grid[i][j] = FLOOR
def add_room(self, min_size=4, max_size=8, max_attempts=200):
"""Try to add a room without overlapping existing ones."""
for _ in range(max_attempts):
w = random.randint(min_size, max_size)
h = random.randint(min_size, max_size)
x = random.randint(1, self.width - w - 2)
y = random.randint(1, self.height - h - 2)
new_room = (x, y, w, h)
# check overlap
if any(self.overlaps(new_room, other) for other in self.rooms):
continue
# carve into grid
self.carve_room(x, y, w, h)
self.rooms.append(new_room)
return True
return False
def overlaps(self, room1, room2):
"""Check if two rooms overlap (with a 1-tile buffer)."""
x1, y1, w1, h1 = room1
x2, y2, w2, h2 = room2
return not (x1 + w1 + 1 < x2 or x2 + w2 + 1 < x1 or
y1 + h1 + 1 < y2 or y2 + h2 + 1 < y1)
def place_start_and_exit(self):
"""Put start in the first room, exit in the farthest room."""
if not self.rooms:
return
first_room = self.rooms[0]
last_room = self.rooms[-1]
sx, sy = first_room[0] + 1, first_room[1] + 1
ex, ey = last_room[0] + last_room[2] - 2, last_room[1] + last_room[3] - 2
self.grid[sy][sx] = START
self.grid[ey][ex] = EXIT
self.start = (sx, sy)
self.exit = (ex, ey)
def generate(self, num_rooms=8):
for _ in range(num_rooms):
self.add_room()
self.place_start_and_exit()
# corridors not yet implemented (students’ task!)
def display(self):
for row in self.grid:
print("".join(row))
# Example run
if __name__ == "__main__":
dungeon = Dungeon(width=50, height=25, seed=42)
dungeon.generate(num_rooms=8)
dungeon.display()