Simulation of History and Recursive Narrative Scaffolding

I wanted to write a blog post about some of the thoughts I’ve been having about character backstory / history generation techniques. I don’t claim they’re original, but I think they’re pretty powerful!

There’s a great quote from the makers of Caves of Qud on their history generation approach that gives a really good organizational framework for this post, so I’m gonna start with it:

“There’s a distinction to be made between history as a process and history as an artifact. The former can be conceptualized as the playing out of rules and relationships that continually produce the present. To simulate this process, we might seek to reproduce its logic. On the other hand, the latter is a constituent of the present, something we engage with through a contemporary lens and whose complexities may be obscured by that flattening of perspective.”

(Subverting historical cause & effect: generation of mythic biographies in Caves of Qud)

I’m going to take these two approaches, apply it to a technique I call “recursive narrative scaffolding”, and talk about each approach’s advantages and disadvantages.

The Technique: Recursive Narrative Scaffolding

The general approach isn’t one I’m claiming is unique, and it may go by other names elsewhere, but the name I use for it is recursive narrative scaffolding. The idea is pretty simple, but can give rise to complex structures if built out and designed correctly.

If you’ve played the indie RPG Microscope, well, it’s that thing. Scaffolds are a generalized narrative building block that can stand in for a Period, Event, or Scene, depending on how large a time period it tackles.

Here’s a quick example. Say you have an event for 7 timesteps. Let’s call it BikeTheftWeek.

At the beginning of BikeTheftWeek, you saw someone stealing your bike. Before you could stop them, they rode off laughing. The jerk! We’ll call this event BikeTheft.

scaffold2

You went through the rest of your week as usual. But then on Friday, you saw your bike! The person that stole it was on the ground, and a dog was biting his pant leg. Ha ha, take that!

So, modeling this, we would say BikeTheftWeek has 7 timesteps (one for each day) and at timestep 1 the sub-event BikeStolen happened. A bunch of other stuff happened for timesteps 2-6 that we don’t care about right now, and on timestep 7 DogAttack happened to the bike thief.

scaffold3

You could zoom out and imagine an even bigger scaffold, something like WhatGoesAroundComesAround, where BikeTheftWeek is a sub-event that happens in the middle of it, with the beginning containing an event (or events) where the character demonstrates their skepticism of fate, then an ending where they come to believe in it.

scaffold4

There’s no limit to the amount you zoom in or out. You can have one event which is “GoodLife” that encapsulates an entire character’s life, or one that’s “CharacterBlinks” that’s only one second long. You can adjust the scope up and down depending on where you want to put content. In my current game Delve (working title), there is one root event called “History”, which lasts as long as the simulation, and involves every character. Everything else from there is just…sub-division.

That’s it! So now that we have an approach, let’s talk about two different types of implementations: history as artifact, and history as process.

History as Artifact: Dwarf Grandpa and Rationalization

I made this thing back in 2014 I call Dwarf Grandpa. It was just a prototype mod to Legends Viewer for Dwarf Fortress, so I won’t talk it up much. But basically, it took the events exported from Dwarf Fortress, and wrote character stories from them.

Actually, stories for all kinds of characters is a big ask, so it just did stories for vampires.

Actually, stories for all vampires is a big ask. It did certain stories for certain types of vampires in Dwarf Fortress.

