Procedural Stories and Constraint Satisfaction (Part 1)

Ages ago, in the first issue of Dragon Magazine that I had ever read, there was an article on campaign preparation.  For those of you unfamiliar with it, Dungeons and Dragons is a game of cooperative storytelling.  One player, often referred to as the game- or dungeon-master, puts together the outline of a story, and the remaining players take up the role of characters in that story.  This outline, often referred to as a campaign, can also be thought of as the fragment of the story not under the direct control of the normal player's characters (PCs).  

The point that the Dragon article was trying to make was that, like any story, a campaign must be self-consistent, or the players will lose their suspension of disbelief and stop being interested.  Over the course of the game, players will learn facts about the world, and the other characters in it (aka, a non-player characters, or NPCs).  For example, players might learn that a certain duke (let's call him Bob) lives in a particular city and hates ferrets.  If a later event calls for some duke to be present half a continent away, in a village known for its ferret breeders, then Bob is probably not the best choice for this particular role.

If you squint hard, the problem of campaign construction begins to look a lot like a big constraint satisfaction problem.  You have certain entities in the world: NPCs, villages, organizations, etc..., and certain relationships between those entities.  Based on these relationships, entities in the world can take actions that change their respective relationships (e.g., one NPC leads an attack on a neighboring town and either succeeds or fails, changing the state of the world in the process).  

The tricky bit is that a world is typically far too complex to try and simulate in real time.  I have yet to meet someone who runs a game of D&D by exhaustively deciding explicitly what all of his NPCs are doing at any given moment.  Rather, what I have seen most often is that a game master will put together an outline of a character's motivations, and maybe some general plans.  They might have a timeline (of varying complexity) that says what will happen and when.  However, especially since the story is meant to be driven by the other players, the exact details are never developed until they become relevant to the story.

Think of this as a sort of Schroedinger's story.  The exact nature of the story can be entirely undetermined, until the players start to interact with it.  

This can be a bit dangerous, since like quantum particles, a game master can't afford to get into an inconsistent state (while preserving the player's suspension of disbelief).  In short, although the story is evaluated lazily, the lazy evaluation must avoid leading the story into an inconsistent state.