The Saturday Paper - Turn Left At Next Plot Twist

Crossposted from Games by ANGELINA

Procedural generation systems - they're just tools, right? They're little bits of code we slot into games to solve a tiny problem for us. Don't want to design levels? Randomly generate them! Players getting bored? Randomly spawn fetch quests for them to do! Some people are interested in procedural generation being more than this though, and one way this can be achieved is to get different generators to start working together. This week on The Saturday Paper: a world generator that takes its cue from a space of procedural stories.

We're reading Towards Story-Based Content Generation: From Plot-Points to Maps by Josep Valls-Vargas, Santiago Ontañón and Jichen Zhu. This paper is all about bridging the gap between two very exciting kinds of procedural generation - stories and game worlds. We're going to look at a system that can take in story descriptions generated by another tool, and produce world designs that appreciate the structure of the story and help to convey it properly. Interactions between different procedural generators is something we don't see all too often, which makes this interesting reading! This is quite a dense paper, with a lot of technical ideas in it, so I'm going to try and give a good overview to the ideas in the paper. However, if you're planning on building a system similar to the one that Josep and co. describe here, I really recommend reading the full paper and getting in touch with them.

In The Beginning - Giving The System Input

The input to the system, rather than being a simple fully-formed story, is more like a space of stories that are linked by a shared environment. First you provide facts about the environment, things like the types of objects or locations that are allowed to exist in your world. Then you provide details about the initial state of the world, which adds concrete details about which objects or locations actually do exist right now, and what relationships they have - this also provides important information like which locations can be next to each other in a map (so you can't have a cave in the middle of a city). That gives you the story's beginning. Then you specify the goals of the story - things you want to be true by the time the story concludes. This gives you the ending you hope to achieve. Finally, the most important bit of the setup: plot points.

A plot point is an event that can happen inside a story, a self-contained event or bit of action. Since we're dealing with nice, clean logical descriptions, plot points are described very precisely: they have a set of preconditions, which are things that must be true before the plot point can happen, and they have a set of postconditions, which are things that happen as a result of this plot point taking place. Here's a rather sketchy example of my own to illustrate:

Plot Point: Sea Monster Attack!
Precondition: The player is on a boat.
Postcondition: The player loses her items. The player is stranded on a beach.

Ignoring my dubious narrative skills, you get the idea: plot points are individual bits of story. Preconditions help us choose sensible places to put them into, and postconditions applies consequences to the story that make sense[ref]The paper actually separates what I'm calling 'postconditions' into two lists, but I'm simplifying things for the column. Check out the paper for the gritty details![/ref]. While you might expect the system to take in a single sequence of plot points that describe just one story, it's more clever than that. It actually takes in a big set of plot points that all intermingle together, and can lead into one another so multiple paths exist through the story world. Here's a nice diagram from the paper, and yes their example is better than mine:

What this graph shows is the result of the world generator reading all those facts - the plot points, goals, initial state and so on - and working out all the different links there are between plot points in this story. There's lots of info on how this graph is built in the paper itself, if you're interested, but you can sort of see it's about what's possible from each plot node. You can't give someone water until you've picked up the water, and so on. Armed with this information, we can begin building a map for our story.

Mapping The Story

We can already begin to draw a map that a story could take place in, by just looking at the location map we gave earlier (the one that tells us which locations can be accessed from which others) and just randomly grabbing locations from it and sticking them next to each other. However, if we did that without thinking, we might end up with a really boring map for a story. Imagine if the player had to deal with a dispute between two kings. If the kings are at either end of a very, very long chain of mountains and forests, the player will be doing a lot of travelling for each plot point, and might get bored.

What the system does instead is this: first, it generates a potential world map abstractly by selecting locations that can appear next to each other. Then, it evaluates that map configuration by generating all the possible stories that fit in the map, and seeing what qualities they have. There's a list of the metrics the system uses in the paper, but they're sensible things like how much travelling is required to unveil a new plot point or how connected the events of the plot are (based on whether the player's goals are constantly switching). If the abstract map's score isn't high enough, the system throws the map away and generates a new one (recording the features that the map had so it doesn't generate a similar map next time).

Now we have an abstract map that links locations together. This tells us, for instance, that the river is accessed by going through the meadow. But it doesn't tell us how many screens the meadow is, or which bits of the meadow allow you to reach the river. We need to take the abstract location map now and turn it into a proper game world. This is done via a rather complex process which the paper calls graph embedding. The system goes through each connection between two locations in the abstract map, and tries to make nodes in the game world that correspond to those locations. If it tries to connect a new location to one that already exists in the game world, it builds a chain of rooms that connect to the two. There's a great example in the paper, where the room denoted V is chained together to connect the G and F rooms. Check it out:

The full algorithm is quite complex, so I recommend as usual that you check out the paper for all the details. At this point, we've more or less completed our world design. All that remains is to block it out in our game however we see fit. In the above example we might want to ensure that rooms of the same type (such as v_1 - v_5) all flow into each other. For adventure games or the old-style Final Fantasy format, the screens are all fairly separate anyway, so the realisation of the game world is more straightforward.

Today's paper was quite overwhelming, so let's collect ourselves before we sum up. This system starts with a description of dozens of possible world events, as well as information about what locations are allowed to connect to each other. It builds possible worlds out of this data, and then tests all potential stories on this world design, to see if they're too boring, illogical, or long-winded. If a design looks good, it then tries to flesh it out into a series of interconnected rooms, while being careful to make sure it doesn't break any rules about what should connect to what.

The result is a world that is procedurally generated, but obeys the narrative the designer has in mind for it. We're very focused on 'simulation-as-narrative' in certain indie circles these days. Dwarf Fortress and their ilk randomly generate as much as possible and hope for interesting stories to emerge from it. But I think there's a lot to be said for procedurally designing content with the explicit aim of telling a particular story. The work described in the paper we looked at today does just that - it generates a real story, instead of randomly hoping for one, and then engineers a world that suits its various events and plot twists. I'd like to see more of this sort of thing coming out of medium-scale indie projects.

Where To Find More

Josep is currently a PhD at Drexel University, under the supervision of Santiago and Jichen who are both Assistant Professors there. I first got to know them at last year's Intelligent Narrative Workshop at AIIDE, and they're all tremendously enthusiastic about narrative and games. I know a lot of indie developers like this topic area as well, so you should think about getting in touch!

Addendum

I've just posted up the Call for Papers for the International Conference on Computational Creativity 2014, and I want game developers to get involved! More info right here.