Friday, March 30, 2012


After a brief detour to upgrade my IDE so I can use C++11 and its many exciting new features, I'm back to more layout fun.  While I've got it generating some levels I'm very happy with, much of the time it fails to find a solution and winds up searching forever.  I've taken a couple of stabs at coding my way around this in the dark, and I've pretty much settled on the conclusion that I'm going to need to make the visualization happen so I can diagnose the problem(s) directly.  Probably I've wasted more time hemming and hawing about doing this visualization than it will even take, so... yeah.  I'll get right on that.  Maybe after a short break.

Tuesday, March 27, 2012

Lock and Key

Tonight I put in the first keys and locked doors, along with a primitive run command.  Right now running is bugged so it takes only one step to cross a whole line of squares; this is pretty handy for keeping the monsters off my back, hehehe.

The locked doors worked fine pretty much off the bat; the logic is very simple, after all.  However, it's a good opportunity to start thinking more about how to keep track of where level features (keys, locked doors, stairs, monsters, etc.) are supposed to go.  This information is intimately tied up with the generation of the graph, so it's a bit tricky to conceive of separating those concerns.  Anyway, I got something fairly sensible in place and it seems to work, so I'd say it's a nice step.

Next up will be to parameterize the graph generation so that I can specify what I want in terms of abstract characteristics (number of key/lock pairs, amount of extra rooms beyond core structure, etc.) and get a variety of corresponding levels.  I'll hold off on screenshots for now, because the upcoming ones will look much nicer than my little three-room test with one locked door.

Monday, March 26, 2012

Now We're Getting Somewhere

The switch back to force-directed layout proved to be a big success; the level aesthetics are far better now, as expected, and the hallway pathing is proceeding much more cleanly due to greater locality between neighbors.  Here's a 5x5 grid of rooms, looking very fine:

I'd still like to get those rooms a lot closer together, but this is way better than before.  The process is also still pretty slow for a level this size, but not so slow that I'm worried; at worst, there could be a background thread generating levels ahead of time.

This seems like a good place to let the hall layout stuff rest for a moment and change gears to something new.  I guess I'll get on to those lock-and-key puzzles next!  Oh, and I've got to implement a run command; going down those long hallways is driving me crazy.  Progress should come much more quickly on those kinds of features, compared to the research project these hallways have turned out to be, so perhaps we can start to have something that feels like gameplay before long.

Sunday, March 25, 2012

Hallway Headway

I've made a satisfying bit of progress tonight on this hallway layout problem.  Here's an example of an 8-room graph it's doing well with now:

The key improvement that got me to this point was to reuse some intermediate values from the layout algorithm to help me choose the best order in which to draw things.  The rooms are gone through in planar canonical order, which guarantees that vertex k+1 is on the external face of the subgraph with vertices 1..k; this ensures much easier edge-drawing.  Furthermore, there is a representation called a "planar embedding" that lists the edges for each vertex in clockwise order.

By following these two orderings, I got a lot of hallways to stop running into each other, wrapping around rooms, and hogging space in weird ways.  Oh, I also changed the A* heuristic from Euclidean to Manhattan distance, which helps avoid wall-hugging and gives a more organic feel overall.

There's still a ways to go, I'm pretty convinced of that.  I tried a 10-vertex graph similar to the above, but that seems to be asking too much.  I'm increasingly thinking I'll go ahead and invest the time in a realtime display of level generation in progress, so I can see what's going on rather than trying to guess what goes wrong based on looking only at successful levels.  Should be fun to watch, too.

I'm also considering moving away from the Chrobak-Payne straight line drawing algorithm for layout, most likely in favor of going back to Fruchterman-Reingold force-directed layout I was using earlier.  The Chrobak-Payne output seems a bit too regular to give a satisfying sense of randomness.  It has a characteristic triangular shape, which leaves a lot of space unfilled, and there's always that long straight hallway at the top between the first two rooms.  Of course, I could imagine ways of fudging around that (e.g. put in dummy rooms and don't include them), but I think I'd like to see what my other options look like at this point.  A different choice of layout strategy could even turn out to make hallways route more cleanly, so it's an opportune time to consider it.

Oh, I also found an interesting paper that seems very applicable to this problem, discussing a method for drawing planar graphs with vertices and edges that take up space rather than being infinitesimal.  I'm still mulling over their algorithm, but it's nice to find some relevant recent work.

Friday, March 23, 2012

Something in the Way

I put in some changes to door placement code, which has stopped hallways from being blocked at the source.  However, the general issue of existing hallways blocking where other ones need to go persists.  This is an artifact of the discrete nature of the grid -- while it may be true that I have a planar graph layout,  so that rooms can be connected without hallways crossing, there's nothing to guarantee that the hallways actually have enough room.

Currently I've got it taking a trial-and-error approach with different pairs of door locations for each hallway.  This works out in a larger number of cases (I've had it generate reasonable levels, some of the time at least, for 5 or 6 rooms), but past a certain point of complexity it just gets stuck in a hopeless state and runs forever.

