Phase 1: World Generation

Building a pseudo-random dungeon generator.

Prerequisites to running the code.

Instructions: https://fa22.datastructur.es/materials/proj/proj3/#phase-1-world-generation

Solution: https://github.com/tomthestrom/cs61b/tree/master/proj3

Requirements

The world must be a 2D grid, drawn using our tile engine. The tile engine is described in lab11.
The world must be pseudorandomly generated. Pseudorandomness is discussed in lab 11.
The generated world must include distinct rooms and hallways, though it may also include outdoor spaces.
At least some rooms should be rectangular, though you may support other shapes as well.
Your world generator must be capable of generating hallways that include turns (or equivalently, straight hallways that intersect).
The world should contain a random number of rooms and hallways.
The locations of the rooms and hallways should be random.
The width and height of rooms should be random.
Hallways should have a width of 1 or 2 tiles and a random length.
Rooms and hallways must have walls that are visually distinct from floors. Walls and floors should be visually distinct from unused spaces.
Rooms and hallways should be connected, i.e. there should not be gaps in the floor between adjacent rooms or hallways.
All rooms should be reachable, i.e. there should be no rooms with no way to enter
The world should be substantially different each time, i.e. you should not have the same basic layout with easily predictable features

As an example of a world that meets all of these requirements (click for higher resolution), see the image below. In this image, # represents a wall tile, a dot represents a floor tile, and there is also one golden colored wall segment that represents a locked door. All unused spaces are left blank.

Demo

Implementation - How To (possibly) Build Your Own Dungeon Generator

In the following paragraphs, I'll try to describe how I implemented a pseudo-random map generator that would generate a randomly different map for each unique integer seed (while always generating the same map for the same seed).

After doing some research, I decided to go down the route of using a BSP Treeto divide the space on the 2D grid (the World). By using binary space partitioning, I ensured that the future rooms wouldn't overlap. My goal was to deal with creating the rooms first and connecting them later.

I named the class that dealt with binary space partitioning accordingly - BSPTree (code on GitHub).

`BSPTree class` - description

its basic building block is a Node, which is its nested class.
The Node is being recursively split and its leaves are the basis for creating the Rooms after the splitting is done.
private property root (the topmost Node) gets initialized in the BSPTree constructor with the given grid width and height - as such, the root represents the whole grid, while it's future nodes will represent it's subparts and its leaves will get turned into Rooms.
private property random (of type Random) gets initialized in the constructor with the seed
private static int properties MIN_TIMES_TO_SPLIT and MAX_TIMES_TO_SPLIT - denoting, as the name suggests, the lower and upper bounds of the number of times the grid is split / the depth of the recursion. These props are used along with the seed to generate a pseudorandom number of times the grid is split to ensure that maps have a varying number of rooms.
public BSPTree method generateTree - this is were the splitting/recursion happens.
public List<Room> method getRoomsFromLeaves - collects the leaves of the BSPTree, turns each one into a Room and returns a list of Room instances.

BSPTree - generateTree() - How Does it Work?

Workflow:

Randomly determine whether the 1st split (on the root) is in the vertical/horizontal direction and get the (random) x/y coordinate of the split point.
Do the first split.
Initialize a max heap (Max PQ). The max heap ensures that the Nodes are sorted according to their size (the first element is the largest one).
Insert the two split Nodes(subgrids) into the max heap.
Loop random number of times (lower/upper bounds: MIN_TIMES_TO_SPLIT & MAX_TIMES_TO_SPLIT):
1. Get the largest Node from the max heap.
2. Get split direction - if it's height is < width, it will be split vertically, otherwise horizontally - ensures rooms are more "properly/proportionally" sized
3. Get a random split point (in vertical/horizontal direction) (within certain bounds of max/min Node width/height) to ensure future rooms are not too small).
4. Split
5. Now the result of splitting is that we have 2 new Nodes (subgrids)
6. Insert the 2 new Nodes into the max heap
7. increment the counter for number of times split
8. Run the loop again, if conditions are met (split depth not reached yet)

BSPTree - getRoomsFromLeaves() - How do we turn Nodes into Rooms?

Collect the leaf Nodes
Generate Rooms of random size within the xMin, xMax, yMin, yMax bounds of each leaf.
Return List<Room>

PS. I think it would be cleaner to do this in another class. Originally, I wanted to have a method return the leaves of the tree (as a List of AbstractGridObject (code on Github), since each Node is also an AbstractGridObject) and then turn them into Rooms in a separate class, but left it like this because of time constraints.

After generating the Rooms, I paint them on the grid using class GridDrawer (code on GitHub).

Connecting The Rooms

This turned out to be the most challenging part. Connecting instances of Room(code on GitHub) presents 2 different problems:

The connecting logic was implemented in class RoomConnector (code on GitHub).

This class has 3 instance properties
- TETile[][] worldGrid representing the state of the grid after painting the Rooms
- List<Room> disconnectedRooms - the List of the Rooms returned via the BSPTree
- MinPQ<GridSearchable> distTo - holds instances of Rooms
  - Room implements the GridSearchable Interface (code on GitHub). Sorting rules are defined in GridSearchableDistanceComparator (code on GitHub)
The connecting logic is implemented in connect method.

