Friday, August 10, 2012

A Late Night, and a Milestone

A couple close friends have been kindly chomping at the bit to playtest, and I decided to scope out a demo and work towards that as a milestone.  Focusing my work like this felt pretty helpful, and a few sessions later I found myself cranking out the last few bits.  It kept me up until 3 in the morning, but I got it done and sent off.

It's too early to release anything public, but I'll talk about what it includes and what's next.  Basically, this demo shows the initial set of plot types all working together in randomly variable configurations, forming chains of related goals.  The most complex scenario, involving most of the available pieces, is a hostage situation in which the kidnapper is immune to normal weapons, necessitating a secondary quest to find a magic sword.  This secondary quest can be complicated by the sword being broken into several pieces that must be found.

The storytelling model continues to evolve with each new thing I try to make it do.  Every step so far feels positive, and I get a lot of opportunities to introduce things that feel like they'll be useful as the amount of content increases.  A recent example is an abstraction of a "fact," such as the fact that a hostage has been taken -- these relate to goals but have a separate identity and different responsibilities.

Now that the demo is done, I'll be going back to level layout.  I had a flash of inspiration the other night and want to try out a very promising new strategy that just might lead to great things.  I'll hold off on the details until I see how it pans out, but this could be very good.

Wednesday, August 1, 2012

Less Ugly

Spent the evening working down the backlog of bugs and display issues a bit, trying to prioritize stuff I can't imagine leaving unfinished in any demo I'd give to a playtester.  In particular, I finally took the time to sort out a crash-on-exit bug that I didn't realize quite how much I'd grown to hate until it was gone.

Here are some screenshots demonstrating a simple fetch quest for an item broken in two pieces:

The level structures here are trivial ones used for testing, naturally.  Twisty passages are still ready on tap, with much more to come down the road.

Stuffing the Guts Back In

Quick update today on progress from yesterday evening.  The new core of the quest dependency system is in place and humming along nicely, though I've got a lot of rough edges to grind down now.  The most complex working piece is the "unite the pieces" quest, which now creates individual "find item" quests for the pieces; each of these creates its own location exposition sub-goal that must be satisfied (currently, by listening for rumors in town) before you can go to the area holding that piece.

The next big goal in my sights is a longer chain of quests with a few more pieces: a hostage quest with a specific goal to slay the captor, for which you'll need a special weapon that's broken into pieces that must be found and reforged.  I think I can get this put together pretty quickly now, with the new works in place, but I'm starting to have to devote more attention to narrative details such as how exactly the "hook" for each goal is exposed to the player.

Monday, July 30, 2012

Tangled Web

Got a good chunk of time this evening and decided to rip out and replace more guts; in this case, the dependency structure of the goal system.  The prototype involved a verbose and redundant system of class factories, and they're simply not carrying their weight.  Much better, it seems, will be to implement the dependency structure with the Boost Graph Library, which I'm already using for levels.  I had wanted this originally, so now that I'm more familiar with the tools seems a good time.

Naturally, it's a huge mess.  I think this will cut out a lot of friction for me, though, with the ongoing plot work.  For now, there's a lot of old code commented out, and some half-written graph code awaiting further brain cycles.

Sunday, July 29, 2012

On the Questing Path

