Two six-room dungeons

This year there is an RPG game jam for making zungeons, which are a zine-inspired D&D dungeons. Marcia B’s Bite-Sized Dungeons are recommended.

Marcia created a list of ten abstract dungeon layouts. I found two other layouts that essentially “finish the collection”.

This got me thinking about generalizations.

Criterion

In the language of graph theory, Marcia is recommending that the abstract dungeon layouts be connected, planar graphs with six vertices and six edges.

Possible layouts

Marcia’s post lists ten such layouts. She mentions that hexagons also meet her criterion, but that she isn’t interested in plain loops.

It turns out that there are exactly 13 such layouts. The two which do not appear on Marcia’s blog are:

As maps, these could look like:

So if we throw out hexagons, we can randomly choose a layout with a d12.

By “exactly 13 layouts”, I mean up to graph-isomorphism. This may not, however, be a good assumption in practice. The following two graphs are graph-isomorphic, but are arguably different enough as dungeons:

Resources for connected, planar graphs

The house of graphs contains a collection of connected, planar graphs in graph6 format.

If you download the collection of order 6 graphs, you can easily find the ones with six edges using the showg program. The -e flag will display the number of edges:

$ showg planar_conn.6.g6 -e

Any graph whose second line is

6 6

will correspond to one of the abstract dungeon layouts. So you can count them with:

$ showg planar_conn.6.g6 -e | grep "^6 6$" | wc -l

Seven-room dungeons?

Connected, planar graphs make good sense as an abstract layout for a dungeon. Six rooms/vertices was chosen as a sweet spot in game design. With six vertices, five edges is enough connect the graph. The sixth edge gives the dungeon a loop.

Every connected, planar graph that has the same number of vertices as edges will always have exactly one loop. More generally, Euler’s formula says that:

\[ v - e + f = 2 \]

where

• v is the number of vertices
• e is the number of edges
• f is the number of faces (regions bounded by edges)

Note that one of the faces is always the outer, infinitely large region. Let’s refer to the finite faces as “regions”.

So if we want, say, a seven-room dungeon with two regions, we would choose eight edges.

How many layouts?

Using the data from the house of graphs: