Tuesday, February 26, 2013

Back on the Job, with Some Progress

I'm back from my unannounced half-year hiatus.  After hitting my little tech demo milestone last August, I tried some more new avenues on the force-directed layout approach but continued to hit the same fundamental wall.  I needed to take a break to generate some new ideas, and also to devote some extra attention to helping someone I care about through a difficult time.

The break was good, and eventually I found myself reimmersed in the problem.  I went back and did a much more thorough literature review, turning up all kinds of sources I had missed before.  After spending a bunch of time poring over papers and books on graph drawing, I belatedly discovered OGDF, the Open Graph Drawing Framework.  OGDF is more specifically focused on graph drawing than the Boost Graph Library, and it contains an algorithm that seems extremely suitable.

I've managed to integrate it in a basic way over the past couple of evenings, and the early results look promising:

As you can see, the new algorithm can handle quite large layouts with little difficulty.  The aesthetics will need some work, obviously, and there are a few edge crossings happening with the current naive hall routing code.  So, the next trick will be to perform some kind of compaction on these maps to bring it all in closer and hopefully do away with the grid-aligned, circuit-board feel it presently has.

Well, that's plenty of excitement for one night.  If I can get the compaction nailed down in a decent way, I'd like to move on to putting more interesting content in levels, such as puzzles.  I'm less interested in worrying about hack-and-slash mechanics right now; any game can do that, and I want to focus on mechanics that are enabled by the graph structure.  I'm thinking a lot about ZZT.

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.