Procedural Generation and User-Generated Content by Gavan Woolery

[zarx]

In my last article, I gave a brief overview of Procedural Generation (PG) and User-Generated Content (UGC).  In this article, I have decided to discuss something that gets surprisingly little attention: procedural generation of storylines/plot/quests/dialog and so forth.

Procedural generation of storylines is very common, whether or not we realize it.  Sadly, most of these consist of fetch object X to receive reward Y or kill monster A to proceed to area B.  We use these kind of mechanisms all the time, but we have a hard time pinning down what is “wrong” with them.

I think that games stand as their own medium, but that does not mean we cannot learn from other types of media.  Imagine that you are reading a book.  Throughout the book, the character kills monsters, grabs loot, travels through different areas, and talks to different people.  This describes many books, but it is a superficial aspect of them.

Bad books tend towards this superficial aspect.  Good books have something going on under the surface.  Everything that happensmakes sense, but at the same time, is not entirely predictable.  There are a million ways you can break it all down, but I am going to start from the top and work downwards.  Note that I have no formal education in writing, so I am doing my best to describe patterns as I have seen them.  I will scatter some examples from popular stories throughout.

At the top level, you have:

• Characters (Actors)
• Items (Props)
• Environments (Scenes)

CONTEXT

Now, let’s dig deeper.  Every character, item, and environment has a timeline that dictates their qualities, abilities, and motivations, from past to future.  We will call this the context.

• Characters (Actors)
  • Beginning: Character is born, genetic makeup is determined.  Also notable are the family and environment the character is born into. (Hercules was the bastard child of Zeus and Alcmene, Zeus’s real wife Hera was pissed.)
  • Past: Character’s back-story, determine’s their learned behavior.  In combination with their genetic makeup, this determines their personality and motivations. (Jean Valjean was born into hardship, learned the ways of a thief, and grew to value morality over the law.)
  • Present: Character’s current state, location, conflicts, tasks, etc. (Horton’s acute hearing tasks him with helping a village of tiny people.)
  • Future: potential of character, fulfillment of a prophecy, etc. (Harry Potter was viewed as one of the few people who could defeat Voldemort.)
• Items (Props)
  • Beginning: how the item came to be; where its resources were collected from, how it was crafted, etc. (The Ring was forged in the fires of Mount Doom.)
  • Past: who owned the item, what historical significance the item has, etc. (The Ring was lost in a river and eventually found its way to Gollum and corrupted his figure and morals.)
  • Present: where the item currently is, its current state (broken, hidden, scattered across the land, etc). (Frodo carries the Ring, Sauron is looking for it.)
  • Future: where must the item go? (The Ring must be taken to Mount Doom and destroyed.)
• Environments (Scenes)
  • Beginning: How was the land formed, how was the structure built, what inherent qualities does the land have, etc.
  • Past: how did the environment change over time, what happened in the area, etc.
  • Present: the present state of the environment, what events are occurring.
  • Future: what will happen to the environment (The Tree of Souls will be destroyed unless the Navi can stop the humans.)

All of these things set the context – they explain why things happened, what is happening, and what might happen.  But the context alone does not make a story, in fact it only introduces what we need to know to understand the interactions that will occur throughout the story.

INTERACTIONS

Given the context of the characters, items, and environments, how will things play out?  These interactions are a fundamental part of the progression of the story, but on their own they do not necessarily make for an interesting story.

Lets look at all of these permutations of interactions – below are just a few examples, I am sure you can think up more:

• Character-Character: Characters talk to each other, lie, fall in love, (attempt to) assassinate each other, vow for revenge against one another, transport one another (hostages, bodyguards…), etc.
• Character-Item: use items to empower themselves (i.e. drink a potion) or achieve a goal (i.e. using a key to unlock a door), or even kill themselves (Juliet uses Romeo’s dagger to kill herself.)
• Character-Item-Character: characters give an item to empower or curse another character, they use items on one-another, etc.(The Witch gives Snow White a poisoned apple.)
• Character-Environment: Characters must travel to their destination, seek haven, find a place to eat, etc. (Harold and Kumar seek out White Castle.)
• Character-Environment-Item: Characters must seek out hidden items from environments, collect items scattered across different environments, use an item to proceed to a new environment, etc.

Interactions will create a story, but not necessarily an interesting one, as stated earlier.  You need to have a clear goal and progression in order to derive meaning.

MEANING

Meaning is all of those “intangible” things you learned about at some point: theme, climax / turning point, epiphany, character progression, and so forth.  Instinctively, we might think that it is impossible to put effective meaning into games, unless they are very linear in nature like books and movies.  I would argue that it is not impossible, just hard.  If you give your users free reign and make a total sandbox game, chances are they won’t produce a very effective storyline.

