Random Dungeon Design Strategy Question

Hi folks,

I am trying to create a dungeon crawl component to a story I am writing via Twine + Harlowe, and I am looking for feedback on my general approach.

My idea is that I can have just one passage with hooks that change as the player “explores” the dungeon. The passage would have static containers for the hooks, like “Room Description,” and some of the hooks would be hidden, so that the player would have to sometimes search to reveal items, traps, or hidden doors.

I’m thinking I can generate nested arrays to serve as the “rooms” and their corresponding hooks, and I would also like to have some randomization to determine, say, whether a trap triggers and hits the player with a dart when she tries to move on to the next room. If she had searched for traps, then a dice roll to see if the hook describing the trap is revealed. Same thing for encounters with monsters, angering the gods, etc.

Hopefully all of this is a reasonable plan so far. The one thing I am having difficulty working out in my head is how to generate random connections between the “rooms.” I would like each room to have 1-5 connections, some of them hidden so that they player has to “search” for them, a la Nethack. I would also like to have some of the connections lead to “dead ends” (the “dead ends” are just a special kind of room with a chance that searching will reveal a continuation to a room versus having to double back).

I’m planning for the connections to not be passages. Instead, clicking the link will kick off a script that runs for a random number of seconds from 1-10 seconds (the connector length), with feedback describing what is happening as the player traverses the connector. Every 3 seconds of travel time has a random chance of an encounter of some kind, or merely describes the journey ("the oddly smooth walls of the corridor reflect the light from your $light_source).

I’ve been trying to come up with the algorithm that should occur whenever a dungeon level is first generated to create 5-8 rooms with each room being connected to at least one other room. If anyone knows of a good resource/reading for how to do this kind of thing, I would greatly appreciate it. Any any feedback on my plan would be awesome as well.

  1. Make an array of 5 - 8 rooms.
  2. For each room (an array itself), assign values for {description, light_level, trapped (boolean), items, monsters, connectors}. Perhaps a dataset is the correct tool here…?
  3. For each element in the room, the assigned values are picked randomly from predetermined arrays (the contents of which are based on the depth and level of the player), except for the connectors.
  4. For connectors, create a link to a randomly selected room from the array of rooms created in (1) + the “dead end” room and a null value (in which case no connector is made). Repeat this process until at least a few connections are made in addition to any connections made to null and/or dead end. Hide half of the connections so that they have to be found by searching.

Thanks so much to anyone who read all of the above and double thanks for comments. Hopefully the above isn’t just the insane ramblings of someone trapped in the Dungeons of Doom!

1 Like

I can’t comment on the Twine implementation specifics, but in general, I think you’re looking to create what’s called a connected graph in computer science. The graph consists of vertices and edges: a vertex corresponds to a location in your dungeon, and an edge corresponds to a connection between two locations. The edges can also have numerical weights, representing length/duration/cost, for example.

The graph is called connected because there is some way to reach each point from every other point via the edges (there is no completely isolated part).

If you do not have any special constraints (for example, that the locations should form a “plausible” set of rooms or follow a certain layout or floor plan), then one simple way to make a connected graph would be to just pretend you’re a miner:
Cave out a room (create R1), dig a corridor (create connection R1-R2) and cave out the next room at the other end of that connection (create R2). (Depending on the implementation, these steps could mean creating the connection to a random R2 picked from the initial list of rooms, basically as you said, and removing that room from the list.) Then repeat that, continuing from R2.
When you have enough rooms, you can stop, and it’s guaranteed that there are no isolated parts. Then you can put in some random additional connections between the rooms (for example, between R1 and R5, R6 and R8, etc.) to spice things up.

There’s a similar algorithm on the following site, for example: How to generate a random connected graph? - Algorithms Q&A

I hope this goes in the direction you’re aiming for, and/or gives you some good search terms (generating a random connected graph).

1 Like

A few years ago i wanted a simple method i could make work on an old 8-bit computer. No memory = Nothing fancy.

I built a derivative of this method, so i could generate “rogue” like layouts like this:

................................................................
................................................................
................................................................
.............┌──────┐.....┌─────┐...............................
.......┌─────┤      │.....│     │..┌──────┐......┌─────┐........
┌──────┤     │      ├────┐│     │..│      │......│     ├────┐...
│      │     │      │    ││     │..│      ├──────┤     │    │...
│      │     │      │    ││     │..│      +      +     │    │...
│      │     │      │    ││     │..│      ├──────┤     +    │...
│      │     +      +    │└┬─+──┴┐.│      │......│     │    │...
│      +     │      │    │.│     │.│      │.....┌┴───+┬┴──+─┤...
│      │     │      │    │.│     │.│      │.....│     │     │...
│      ├┬─+──┼───+──┴─┬──┘.│     ├─┴───+─┬┘.....│     │     │...
│      ││    │        │....│     │       ├──────┤     +     │...
└──────┘│    │        │....│     +       +      +     │     │...
........│    +        ├────┤     │       ├──────┤     │     │...
........│    │        +    +     │       │......│     ├─────┘...
........│    │        ├────┤     ├──┬+┬──┘......│     │.........
.......┌┴─+─┬┤        │...┌┴──+──┤..│ │.........└─────┘.........
.......│    ││        │...│      │..│ │.........................
.......│    │└────────┘...│      │..│ │.........................
.......│    │.............│      │..│ │..........┌────────┐.....
.......│    │.............│      │..│ │┌────┐....│        │.....
.......│    │....┌────┬───┴───+┬─┴──┴+┴┤    ├────┤        │.....
.......│    │....│    │        │       │    +    +        │.....
......┌┴──+─┴┐...│    │        │       +    ├────┤        │.....
......│      │...│    │        +       │    │....│        │.....
......│      │...│    +        │       │    │....└────────┘.....
......│      │...│    │        ├┬+┬────┴────┘...................
......│      │...│    ├─────┬+┬┘│ │.............................
......│      │...└────┘.....│ │.│ │.............................
......└┬+┬───┘..............│ │.│ │....................┌───────┐
.......│ │.......┌────┐.....│ │.│ │....................│       │
.......│ ├───────┤    │.....│ ├─┴+┴┬────────┬────┐.....│       │
.......│ +       +    │.....│ │    │        │    ├─────┤       │
.......│ ├───────┤    │.....│ │    │        │    +     +       │
.......│ │.......│    ├─────┴+┤    +        +    ├─────┤       │
....┌──┴+┴─┐.....│    +       +    │        │    │.....│       │
....│      │.....│    ├───────┤    ├────────┴────┘.....│       │
....│      ├─────┤    │.......└────┘.................┌─┴─+───┬─┘
....│      +     +    │.......................┌──────┤       │..
....│      ├────┬┴──+─┴─┐.......┌───────┐.....│      │       │..
....│      │....│       │.......│       ├─────┤      │       │..
....│      │....│       ├───────┤       +     +      +       │..
....└──────┘....│       +       +       ├─────┤      │       │..
................│       ├───────┤       │.....│      │       │..
................└───────┘.......└───────┘.....└──────┴───────┘..
................................................................
2 Likes

Hi, that’s exactly the kind of thing I’m looking for – I just didn’t know what to call it. Even better that the example is in Python. Thanks very much!

1 Like

Nice, thanks very much!