To calculate the distance between 2 points, I used the formula for euclidean distance implemented in GridMathUtils class (code on GitHub).

Choosing which Rooms will be connected with each other

Naturally, we want to connect Rooms that are the closest to each other to ensure our corridors are not cutting through another Room in between.

If we imagine that each Room is a node (vertex) in a graph, connecting them via the shortest path sounds like building an MST (Minimum Spanning Tree).

My method of determining which 2 Rooms to connect is very similar to how Prim's algorithm works.

Prim's Algorithm for building an MST

start from some arbitrary node - the "source" (in the beginning the only node in the Tree)
insert all other nodes into a Priority Queue in order of distance from the Tree
Remove the closest node from the PQ - connect it to the Tree
Recalculate the distance of the nodes in the PQ from the Tree using the newly added node
Repeat from step 3. until no nodes in PQ

Prim's Inspired Room Connecting

As the source, pick the 0th element of the List<Room> disconnectedRooms instance property
Populate MinPQ<GridSearchable> distTo instance property with the rest of the Rooms - using euclidean distance to determine proximity to the source
Pick the first element (the closest one in the PQ)
Now I try to find the path for the corridor to connect them
After connecting the 2 Rooms, I recalculate the distance to the rest of the Rooms in the distTo MinPQ from the newly added Room.
Repeat, starting from step 3, until there are no Rooms left in the distTo MinPQ.

Finding a path and connecting Rooms with a corridor

A path on a 2D grid is basically a sequence of (x,y) coordinates, these are for the most part represented by GridCoords (code on GitHub). To reflect this, I implemented the PathFinder class (code on GitHub) as an Iterable that provides an Iterator for sequential access to the coordinates (so they can be requested/accessed one at a time).

The PathFinder:

uses an A* inspired approach by using heuristic to direct its search
The heuristic in this case was the aforementioned euclidean distance, where the PathFinder calculates the next coordinate based on it's closest proximity to the target
when public minimizeZigZag method is called, the PathFinder will intend to provide the next coordinates in the same Direction (code on GitHub) as the previous one - this is useful to have nice straight corridors/hallways with proper corners (no zig-zag)

First we need a door

To build a corridor between 2 rooms, we need a starting point.

The starting point is a door.

Turns out that in order to find a door, we need a path finding algorithm too!

PathFinder comes to the rescue:

the source is the center of the Room
the target is the center of the Room we will try to connect to (this is just to provide the heuristic for PathFinder)
one simple constraint - the door cannot be on the edge of the Room
after we hit the first wall tile of our Room, we have a door
after finding the door in the source Room, we do the same for the target Room
set the target of the target Room to be the door of the source Room, so that PathFinder searches in that general direction
after finding the door of the target Room, set the target of the source Room to be the newly found door of the target Room

After we have a door, we want a corridor

We run PathFinder again - this time with minimizeZigZag.

An important property of a corridor is that in addition to being a sequence of x,y coordinates, when painted, it's also a sequence of a set of tiles - each floor tile must be surrounded by wall tiles.

For this reason, we need to be able to combine each coordinate with the proper set of tiles. When I started thinking about this, I realized that there were actually 10 possible types of sets of corridor tiles and the needed type can be determined by combining the direction of the last 2 moves.

So now it sounds like we need to store GridCoords and their Direction, that's what I implemented GridCoorsDirection for (code on GitHub).

If Direction 1 is UP and Direction 2 is LEFT, I will need TopToLeft (code on GitHub) a corner tile that will eventually be painted like this:

 WALL WALL
 FLOOR WALL

Similarly, there are 9 other types of CorridorTile (folder on GitHub)

For this reason PathFinder is implemented such that in addition to providing the coordinates vianext, it's also able to return the direction of the move via getLastMove (I admit it's a bad name), we save this combination into a List<GridCoordsDirection> directionsTaken.

Upon reaching the target door, we provide directionsTaken to the build method of Corridor class (an ArrayList of CorridorTile) (code on GitHub) which builds itself picking the suitable CorridorTile for each entry in directionsTaken using CorridorTilePicker (code on GitHub).

FInally, after going over the cycle of picking 2 Rooms to connect, finding their doors and building a list of CorridorTiles for each Corridor until there are no more Rooms in the distTo PQ to connect, we iterate over all the Corridors and paint them using GridDrawer.drawCorridor.

Summary

Uff, that was a mouthful to read!

I really enjoyed working on this project and I feel like I learned a lot.

However, I have a couple of remarks:

Within the course at UC Berkeley the students do this as a group project, so they get immediate feedback on their ideas and are able to improve upon them fast. That's the part I felt I was lacking, getting feedback is the best way to progress fast.

In hindsight, writing these lines 3 months after finishing this project, I think the whole Corridor Tile picking & building thing is unnecessarily complicated. At the time I was too deep in the tunnel to recognize it. It actually fails to build a perfectly connecting corridor in some cases.

I haven't managed to find the bug, sometimes it cuts strangely into a room it's supposed to connect to. I "fixed" this by writing a mapPostProcessor method in GridDrawer, to get a working implementation and not waste more time on trying to build the perfectly connecting corridor.

I'd like to clean up the code one day too!

PreviousProject 3 BYOW

Last updated 1 year ago