Representing a dungeon as a data structure
-
Language: C# if it matters.
So consider the following problem domain. I want to model a D&D dungeon (the physical layout, anyway), as a code object or data structure.
Dungeons have one or more chambers, with each chamber having one or more exits (including the way into that chamber), which connect to doors or passages. Doors connect to either passages or chambers; passages can have 1+ exits (including the initial one, which themselves could be doors, passages, or chambers). A passage or chamber with only one exit is called Terminal. The dungeon always has a single starting chamber, which is a bit special and is guaranteed to have at least two exits. Each passage or chamber or door has a string description; passages and chambers can have contents (which for this purpose are a string). The dungeon ends after a certain number of chambers are constructed; all other passages and exits are marked as Terminal.
The end goal is to be able to create some kind of (for now) textual representation of this dungeon, something like
StartingChamber: Description | - Passage : Description | - Chamber : Description | - Door : Description | - Chamber : Description | - ... | - Door : description | - Passage : Description | - ...If I were really fancy, I'd produce a tree graph showing the connections. But that's a project for a later day.
To me, that sounds like a graph or tree of some kind, with the starting chamber as the root node, and the other nodes being items of an interface type (implemented by
Chamber,Passage, andDoor).Is there a standard way of
a) representing such a tree in code (such as a built-in data structure for such things)
b) generating such a tree? Recursion? Some form of iterative tree/graph traversal?Any ideas on whether I should go
a) breadth first--for each node, generate one layer deeper on each exit, then go to the next layer, stopping when all chambers are generated (or on a branch when I hit a terminal passage/chamber)
b) depth first -- for each node, follow one exit until I hit a terminal node, then step back up one layer and repeat?I don't have tons of experience working with graph or tree structures as such. Lots of experience using data structures that are implemented as trees, but which hide the whole implementation structure and just provide a simple "get"/"set"/"find" interface, such as
Dictionarytypes (which are often a HashMap/tree under the hood), but this is my first attempt at implementing a custom tree or graph.Edit: I have already built the base units (doors, chambers, passages) with all the rules needed to generate them. It's the wiring them all together into a full structure that I'm not sure what is the best way to approach it.
Edit 2: For now, the ability to "loop" (ie connect a passage or chamber to an already-generated passage or chamber is optional. I believe that'd be the difference between a graph and a tree--trees are singly-connected while graphs (in general) can be cyclic. But I guess I should choose sooner rather than later, because the implementations will be different.
Note: This is a hobby project, mainly for learning and (secondarily) to help me build D&D stuff easier. I know there are plenty out there that do it better, but still.
-
I was pondering but then I saw the author before going "wait, didn't someone here do this?"
If you don't care about being able to physically represent the rooms in Cartesian space relative each other, simply giving them an ID and an array of associated "connecting to" IDs should do the job, can be as fancy as you like.
Generating a printout is easy enough assuming you have a way of denoting repeated entry links (if any).
I'm not really keen on a tree view, mostly because I'm wondering why you're starting with the textual representation? It almost like you're trying to work backwards.
-
@Tsaukpaetra I'm starting with text because that's what the rules generate--I'm turning a set of random dungeon generation tables into an automated, one-click generator.
So a chamber might be '20x20 square with a door on opposite side from entrance and a passage leading off the right wall." A passage might be "10ft wide, straight 10' and then an exit on the right, then 30' straight."
And all the possible "tiles" are in d20 or d100 tables, with rules on when you roll on each one (generate a chamber by rolling on the chamber table to get the size, then on the appropriate exits table for that size, then roll for each exit to see if it's a door or passage, then...)
-
Is there much of a difference between "chamber" and "passage" other than description? A passage might described in terms of simply being a long
skinnytwisty chamber.If there is no such difference, then you're looking at a graph structure, with the chambers/passages being the nodes and the doors connecting them the edges, attaching the doors' descriptions/state (open/closed/hidden) to their respective edges.
It would be best to assume a graph from the start I think, rather than a tree, because wanting cycles would I expect be pretty much inevitable.
-
@Benjamin-Hall said in Representing a dungeon as a data structure:
Any ideas on whether I should go
a) breadth first--for each node, generate one layer deeper on each exit, then go to the next layer, stopping when all chambers are generated (or on a branch when I hit a terminal passage/chamber)
b) depth first -- for each node, follow one exit until I hit a terminal node, then step back up one layer and repeat?Firstly, I'd go with unifying chambers and passages into rooms; doors don't have to care what type of room there is on each side. I'd also go entirely with concrete classes to start out with, at least until it's proven that there's a need for interfaces.
I'd use a depth-first iteration strategy, but I'd track what rooms have already been visited as well (basically some sort of set implemented as a hash table; C# must have such a thing as standard), adding the room to the set of visited rooms on first entry. Like that, I'd be able to handle loops in the dungeon without the code going berserk; purely tree-like dungeons are easy to generate, but ultimately boring. (I used a similar sort of strategy in my first job, except the “dungeon” was the temporal execution graph of a program running in a simulator whose state I was searching for deadlocks and livelocks.)
-
a) representing such a tree in code (such as a built-in data structure for such things)
There are three common options. I'd go for a graph stored as an adjacency list. Each room has an identifier and a list of identifiers for adjacent rooms. A separate dictionary maps identifiers to room instances. This also makes it very easy to serialize.
b) generating such a tree? Recursion? Some form of iterative tree/graph traversal?
You can use a modified randomized Prim's algorithm: keep a list of walls (or wall segments). While the list is not empty, pick a random wall and generate an adjacent room, adding its walls to the list. You can randomly leave out walls or entire rooms from this list to bias the size of the dungeon and the number of terminal rooms.
If geometry is important, i.e. you don't want impossible, overlapping rooms, you can keep rerolling the room dimensions, use a grid system and "grow" rooms around a seed room, use a spatial tree, and so on. The possibilities are endless. I built a genetic algorithm for generating floor plans based on this paper.
For printing, if the dungeon is more graph-like than tree-like, I'd construct a tree breadth-first so you don't end up with a very deeply nested output. Implementing this is easy: you create a "to-be-visited" queue and a "visited" set. Put the root in the queue, and while the queue is not empty, dequeue a room and add any unvisited neighbors to the set and queue, while erasing the edges to the visited neighbors.
You can then print the tree using depth-first traversal. There may be a more efficient way to do this, though.
-
I think I’d do this by numbering all the exits of each room and indicating to which number of exit of which other room each exit connects. This would also easily let you do things like one-way doors, teleports and similar magic stuff.
Also, as has been said, treat passages as rooms — there’s only a semantic difference, after all.
If you want to be able to actually map this out automatically, I suppose you’ll have to incorporate a way to describe the shape and size of the room as well as the locations of the exits, of course.
-
Back some years ago when I worked with Boost.Graph (C++), I ran across a C# library and some talk how the concepts map to interfaces and such. I am not sure whether it was QuickGraph, but whether it was or not, QuickGraph should give you some head start as it already implements the adjacency list with appropriate maps for searching (and serialization), and some basic search algorithms (and lots and lots of other algorithms).
Most likely you want rooms (chamber or passage) to be vertices and door to be edges. You can make passages edges with the two door being just attributes of the edges, but then if passages can branch, you'll need to make it a multi-graph.
-
For those saying to treat passages as chambers, there is a difference in the original generation method. Chambers can have contents and purposes, while passages can't.
Which leads me to a realization (after I posted it)--for my purposes (which aren't to actually produce a geometric map, because that requires way too much manual intervention to get something I like), chambers are important. Passages (and even doors) are not--they're just connectors. So I could just assume that every chamber connects to at least one other chamber, and treat all exits as either being
- a (vaguely-described) passage + door ensemble to one or more chambers
- a (vaguely-described) terminal passage
This lets me start at the starting chamber and for each exit decide if it's a dead end or not; if not, generate that next chamber. For each subsequent chamber, keep a list of existing ones and decide "new chamber or visited chamber"; if visited, pick an exit to link to. Then in presentation I can just present the chambers, with a list of "exit X connects to chambers A and B via <description, possibly with hazards/obstacles>". Each chamber would know the identifiers of all the chambers it connects to, but I can otherwise treat the chambers as separate things without worrying about cyclical references and I don't have to worry about passages or doors pretty much at all. I can add those in whenever, or have the same dungeon in a radically different geometric shape by varying the passages.
Effectively, this makes a point map rather than a "full" map. Which is more useful for many of my cases.
-
@Benjamin-Hall Or you could add a flag
isPassageand only generate contents if that’s set tofalse.
-
I could imagine having more room types than chamber and passage if you want to group similar chambers together. I mean, it's pretty unlikely for a prison cell to sit right next to the lord's bedroom.
-
@PleegWat For the purposes of this project (which is to port a set of random tables and associated rules), having chambers and passages is enough. Since really this is more about producing inspiration, which is then expected to be tweaked, rather than actually procedurally-generating a playable dungeon directly.
The overall project is to provide help to a TTRPG DM (ie me) in creating content. I have modules to create settlements (using setting-specific data), NPCs (focusing on town ones with things like occupations, culturally-proper names, religiosity, and personality) and adventure sites (really just creating things that say "a level [5] [underground] [vault] populated by [beasts] [with a boss monster]", where things in [] are randomly generated from input data representing the regions of the fictional world with probabilities set (so places without giants aren't going to have giant dungeons).
-
@Benjamin-Hall It kind of sounds like you’re trying to implement something like this:
-
@Gurth sort of, but way more heavily customizable for a setting.
-
@Benjamin-Hall I wouldn’t suggest basing it on that set, for sure … I think I did a bit of a trial run with it once, and quickly gave up.
-
@Gurth Yeah. Thankfully I'm not doing that. The dungeon tables come from the 5e DMG, just tweaked a bit. The rest is all my invention. The tables are fine, but super labor intensive to use. The goal is to let the computer do all the rolling and table lookup stuff.
I may implement treasure tables that include the non DMG items and random encounter generators for different areas and types, but that's in the future.
-
Dammit now I miss the boxed set of Warhammer Quest I used to have :(
-
@Tsaukpaetra said in Representing a dungeon as a data structure:
I was pondering but then I saw the author before going "wait, didn't someone here do this?"
Were you thinking of Mason Wheeler's Stormhunter Studios project?
Unless of course @Benjamin-Hall has posted before about this and I just forgot whether it was his thread that was debating such data structures.
-
@JBert I may have posted something on this project, but it was a long time ago and both my experience level and thinking has changed on the matter. Plus, threads are free!
-
@JBert now I've read this thread and I am disappointed, I see the game on Steam but I don't really want to throw money at something - even a few bucks - if it looks like it's guaranteed to not work.
-
@PleegWat said in Representing a dungeon as a data structure:
I mean, it's pretty unlikely for a prison cell to sit right next to the lord's bedroom.
Depends on how sexy the prisoners are.
-
@Arantor Huh, I hadn't actually checked out the Steam page because I thought Tsaukpaetra might have been thinking of the discussions on this board.
Seems Mason Wheeler went for a cloud login which couldn't be bothered to work. That's a pity, but I would indeed recommend staying away from it. Mason seems to no longer frequent this forum so getting support this way is unlikely.
-
@Zecc said in Representing a dungeon as a data structure:
@PleegWat said in Representing a dungeon as a data structure:
I mean, it's pretty unlikely for a prison cell to sit right next to the lord's bedroom.
Depends on how sexy the prisoners are.
Or how into torture the lord is.
-
@dkf Inclusive or, of course.
-
Now I’m imagining some weird hybrid of Warhammer Quest and Dungeon Keeper…
-
For all those complaining about posting unhelpful things in a help thread:
- It wasn't unhelpful, since that (or equivalent) is actually something I have done in a dungeon.
- I consider the help request filled before that, so feel free to treat this as a regular thread.