Vampire dwarf by DevBurmak
Vampire dwarf by DevBurmak (https://devburmak.deviantart.com/)

Basically, I made a small library of scaffolds. In this implementation, a scaffold was a grouping of sub-events that were ordered in time, but not in strict increments (i.e. I wouldn’t care if “Eat” came 2 or 3 or 50 timesteps after “Hunt”, I just cared if “Eat” came after “Hunt”). These scaffolds had associated contextualized grammars that could read simple data from state (like which characters were involved, etc).

Once I had a library, I ran pattern matching over the events for each character in the exported Dwarf Fortress history, checking to see if I could apply a scaffold to it. If so, then I would run the simple grammar for it, and include it in the character’s bio.

The system would start from scaffolds that could account for the largest swath of a character’s life, down to the smallest. Scaffolds could overlap, etc.

A simple 3-step scaffold for a character desiring immortality, profaning a temple, and being cursed to become a vampire.
A simple 3-step scaffold for a character desiring immortality, profaning a temple, and being cursed to become a vampire.

You could imagine using this approach if your game puts more emphasis on simulation, so you have a rich data model to draw from, and you know in advance that the events recorded are following some sort of logic, so you don’t have to gate a lot of pre-condition logic on the scaffolds. Essentially, this is providing a “human-readable” version of the simulation processes, with extra flavor added.

Caveats

The generated events for characters must not be random. They in fact follow a rigorous simulation logic, so the “facts” of the stories are already baked in. I can rely on the simulation to not give me an event set where the character dies in the middle, or somehow is in two places at once, etc. The conventions of the simulation logic are the bare minimum conventions of the storytelling about that world, so they do the heavy lifting for me.

You have lots of material per character. This worked for me because Dwarf Fortress exports a crapload of event data for characters. Especially vampires, holy cow. You can get enough material to tell an interesting bio using only 1% of their life events, given there are so many. This made the bar for generating surface text pretty low, which was cool. We could filter the hell out of the events and still have plenty of material left over.

Why Is This Cool?

Using this approach, it’s fairly straightforward (I won’t say easy) to implement a system where there is a subjective notion of history, and those notions can be unique to different character perspectives.

Imagine a set of global scaffolds you can apply, then culture-specific scaffolds, then character-specific scaffolds, then state-specific scaffolds. Maybe there’s a character who reads lots of romances. If you write lots of romance-specific patterns for their use, then when you have a player ask them to describe a brooding, aloof character, they may come up with a very different interpretation of said character’s history than if you asked someone who hates people that brood. None of the actual motivations or things referenced in the event text need necessarily be modeled in the simulation, so long as they’re consistent. That way, you always have a core you can work from.

Conflicting accounts! That conflict in consistent ways, that you could even surface to the player! You could have two characters witness a murder, one who’s a pessimist, and another who believes in justice in the hereafter. When asked to describe the event, the pessimist would consult their library of scaffolds, output the text “Someone was murdered–which just goes to show that life is short and brutal.” and you could surface why to the player with something like “(Char1 is a pessimist)“. The other character would have access to scaffolds that would render text “Someone was murdered–but the murderer will get what’s coming to them, in life or the hereafter” with the explanation “(Char2 believes in justice in the hereafter)”.

Phantasmal Media by Fox Harrell

Again, the power of this approach is in the scaffold library, which can be gated on groupings of characters on culture, socio-economic status, disposition, or even dynamic tags that happen as a result of the simulation, like “survived trauma” or “wonderful childhood”. It makes me think of all the cool work Fox Harrell does with cultural phantasms. And if you don’t know what I’m talking about, you need to read Phantasmal Media pronto.

Simulation is a lot of work, though. “I’m just doing this for the stories, man. I don’t care if this character has a negative trust value with this other character. Who has time to model all that?”

Well yeah, ok fair. Consider this other approach:

History as Process: Delve (working title) and Recursive Pooling

In the current game I’m working on, I take the same scaffolds, but instead of having slots that match a pattern of events provided by the simulation, we give each sub-event in the scaffold pre-conditions it has to pass. These pre-conditions may focus more on story than simulation state–they may use flags or traits that don’t effect the wider game like “hadBadEvent” or “ripeForDistrust”.

The library of scaffolds is therefore also the library of simulation events, which means as the simulation proceeds through time, at any given point we may have one or several scaffolds determining what our future holds (I call this a character’s geas or fate).

The difference between this approach and the earlier one of historical rationalization is that the scaffolds, which might look like:

Timesteps 1-50: make some friends
Timesteps: 51-100: friends gradually end up owing you favors
Timesteps: 101-151: you call in favors to rise to power

ensure that the patterns they encode take place. In contrast, it might be relatively difficult to ensure that such specific arrangements of events happen if we randomly generate events, then try to apply a pattern onto them. For example, if I write only one incredibly specific scaffold for 50 events in timestep sequence using this approach, the downside is that everyone has this scaffold. In the earlier approach, the downside is that hardly anyone meets the state requirements, and thus it doesn’t show up very often.

Caveats

Until you get a rich library of events, everyone will do the same thing.
This isn’t terribly surprising–it’s an outgrowth of closely tying the generated story events to the simulation logic. This means that until your library reaches a critical mass, you’ll be stuck with all your characters doing the same, possibly highly-specific action chains again and again, and until you design a scaffold approach that’s generative and flexible, it’s going to stay that way.

Player interaction can wreck your china shop.
This approach is great when you have total control over the system that’s generating events, but adding a player into the mix can really throw a wrench in the works. If your characters are currently stepping through a series of nested scaffolds which lead to them ascending to the high court and becoming ladies and lords of the land, but the player causes an explosion at timestep 2 that kills them all, you’ve got a serious problem on your hands. Ideally, your scaffold library should be granular and flexible enough to recover from this, but it will take some careful forethought.

This might mean this approach is especially good for generating backstories that take place before player interaction, so you don’t have to handle that case.

Why Is This Cool?

More control, more complex event structures.
Because the scaffolds are calling the shots (and playing a larger role in driving the simulation) you can create more complex structures and guarantee they appear. Whereas it might be statistically difficult to generate a 30-event simulation event sequence in the first approach that conforms to an authored pattern, it’s quite easy to make that happen when the scaffold pre-conditions are the only blockers.

Proceduralized Fate system
Because this runs at the same time (or as!) the simulation, it means at a given point you can know which actions characters are currently “fated” to take. A character might have a scaffold selected for them of Doomed Lover at timestep 2 which won’t play out for a long time, but you can query the system to give intimations of their eventual fate.

Why Not Both?

You don’t have to pick one or the other, of course. You could layer these systems on top of each other, using the “history as process” to generate backstories, then using a simulation to handle character decisions moving forward, and  only building out text descriptions on a need-to-know basis when the character interacts with historical accounts or NPC conversation, depending on which character is doing the rendering.

What Are You Using?

For Delve I’m using the second approach, because simulation is not as important to me as generating fully fledged-out, rich event descriptions. My hope is that I can slowly turn the dial up on the simulation by building out pre-conditions, post-conditions, and effects. But the most important thing for me is the memories themselves–specifically, the semantic tags associated with them, and the breadth of generativity I can push without giving myself an unholy authorial burden.

If you want to know more about the full spec for events beyond scaffolds, check out this other blog post. If you’re going to be at GDC 2018, you can also pull me aside and I’ll be more than happy to show you a demo and talk your ear off about it!

 

…holy shit you read the whole thing? Thanks!

Event Systems and Ontological Skill Trees

Disclaimer: I Have No Idea

This is a somewhat rambly post where I’m trying out some ideas that I’m currently halfway through implementing…

Making Memories

Before the player can mess with character memories, they need…well…memories.

This is done currently by starting off with some number of characters, and letting them each randomly choose an event to add to their timeline, whose pre-conditions they satisfy.

(It might be confusing right now that I call them events instead of actions, but hang with me.)

Here’s an event:

Screen Shot 2017-07-23 at 6.43.55 PM

Not so bad, right? Here are the fields:

id: unique ID
timeSteps: how long this event takes
surfaceText: the Expressionist grammar to generate surface text for this event, depending on who’s asking.
preconditions: simple blackboard-style state variables that must be valid
effects: changes applied to every character in cast after event runs

What About Cast?

Ok this is the complicated bit. Cast can be any number of characters. Each character has their own “characterArgs” (preconditions for filling the role) and a memoryGrammarBank.

So…Events are tree structures. For each character in cast, for the number of timesteps, it iterates over their memoryGrammarBanks and chooses one to process.

What are those things in memoryGrammarBanks? They’re other events. When trying to pick one from a memoryGrammarBank, it:

1. Favors Events whose timesteps are largest while still less than or equal to the remaining time of the parent event
2. Picks only Events whose preconditions hold
3. Picks only Events who can be cast
4. Favors casting characters already cast for parent events, and failing that, characters who are lower-status than the parent character, and who have similar Substrate (that’s the game ontology) domains to the first character

This means that, dramatically, events are written with the first cast slot as the most important. And it means that characters that are subordinate to, but of the same domain as the main character, or more likely to get drawn into their event orbit.

We build out the tree depth-first, which means we just keep iterating down until we get to a base grammar that doesn’t have any further grammars in the castSlot, just in the surfaceText. We then generate that surface text by running it through Expressionist, add the event to the character’s timeline, process the effects, and pop back up to the parent to expand out the next cast call.

What’s Expressionist Surface Text?

Expressionist is Jame Ryan’s system for generating surface text by iterating through attribute grammars. The cool thing about it is that, unlike vanilla grammar structures, each processed rule applies a metadata tag to the section it generates. These tags can be anything, from “cat” to “effect: <char1> anger +1”, which brings me to the cool part:

In generating the surface text from production rules carefully tagged at author-time, we can get emergent simulation behavior.

We do this so that we get the authoring benefit of writing combinatorial surface text, and the effects that fall out from that via meta-tagging can update the state accordingly.

So that’s how we do timestep 1!

What About the Rest of the Timesteps?

We don’t expand out the rest of the tree, because after a character’s timestep is run, the effects are applied. This could potentially change the state such that casting decisions made from an earlier state aren’t valid.

The rest of the tree, as it applies to each character, is called their Geas. When the next timestep is processed, we repeat the same process, for the events that haven’t been rendered out yet. If it turns out we can’t process the event due to the preconditions no longer being valid, we bump up the tree to the next level up, and see if we can process from there.

If none of the events are valid for the character, then we start a new root tree for them.

Fate

The cool thing about this event structure, I think, is that it means we can conceivably group events together under loose category events (happyWalking and sadWalking are in the memoryGrammarBank for walking) and chain them for long timesteps. You could have one giant event called “tragicLife” that has 1000 timesteps, composed of 5 100-timestep “normalLife” events, followed by 3 100-timestep”wonderfulLife” events, followed by 1 100-timestep “terribleLife”, and 1 100-timestep “disastrousLife”. These loose categories would have very large memoryGrammarBanks, but would allow the author to specify a general structure this character’s life should take.

Ontological Skilltrees

Remember when I said you could generate surface text with tags like “effect: <char1> anger +1”? Because we don’t need to worry about acting out the characters’ actions in the simulation, we can use this to run game actions, so that we can update the simulation as the surface text describing what happens is generated.

For this game, we want whenever possible to tie things back to the Substrate. So for a surface text production “she climbed the tree to marvel at the mockingbird’s nest” the production rule for generating “climbed”  has the tags
“prec: <char1> climb > 5” and
“effect: <char1> climb +1”.

This means that when we ask Expressionist to give us an expansion, we can say “don’t give us an expansion that has a precondition tag for stats higher than ours”. This also means that, because this production is returned, the character in cast slot 1 was “given” more affinity for climbing when this action completed. We could also imagine “tree” having a tag of “effect: <char1> tree +1”. This means the character has more “treeness”, and for things involving trees in the future, they may do better with them, or talk about them more in conversation, or find themselves more wary of fire, etc. Those things are determined by the connections between the concepts in the Substrate.

We could also specify who did the effect. For surface text like “Fivetoes took her music box” we could use an effect “effect: <char1> takeItem music box causedBy <char2>” which is (confusingly) char1 losing the music box as an effect done to them by char2.

These effect tags are returned from Expressionist with placeholders like <char1> etc, and those are replaced by the system, and processed into state updates. So the string processed by the system would read something like “effect: starEye takeItem musicBox5 causedBy fivetoes” which would run the function takeItem(starEye, musicBox5, fivetoes)

More Flexibility

If we look at skilltrees as conceptual affinities for actions done to entities (potentially with other entities) it seems like we can get some pretty interesting fertile ground, especially we can leverage hierarchies through linking.

Thus, I may be able to avoid a dragon’s fire if I have experience with either dodging, fire, or dragons. Or…I may be able to avoid it because I am good at dancing, which has the connection facilitatedBy to agility, and dodging also has a connection facilitatedBy to agility. But if I want to change that, all I need to do is break the connection between dodge and agility, and move it to “daring” or “reflexes”, and the rest falls out from there.

Dev Update- April 2017

Rough Stuff & Research

First 3D Room
First thing I did in 3D was make a gothy reading room. Sounds about right.

The first three months of the year threw me for a bit of a doozy. I was able to secure a contract gig for the summer (yay) involving some work in Unity (oh.) so I decided to upend the dev priorities to facilitate brushing off my C# / Unity skills.

I made a sample room using assets from the Victorian Interiors and Sally’s Country Home asset packs (just to get my feet under me for working in 3D) and a simple room generator (though no decoration). The room generator is embarrassingly buggy so I won’t link it, but if you want to see the first 3D thing I’ve ever made in Unity and have a Mac, knock yourself out.

Most of the rest of the work was getting up to speed on pipelines for photogrammetry, 3D stuff in general, and figuring out the development plan for the following quarter.

Collaboration

I have reinforcements for spring quarter! Three people working with me to make room generators, and two working on photogrammetry. We’ll see what we get done, but the rough plan is to have working room generators with room decoration for two asset packs (Victorian Interiors and Village Interiors), and interstitial connecting rooms.

I’ll be mostly working on the character generation system, starting with porting the prototype from Javascript to C#. I’m collaborating with some lab mates (@JoeOsborn and @xfoml) on memory authoring content verification, so I’ll also be focusing on authoring tools this quarter, with the hope of getting some tech for satisfiability analysis on memory production.

The hope is by the end of the quarter, I’ll have a (terrible, probably buggy) online memory writing environment that, given a

  • JSON of the palace generator tag generation space
  • JSON of the ontology graph
  • JSON of the current memory library

will be able to say “this memory could currently be a rusty lamp sitting in on this particular rug” as you write.

It’s really important to me (maybe misguided?) to make it possible for people to add new memories, change the ontology, or even add new 3D models through packages. But I also want people to be able to do that without knowing all the plumbing, so we need tools.

I’ll admit I don’t understand it fully (I’ll see if Joe has a post / paper I can link) but the memory object verification comes from using visibly pushdown automata to help navigate the possibility space in the intersection of the two grammar libraries: memories and room generation.

I need to arrive at a spec for the room generators soon, but a piece that’s still up in the air (that I’d like to resolve more this quarter) is the interplay between super-rough simulation, and parameterized text / grammars. Simulation to enforce some model of causality, and parameterized text to deliver the surface text of the generated characters’ stories.

Generating Characters

Currently the prototype just grabs a bunch of memories (root grammars) and smushes them together for a character. This won’t cut the mustard for causality, especially when those events involve other characters, so I need another layer on top for making the variable outcomes / character qualities consistent.

First, I’ll implement a rough simulation layer, which will work as a generator / selector for events. In turn, events spawn “casting calls” for characters as part of their pre-conditions, and work some kind of effects on said characters. Events will also have state-driven pre-conditions, so if I put in some really basic planning (GOAP?), I’ll hopefully create a system where I can use the simple simulation to generate a skeleton that’s used to pull in grammars, and inform which parameterized text they cash out in.

The filled casting calls and effects for events will then be passed to the memory text system, which will generate the surface text, and likewise the hierarchical metadata necessary to interface with the palace generator. It’s sort of like the casting / quality use in Ice-Bound‘s system, except pushing another layer of procedurality on top (the simulation), using a simple planner to direct it all, then piping that output into another generative system (palace generator).

I like this approach because it silos the simulation away from the text production, which means I can decide separately where I want to turn the dial up on complexity…I can either have really nice, complex, generative surface text to rough events, or more complex, generative events with rough text. Whichever ends up more feasible / expressive / compelling!

I’m worried that will up the authoring complexity / overhead, but it’s all so up in the air currently, it’s hard to even do rudimentary analysis of it. The authoring tool may shed some light on what the requirements analysis would need to be to trigger “laugh hysterically and run”, but until then we’ll just have to make some prototypes and see what sticks.

Dev Update- January 2017

Beachhead

the Substrate

Play

This is the first interactive prototype, so it’s more of an interface to explore how the systems behave than anything remotely resembling a game. This evolving JS prototype will eventually be used to get player feedback on some of the underlying assumptions, while I (and possibly others) toil at the 3D realization angle in Unity this year. The biggest goal of this first prototype was to get a large chunk of the generative systems working in concert.

Features

  • Knowledgebase / ontology (I call it the Substrate)-driven generation of:
    • palace façades (text description)
    • palace layout (text description)
    • room decoration (text description)
    • memory objects (text description)
  • Semantic tag-driven object affordances:
    • breaking and burning objects
  • Attribute grammar-driven memory generation (courtesy of James Ryan‘s Expressionist)
  • A force-directed graph of the Substrate
    • nice to look at, but not terribly useful. I’ll probably be switching to a different visualization approach, as much as it breaks my heart.

Didn’t Get To…

  • user-editable NPC qualities
  • user-editable sub-system qualities (not sure what this even means anymore, to be honest)
  • user selects memories for their palace, suggests realization possibilities
  • diagnostic output number of possible combinations w/ same current parameters
  • diagnostic: “uniqueness” of possible builds
Pre-mortem (written Jul 2016)

The first demo will be a toy example, where I’ll be testing out super-basic levels of the generative systems. I’m doing this in Javascript, because that’s what I have loaded in my brain currently, and it’s good for fast prototyping.

The output will be text descriptions of memory palaces, and collections of NPC memories. You’ll be able to change the objects in the rooms via dropdown menus of actions, and hopefully make your own palace from the available memories. I’ll have basic editing for the ontology as well, so if the warmth of a candle’s flame doesn’t symbolize love to you, then you can change that to something else.

Post-mortem (written Jan 2017)

Laying the initial foundations takes time, and I had to re-write some of the systems a couple times to correct bone-headed software engineering mistakes. You can look at and change NPC memories, and the plumbing is in there to do the same for the player to make their own memory palace, but that will need to be pushed off for the focus of the next demo.

There ended up being more gotchas than I initially planned for, and I didn’t put in as many hours as I thought I would. Might be symptomatic of recovering from post-release burnout from Ice-Bound. Long story short, I overshot this deadline by four months, so I need to get less ambitious with my commitments!