Build Your Own World — Technical Design Document

Data

Input: A seed string of the form N#####S (e.g., N12345S), optionally followed by movement characters (e.g., N12345SWWAAD). A string beginning with L loads a previously saved world state.

Parsing:

Strip the leading N and trailing S to extract the numeric seed.
Pass the seed to java.util.Random to drive all pseudorandom decisions (room count, room positions, room sizes, connection order).
Any characters after S are interpreted as avatar movement commands (W/A/S/D).
:Q triggers a save-and-quit; the full input string up to that point is serialized to disk.

Usage: The Random object seeded by this value is the single source of randomness for the entire world generation pipeline. Every class that needs randomness receives this Random instance rather than constructing its own, ensuring deterministic replay from a given seed.

Data Structures

Each data structure below is annotated with its per-operation runtime as defined in the CS61B textbook.

`TETile[][]` — The Tile Grid (Ch. 6: 2D Arrays)

The world is ultimately rendered as a 2D array of TETile objects of size WIDTH × HEIGHT. A 2D array in Java is an array of arrays; element access at any (x, y) is Θ(1). Filling the entire grid (e.g., initializing to Tileset.NOTHING) is Θ(WIDTH × HEIGHT).

Operation	Runtime
Access `tiles[x][y]`	Θ(1)
Fill / initialize	Θ(WIDTH × HEIGHT)

`WeightedQuickUnionUF` — Connectivity Tracking (Ch. 14.4–14.5)

Used during world generation to track which rooms are connected into a single component. We create a WQU with N elements (one per room) and union rooms as hallways are built, stopping when a single component remains.

From the textbook (Ch. 14.5): WQU with path compression achieves O(α(N)) per connect and isConnected call, where α is the inverse Ackermann function. This "behaves as constant in long term" (amortized). Without path compression (Ch. 14.4), both operations are O(log N) because the maximum tree height is Θ(log N).

Operation	WQU (Ch. 14.4)	WQU + Path Compression (Ch. 14.5)
Constructor	Θ(N)	Θ(N)
`connect` (union)	O(log N)	O(α(N))*
`isConnected` (find)	O(log N)	O(α(N))*

*Amortized near-constant. For M operations on N elements, total cost is O(M α(N)).

`HashMap<Room, List<Room>>` — Adjacency List Graph (Ch. 20.2, 24.6)

The room connectivity graph is stored as an adjacency list: a HashMap mapping each Room to a List<Room> of its neighbors. The textbook (Ch. 20.2) identifies the adjacency list as the most common graph representation. Its space cost is Θ(V + E) and iterating all neighbors of a vertex takes O(degree(v)). DFS/BFS on an adjacency list runs in O(V + E), compared to O(V²) for an adjacency matrix.

The underlying HashMap provides amortized Θ(1) get and put (Ch. 24.6: "a HashMap which allows for amortized constant time access to any key-value pair"), assuming the hash function spreads keys evenly and the load factor triggers resizing.

Operation	Runtime
`get` / `put` (HashMap)	Θ(1) amortized (Ch. 24.6)
Add edge (append to both neighbor lists)	Θ(1) amortized
Iterate neighbors of room `v`	O(degree(v))
Space	Θ(V + E) where V = rooms, E = connections

`ArrayList<Room>` — Room Storage (Ch. 7)

All generated rooms are stored in an ArrayList. With geometric resizing (doubling the backing array), addLast is Θ(1) amortized, and indexed access get(i) is Θ(1). Scanning all rooms (e.g., to find the nearest unconnected room) is O(N).

Operation	Runtime
`add` (addLast)	Θ(1) amortized
`get(i)`	Θ(1)
Iterate / scan all	O(N)

Classes

`World`

The top-level container that owns generation and rendering.

Field	Type	Purpose
`rooms`	`ArrayList<Room>`	All generated rooms
`graph`	`HashMap<Room, List<Room>>`	Adjacency list for room-to-room connections
`wqu`	`WeightedQuickUnionUF`	Tracks connected components during generation
`tiles`	`TETile[][]`	The rendered grid passed to the renderer
`avatar`	`int[2]`	Avatar position `{x, y}` on the tile grid
`random`	`Random`	Seeded PRNG threaded through all generation

Methods:

