Phase 1: World Generation
Building a pseudo-random dungeon generator.
Last updated
Building a pseudo-random dungeon generator.
Last updated
to running the code.
Instructions:
Solution:
The world must be a 2D grid, drawn using our tile engine. The tile engine is described in .
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.
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).
BSPTree class - descriptionits 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.
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):
Get the largest Node from the max heap.
Get split direction - if it's height is < width, it will be split vertically, otherwise horizontally - ensures rooms are more "properly/proportionally" sized
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).
Split
Now the result of splitting is that we have 2 new Nodes (subgrids)
Insert the 2 new Nodes into the max heap
increment the counter for number of times split
Run the loop again, if conditions are met (split depth not reached yet)
Collect the leaf Nodes
Generate Rooms of random size within the xMin, xMax, yMin, yMax bounds of each leaf.
Return List<Room>
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
The connecting logic is implemented in connect method.
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.
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)
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.
The PathFinder:
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
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
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.
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.
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.
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!
After doing some research, I decided to go down the route of using a 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.
I named the class that dealt with binary space partitioning accordingly - BSPTree ().
- this is were the splitting/recursion happens.
- collects the leaves of the BSPTree, turns each one into a Room and returns a list of Room instances.
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 (), 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 ().
This turned out to be the most challenging part. Connecting instances of Room() presents 2 different problems:
The connecting logic was implemented in class RoomConnector ().
Room implements the GridSearchable Interface (). Sorting rules are defined in GridSearchableDistanceComparator ()
To calculate the distance between 2 points, I used the formula for implemented in GridMathUtils class ().
If we imagine that each Room is a node (vertex) in a graph, connecting them via the shortest path sounds like building an MST ().
My method of determining which 2 Rooms to connect is very similar to how works.
Now I
A path on a 2D grid is basically a sequence of (x,y) coordinates, these are for the most part represented by GridCoords (). To reflect this, I implemented the PathFinder class () as an Iterable that provides an Iterator for sequential access to the coordinates (so they can be requested/accessed one at a time).
uses an inspired approach by using to direct its search
when public minimizeZigZag method is called, the PathFinder will intend to provide the next coordinates in the same Direction () as the previous one - this is useful to have nice straight corridors/hallways with proper corners (no zig-zag)
So now it sounds like we need to store GridCoords and their Direction, that's what I implemented GridCoorsDirection for ().
If Direction 1 is UP and Direction 2 is LEFT, I will need TopToLeft () a corner tile that will eventually be painted like this:
Similarly, there are 9 other types of CorridorTile ()
Upon reaching the target door, we provide directionsTaken to the build method of Corridor class (an ArrayList of CorridorTile) () which builds itself picking the suitable CorridorTile for each entry in directionsTaken using CorridorTilePicker ().
