BYOW: Build Your Own World

A 2D procedurally generated dungeon exploration game built for UC Berkeley's CS 61B (Data Structures).

Score: 165/150 (including ambition features)

Features

Core Features

• Procedural World Generation: Random dungeon generation using rejection sampling for room placement
• Prim's Algorithm: Minimum spanning tree-based corridor connections ensuring all rooms are reachable
• WASD Movement: Smooth avatar navigation through the dungeon
• Save/Load System: Persistent game state with :Q save-and-quit functionality
• Seed-Based Generation: Same seed always produces identical worlds (deterministic)

Ambition Features (Extra Credit)

• Fog of War: 5-tile line-of-sight radius with Bresenham's algorithm for wall occlusion
• Exploration Memory: Previously explored areas shown in darkened colors
• Minimap: Real-time overhead view showing explored areas and avatar position
• New World Generation: Press R to generate a completely new random world

Technical Implementation

World Generation (WorldGenerator.java)

1. Initialize world with NOTHING tiles
2. Generate 20-35 random rooms using rejection sampling
3. Connect rooms using Prim's MST algorithm with L-shaped hallways
4. Add walls around all floor tiles

Fog of War (FogOfWar.java)

• Vision Radius: 5 tiles (Euclidean distance)
• Line of Sight: Bresenham's line algorithm to detect wall occlusion
• Three visibility states:
  • Visible: Full color (within radius + clear LoS)
  • Explored: Darkened (previously seen)
  • Unexplored: Hidden (never seen)

Data Structures Used

• ArrayList: Room storage and MST construction
• 2D Arrays: Tile map and exploration tracking
• Random with Seed: Deterministic world generation

Controls

Key	Action
W	Move Up
A	Move Left
S	Move Down
D	Move Right
F	Toggle Fog of War
M	Toggle Minimap
R	Generate New World
:Q	Save and Quit

Project Structure

src/
├── core/
│   ├── Main.java           # Game entry point and loop
│   ├── World.java          # World state management
│   ├── WorldGenerator.java # Procedural generation
│   ├── Room.java           # Room representation
│   ├── Avatar.java         # Player character
│   ├── FogOfWar.java       # Visibility system
│   ├── GameState.java      # Save/Load functionality
│   └── Minimap.java        # Overhead map display
├── tileengine/
│   ├── TERenderer.java     # Rendering engine
│   ├── TETile.java         # Tile representation
│   └── Tileset.java        # Tile definitions
└── utils/
    ├── FileUtils.java      # File I/O utilities
    └── RandomUtils.java    # Random number helpers

Algorithms

Room Placement (Rejection Sampling)

while (rooms.size() < targetRooms && attempts < MAX_ATTEMPTS) {
    Room newRoom = generateRandomRoom();
    if (!overlapsExisting(newRoom)) {
        rooms.add(newRoom);
    }
}

Hallway Connection (Prim's Algorithm)

while (!unconnected.isEmpty()) {
    // Find closest pair of (connected, unconnected) rooms
    Room nearest = findNearestUnconnected();
    createLHallway(nearestConnected, nearest);
    connected.add(nearest);
}

Line of Sight (Bresenham's Algorithm)

// Trace line from avatar to target
// Return false if any wall blocks the path
while (x != targetX || y != targetY) {
    if (tiles[x][y] == WALL) return false;
    // Step along line...
}
return true;

Running the Game

# Compile
javac -d out src/**/*.java

# Run
java -cp out core.Main

Course Information

• Course: CS 61B - Data Structures (Fall 2025)
• Institution: UC Berkeley
• Project: proj5c (Build Your Own World)

Author

Hei Shing Frick Feng

• UC Berkeley BGA Exchange Student (Fall 2025)
• GitHub: @oinani0721

License

This project was created for educational purposes as part of UC Berkeley's CS 61B curriculum.