Bamboo Cyberdream

a panda wanders the electronic landscape

Procedural Orders

Oh wow, I haven’t blogged in a while. The last time I did it was met with a small shitstorm of people passionately agreeing and passionately disagreeing with me. So I guess I touched a nerve?

Anyway, in the meanwhile, I helped put out a game. It’s doing pretty well. You should play it. Also, in place of a love letter to Marathon, I’m doing a whole blog series with George Kokoris and Brendan Keogh. Both of them are inimitable and excellent, and I’m looking forward to seeing where we go with this.

I am now about to make the most pointy-headed blog post I’ve ever made or likely will make. Fair warning.

I’ve spent a lot of my professional career (and a lot of my academic studies before that) thinking about procedural story. It’s a topic near and dear to my heart, and I was thrilled by how much of it we managed to squeeze into Skyrim (even if it’s just scratching the surface). If you’ve ever heard me start expounding on this topic (especially if I’ve had a few), you may have heard me mention this notion I have of “orders” for procedural stories.

In my mind, it’s essentially a way to break down various degrees of procedurality so that they can be more productively discussed. I’ve seen way too many purists dismiss something as “not really procedural” because it doesn’t hit their particular standard. But the only way this tech will get pushed forward (and eventually disrupt, as I still believe is possible) is if we can acknowledge that there’s a continuum and that a game’s specific position on that continuum need not disqualify it from discussion and study.

With these orders, I’m thinking very specifically of narrative and story at a high level, and not terribly interested in lower-level action-driven experiences. Yes, you could argue that a chase sequence in Assassin’s Creed contains procedural story-like substance, but if we go down that road than any executable code could be seen as a type of procedural story. Once everything is everything, it’s not as fun to talk about.

OK, so here are the orders as I’ve defined them. I know I’ve got some academics who will read this and might have their own definitions that conflict — awesome, let’s talk more! Tell me what about this is useful or not useful. I hate getting bogged down in semantics (I’m sure I’m out of synch with the current academic definitions of “narrative” vs. “plot” vs. “story”), but think high-level frameworks for discussion are immensely useful. (Obviously, my thoughts on this have been pretty thoroughly influenced by the way our tech works on Skyrim. Sapir-Whorf and all that.)

0th Order

Authored Content with Procedural Role-Filling

This is where you take a traditional, authored game story, and give it flexibility to swap specifics based on the player’s history in the game. So the typical “The President has been kidnapped by ninjas” plot becomes “[Character X] has been kidnapped by [baddies Y]” with some algorithm used to fill in X and Y.

Potential Uses: Guiding the player towards unseen content; allowing quests to proceed if key characters are not available; adding variety to different playthroughs; providing a degree of repeatable content (though the seams become apparent fairly quickly).

1st Order

Localized, Responsive, Event-Driven Scenarios

Similar to 0th order, but it’s kicked off in the game in direct response to the player’s actions. This needs to be something beyond just “playing a scene because the player hit a trigger” — there needs to be data from the player’s action that helps populate the moving pieces of the content. The “localized” part of it means that it doesn’t have a long-lasting impact on the overall play experience. This is the situation where the player drops an item and a child comes and brings it back, or an NPC hiring assassins to deal with the player in response to a theft.

Potential Uses: Giving NPCs richer (if still very bespoke) reactions to the player’s immediate actions; providing interesting responses to player’s higher-level choices.

2nd Order

Chained 1st Order Content

Adds persistent knowledge to 1st order content so that it can be chained together into a larger, more cohesive experience. At a tech level, this is simple. At a design level, it’s hard, especially if you want each phase of the experience to contain the same levels of variation. If we stick with our previous example of an NPC sending assassins after the player, a 2nd order narrative could allow the player to pay off the assassins, and then help them kill the original NPC, which angers his sister, who curses you, etc. etc. (Note that with sufficiently dense 1st order content, this has the potential to emerge naturally; I’m mostly thinking of something slightly more intentional on the designer’s part.)

Potential Uses: Giving the player a full story experience with a range of expression, while allowing for the same levels of variation we get from 2nd order and lower.

3rd Order

Game-Directed Experience Management Using Procedural Tools

