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.


  1. You seem to have some nice ideas, anyways, have you thought more about generic quest making any more? I'm myself thinking more of ways how quests would be created from some entities strategic agendas.

  2. Hey, sorry I haven't responded sooner. Reports of my being back on the job may have been slightly exaggerated -- life's still not quite giving me the space for this, though I'm still dead set on getting back to it.

    Anyway, no significant new developments on the procedural narrative stuff. I need to do a richer implementation of my existing ideas before I can really decide how well they work out and what improvements might be made.

    An entity's strategic agenda would essentially be derived from that entity's involvement in various plot pieces. Different roles that entities can be cast for would have appropriate restrictions about necessary attributes for an entity to fill them. The challenge will be to have interesting cross-referencing, or aliasing, in which an entity serves multiple local roles that fit together into a sensible plot on a larger scale. That's how you can have stuff like "the traitor is your brother" etc.