Improving on this situation is a significant challenge; I'm still thinking of what I want to try.  One thought I've had is to change the A* heuristic to discourage hallways clustering around rooms.  This would particularly address a situation I commonly see where a hallway wraps tightly around the perimeter of a room, blocking most possible door locations for other hallways yet to be routed.  However, it's clearly a band-aid idea, and I'm not sure it wouldn't create problems when rooms are close together (currently the levels are quite spread out, another matter I hope to address in due course).

What I'd like to do more ideally is let the hallways "shove" each other around until they fit.  I'd like to be able to treat the grid as a rubber sheet and just stretch out new areas when I need more room.  It sounds like a good general solution, if I can manage to implement it reasonably.  I expect deforming existing dungeon features without messing up structure to be pretty hairy, though.  Going to ponder this one for a while.

In a way, the existing approach is a simplified rubber sheet.  Having chosen a particular scaling factor and failed to lay out the level within that size, it bumps up the scaling factor and tries again until it succeeds (or enters a quagmire).  At first blush it would seem that this solves the problem, albeit gracelessly, since if you expand endlessly there should eventually be a big enough gap wherever you need one.  However, since it re-routes every hallway after it re-scales, the same exact situation can simply occur again because it will just hug the corners that much tighter.  So, something more sophisticated is called for.  I'm still convinced it's tractable, though.

Thursday, March 22, 2012

Where's Monty Hall When You Need Him?

A detailed debugging dive on a 4-room layout revealed what I hope is the primary problem with hall layout: doors are being placed too close together.  Nothing surprising about this, in retrospect; the doors are being placed along the line segment connecting the two rooms' centers, which by no means guarantees doors won't be adjacent (actually, they could probably even wind up on the same tile, in theory).  Since the layout algorithm forbids running hallways through any point adjacent to an existing open space (such as another hallway), an adjacent door with a hall leading out of it makes the new hallway a non-starter.

So, it's time for a new theory.  I'm now pursuing an approach that seeks to space the doors out evenly along the room perimeter, then assign each door position to the most suitable hallway.  Iterating around the edge of a room should be a fun little coding exercise, and I'm hopeful that the extra space will give the multiple A* calls enough elbow room to work their magic.

More, as always, when I have further results.

Oh, a couple bonus items.  I found this interesting article about a particularly twisty hand-designed dungeon map, containing a number of Escher-inspired twists and bits of impossible topology.  I've had numerous ponderings of putting similar areas into SnargleQuest (to make it all the more snargly), so this is excellent food for thought.  I recommend a proper look at the PDF itself, for details on the areas of interest.

Secondly, I managed to find an online copy of the pen & paper RPG Lost Souls, which I'm happy to see is now under the Creative Commons license.  Page 64 has the table at the core of the skill system, which as I've mentioned before has heavily influenced my own approach to handling skills.

Wednesday, March 21, 2012

n == 3

Progress on hallways continues to grind along, never as easy as it appeared in the distance, but always in motion.  I spent a while getting A* to filter out open squares and their neighbors, to prevent leaks; now it's developed a tendency to search forever without finding its destination.  I'll be ramping up the unit tests to get a handle on this business, most likely.

That said, it's starting to look reasonable for the case of just 3 rooms, if we can look past some minor door placement issues:

I redid the positioning in a new way that gets rid of the skew we had before; now it just scales the raw coordinates (which are too close together to begin with) by a constant factor, increasing that factor if things turn out to be too tight.  Nice and simple, but it doesn't solve the problem of A* searching forever.  Hallways must somehow be cutting off doorways, but it's a little difficult to get visibility into how unless I build a bunch of new (probably sorely needed) instrumentation to help me see.

I find myself pondering again an idea that had occurred to me before, which was to route hallways first and then overlay rooms on the intersections.  This would have some advantages, but brings issues of its own.  The more I think about it, though, I think it may be the way to go.  Guess I'll sleep on it.

Monday, March 19, 2012