My work to integrate the quest generation prototype into the game proper has come along a good way, and afforded me the opportunity to tighten up some bolts and introduce useful infrastructure.  I unified and rearranged the UI, and re-routed all the text output through the event system (so now I'm not passing output stream handles around everywhere, which is nice).  The event system has also provided a nicely succinct way to handle quest goal satisfaction, since different goals are satisfied by different sorts of occurrences; the trigger sites can simply fire an event like "picked up item" and move on, without needing direct plumbing to the goal that cares about it.

Right now I've got basic (trivial, really) rescue and fetch quests working, along with a "unite the 6 pieces of the broken fooble" variant.  Each one I do sheds clear light on areas where the infrastructure needs to grow, so I plan to continue on into a number of these until they start to feel less useful.  Hopefully by that time the system will have enough working combinatorial pieces to make some emergent magic happen.  In any case, that should still keep me busy for a while.

I'd like to extend a nod to Lenna's Inception, a project I came across this week that has a lot in common with SnargleQuest; both are roguelike games (though LI is not turn-based, but a realtime action RPG strongly derived from Zelda) with gameplay based on procedurally generated lock-and-key puzzles.  I'm excited to see another developer exploring this space, and hope to see great things from that project.  I encourage you to check out the demo, released in June.

Sunday, July 8, 2012

Goings On

Not much to post about of late, but the adventure gradually continues.  I'm trying out a new health system; a prototype health bar GUI is visible in the screenshot.  Most of my current work, though, is about reviving my proof-of-concept code for narrative generation, untouched for some months, and using the generated plots to drive environment creation.  Everything is still incredibly basic at this point, but the plumbing is beginning to come together.  Here we see our hero entering the (unelaborated) lair of a spiked mummy (Z) who has kidnapped Princess Damsel (p):

Right now I'm finishing up the actual rescue portion of this scenario, after which I'll go to work on the other simple plots I've got so far, taking advantage of commonalities wherever I can.  Reuse of functionality for similar story elements is fundamental to my approach for narrative generation, so I'm eager to generate enough working content to let the concept prove itself out a bit.

Behind the scenes, I've used the quest stuff as an opportunity to start introducing a much-needed event system that will untangle my data flow appreciably.  Since quest goals could be anything, I needed something sufficiently general to handle event notifications without passing listeners around everywhere, so a central registry is an obvious choice.  In a similar way, implementing NPC behavior is providing tools that will also be needed for monster AI.

I'm playing with some fun possibilities for the medium term.  I think I may delve a bit into pixel shaders to try and get more of a neon glow look than the current flat line graphics.  I want to keep things simple and avoid spending a lot of time in a graphics hole, but I'd like to achieve the look I've got in my head.  In terms of game mechanics, I've come up with a fun idea where you change color by picking up a power-up, and different colors give you different abilities.  I'm still pondering ideas for what abilities would be good, how they could be used for puzzles, etc., but I like the number of gameplay possibilities that could arise out of this scheme.  Also, the color-change thing goes along with a general emphasis on color that I want to keep working for.

Saturday, June 23, 2012

Outside the Box, Just a Little

There seems to be no end to refactoring, but every step now makes something easier later.  Also, it's made some things easier now, and I've been up to a few new things today.  Rooms now have basic random monster and loot tables, and support is in for different room shapes:

The new ones are just made out of two overlapping rectangles.  I need to fix up the door attachments a bit so they don't do the diagonal thing you see here.

Had to update the display code for these new rooms, since it's no longer possible to just draw a rectangle.  Did a bit of research, skimmed the marching squares article on Wikipedia, and got to work.  To my great pleasure, it worked perfectly the first time.  Nice when that happens.  This algorithm should work fine for other room shapes I want to do later; I'll have to adapt it, though, for rooms with "holes" in them.

Up next, implementing a couple more layout types to get a bit of variety and further explore what works (and looks, and plays) best with the engine's current capabilities.  Then I think I'll get the AI working again (it's been broken since I converted the level indexing from unsigned to signed, quite a while ago).

Thursday, June 21, 2012


Progress rumbles beneath the surface.  I'm reworking things to make it possible to set up different room types while establishing level structure.  Getting some nice healthy refactoring into my programming diet.  Treasure chests are in, though loot tables need to get a lot more interesting.

Also, there's this:

The magenta network is a debug view of the level graph, meant to help me visualize what's going on when generation fails.  It's not quite finished for that purpose (I need to fix some stuff I broke), but it's interesting to see.

Monday, June 11, 2012

More Eye Candy

Today's been a grab bag including graphical tweaks, a new graph type generator, and a lot of rework that's helping me try new things in areas of level gen that had previously been inflexible.  That's a constant battle, but I'm starting to work my way into some new avenues.

The results are sure pretty:

I think once I can get these kind of results a bit more reliably at this size, I ought to be satisfied for a while -- this is definitely enough room structure to play with for now.  Later I'll crack the divide-and-conquer nut and really go hog wild with some big levels that aren't all stretched to annoyance.

There's any number of small tricks that can perhaps be applied at this point, too.  For example, long hallways that twist around only to dead-end at a single room are fairly common; it wouldn't be hard to move those dead-end rooms closer to the source.  I'm also looking into directly adjusting the force pairs between rooms.  This could be used to introduce extra repulsion between "problem" rooms that wind up too close to one another.

I'm putting in some basic treasure chests now, and planning on some more debug visualization stuff because it's just so darn helpful.  I saw a great talk online recently about the value of immediacy in design tools, and it's so true.  Looking directly at what's going on gives me much greater insight about what I'm doing, and extends my grasp.  After that I'm planning some infrastructure related to boss monsters, loot tables, and similar stuff that will pertain to quest design.

Sunday, June 10, 2012

A New Look

Today's screenshot speaks for itself:

I did a bunch of optimization work last night, primarily reworking the way location and feature data are structured and indexed.  Once the major gains had been made there, the remaining slowness was all related to the way I was doing tile graphics.  Since I'd been interested in taking more of a vector-based graphical approach anyway, I decided this would be a good time to take some steps in that direction.  The results are above.

Things may get even more neon from here on out.  The game runs quite a bit faster now too, which bodes well for my further efforts.

Friday, June 8, 2012


Hooray!  I'm back at it after what turned into a couple months' worth of hiatus.  The programming break did give me time to step back and think through some solutions, and now that I'm coding again the progress is coming quickly.

For a start, I fixed what I feel was the root problem with hallway routing by changing my algorithm to go from room center to room center and figure out the doors afterwards.  It's still necessary to avoid all the other rooms, so it's not quite as simple as routing the hallways and then thinking about rooms, but the application of a few elementary set operations proved sufficient for this approach.

Things didn't go perfectly smoothly at first (pretty good though, really), so I wound up finishing work on the level generation visualizer.  Being able to see what was going on proved both fascinating and helpful, and I'm making extensive use of it now.  A* is fun to watch in action.

With the aid of the visualizer, I have been able to significantly improve the capability of the level generation engine.  It's definitely still a work in progress; I need to work quite a bit more on getting the rooms closer together, particularly in the case of larger levels where things can really go wild at the moment.  I haven't got it all robustified yet, so ugly cases still cause some crashes and endless loops, but I've seen it do enough that I'm convinced it can be made to produce an acceptable variety of levels.  Eventually I'll get into things like divide-and-conquer to tackle more ambitious layouts, so the horizon still has plenty to offer.

Okay, enough talk, time to give up the goods.  Here are a few fairly attractive levels from the latest engine:

Hub-and-spoke layout with locks & keys

3x3 grid

Chain of locks and keys.  These can get plenty long.

These are by no means the most complex levels possible now, but things do get a bit spread out looking as we go bigger:

Longer chain of locks and keys, getting a bit spacey.

This will obviously need a bit more work, and I've a number of ideas yet to try, so we'll see what comes of that.

I'll also be spending some time with a profiler to try and optimize out some slowness that's making my debug runs drag.  It's mostly in the graphics layer (ironically), and I upgraded to a new version of the graphics library (SFML 2.0 RC), which helped some, but really it's got no excuse to be this slow and I'm going to have to hammer it into shape.  There should be some good low-hanging fruit, though, so I'm not concerned; at any rate, it runs plenty fast in release mode.

I'm not sure how much longer I'll spend on level generation after that.  Once it's running fast enough, can make larger levels that aren't way too spaced out, and I've got a decent library of structures ready to generate, I think it'll be time to proceed on to other things.  I need to make the monster pathfinding work again and maybe start some other AI inroads, and then I'd like to change gears completely and start focusing on procedural narrative, to breathe life into these generated environments.

Thanks to everyone for staying interested!  There's still plenty more to come.

Thursday, April 12, 2012

Still Kicking

Haven't had much time for development the last couple of weeks, but I'm still feeling immersed in the project.  In my few moments of productivity, I've laid most of the plumbing for the "level gen mode" debug UI without having to ugly things up too terribly.  Perhaps this weekend I'll get a chance to settle in to some real coding and finish that up, then use it to see what's going haywire in the hallway routing.  I don't know if this means the end is in sight right away, but the added visibility should dramatically improve my process.  Stabbing around in the dark really isn't too encouraging, so the change is welcome.

Continuing to ruminate quite a bit on procedural narrative.  I really need to start getting my hands dirty with code to advance my ideas much more at this point, so I'll probably get on to that as soon as possible after resolving the level gen thing, assuming that's sometime while I'm still young.

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

Tuesday, February 28, 2012


The dungeon just got a lot more dangerous: monsters now chase the player from all over the map.  I'll have to put some limits on this (waking and sleeping, disturbance, stealth, etc.), but for now it's amusing to see situations such as this arise:

At the moment it's just doing basic Dijkstra shortest-path stuff.  As level structures get more sophisticated, I anticipate perhaps doing some hierarchical pathfinding based on the level schematic graph.  This works pretty well for now though, so I'm not sure how soon I'll need anything fancier.

The screenshot also showcases the colorful new combat log.  Revel in its translucent beauty.

Next task is to fix dungeon hallways so that they don't cross; this is crucial in making the level maps obey the connectivity constraints of the schematic.

Monday, February 27, 2012


I got the initial basis of the skill advancement system laid out the other day; it seems to be working essentially as intended.  Lots of tweaking down the road for this one, but for now game balance means nothing.

Tonight, I implemented multi-color functionality for text fields.  Bit of a fiddly necessity, but color-coded output is going to make visual scanning a lot quicker.  Too ugly for screenshots yet.

Saturday, February 25, 2012

Coin of the Realm

Dungeon delving just became profitable; monsters now drop little piles of gold, which you can pick up.  Also, I've introduced difficulty leveling for monsters and populated dungeon levels of increasing depth with more difficult monsters.  Lastly, I've added a vestigial combat log, so I can stop looking at the console window to see what's going on.  The combat log's pretty ugly, and I think I'm going to bite the bullet and start doing some more complicated graphical string handling soon.  Doing that will help make a dent in the work I need on that front for the town UI.

Up next on the roster, experience gain and pathfinding.

Wednesday, February 22, 2012

Red, Then Dead

Just a little time left for feature work today after half a dozen blog entries, hehe.  Today I made creatures turn shades of red as they're injured.  Works nice.  Next, monsters in the dungeon will start to fight back!

edit: One bout of insomnia later, monsters are attacking the player.  Now I need to make death work properly, but it's satisfying to see the '@' turn red.


Ever play LORD?  It was this great BBS door game that had us all hooked, back in the day (and a spate more recently when we had a LOGD (Green, not Red) server running at work, back a couple jobs ago).  It's a menu-driven RPG, all pretty simple but somehow quite fun.  I decided to rip it off for the town environment in SnargleQuest, because I for one am completely tired of walking around towns in roguelikes.  If there's no risk of dying, walking around is really just wasted time.  So let's just give the player menus.

Here's what my take on this looks like at the moment; this is the main town screen:

The idea to rip off LORD was initially just an expedient way to prototype something that would let me exercise the skill system before the dungeon game proper was far enough along for that.  LORD didn't have a dungeon -- you just wander out into the forest looking for trouble, and something finds you.  I put a similar mechanic into SnargleQuest (maybe I'll start abbreviating that "SQ"); here's a shot of that, including some debug output that demonstrates the skill and combat mechanics a bit:

I'm still debating whether to take this feature out now that dungeon combat is starting to come along, but I'm tempted to leave it in just to have another option and allow some LORD-style fun.  Obviously, if it's kept in I'll deepen it quite a bit -- random encounters that aren't fights (an introduction vector for plot elements, perhaps), the ability to go deeper into the woods for more challenge, etc.  Opinions?

Baby Pictures

What there is to show right now ain't much in terms of being anything that doesn't just look like a really bland roguelike, but I'll post this for posterity.  At this point, all those monsters you see are totally immobile and don't fight back.  But you can kill them!


The most ambitious (and vestigial, so far, though I do have a little prototype) aspect of the SnargleQuest project to date is its approach to narrative -- essentially, procedural quest generation.  Doing this well is generally found to be quite a difficult problem, and most games to date have kept their aspirations exceedingly modest -- e.g. a random quest every few levels to kill n monsters of type T.  I have some concepts in mind for SnargleQuest that I hope will demonstrate the feasibility of a much richer system.  My ideas here are still developing, so this is all to be taken with salt.

My basic approach is to represent common story elements as elements in a dependency graph, and construct quest-type stories by working backwards from goals of various types.  The idea is to represent story elements in a way that are generic enough to be recombined, thus allowing a wide variety of different story structures.

It's a bit like a game of Recursive Fantasy Trope Mad Libs.  We may start with a goal like Rescue the Princess -- a common enough trope.  Actually, our internal schema may be a bit more generic -- Rescue X, where X can be anyone who might reasonably require rescue.  A rescue plot admits the introduction of certain necessary plot elements.  We have the captor, presumably some generic nasty.  The captive will be held at some location; we may require exposition so the player can find the location, and exposition can take may forms.  A rumor in a tavern?  A dying confession?  A trail of blood?  A tip from a guild colleague?  The possibilities are many and varied.

One critical aspect to making interesting content out of a scheme like this is the possibility for significant subquests.  Here our example may involve a main (perhaps game-winning) quest to Defeat the Evil Menace.  And what kind of Evil Menace would it be without a critical weakness?  Perhaps there's only one weapon in the world that can defeat the Menace, and that weapon must be sought -- bam, subquest.  It could go further still -- the One Sword might be broken into Pieces Three, hidden throughout the land.  The nice thing here is that the component parts can easily involve reusable logic -- there are many kinds of quests to Find Something, and those all have some aspects in common with quests to Find Someone.  For this system to fulfill its promise, sufficient advantage must be taken of such commonalities, and the results must be fun.

One thing I hope to accomplish as the system develops is a meaningful ability to set constraints on the various recombinations, to ensure that they make some amount of sense.  I would like, for example, to introduce things like plot twists resulting from hidden agendas.  We may have a plot graph that involves multiple characters; perhaps it's possible for two of these characters to turn out to be one and the same!  But we can't just alias any two characters, unless we're able to provide a sensible explanation why the King and the Princess's Kidnapper are the same person (this example, though, being far within the realm of reasonable palace intrigue).

So essentially I'll need some kind of system for expressing and enforcing constraints, and I'll have to design it to be expressive enough to say what I want, without being painfully verbose.  I'm busy working on more fundamental parts of the game, so it'll be a while before I get down to seeing how much I can really accomplish here.

I do, however, have a little prototype that does all this in a very basic way.  It's essentially just the very basic Mad Libs thing I describe above, with a few variations and some amount of overlap between the two or three different root scenario types.  Early days, but I have hopes.

The Skill System

Growing up on RPGs, I rarely found myself satisfied with the skill and advancement systems in games I played.  Levels and experience points feel artificial -- it seems more realistic to adopt a scheme in which skills improve through use.  However, every game I've seen that attempts this makes a mess of it.  The standard problem is that, when you simply get credit for using skills a certain number of times, this forces the player into artificial and annoying grinding behavior to top up skills that are infrequently-used, but important.  An effective single-skill-advancement system should reward you satisfyingly for using your skills usefully, and furthermore make risk-free grinding ineffective.

I'm also dissatisfied with all-or-nothing results from skill rolls.  I would prefer to allow for varying degrees of success.  The degree of success should depend on the roll, of course, but also the difficulty of the task being attempted, compared to the skill level used.  Rather than a binary cutoff, I prefer a system in which a slightly below-average roll (say, 49 out of 100) implies slightly less success than an average roll.  For some cases, like jumping far enough to clear a chasm, it still boils down to something binary.  But for something like combat, the shades of meaning hereby introduced permit much more satisfyingly naturalistic mechanics.

The SnargleQuest skill system is based on these principles.  Using combat as an example, a single attack involves multiple rolls, each with its own notions of skill level, difficulty, and outcome (degree of success).  Let's look at an example attack, to illustrate.

Our player, with Novice attack skill and wielding a Fantastic scepter ("Fantastic" being a designation of weapon quality), encounters a zombie.  Attempting a strike, we first determine the difficulty, which is derived from the difference between the attacker and defender's attack skills (other factors will probably come into play later).  In this case, we find the strike difficulty to be Undemanding.  Our roll of .283 (out of 1.000) is unimpressive, but still sufficient to strike the enemy, although the strike is described as "Embarassing," a low rating which will reduce the likely efficacy of the strike.
The zombie now attempts a dodge, but it is Unskilled at dodging.  Even though the difficulty is just Simple (since the attack was so Embarassing-ly poor), the zombie rolls 0.225, getting a dodge outcome of "Pointless," not good enough at all.  Thus, we strike the zombie, and now must determine damage.
I've gone back and forth on using separate skill tests for armor penetration and injury, or just combining them into one roll.  For now, it's just a single roll, with a difficulty-to-wound determined by the combination of toughness and armor quality (if present).  In this case, the zombie is not very tough or well-armor and we find the wound difficulty Undemanding.  Rolling a very satisfactory 0.894, the player grins wickedly and delivers a Grievous Injury to the zombie.

Playtesting has convinced me that this approach is sound.  I'm able to describe combatants with varying arrays of skills, and I find that the resulting combats play out pretty much as you'd like.

You'll note that skill levels, difficulties, etc. are not described numerically.  Of course, there are numbers underlying everything, but this system strives to deemphasize the numerical nitty-gritty and simply present a self-consistent abstraction that captures what's important without polluting the texture of the game.

There are no hit points, for example.  I've never liked hit points; they don't make sense.  It's silly that a character with only one hit point left still fights at full strength.   And why should it be possible for one human to have ten or twenty times as many hit points as another, when a single well-placed blade can still kill even the toughest warrior?  The absurdities compound endlessly.

I've opted instead for a system based on wound severity.  We keep track of the wounds you've suffered, but generally only the worst wounds are consequential.  There's a mechanism by which, if you repeatedly suffer one kind of injury, it gets gradually "upgraded" to a worse injury.  As the punishment continues, the blows add up over time in this way until eventually the wounds become mortal.

I started out by talking about skill advancement, so let me finish with that now that the intermediaries are covered.  The fundamental idea of SnargleQuest skill advancement is that you get more "credit" towards advancement, the more difficult the tasks you do with that skill, and the better you do at them.  The probability of advancement is based on the total accumulation of skill rolls and outcomes since the last increase of that skill; each time you chalk up another success, the game rolls to see if your skill advances.  Initially the probability is quite low, but over time it becomes essentially inevitable so long as you continue to undertake nontrivial tasks.

I find so much to like about this.  The mechanics are opaque enough not to distract from gameplay, and the player is incentivized to take on appropriate-level challenges.  Players who take a more difficult road can be rewarded with faster advancement, whereas less aggressive players can count on advancing eventually so long as they do something worthwhile, even if a bit easy.  Skill types can be tuned individually -- we might wish to have a skill such as Ritual Magic, which would consume time or resources and perhaps see only occasional use; such a skill should not require as many successes to advance as, say, the Fireball spell you use in every fight.  Finally, I personally really like the way it represents a "flash of insight" after handling a particularly tough problem, exactly the sort of experience that leads to learning and skill development in real people.

That's about what I've got to say about the skill system for now.  I owe a debt of inspiration for some facets of this scheme to a couple of old pen-and-paper RPGs.  One, which nobody is likely to have heard of, was called Lost Souls; it introduced me to the notion of a skill system based on tasks of various difficulties each having their own percentile roll for success.  I must also acknowledge Shadowrun, from which I plan to pretty much steal another idea related to all this, which is the notion of using "similar" skills to substitute for each other, albeit at a penalty.  That part, along with the advancement mechanics, are still just design at this point, but I'll post more about them once they're implemented and working.

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.

Statement of Intent

This is the inaugural post for the SnargleQuest dev log.  "SnargleQuest" is the working title of a roguelike game I started making as a hobby project in August 2011.  Having played RPGs and roguelikes for much of my life, I've got many ideas about how I'd like to see things done better or differently.  It is my hope to create a game that is both fun and a working demonstration of exciting new ideas for the genre.

Some of my top-level desiderata include:

  • Dungeon levels with meaningful structure, connected with generated puzzles and quests.
  • A system for skills and progression that avoids artificiality and maintains fun.
  • Generated narrative content that feels like a story.

Based on some initial prototyping and percolation of ideas, I have some inroads for all of these aspects and more.  I'll make separate posts shortly on these aspects, to avoid making too large a wall of text here; I'll try and get some teaser screenshots up pretty soon as well, once the game is at a point where there's some visible evidence of the above (at least some of which is true now or not too far off).