void generate() — runs the full pipeline: rooms → connect → hallways → render → place avatar
void addRoom() — attempts to place a random room; retries on overlap (capped at MAX_ATTEMPTS)
void connectRooms(Room r1, Room r2) — adds edge in graph (both directions) and calls wqu.union(r1.id, r2.id)
boolean allConnected() — checks if all rooms share a single WQU component
TETile[][] renderTiles() — stamps rooms and hallways onto tiles, returns the grid
void moveAvatar(char direction) — updates avatar position if target tile is FLOOR
void save() / static World load() — serializes/deserializes the input string for deterministic replay

`Room`

A rectangular region on the grid.

Field	Type	Purpose
`topLeft`	`int[2]`	`{x, y}` of the top-left corner
`width`	`int`	Horizontal span (including walls)
`height`	`int`	Vertical span (including walls)
`id`	`int`	Index into the WQU

Methods:

int[] centroid() — returns {topLeft[0] + width/2, topLeft[1] + height/2}
boolean overlaps(Room other) — returns true if bounding boxes intersect (with a 1-tile buffer to prevent wall merging)
void stampOnto(TETile[][] tiles) — writes FLOOR for interior tiles, WALL for border tiles
double distanceTo(Room other) — Euclidean distance between centroids, used for nearest-room selection

`Hallway`

A path connecting two rooms, represented as an ordered list of floor positions.

Field	Type	Purpose
`segments`	`List<int[]>`	Sequence of `{x, y}` floor positions along the hallway
`source`	`Room`	Starting room
`dest`	`Room`	Destination room

Methods:

void stampOnto(TETile[][] tiles) — writes FLOOR at each position in segments; for each floor tile placed, checks all 8 neighbors and writes WALL on any tile that is currently NOTHING. Never overwrites an existing FLOOR with WALL.

Algorithms

1. Room Generation

N = random int in [MIN_ROOMS, MAX_ROOMS]    // e.g., [15, 30]
for i in 0..N:
    attempts = 0
    do:
        x, y = random position within grid bounds (with margin)
        w, h = random size in [MIN_ROOM_SIZE, MAX_ROOM_SIZE]
        candidate = new Room(x, y, w, h, id=i)
        attempts++
    while candidate.overlaps(any existing room) AND attempts < MAX_ATTEMPTS
    if attempts < MAX_ATTEMPTS:
        rooms.add(candidate)

MAX_ATTEMPTS (e.g., 50) caps retries so generation always terminates.
overlaps() checks with a 1-tile buffer so rooms never share or merge walls.

2. Room Connection (Spanning Tree via WQU)

wqu = new WeightedQuickUnionUF(rooms.size())
while not allConnected():
    A = random room from rooms
    B = nearest room to A such that !wqu.connected(A.id, B.id)
    graph.get(A).add(B)
    graph.get(B).add(A)
    wqu.union(A.id, B.id)
// Optional: add K random extra edges for loops/variety

"Nearest" = minimum Euclidean distance between centroids.
The !connected check is O(α(N)) per call via WQU with path compression (Ch. 14.5), ensuring we never add redundant edges and always make progress toward a single component.
Each iteration scans all rooms to find the nearest unconnected neighbor: O(N) per iteration, up to N iterations total → O(N²) for the full spanning tree construction.

3. Hallway Pathfinding (L-shaped corridors)

For each edge (A, B) in the graph:

start = A.centroid()
end   = B.centroid()
current = copy of start
segments = []

// Randomly choose horizontal-first or vertical-first
if random.nextBoolean():
    walkHorizontal(current, end, segments)
    walkVertical(current, end, segments)
else:
    walkVertical(current, end, segments)
    walkHorizontal(current, end, segments)

hallways.add(new Hallway(segments, A, B))

walkHorizontal: step current.x toward end.x one tile at a time, appending each position.
walkVertical: step current.y toward end.y one tile at a time, appending each position.
Randomizing axis order adds visual variety.
If a hallway passes through an existing room, the floor tiles simply overlap — this is fine.

4. Tile Rendering

// Step 1: Fill entire grid with NOTHING — Θ(WIDTH × HEIGHT)
for x in 0..WIDTH:
    for y in 0..HEIGHT:
        tiles[x][y] = Tileset.NOTHING

// Step 2: Stamp each room — Θ(room.width × room.height) per room
for room in rooms:
    room.stampOnto(tiles)

// Step 3: Stamp each hallway
for hallway in hallways:
    hallway.stampOnto(tiles)
    // For each floor tile placed, surround with WALL
    // on any neighbor that is NOTHING

// Step 4: Place avatar on a random FLOOR tile
do:
    ax, ay = random position
