The Saturday Paper - A World Just For You

Originally posted on Games By ANGELINA

Which is more important - story or setting? In some games, particularly RPGs, it feels almost impossible to separate one from the other. Setting dictates the where, the when and the how of the game. But the story has demands of its own - the order in which things must happen, and what it is the player will be experiencing. Is it possible to include procedural generation in this process without upsetting the balance? This week on The Saturday Paper, a world generator that understands stories - and can adapt to both the designer's and the player's preferences.

More...

We're reading Toward Supporting Stories with Procedurally Generated Game Worlds by Ken Hartsook, Alexander Zook, Sauvik Das and Mark Riedl. The paper describes Game Forge, a system that can be given a narrative structure and will design an RPG world to suit it - even taking into account what kind of gameplay the player is after. It has some interesting ideas about how to generate worlds that suit stories, and the adaptive nature of the tool is something that developers of all genres, from roguelikes to casual games, will be interested in.

Game Forge starts off with a story template expressed as a list of story events - whether it's human-authored or autogenerated - that states key information like the people involved in the event and where the event takes place. Here's a simplified example from the paper:

kill(paladin, witch, graveyard)
drop(witch, jewel, graveyard)
take(paladin, jewel, graveyard)
gain-trust(paladin, king, jewel, palace)

In order to start generating a world for this story, Game Forge needs two other bits of information: a designer-specified location model that helps it create worlds that make some kind of sense; and a player model that describes what this player wants from the game. The designer model is useful because it adds context to location names like 'castle'. Here's an example from the paper:

This gives the world generator guidance on how likely a swamp is to occur next to a palace (in this case, not likely at all). The player model, which Game Forge could theoretically work without, adds in information like how much time the player wants to spend travelling between locations (some players might enjoy the combat and exploring, while others just want to experience a narrative, for instance). Like the story layout, how this is gained is up to the designer - it could be as simple as a questionnaire the player gets given, or you could make versions of the game for demographics you define yourself. "Super Roguelike VI: Casual Edition" maybe has less enemy encounters because you fed it a particular player model. There's more information on exactly what kind of metrics they use in the player model in the paper itself.

The worlds themselves are then generated using computational evolution. If you want to know more about evolution as a process, I wrote a little post about it here and put up some simple sample code on GitHub. I want to mention two parts of the evolutionary process here, though: how Game Forge represents its game worlds, and how it evaluates them.

For Game Forge, worlds are represented using the idea of islands and bridges. Islands are places where game events happen, like the Castle location in our example story above. Bridges are the game spaces between islands, which the player travels between and may encounter battles or side quests within. A game world is a collection of these islands with appropriate bridges connecting them. I like this separation of fixed and variable gameplay - it lets the worlds vary in their layout easily, and gives lots of scope for extra procedural generation to happen in the gaps. Here's a picture of several worlds generated by the software, where you can see the variation in the length of the bridge sections, or how branching and diverse the paths are:

Evaluating a world design uses the player and design models we talked about earlier. The design model evaluates things like which bridge and island types are placed next to each other (worlds that break those rules score lower than worlds that don't) while the player model scores the world for how well it suits the player preferences - how much exploration do they like? If they like a lot, then paths with lots of branching and travelling get better evaluations. This combined score is used to drive evolution by evaluating a bunch of possible world designs, and selecting the highest-scoring ones to generate a new set.

Crucial to evolution is how to generate new things from the highest-scoring examples you already have. In the case of Game Forge, once we've evaluated our set of game world designs, we want to know how to generate a new set from these 'parent' world designs. Game Forge can mutate a single world design by randomly swapping the environment type of a node, or by randomly adding and deleting nodes from a given design. Or, given two world designs, it can breed them together to create a new world design. It does this by selecting a subgraph of one world's islands and bridges, and connecting it to a complementary subgraph from the other design.

Once the world design is complete there are just a few tasks left. First, Game Forge actually lays out the individual world areas using some template layouts that describe the distribution of game elements. A castle area, for instance, uses a guide for distributing houses and castle towers in a pattern that looks sensible, whereas a forest can afford to be more haphazard in the placement of trees and rocks.

Finally, Game Forge needs to place story items and people in the world, and then execute the game's script. Placement of key items and NPCs uses the story as a guide, placing them wherever they first appear in the narrative. These NPCs, as well as incidental characters that may be appropriate for a given location (castle guards, for instance), will act out the game's script that is attached to each line of the generated story we gave to Game Forge at the beginning of the process. Game Forge is able to assign the script to appropriate NPCs, and even able to redecorate game locations according to different events. When you return to the Castle that is experiencing a 'siege' event, it looks different to how it was when you left to go out on your adventure. All of this is built into Game Forge, meaning it needs no further guidance than to have each event or scripted sequence described in the input story.

Although this paper focuses on RPG worlds, the idea of representing key location as nodes and having links between them is a nice representation for lots of things: story beats in a first-person shooter, big puzzle rooms in a platform game, or even major encounters in an MMO. The balance between "I need this to happen" and "I need something in-between here" is one that crops up a lot in certain game genres. When it happens, the idea of letting your game vary in those in-between bits is really appealing. While I'm not crazy about the idea of personally adapted games, I do like the idea of variable flavour. It reminds me of a previous post where we talked about procedural generators with personality.

When you look at some of the heaviest hitters in the modern games industry, we often see either an abundance of procedural generation or an incredibly slick story and setting (The Last Of Us has been all my friends could talk about lately). Finding dependable ways to tie these things together could be big for a number of genres. Game Forge offers one possible route to doing so.

Where To Find More

Ken Hartsook graduated with a M.S. in computer science in 2011 and is now at EA/Mythic Studios. Alex Zook is currently finishing his PhD with Mark Riedl at Georgia Tech. Alex has worked on a lot of interesting papers since then, the latest of which is AI For Game Production, which I've not had a chance to read yet but comes highly recommended! Sauvik Das graduated with a B.S. in computer science in 2011 and is now a Ph.D. student at Carnegie Mellon University. Mark Riedl heads up the Entertainment Intelligence Lab at Georgia Tech, and if you're even a little bit interested in procedural or interactive narrative, you should be following him on Twitter. Everyone at the EI Lab is incredibly friendly and open about their work - get in touch with them if you want to know more!
 
Let me know what you'd like to see more of in the Saturday Papers on Twitter @mtrc