Tuesday, February 28, 2012

Pathfinding

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

Argeebee

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.

My LORD

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!



Narrative

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).