In my previous post, I covered Pixel Dungeon’s level generation which relied on the subdivision of a rectangular region. I’ve decided to check if the popular fork Shattered Pixel Dugneon had any significant changes and I was fairly surprised by what I found. Shattered throws away the underlying level generation process which was bounded by a finite rectangular region and replaces it with one that is unbounded but still confined to grid cells. This required significant changes and increased the complexity of level generation but increases the freedom of level configurations.

If you read the previous post be careful about applying any concepts learnt there onto Shattered. The only concepts that remain the same are rectangles and that rooms are defined as a rectangular region. In Pixel the type of room was encoded as a enumerator whereas in Shattered the type is based on its class. Each room can dictate what its dimensions are and how many connections to it are allowed. A new concept called Builder is used for level generation and contains two major functions called placeRoom and findFreeSpace. Different builders inherit from Builder and provide different build functions that are responsible for a collections of rooms that are connected. The most notably descendent of Builder is LoopBuilder which is used for the typical dungeon level. I’ll first explain findFreeSpace and placeRoom before explaining LoopBuilder.

findFreeSpace

Given a point and a collections of rooms maximize the rectangular space around the point without overlapping any rooms. If a point is contained within any room then there is no free space. Also we don’t want a space of infinite size so we have a maximum distance from the point called maxSize.

Here is a general description of the algorithm. Let p be provided point. Let rooms be the provided rooms. Let maxSize be the maximum distance from p.

Initialize a rectangle called space with dimensions (p.x - maxSize, p.y - maxSize, p.x + maxSize, p.y + maxSize) Now while the size of rooms is not zero perform the following: Iterate through all the rooms removing any empty rooms or rooms that do not overlap space. Now the first element in rooms will be non-empty and will overlap space, pop it off and call it r. If the point is contained within this room, then return an empty rectangle, otherwise modify space in the smallest way possible so it does not overlap this room, which can be accomplished as follows. When reducing space we only need reduce its width or its height but not both. The dimension we perform the reduction on is the one that removes the minimum area from space. Set wDiff and hDiff to infinity,

if r.left >= p.x
    wDiff = (space.right - r.left) * (space.height() + 1) 
else if r.right <= p.x
    wDiff = (r.right - space.left) * (space.height() + 1)
 

if r.top >= p.y
    hDiff = (space.bottom - r.top) * (space.width() + 1)
else if r.bottom <= p.y
    hDiff = (t.bottom - space.top) * (space.width() + 1)

if (wDiff < hDiff) == 0){
    if (r.left >= p.x && r.left < space.right) space.right = r.left;
    if (r.right <= p.x && r.right > space.left) space.left = r.right;
} else {
    if (r.top >= p.y && r.top < space.bottom) space.bottom = r.top;
    if (r.bottom <= p.y && r.bottom > space.top) space.top = r.bottom;
}

As stated previous we continue this until rooms is empty which after repeated iterations obtains the free space around a point if one exists.

Here is visual of the above

Find Space

This is the actual source code for findFreeSpace.

placeRoom

Given a non-empty room and an empty room, we want to initialize the empty room next to non-empty room and have placed at a certain angle. We also want to ensure that we can connect these two rooms. Here are the parameters this function takes: A collections of rooms called rooms. The non-empty room called from. The empty room called to. An angle called angle.

We determine the center of the non-empty and cast a ray with an angle of angle from this point. We then determine where this ray intersects one of our bounding walls. Now determine the free space around this point by calling findFreeSpace and attempt to initialize the empty room using this free space. Given the dimensions of the new room we extend the previously cast ray to determine the ideal center for this new room and adjust the position accordingly. Then shift the new room so it shares a wall with from. Now since we shifted the new room around it may not be within the bounding region determined by findFreeSpace so we perform any necessary shifts to nudge it back in. Finally attempt to connect the new room and from. There are three main points where this process can failure, findFreeSpace can fail, the free space is too small for the room, and the connect function can failure if the two rooms don’t share a wall. This is the actual source code for placeRoom.

LoopBuilder

I’ll explain a simplified version of the LoopBuilder to help build an intuitive understanding of it. The goal is given a collection of uninitialized rooms, we want want to connect them in circular pattern and ensure that a loop exists. Each level creates a collection of rooms, rooms, that must appear in the level. A shallow copy of these rooms are created and are filtered into two collections, MultiConnections, and SingleConnections. Only rooms from MultiConnections can appear on the path since at least two connections are required for rooms in a cyclic path. The path will contain a portion of rooms from MultiConnections this portion is called, pathLength, thus this path will contain MultiConnections.length() * pathLength rooms from MultiConnections.

Now a create room containing the entrance and set it at the origin (0,0), create a collection called path, add the entrance to it, and while we have rooms left to be placed do the following:

  1. Pop a room from MultiConnections and push it onto path
  2. Randomly add ConnectionRoom to path. This ensures 0 or more tunnels exists between each room.

After this process is complete we add the exit room in the middle of the path collection. Now create a reference called prev which refers to the last room placed. It is initialized to the entrance room, which is the first room in path. Now beginning at the second room in path for each room do the following: Let the current room be referred to as curr.

  1. Calculate the target angle, angle, for the current room.
  2. Call placeRoom with parameters rooms, prev, curr, angle.
  3. Set prev to curr

The target angle can be calculated as follows: Let i be the index of the room in loop Let s be the size of loop angle = 360 * (i/s) This is a lerp (Linear interpolation) between the angles 0 and 360. Also recall that placeRoom can fail and if it does we have to retry the entire level.

The path is not yet complete! The above procedure does not connect the last room and the entrance so we handle that case, thus completing the loop. Any remaining rooms in MultiConnections and SingleConnections must be added. These rooms are uninitialized so for we randomly select an initialized room, generate a random angle, and attempt to connect the new room. During this we may also add additional ConnetionRooms between the two rooms. Rooms placed in this manner are referred to as branch rooms.

Afterword

I initially found this level generator harder to analyze compared to Rouge’s and Pixel Dungeon’s generators mostly because there are multiple edge cases that can occur throughout the process. I painted some broad strokes with the overall process and some details were left out. The most notable is the equation for target angle can lerp the angles of an oval. I found Shattered approach to be fairly insightful and was definitely worth a look over. Finally here are some screenshots of the end result.

Level 1 Level 2 Level 3 Level 4