A* is Born

It works!  Here's a screenshot of the first level generated with A* hallway pathing:

It's not picture-perfect yet, but the laundry list to get it there is short now that the core is working.  I need to filter the grid graph used in search so that only orthogonal edges are used (to prevent those ugly diagonal hallways), and further to prevent pathing through squares with open neighbors (creating pervasive "leaks" in the level structure).  Oh, and I need to rewrite the coordinate scaling code so the level doesn't have that weird skewed look.  I've already got working code to do the orthogonality part, so we really are almost there.

Sunday, March 18, 2012


I've finally had my first successful test running BGL's A* search on an implicit graph representing the level.  I'm going to test it a bit more, then start working it into the hallway code.  Barring unknowns (hah), I'd say I'm over the primary technical hurdle for dungeon layout now.  Feels good to prove it to myself, but I'll be happier still when I can show it here.  Hopefully I can update later tonight with results for your eyeballs.

edit: Well, maybe not tonight.  Ran into some issues with the filtered_graph adapter.  I'll sort out a way around it soon enough.

Thursday, March 15, 2012

The Slow, Good Way

Once again, I've decided to substitute long-term measures for short-term ones in my ongoing level layout work.  I had been able to get pretty far by cannibalizing the pathfinding code, but my preferred design has always been to run A* on the graph described by the level grid.  Several months back I took a crack at this and found it difficult to make hay out of BGL's astar_search; I'm feeling more practiced now, though, and hence more ambitious.

Fortunately, too.  With an infinite grid, this graph can only be represented implicitly; fortunately, BGL once again has the answer.  User-defined graph classes can be designed conforming to the family of concepts used to specify BGL's algorithmic interfaces, and such classes can be designed to represent implicit graphs (even infinite ones).

I'll be wanting this level detail graph stuff later on for many other purposes anyway, so once again it seems worthwhile to take the time and do it, though it's another pesky impediment to my visible progress.  Speaking of worthwhile investments, I've finally spent the chunk of time to set up a testing framework, so I should be able to keep things less chaotic going forward.

I expect it'll be a minute before screenshot time comes again, but I sure hope to be able to show off some dead-on perfect hallways by the end of it.  Wish me luck.

Tuesday, March 13, 2012

Tunnel Vision

The hallway routing fun continues, and I threw the center-on-player thing in.  This would be going faster if I were less lazy (not the "good programmer" kind of lazy) and set up some automated tests.  But that would make it more like work, and I'm enjoying my hackish hobby ways.  Anyway, it's coming along:

There's a bounding box problem cutting off those hallways you see, for one.  Also, halls still abut one another and cut through rooms where they shouldn't, doorways are often diagonal and shouldn't be, the room layouts aren't evenly distributed, and the whole thing is dog-ass slow.  Who's training these monkeys, anyway?

Next episode, I hope to clean up enough of this stuff to make it passable enough so I can move on to playing with locks and keys.

Monday, March 12, 2012

Proving the Concept

Unfortunately, Real Life has not handed me a lot of time for programming in the last week; however, I seized a few moments this evening to try and get some kind of in-game view of the BGL-generated room layouts.

Since the algorithm I used generates a layout within a smaller coordinate plane than I'm using, I needed to stretch the space out somehow to make sure the rooms all fit.  My method for now is very simple: I maintain an integer offset as I'm placing rooms, adding it to both x and y.  Any time I try to place a room but find the desired spot unavailable, I just increment the offset and try again.  I think I'll probably have to go back and tighten this up a bit to make sure the rooms are iterated through in a particular order, but it seems to be basically working:

As you can see, the rooms are too close together, and the doors and halls are a complete mess.  I'm sure to be sorting that stuff out (again) for the next little while, especially since I've also disrupted things by changing the coordinate system from signed to unsigned, no doubt wreaking all sorts of subtle havoc.  Making everything unsigned was a mistake to begin with; I should have realized I'd want to be able to expand in any direction.  So far the problems seem minimal, though.  The level bounding box had been giving me headaches anyway, and tended to complicate hallway routing, so I can't say I'll be missing it much.  This does mean I'll have to put in scrolling exploration soon, to get to offscreen areas, but that'll be simple.

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.

Friday, March 2, 2012

Wacky Fun Door Time

Tried a new approach to the hallway thing, based on the pathfinding data structure.  I don't think I'll stick with it:

Basic doors are working, though, and I reckon I'll have this hallway business sorted out properly soonish.

Thursday, March 1, 2012