# Overview of Three Techniques for Procedural Storytelling

Last week I read a recent paper on a new system of procedural narrative called Story of the Town.1 What interested me was that this paper combines the three major “classic solutions” to the generative storytelling problem: simulation, planning, and Context-Free Grammars.

In this article, however, we are not talking about Story of the Town. What I like is that the paper does an excellent job of highlighting the pro and cons of every single classical approach. Do you see a better opportunity to explore these three separate approaches for classical procedural storytelling? I don’t.

## Simulation

In this approach, we let characters evolve according to some internal rules, and you let that the story emerges autonomously over time. As you see, it is a pretty straightforward solution: you put a bunch of characters in a closed space and see how they react. It is like a lab experiment (or a reality show, if you are the kind of person who likes those things).

I am pretty sure you already know some games that rely on this technique. The most famous approach to this kind of storytelling is probably Dwarf Fortress. Civilizations interact, dwarves have personalities, events evolve, there are wars, evil necromancers: you can just run the simulation and see the story unravel under your eyes.

Another game with similar behavior is Rimworld. It is way less advanced, but in the fan communities, you can watch the variety of its emergent storylines.

However, everything has a price. First, the complexity of the stories is as intricate as the underlying interaction rules are. To have the chance to observe a complex story, you need to have complex rules (in the Dwarf Fortress case, you need to model dwarves, civilizations, outposts, wars, villains, and much more).

Yes, to have a chance. In fact, another drawback is that you have no control over the story. Moreover, most of the stories are not enjoyable (as in life: not everyone’s life is worth a book or a movie). Therefore, the player needs to search for and reconstruct interesting stories actively. Like an archeologist. On the other hand, some people love this extra work. Kruggasmash, a well-known YouTuber in the Dwarf Fortress community, based his entire channel on expanding the storytelling seed of the game.

## Storytelling via Planning

It is possible to see a story like a planning problem: there is an initial condition, the start of the story, and an objective, the resolution. The story in between is the story of how the characters “solve" their problem.

Let’s do a simple example. Suppose that at the beginning of the story, we have the following classic tale scenario. Mario is at home, and Bowser kidnapped Peach into his castle. Then we know what we want at the end: Mario frees Peach, and they came back home.

To apply planning to our story, we first need to translate it into a planning problem. We start by converting the starting state into some First Order Logic formula. This may be something like this:2

IsAt(Mario, Home)
IsAt(Peach, BowserCastle)
IsAt(Bowser, BowserCastle)
Trapped(Peach)


And then our expected ending:

IsAt(Mario, Home)
IsAt(Peach, Home)


Now, we need to provide Actions, that are, the things characters can do in the story. For instance, they can travel, get PowerUps, defeat enemies… the usual stuff. In planning these are defined by preconditions and effects. For instance, we may have a $$Travel(X,Y,Z)$$ action with the prerequisite that $$X$$ is in the location $$Y$$ and $$X$$ is not trapped.

$$IsAt(X,Y) \text{ AND NOT } Trapped(X)$$

And the effect that we move the character to the new location:

$$IsAt(X,Z) \text{ AND } (\text{NOT } IsAt(X,Y))$$

With the same fashion we can define an action like $$Free(X,Y)$$ for character $$X$$ to free character $$X$$ with the prerequisite that $$X$$ and $$Y$$ must be in the same location (and, Bowser must not be there!).

You get the idea.

After we set up everything, it is time to run the planning engine. The engine will try to “solve” the story and will return something like this:

Travel(Mario, BowserCastle)
Defeat(Mario, Bowser)
Free(Mario, Peach)
Travel(Mario, Home)
Travel(Peach, Home)


Cool. The story is there, but the “prose” is definitely substandard.

Planning Storytelling is very powerful and can generate very intricate stories. There are, though, two major drawbacks.

1. Setting up all the preconditions, actions, states, etc., is not easy. The complexity of the story is limited by the complexity of the actions we encode into logic. Too many constraints and you are just writing the story yourself, too few and the story may be dull and predictable.
2. The generated story is just symbolic. As you can see from the example above, you have just a list of actions. You need extra works to encode this output into something enjoyable by the players.

## Procedural Storytelling via Context Free Grammar

In this last approach, the system just expands text using a Context-Free Grammar.3 That is we start from one symbol.

#STORY


Then we have a rule.

#STORY -> #BEGINNING. #MIDDLE. #END.


The rule tells us that, when we find the symbol #STORY, we need to replace it into with a new string: #BEGINNING. #MIDDLE. #END..

So far, so good. Now we may have more rules:

#BEGINING -> Once upone a time, a #JOB called #CHARACTER was in love with #CHARACTER
#MIDDLE -> But one day #CHARACTER is kidnapped by the Evil Lord #CHARACTER.
#END -> So #CHARACTER defeted the evil lord and they lived happy ever after.


And then more rules:

#CHARACTER -> ["Mario", "Peach", "Bowser"]
#JOB -> ["Plumber", "Electrician", "Game Developer"]


Where the square brackets represent one of the possible expansions.

At each step, the algorithm replaces each symbol (the ones starting with #) until there are no more symbols to expand.

This technique is very good at generating small “random” stories or funny texts. However, for the storytelling point of view, the main problem is that the algorithm completely ignore the semantic of the story. For instance, we can legally generate incoherent stories like this:

Once upone a time, a plumber called Mario was in love with Bowser.
But one day Mario is kidnapped by the Evil Lord Mario.
So Mario defeted the evil lord and they lived happy ever after.


This problem may be addressed, for instance, by making more complicated rules. For instance:

#BEGINING -> Once upone a time, a #JOB called #MAIN_CHARACTER was in love with #LOVE_CHARACTER
#MIDDLE -> But one day #LOVE_CHARACTER is kidnapped by the Evil Lord #EVIL_CHARACTER.
#END -> So #MAIN_CHARACTER defeted the evil lord and they lived happy ever after.


But, as you can imagine, this reduces the generative space of the system and makes everything more complex. And this complexity may increase exponentially for longer and more convoluted stories.

If you want to take a look at a real system like this, you can take a look at Tracery.

## Conclusion

This is just a very high-level overview and, as you can imagine, we could write books on each one of them. However, I hope this article can give you an idea of the main approaches in procedural storytelling.

1. Miller, Chris, Mayank Dighe, Chris Martens, e Arnav Jhala. «Stories of the Town: Balancing Character Autonomy and Coherent Narrative in Procedurally Generated Worlds». In Proceedings of the 14th International Conference on the Foundations of Digital Games  - FDG ’19, 1–9. San Luis Obispo, California: ACM Press, 2019. https://doi.org/10.1145/3337722.3341850↩︎

2. For teaching reasons, this is not a rigorous FOL conversion. Many details are missing, such as that Mario is a character (e.g., $$Character(Mario)$$) or that Home is a location. But I do not want to makes things more complicated than we need. ↩︎

3. To be precise, a Probabilistic Context-Free Grammar. That is, in short, that the rules select a possible expansion at random. ↩︎

##### Marginalia: Rebooting AI by Gary Marcus and Ernest Davis

With this new year, let’s try a new format. Marginalia will be a series in which I’ll share notes and comments on interesting books I read. The name is directly inspired by the old word …