The game has some awareness where interesting 2nd order content might be, and it uses 1st and 0th order content to nudge the player towards it. Note that “where” is not necessarily a 3d location, but also includes the more abstract “story space,” or if there’s a particularly deep NPC, the emotional space. Imagine that a particular NPC is very close to some threshold in her “Respect” variable with regard to the player, and if the value crosses that threshold, it will be the inciting incident for some 2nd order content. The game then uses the lower order content to create opportunities for the player to affect this variable.

(Of course, the same algorithm could deploy 0th and 1st order content to direct towards purely authored story as well.)

I recognize that this order may seem like the odd man out in the continuum, but I think some level of dramatic awareness and management is key in making procedural story even worth discussing.

Potential Uses: Making sure the player is having a good time; having a higher percentage of content seen; detecting experiences the player enjoys (a difficult task in itself) and helping direct towards similar ones.

4th Order

Chained Content Constructed from End-State

The game has a specific set of “desirable” end-states, and it uses a large pool of 3rd order content to assemble and guide towards those states. (This is essentially 2nd order content working backwards.) “Desirable” in this case just means “interesting from a story perspective,” which could very well be a “bad” ending.

It’s important not to think of this as “the game forcing the player along a set path,” but rather allowing a broad range of story experiences that lead to a defined conclusion. Imagine a Lord of the Rings game, where the player allows Gollum to steal and escape with the ring. Currently this leads to an awkward “Game Over; Try Again; LOL.” But with 4th order procedural content, the game can look at the current state of the world and devise multiple ways the player could still get to the end state of “Player destroys the ring.”

I’m starting to get handwavey here. That’s because this is hard. If it was easy to talk about in a few paragraphs, a lot more games would do it. :-) It’s worth noting, though, that even moderately experienced pen-and-paper game masters can do this kind of thing on a regular basis.

Potential Uses: Letting the player never make a true “mistake,” and just incorporating actions into a larger story that can still be narratively interesting; letting the player own their experience at a very high-level of decision making.

5th Order

Autonomous Assembly of Lower-Order Content from Parameterized Input

Remember the Star Trek: The Next Generation episode Elementary, Dear Data? Geordi tells the computer to make a holodeck experience in the style of the Sherlock Holmes stories, with a villain capable enough to defeat Data. (Spoilers: Hilarity ensues when Moriarty achieves sentience.)

That’s 5th order content right there. Letting the game system construct an experience, using all the tools of 0th-4th order content to fulfill a set of high-level goals that are given as inputs.

Honestly, I could have just labeled this as “∞ Order,” since I pretty much just described the holy grail of procedural story, and there are almost certainly other incremental steps between 4th and there.

Potential Uses: Fulfillment of the dreams of every procedural games researcher ever; effectively removing “game designer” from the list of useful professions; providing individually tuned entertainment experiences to everyone in the world.

So what?

While I didn’t mention the holodeck until 5th/∞ order, I really started getting into that turf around the 4th order. While there are examples of 0th-3rd at varying levels of fidelity today, I don’t know if anyone is even realistically attempting 4th.

In Skyrim we did a boatload of 0th, a good amount of 1st, and just started sniffing around 2nd. I think the tools are there for more, though, and that’s one of the reasons I’m excited for the impending release of the Creation Kit ; I can’t wait to see what smart people do with Radiant Story systems.