while tiles[ax][ay] != FLOOR
tiles[ax][ay] = Tileset.AVATAR
avatar = {ax, ay}

Key invariant: A tile that is already FLOOR is never overwritten with WALL. This prevents hallways from blocking rooms and vice versa. Rooms are rendered first so their floors are established before hallway walls are placed.

5. Avatar Movement

moveAvatar(char dir):
    (dx, dy) = offset from dir    // W→(0,1), A→(-1,0), S→(0,-1), D→(1,0)
    nx = avatar[0] + dx
    ny = avatar[1] + dy
    if inBounds(nx, ny) AND tiles[nx][ny] == FLOOR:
        tiles[avatar[0]][avatar[1]] = FLOOR
        avatar = {nx, ny}
        tiles[nx][ny] = AVATAR

Each move is Θ(1): one bounds check, one tile read, two tile writes.

6. Save / Load

Save: Write the full input string (seed + all keystrokes so far) to a file on disk.
Load: Read the file, replay the seed to regenerate the identical world (deterministic via Random), then replay the stored movement characters.
This avoids serializing the entire TETile[][] grid — the seed is sufficient because generation is deterministic.

Complexity

Let N = number of rooms, M = WIDTH × HEIGHT (tile grid area), E = number of edges in the graph (≥ N−1 for spanning tree).

Operation	Time	Space	Source / Justification
Grid initialization	Θ(M)	Θ(M)	Fill 2D array (Ch. 6)
Room generation	O(N × MAX_ATTEMPTS × N)	O(N)	Each candidate overlap-checks against all existing rooms; MAX_ATTEMPTS is a constant cap
WQU construction	Θ(N)	Θ(N)	Ch. 14.4: constructor is Θ(N)
Connection loop (spanning)	O(N² × α(N))	O(N)	Up to N rounds; each round scans N rooms and calls `wqu.connected` at O(α(N)) per call (Ch. 14.5)
`wqu.union` per call	O(α(N))*	O(1)	Ch. 14.5: amortized near-constant with path compression
`wqu.connected` per call	O(α(N))*	O(1)	Ch. 14.5: amortized near-constant with path compression
HashMap `get`/`put` per call	Θ(1) amortized	—	Ch. 24.6: constant time assuming even spread
Hallway generation (all)	O(E × (W + H))	O(E × (W + H))	One L-path per edge; each path ≤ WIDTH + HEIGHT steps
Room stamping (all)	O(total room area)	O(1) extra	Each room writes its tiles; bounded by O(M)
Hallway stamping (all)	O(total hallway tiles)	O(1) extra	Each segment tile + 8-neighbor wall check
Avatar movement	Θ(1)	Θ(1)	Single tile lookup and swap
Save	O(input length)	O(input length)	Write string to file
Load	O(generation + moves)	O(M)	Replay seed then replay keystrokes

Overall generation: O(N² + M) time (dominated by the connection loop and grid fill), O(M) space (dominated by the tile grid). The WQU operations within the connection loop are effectively constant per call thanks to path compression (Ch. 14.5), so the N² factor comes from the nearest-room scan, not from union-find overhead.

Questions

Open Questions

What should MAX_ROOM_SIZE and MIN_ROOM_SIZE be to get a good aesthetic at the default grid size (80×30 or similar)?
Should extra edges beyond the spanning tree be added for more interesting topology? If so, how many? (Adding K random non-duplicate edges would cost O(K × N) for the connected check.)
How should hallway corners be rendered — should the bend tile get a special floor treatment, or is a regular floor tile sufficient?
Is there a cleaner way to detect "all connected" than iterating and calling wqu.connected(0, i) for all i? (One approach: maintain a component count, decrement on each successful union, stop when count == 1.)
Should rooms have a minimum separation distance beyond the 1-tile buffer, for aesthetic reasons?

Closed Questions

Q: How to prevent rooms from sharing walls? A: Add a 1-tile buffer in overlaps() so rooms are always separated by at least one empty tile.
Q: How to avoid wall-overwrite conflicts between rooms and hallways? A: Enforce the invariant that FLOOR tiles are never overwritten by WALL. Render rooms first (establishing their floors), then hallways (which only place WALL on NOTHING tiles).
Q: What graph representation to use? A: Adjacency list via HashMap<Room, List<Room>> — the textbook (Ch. 20.2) identifies this as the most common representation, with Θ(V + E) space and O(V + E) traversal. An adjacency matrix would waste O(N²) space for a sparse graph of ~20 rooms.
Q: Why WQU over plain Quick Union for connectivity? A: Plain Quick Union has O(N) worst-case for connect and isConnected due to potentially degenerate trees (Ch. 14.3). WQU guarantees O(log N) by keeping trees balanced (Ch. 14.4), and path compression further reduces to amortized O(α(N)) (Ch. 14.5).

