Monday, March 5, 2012
Crawling Through BGHell for a Twistier Tomorrow
The hallways were starting to look good-but-not-perfect, when I started running into issues that I knew would not pertain in my ultimate design. I had a working method for generating planar graph layouts, resulting in plausible-looking levels, but the layouts were random -- they did not conform to any specified structure.
To get levels with the structure I want, I saw two possible approaches: take something like what I had, and try to trim away edges to match the desired schematic, or adopt a bottom-up constructive approach. I spent a good while learning about graph expansions and contractions, isomorphisms, homeomorphisms, dominator trees, and so on and so on. There are a lot of NP-complete problems in this space, which gave me no end of worry as I sought for a solution. Finding nothing that seemed quite workable, I went back to the drawing board for a constructive approach.
At this point I hit upon something that I wished I'd noticed earlier -- the Boost Graph Library planarity testing algorithm (boyer_myrvold_planarity_test) actually has an option to compute a planar embedding for the graph. The BGL docs define a planar embedding as "an equivalence class [...] defined by the clockwise ordering of adjacent edges around each vertex in the graph." So from this intermediate representation, it turns out to be possible to chain a number of other algorithms together and ultimately compute a straight-line diagram, the coordinates from which can be mapped into dungeon space and plotted as rooms.
The BGL is an incredible tool, but it's viciously complex and can be demoralizing to work with when you get something even slightly wrong. I gradually discovered, spelunking carefully through callstacks and template parameter lists, ways in which I had missed preconditions such as making the graph biconnected, and then maximal planar, before finally passing it to the layout algorithm. At several points I ran into completely baffling dead-ends, but by continually returning to the provided code samples I was able to sort out the subtleties and see it work from end to end.
At this point I've just got scaling to take care of before I can apply all of this and test it out in-game, but my prototype seems to be working correctly now and I hope to be demonstrating principal success soon. It'll be quite a relief to finish getting over this hurdle -- apart from the frustration it's put me through, it's a critical proof of concept, and the gateway to a number of fascinating new directions I can begin to take soon thereafter.
First on the list are nested lock-and-key puzzles. We've seen some beginnings of this idea in BRogue, but there seem to be some limitations inherent in BRogue's approach (though I'd love to be proven wrong), and my system is designed to overcome them. Playing BRogue on some programming breaks this weekend, I've seen occasional levels with two pairs of keys and doors. Sometimes one key opens a door to a vault containing another key, the door to which is either right there at the back of the vault or somewhere else across the level.
In either case, the limitation is the same -- these vault areas are dead ends and not structurally meaningful for the level. Contrast this with a system in which a player, on opening a locked door, may find their way into an arbitrarily-expansive new section of the dungeon (even multiple levels deep), somewhere in which is hidden the next needed key (or quest item, or boss monster, or hostage, or what have you). Consider the ability, given such generality and the ability to analyze reachability in a tractable way over these large structured spaces, to construct long, branching dependency chains of quest objectives, all carefully structured to conform to narrative requirements while accommodating procedural generation of suitably-constrained environments. I'm pretty excited about it.
Just to say a little more about how these graphs are to be constructed, the basic idea is to start with a simplified graph, derived from the narrative (or just random scenarios, for now at least), that expresses only the fundamental structure required by the plot. The nodes represent all the important areas in the level, and the edges show how they are connected. The connecting edges need not be single hallways, but can be "elaborated" through repeated simple transformations designed to increase level complexity while preserving planarity.
Various schemes can be adopted to determine how much each section gets elaborated, so you get a lot of control over how the player's experience will be paced. In the final graph, the original nodes appear as articulation points; the player has the same ultimate choice of paths through important rooms as in the original small graph, but the elaboration of edges into complex subregions provides for substantial variation in player experience within the same "schema."
As my ideas here advance into concreteness, I'm turning my contemplation cycles increasingly over to the narrative side of all this, where my vague feelings about the dependency graphs inherent in plots have not as yet resulted in anything so coherent as to accommodate being explicitly expressed as a graph and instrumented by BGL. I've got this little prototype that sews a few basic plot pieces together, but the graph there is all implicit, so I've got some engineering yet to do around that. Beginnings in that arena, though, are not I think too far off.