Jan 16

Random Story Generation Part 1: Nothing More Practical Than A Good Theory

A visual depiction of how a Markov Chain story generator works.

I’ve decided to document my experiments in random story generation, in the hope that these notes will be helpful to other developers and hobbyists. This first post will define some of the terms I’ll be using and introduce some of the theory.

My first idea for a random story generator came during a literary criticism class I took during university. We were learning about reader response criticism, which is a model that focuses on the interaction between reader and text. In RRC it doesn’t make sense to say that a text has an inherent meaning; instead, meaning is something that is actively constructed by the reader through the process of reading. The author of the text, and whatever they intended the text to mean, doesn’t enter into it. If we don’t need to worry about authorial intent, why bother with an author at all?

The next piece of the puzzle came from Scott McCloud’s explanation of closure in Understanding Comics. A comic consists of a sequence of separate images; the reader uses closure to combine these images into a coherent story. I realized that the same would apply to a series of short narrative arcs in a computer game. Even without intentional connections between the arcs, the player’s sense of closure would interpret them as a meaningful story.

Finally, Vladimir Propp’s narrative functions provided a way to arrange these arcs so that the reader/player would be likely to interpret them as a coherent story. Propp analyzed Russian folk tales and discovered that all of their plots could be constructed from a finite list of story events which always appear in the same order.

From all this I got the idea to create a big list of story fragments, then use some kind of algorithm to arrange them into reasonably intelligible sequences. Turns out that’s pretty much how all procedural story generators work, even today.

I named the smallest narrative chunk a Plot, which I will capitalize to differentiate from the regular use of the word. A Plot modifies the game world for as long as it is active; it might alter an NPC’s dialogue options, or add an encounter to the world map. In GearHead-1 the Plots are quite coarse, defining an entire mission or a chapter of the core story. In GearHead-2 the Plots are much smaller; a single combat mission might consist of four linked Plots- one for the NPC offering the mission, a separate Plot defining the mission’s combat encounter, a Plot that is activated if the PC wins the mission, and another that is activated if the PC loses. The Plots in Dungeon Monkey Eternal are even more finely grained.

Using lots of small Plots is much better than using few large Plots. First off, if a quest is composed of multiple Plots, it means that the player won’t know how it ends just because they’ve seen this beginning before. Second, it allows reuse of code, which is a huge advantage for both bug control and refactoring. Instead of every mission having to define its own combat encounter, they can just call for a standard combat encounter Plot. Third, it greatly increases the number of combinations your system can generate, and in general you want your random plot generator to be able to generate a really really big number of combinations.

There are numerous ways to arrange Plots, including Markov Chains and context free grammars. The important bit is to have some way to describe the context of a Plot, so that Plots which belong together get placed together. Next time I’ll describe how the GearHead-1 core story context system works. Let me know in the comments if you have any questions.


  1. Another fan

    I got all happy and excited when I saw this entry. ^^
    “[…] in the hope that these notes will be helpful to other developers and hobbyists.”

    Sure enough it helps me. If nothing else plenty inspiring at least!
    But the context free grammar heads-up was already useful. 🙂

    I have plans for a game heavy on AI and randomized parts to make for great emergent situations / gameplay and I absolutely love random story generation.

    I guess I should finally try Dungeon Monkey Eternal and peek into the code maybe.
    https://github.com/jwvhewitt/dmeternal <3

  2. John Connors

    Thanks for providing links for the theory behind this; much food for thought; want to incorporate some of these ideas into my own work – if I ever get that far.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>