> For the complete documentation index, see [llms.txt](https://tomthestrom.gitbook.io/cs61b-fall-2022/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tomthestrom.gitbook.io/cs61b-fall-2022/project-3-byow/phase-1-world-generation.md). # Phase 1: World Generation Building a pseudo-random dungeon generator. [Prerequisites](/cs61b-fall-2022/prerequisites-to-running-the-assignments..md) to running the code. Instructions: Solution: ## Requirements * The world must be a 2D grid, drawn using our tile engine. The tile engine is described in [lab11](https://fa22.datastructur.es/materials/lab/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.

Source: UC Berkeley CS61B FA22 (https://fa22.datastructur.es/materials/proj/proj3/img/compliant_world_example.png)

## Demo {% embed url="" %} ## 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 Tree`](https://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation)to 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.

An example result of running Binary Space Partitioning - a screenshot I took when debugging.

I named the class that dealt with binary space partitioning accordingly - `BSPTree` ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/BSPTree.java)). ### `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`](#bsptree-generatetree-code-on-github-.) - this is were the splitting/recursion happens. * [`public List` method `getRoomsFromLeaves`](#bsptree-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**: 1. **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. 2. Do the first **split**. 3. 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**). 4. **Insert** the **two split `Nodes`**(subgrids) i**nto the max heap**. 5. **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? 1. Collect the leaf `Nodes` 2. Generate Rooms of random size within the `xMin, xMax, yMin, yMax` bounds of each leaf. 3. Return `List` 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](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/AbstractGridObject.java)), 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](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/GridDrawer.java)). ### Connecting The Rooms This turned out to be the most challenging part. Connecting instances of `Room`([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/Room.java)) presents 2 different problems: 1. [Choosing which Rooms will be connected with each other.](#choosing-which-rooms-will-be-connected-with-each-other) 2. [Finding a path for the Corridor to connect them.](#finding-a-path-and-connecting-rooms-with-a-corridor) The connecting logic was implemented in `class RoomConnector` ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/RoomConnector.java)). * This class has 3 instance properties * `TETile[][] worldGrid` representing the state of the grid after painting the `Rooms` * `List disconnectedRooms` - the `List` of the `Rooms` returned via the `BSPTree` * `MinPQ distTo` - holds instances of Rooms * `Room` implements the `GridSearchable Interface` ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/GridSearchable.java)). Sorting rules are defined in `GridSearchableDistanceComparator` ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/GridSearchableDistanceComparator.java)) * The connecting logic is implemented in `connect` method. To calculate the distance between 2 points, I used the formula for [euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance) implemented in `GridMathUtils class` ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/GridMathUtils.java)). #### 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](https://en.wikipedia.org/wiki/Minimum_spanning_tree)). My method of determining which 2 `Rooms` to connect is very similar to how [Prim's algorithm ](https://en.wikipedia.org/wiki/Prim%27s_algorithm)works. **Prim's Algorithm for building an MST** 1. start from some arbitrary node - the "source" (in the beginning the only node in the Tree) 2. insert all other nodes into a Priority Queue in order of distance from the Tree 3. Remove the closest node from the PQ - connect it to the Tree 4. Recalculate the distance of the nodes in the PQ from the Tree using the newly added node 5. Repeat from step 3. until no nodes in PQ **Prim's Inspired Room Connecting** 1. As the source, pick the 0th element of the `List disconnectedRooms` instance property 2. Populate `MinPQ distTo` instance property with the rest of the `Rooms` - using euclidean distance to determine proximity to the source 3. Pick the first element (the closest one in the PQ) 4. Now I [try to find the path for the corridor to connect them](#finding-a-path-and-connecting-rooms-with-a-corridor) 5. After connecting the 2 `Rooms`, I recalculate the distance to the rest of the `Rooms` in the `distTo MinPQ` from the newly added Room. 6. 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](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/GridCoords.java)). To reflect this, I implemented the **`PathFinder`** `class` ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/PathFinder.java)) 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\*](https://en.wikipedia.org/wiki/A*_search_algorithm) inspired approach by using [heuristic](https://en.wikipedia.org/wiki/Heuristic_\(computer_science\)) 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](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/Direction.java)) 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](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/GridCoordsDirection.java)). If Direction 1 is UP and Direction 2 is LEFT, I will need `TopToLeft` ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/Corridor/TopToLeft.java)) 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](https://github.com/tomthestrom/cs61b/tree/master/proj3/byow/Core/Corridor)) For this reason `PathFinder` is implemented such that in addition to providing the coordinates via**`next,`** 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 directionsTaken.`** Upon reaching the target door, we provide **`directionsTaken`** to the `build` method of `Corridor class (an ArrayList of CorridorTile) (`[code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/Corridor/Corridor.java)`)` which builds itself picking the suitable `CorridorTile` for each entry in `directionsTaken` using **`CorridorTilePicker`** ([code on GitHub](https://github.com/tomthestrom/cs61b/blob/master/proj3/byow/Core/Corridor/CorridorTilePicker.java)). 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!