Wednesday, February 22, 2012

Dungeon Structure

Dungeon level generation in SnargleQuest is based on a graph-theoretical schematic representation of the  level, with nodes for rooms and edges for hallways.  The idea here is to be able to reason about and manipulate the structure of a level in a coarse-grained way before letting all the details flood in and make things more complicated.  It seems to me that this represents a new and fruitful approach, and one which roguelikes generally could benefit from exploring.

Since graph theory is so well-developed mathematically, and strong tools for working with graphs exist (e.g. the Boost Graph Library, which is core to my implementation), using graphs natively provides a large set of capabilities for manipulating level structure.  For example, it may be desirable to have a choke-point in the dungeon -- a single room that the player must pass through to reach the goal (exit, stairs down, treasure, etc.).  In graph terms, a choke point is simply a node that connects two otherwise unconnected subgraphs -- quite trivial to identify or create.

A choke point can become many things.  You could have a sequence of choke points containing mini-bosses on the way to a main boss; just as easily, they could be used for lock-and-key puzzles -- not just little local puzzles, which I understand BRogue has now, but big structured puzzles that could potentially send you running all over the level (or levels, or world) in search of a whole series of keys or key-like objects (buttons to push, enemies to kill, NPCs to interrogate, etc.).

Using graphs this way is no free lunch.  BGL is a complicated library to use, for a start.  More fundamentally, the use of a graph for the level brings along the problem of ensuring that the graph is planar, and then providing a planar layout for it (so that hallways don't cross and screw up all my careful structure).  General planar graph layout is NP-complete, but we have the advantage of constructing the graph arbitrarily, so we can adopt strategies to ensure planarity and ease of layout.

I've explored a few ideas related to the layout problem, with varying degrees of success.  I'll certainly continue to explore more in this area and have more to say later, but I'll summarize some of my early efforts.

My first idea was to use a spring-system simulation to make rooms "push" each other into a well-distributed, planar layout.  There are a couple of algorithms for this available in BGL, and I had some success with the Fruchtermann-Reingold algorithm, but ultimately I found the results were a little samey. Also, I wanted the ability to run just a single "step" of the algorithm at a time, to watch the "sproing" in action, but this capability is not available in the current BGL version (apparently the unmaintained Python BGL binding adds this capability, but the hell with that -- this is a C++ project down to the bone).  So, this approach wasn't bad for a start but I've mothballed it for now.

The second idea I started on was a much simpler way of ensuring that we had a planar graph, and layout, to start with: just create a grid, connecting neighbors (orthogonally, and with some diagonals if desired), and then trim the grid down to get a less-connected but still planar graph.  BGL allows us to obtain a random spanning tree of such a graph, which is a great starting point for a decent level structure; if more connections between rooms are desired than this rather sparse tree, they can be imported in from the original grid, and we can feel secure in the knowledge that none of these edges will cross.

So, that's not bad, and I may go on to implement that one at some point, but it's currently also mothballed in favor of my latest approach: discretized Voronoi diagrams generated by cellular automaton.

A Voronoi diagram is a tesselation (division into regions) of a plane, where the plane contains a number of distinguished points (nodes).  The region around each node contains all points within the plan that are closer to the given node than any other.  I found that these diagrams have desirable properties for use in this problem.  In particular, the line segment from one node to any neighboring node (one whose region shares an edge with that of the first node) crosses only those two regions and their shared boundary, not any other regions or boundaries.  This means that, if we use the shared boundaries of the Voronoi diagram to tell us what connections to make, we connect all rooms to their nearby neighbors without any hallways crossing.

There are sophisticated algorithms available for producing Voronoi diagrams (or their dual, Delauney Triangulations, which are sort of what we wind up with after we draw the hallways connecting nodes) on a continuous plane, but for a discrete space defined by dungeon tiles, I found that I could do something much simpler.  I wrote a very simple cellular automaton that simply spreads a region of "influence" outward from each node, tracking the boundaries as the regions run into each other.  I knew I had a winner with this idea when it worked perfectly the very first time I ran it.

I'd love to post some screenshots that show the actual Voronoi diagrams, but for now that's all implicit and you can't see it directly.  Maybe I'll fiddle around and make that happen later, but I'll probably post some regular dungeon screenshots first.  Anyway, enough on this for now.

No comments:

Post a Comment