This “problem” has been solved, and it might surprise you how old the solution is.

Dungeons and Dragons.  I must shamefully (proudly?) admit that I have never played the board game.  Regardless, I understand the mechanics behind it.

I am sure there have been plenty of D&D games where players kind of just mess around and do what they want.  Interestingly, these have probably been the least enjoyable games for everyone.

When players follow a structure, and more importantly, play a role, they tend to have much more interesting sessions, because their games have meaning.

Roleplaying has become a bit of a misnomer.  We are very, very rarely playing a role in modern video games.  We are controlling a person who has a context and is capable of many different interactions, but they are rarely confined to a role. This is why most of the characters we play feel like they have no personality – because we aren’t really confined to one (I’m looking at you, Commander Shepherd).

I am as much against artificial constraints as the next guy, but I think we can easily introduce motivations for people to play their role.  We can do this without having to pretend, but instead using the game’s inherent mechanics.

It all comes back to meaning.  I can go slay the monster, collect the loot, and return for another quest, but what does it all mean? You cannot have meaning without persistence.  What impact does my action have on the world, and what is my incentive to perform this action?  How can we effectively insert meaning into nonlinear games?

STORY ELEMENTS AS GAME MECHANICS

In order to have any semblance of structure, we must play a role.  How do we get players to fulfill roles without placing artificial constraints on them? We have to make qualities of the role a tangible aspect of gameplay, and reward players for following their roles and not reward (or punish) them for stepping out of their role or diluting their role.  Given our character’s context, we must determine their motivations. We must also determine how their interactions fulfill or conflict with their motivations.

How do we turn this into something tangible?  There are many ways, but I will point to one obvious way: the meter.  If you ever played The Sims, this game used a system of meters to determine the state of your character.  They had a hunger meter, a bathroom meter, a fatigue meter, and various meters representing their emotional needs.  If their needs were met, they would function properly and succeed in the various aspects of their life (career, relationships, etc.).  In theory, you could do whatever you wanted with your Sims, but the game encouraged you to try and fulfill the needs of your Sim.

Imagine that in your roleplaying game, a character has a meter (or some other tangible entity) that measures how well you have fulfilled their ambitions, goals, and so forth.  Perhaps this meter affects other areas of gameplay (i.e. how effective your character is in combat), or perhaps it has direct effects of its own.  If your character is a thief, perhaps you must satisfy their urge to steal, and you must avoid combat because it makes your character uncomfortable (they prefer to sneak around).  In order to construct an effective storyline, you need a number of roles to be played.

• The Hero(es)
• Neutral Characters
• The Villain(s)

Additionally, each role should have a fairly well-defined subset of abilities.  Characters that can do everything and have no weaknesses are boring characters.  This is why we have archetypes in stories.  Each character is a piece of the puzzle and they all use their strengths to achieve a goal while their weaknesses are exploited by the villain or other circumstances.  Character archetypes are popular in story-telling, here is a fairly comprehensive list of them:

http://www.listology.com/list/character-archetypes

EMERGENT STORYLINES

We can encourage characters to go down certain paths and motivate them to play their roles, but how do we create a game engine that constructs meaningful storylines on its own?  It is actually surprisingly simple, and only involves a little bit of AI work.  I won’t delve into the technical details, but if you understand propositional logic, backwards chaining, expert systems, and how languages like Prolog work, you probably have a good idea of how to implement systems like this.  I will layout the basic functionality of this system below:

• You play a character who has a set of motivations that you try to fulfill.
• The game controls a number of NPCs via AI.  Each NPC has its own set of motivations.
• One or more NPCs has motivations that are in conflict with yours.

Let’s take a look at a simple example.  Imagine that we present the following facts into our system.

• There is a playing field with a limited amount of gold and three characters, and random walls everywhere.
• One player can only see another if a wall is not blocking their line of site.
• You control character A (the “hero”), whose motivations are to abide by the law and collect as much gold in your stash as possible.
• The computer controls character B (the “villain”), whose motivation is to collect as much gold in their stash as possible.
• The computer also controls character C (the “guard”), whose motivation is to enforce the law and prevent crime.
• The law states that it is illegal to kill or steal, and the punishment for either one is death.
• Dead people cannot perform any actions (namely, they cannot collect gold).
• If a crime is not seen, a punishment cannot be enforced.