Diagram

 GENERATION PIPELINE
 ═══════════════════

 Seed String ("N12345S")
       │
       ▼
   Parse seed ──► java.util.Random(12345)
                       │
         ┌─────────────┴───────────────┐
         ▼                             ▼
   Generate N Rooms              Room objects
   (random pos/size,             stored in ArrayList<Room>
    retry on overlap)
         │
         ▼
   Connect via WQU                    Data Structures Used:
   (nearest-unconnected              ┌─────────────────────────────────┐
    neighbor, repeat                 │ WQU:  union/find O(α(N))       │
    until 1 component)               │ HashMap: get/put Θ(1) amort.   │
         │                           │ ArrayList: add Θ(1), get Θ(1)  │
         ▼                           │ TETile[][]: access Θ(1)        │
   Build L-shaped Hallways           └─────────────────────────────────┘
   (horiz-then-vert or
    vert-then-horiz)
         │
         ▼
   Render onto TETile[WIDTH][HEIGHT]
   1. Fill with NOTHING
   2. Stamp rooms (FLOOR + WALL)
   3. Stamp hallways (FLOOR, WALL on NOTHING neighbors)
   ★ Invariant: FLOOR never overwritten by WALL
         │
         ▼
   Place Avatar on random FLOOR tile
         │
         ▼
   Gameplay Loop ◄──── WASD input
   (move / :Q save / L load)


 TILE GRID EXAMPLE
 ═════════════════

   ########         ######
   #......#         #....#
   #......####  #####....#
   #......#..####...#....#
   ########..#  #...######
             ##  #...#
          ####   #...#
          #......#####
          #......#
          ########

   # = WALL    . = FLOOR    @ = AVATAR (on a floor tile)


 ROOM + HALLWAY STRUCTURE
 ════════════════════════

   Room A (id=0)                    Room B (id=1)
   ┌──────────────┐                 ┌────────────┐
   │  centroid    │                 │  centroid  │
   │   (5,10)     │                 │  (20,7)    │
   │  w=6, h=4    │                 │  w=5, h=3  │
   └──────────────┘                 └────────────┘
          │                                │
          └──── graph edge (HashMap) ──────┘
          │                                │
          └──── Hallway ───────────────────┘
               segments: [(6,10),(7,10),...,(20,10),
                          (20,9),(20,8),(20,7)]

   WQU state after connection:
   wqu.union(0, 1) → both in same component
   wqu.connected(0, 1) → true


 CONNECTIVITY ALGORITHM
 ══════════════════════

   Step 1: N rooms, N components     Step 2: Pick random A,
           in WQU                     find nearest B where
                                      !connected(A,B)
   [0] [1] [2] [3] [4]              [0]──[1] [2] [3] [4]
                                      union(0,1)

   Step 3: Repeat                    Step 4: Single component
   [0]──[1] [2]──[3] [4]            [0]──[1]──[2]──[3]──[4]
    union(2,3)                        allConnected() → true
              └──[4]                  DONE: build hallways
               union(3,4)             for each edge

Build Your Own World — Technical Design Document

Data

Data Structures

TETile[][] — The Tile Grid (Ch. 6: 2D Arrays)

WeightedQuickUnionUF — Connectivity Tracking (Ch. 14.4–14.5)

HashMap<Room, List<Room>> — Adjacency List Graph (Ch. 20.2, 24.6)

ArrayList<Room> — Room Storage (Ch. 7)

Classes

World

Room

Hallway

Algorithms

1. Room Generation

2. Room Connection (Spanning Tree via WQU)

3. Hallway Pathfinding (L-shaped corridors)

4. Tile Rendering

5. Avatar Movement

6. Save / Load

Complexity

Questions

Open Questions

Closed Questions

Diagram

`TETile[][]` — The Tile Grid (Ch. 6: 2D Arrays)

`WeightedQuickUnionUF` — Connectivity Tracking (Ch. 14.4–14.5)

`HashMap<Room, List<Room>>` — Adjacency List Graph (Ch. 20.2, 24.6)

`ArrayList<Room>` — Room Storage (Ch. 7)

`World`

`Room`

`Hallway`