4 archived comments Why no more comments?
  1. Ben C. wrote:

    Thanks for this.

    You got me thinking. I wonder if another useful way to slice it is to discuss the inputs and outputs of the procedural systems. Usually when we talk about AI, we’re talking about procedural generation of behavior of individual actors or groups of actors. However, the Left 4 Dead AI director famously uses monster and resource placement (rather than behavior) as its output, and a model of player tension and resources as its input, roughly speaking. And roguelikes traditionally use a simple RNG for input and generate entire level composition as their output. All of these have some degree of authored input as well.

    If I understand you correctly then, in these terms the difference between orders 0 and 1 are whether player behavior is part of the system’s input. And orders 1 and 2 differ by the degree of feedback* in the system (how much output is in the input). Order 3 and 4 are abstractions that seem to output order 2 and 3 systems, respectively, though it’s a bit more complicated than that. In a broad sense, the AI director is a sibling to the third order system, in that it takes the same inputs, though I’m not sure whether its outputs quite count for third order in your system.

    (*: When I talk about feedback, I’m really thinking of the procedural element being something which itself generates a mechanic, which is then acted upon by a player, so feedback is the result of the mechanic acted upon by the player feeding back into the input of the system — not necessarilly just the system feeding back on itself in the absense of input, though that’s possible too.)

    Sorry for the abstract pseudo-mathematical blather. I should go try to break down the inputs and outputs of some games in more concrete terms. It feels like there’s some fruitful space nearby that we could find just by picking different inputs and outputs, even with fairly straight-forward, manageable procedures.

    Posted December 5, 2011 at 12:29AM
  2. sjml wrote:

    No worries about getting into pseud-math land. I termed them as orders because they naturally build on each other, and I think your recognizing this as defined via inputs and outputs is insightful. It could probably lead to some more concrete definitions and (even more usefully) help extrapolate what the higher orders might be.

    The L4D director is definitely some relation to a 3rd order system, but its operating a lower level in the play experience. I remember Clint Hocking numbering and defining his levels of player choice, from “I am pushing this button” to “I am saving the world.” Unfortunately, some googling has not been able to find a written version of them. I bring them up as I’m wanting convenient vocabulary reference points, so I could say “The director is operating at Hocking level 4; I’m thinking more about level 7 and up” or something like that.

    That said, perhaps by defining the orders by the inputs, outputs, and reflexivity, this structure could overlay onto each Hocking level and create a 2d grid defining all potential procedural gameplay. That may end up being a sparse matrix as far as meaningful analysis goes, and I’m not sure what the point of it would be, but now I really want to construct it.

    Posted December 5, 2011 at 7:37AM
  3. Nathan wrote:

    I think the AI community (specifically behavior/motion synthesis) has a lot in common with what you have state above. Please bear with me talking about “actions” and “objectives”, as I think the approaches and ways of thinking are applicable to non-behavioral work like this.

    Often, the common approach is to generate a set of “primitives”, which comprise all the possible actions the agent perform to manipulate the state of the world and which describe how the world is affected by the action based on its input state. Above that, you have “motion/path planning” algorithms that take an initial state and a set of primitives and try to find a chain of actions that result in a desired end state (i.e. meeting an objective). Finally, at the highest level, you have “objective selection” algorithms that take a high level goal and determine what objectives need to be met to achieve that goal.

    There are a lot of approaches to fill these niches that vary based on the context; however, I think there are three main characteristics to this field that make it worth comparing:

    1) Actions are black boxes — essentially, just opaque transformations on the world. This means that they can be discrete actions (“turn on the light”), parameterized actions (“move X feet this way”), or nested sets of other actions — perhaps even described by some sort of regular grammar.

    2) The methods are generally inherently hierarchical. Often, a solver consists of a method of placing potential actions/objectives/meta-objectives into a graph as nodes, finding reasonable ways to connect those nodes (“after you walk 10 feet to the cliff, you can jump or sit down”) and using a stock graph traversal algorithm to find the most appropriate path from your start point to your end point. This method works at the action planning level and the objective selection level — the difference is just what you use to define the nodes and interpret the transitions to be.

    3) There has been a lot of work done in using training data to automatically generate nodes (which can later be edited) meaning that you can provide an example of what you want the final product to be like and have the system generate something similar that meets external objectives based on the example’s components.

    So, taking all of this into account, consider that you can replace the “actions” with your 0th and 1st orders (along with whatever other primitives you come up with like procedural scene / character generation) and “objectives” with designer-driven goals (“get the player to the Thieves’ Guild”) procedural goals (“the players have been milling about, so encourage them to advance to keep tension high”) or a combination of both.

    Posted December 5, 2011 at 11:56AM
  4. Nathan wrote:

    Oh, and one quick distinction: the AI community is generally concerned with finding the “best” (or at least “a good”) way of transition from state A to state B. In this case though, that’s not really necessary — you just want to ensure that it’s possible to move from A (“in jail”) to B (“on a mountain top fighting the world eater”) via one or more paths, preferably ones that are appropriate to the player’s story so far.

    This means you can incorporate other procedural methods like random walks or “on-demand” generation as you move from one state to the next, and have multiple paths available at any given point.

    Posted December 5, 2011 at 12:04PM