Generating Dungeons (Part 1)

This is the first of what hopefully will be a series of posts about my attempt to generate interesting dungeons for my in-development ARPG.

Layout Overview#

Many classic ARPGs such as Diablo 2 and Path of Exile generate unique layouts for the dungeons and areas the player traverses. The randomness keeps the gameplay experience fresh and adds replayability.

Though the randomness isn’t unbounded. These games often use rules around the generation to keep some consistency between playthroughs. For example a map may always be generated with a start point near the northwest corner and an endpoint in the southeast corner. Anything between those points however, is generated randomly.

With these properties in mind lets lay out some objectives for our generation.

• Dungeon Rooms
  • Rooms generated will be connected to one another by an edge large enough to fit a door, doorway, or entryway
  • Rooms will have random dimensions bounded by parameters that we can easily set
• Determinism
  • The dungeon will be easily reproducible via its seed and the parameters used to generate the dungeon
• Control
  • We will be able to control the dungeon layout via a series of start and endpoints between which dungeon paths will be generated

Base Room List#

We can generate a set of uniquely sized rooms for potential use in our dungeon by starting with a rectangle the size of our level and subdividing it into smaller rectangles of variable length and width.

The algorithm I used for this is fairly simple, here is a very simplified example that should give you the gist of what’s going on.

func subdivide(rectangle, rectangleList, params)
    if rectangle.area < params.minArea
        rectangleList.Add(rectangle)
        return rectangleList

    var subdivisionAxis = Random.int() % 2

    var rectangles = rectangle.split(subdivisionAxis)

    subdivide(rectangles[0], rectangleList, params)
    subdivide(rectangles[1], rectangleList, params)

    return rectangleList

We now have a set of much smaller rectangles that will make up the rooms of our dungeon!

The Room Graph#

We need an easy way to track which of our rooms are adjacent to one another. I decided to go with a bidirectional graph structure. Each room will be represented by a node in the graph and adjacent nodes will be tracked in a list.

class RoomGraphNode
{
  public Rect2 rect { get; set; }
  public int weight { get; set; }
  public List<RoomGraphNode> adjacent { get; set; }
}

I took a naieve approach to building the graph. For each node I just check if any of the other nodes intersect and add them as adjacent.

for (var i = 0; i < rectList.Count; i++)
{
  var node = nodeList[i];

  for (var j = i + 1; j < rectList.Count; j++)
  {
    if (grownRectangle.Intersects(rectList[j], true))
    {
      node.adjacent.Add(nodeList[j]);
      nodeList[j].adjacent.Add(node);
    }
  }
}

This introduces quadratic complexity. I didn’t bother with a more efficient approach because I know that the number of nodes will always be relatively low. A more efficient approach might be to use a k-d tree for finding adjacent nodes.

Here is our graph visualized with lines between adjacent nodes.

Generating Paths#

We’ve generated our rooms and we’ve built a graph of adjacencies between them. We now have the data we need to start generating paths.

I decided to use a shortest path algorithm between points/nodes in the graph. Specifically a variation of Dijkstra’s Algorithm. The only small difference being that instead of using weights on the graph edges I used randomly generated weights on the nodes themselves. That weight is represented by the red/green gradient in the previous images.

Using this algorithm we can find the shortest (weighted) path around the graph.

The nodes that this path takes will be the rooms that make up our dungeon!