Left to its own motivations, the villain might try to kill you (the hero), even though it was never explicitly instructed to, because out of all the paths it can take, killing you might yield the maximum amount of gold (provided it can do so without being seen by the guard).  Or, if the guard is always too close to the hero, the villain might just try to steal from the hero’s stash instead.  On the other hand, you will probably not kill or steal, because the game mechanics will find some way of punishing you for defying your given role, whether or not the guard is watching.  Also, interestingly, the guard will probably follow around the villain more closely, because it knows that the villain is more likely to break the law and it is motivated to prevent crime.

This is a very simple example, but the important thing to note here is that there are no explicitly-defined scenarios, everything isimplicit based on the circumstances.  Personally, I think that explicitly-defined plots are bad for gameplay.  They might be able to create a better, more powerful storyline, but they are bad for gameplay because they tend to force players into linear scenarios, thus limiting replayability, increasing predictability, and diminishing the feeling of a truly interactive environment.

So, what do you need to form a coherent, emergent storyline?

• Characters, Items, and Environments (this should be a given…)
• Context (properties and history of each entity)
• Interactions (each character has a given set of actions they can perform which are probably partially dictated by what items they posses and their current environment)
• Meaning (motivations to perform actions that make sense, clear end-goals)
• Well defined roles
• Abstraction of each of the former for the purposes of AI and gameplay mechanisms – most things should be able to be measured by a number or boolean/fuzzy logic.

Tying it all together: in every instance/turn, characters weigh the facts (context), the state of their present environment, and their motivations against a list of possible actions.  They then select the action with the highest predicted return towards their motivations and the system is updated with the new data.  Repeat as necessary.

MYSTERY

Good storylines have mystery and plot twists, even if they are not explicitly classified in the “mystery” genre. It is fairly easy to incorporate these elements meaningfully into a game.  For example, lets take another set of facts from a hypothetical game (here, the “?” represents facts that are not immediately apparent to the player or AI):

• A farmer has the motivation to keep his sheep alive and has some money.
• You play a mercenary that will kill anything for money.
• Dragons kill sheep.
• ?
• A farmer’s sheep are being killed.

With a bit of backwards chaining, the farmer will probably deduce that he can keep his sheep alive by paying you (the mercenary) to kill the dragon that is killing his sheep.  So, you camp out, waiting for the dragon to attack.  Instead, you see some wolves attacking the sheep (this fact is represented by the “?” – and represents part of the mystery/plot twist).  Again, this is a very simple scenario, but imagine the possibilities when you set the stage with a myriad of characters, items, environments, and context with high potential for mystery, conflict, and other story-telling mechanisms.

DIALOG

So, how might you handle dialog in a non-linear game with emergent storylines?  Well, lets keep it simple for now and imagine that everything is text (no recorded speech).   Creating an AI that is able to fully understand and parse every word you type is probably beyond the scope of most games, but there is a simpler alternative: sentence fragments.  Imagine that you are able to construct your dialog from a series of words or sentence fragments.  Here is one example: [promise to][kill][1][dragon][in return for][20][gold coins].  It might seem difficult to interpret a series of fragments like this, but we have been doing it since the dawn of computer languages.

If you have ever written a compiler, this is exactly what you would need to handle something like this.  So, you have a series of sentence fragments or words, which are basically the equivalent of tokens/keywords/functions in a compiler.  Then you have names of people, places, and items, which are the equivalent of IDs or variables in a compiler.  You could parse any string of sentence fragments and validate it against a Context-Free Grammar (which is basically a grammar check).  Upon parsing and interpreting your sentence, the AI adds it its database of facts or propositions, and then acts on its new set of data.

I cannot recall a game that has yet implemented something like this to an effective degree.  It would lend itself to many interesting possibilities though.  The AI might try and manipulate your character’s motivations by lying to you, or similarly you could attempt to manipulate the AI by asking NPCs to do tasks for you (i.e. distract a male guard by telling a female NPC that the guard thinks they are attractive, thus prompting the NPC to flirt with the guard).  Even beyond manipulation, it could be the infrastructure that creates a real, breathing world in which characters interact with one another in a totally improvised, but believable, manner.

In a greater scope, it might sound like a pipe-dream, but I think that if we attempt to implement simple game mechanics systems like this are totally doable.

There is room for a lot more discussion in this area, but I should probably cut it short at some point. I apologize if I lack clarity but feel free to ask me anything.  Mostly, I just want to get the gears turning.  What do you think? Are systems like this a good idea or doomed for failure? 

http://altdevblogaday.org/2011/04/06/procedural-generation-and-user-generated-content-part-ii-storylines-ai-and-emergent-gameplay/