Author Topic: Procedural generation of quests and narratives  (Read 16630 times)

Snargleplax

  • Rogueliker
  • ***
  • Posts: 50
  • Karma: +0/-0
  • snargleplax
    • View Profile
    • SnargleQuest dev log
Procedural generation of quests and narratives
« on: March 07, 2012, 12:16:43 AM »
I'd like to get some discussion going on procedural generation of quests and other narrative-type content.  This is something which figures heavily into my own game plans, so I've got some self-interest in bringing it up here, but I'd love to get some more input on all this and share some ideas generally.  I've also laid out a little bit of this in one of my dev log entries, but I feel there's much more ground to cover.

Bluntly speaking, most of the quest content I've seen in games is pretty primitive, at least compared to other common narrative forms (books, movies, etc.).  Even without procedural generation, designers are commonly guilty of subjecting players to endless FedEx quests, bounties, etc.  The lame predictability of these simple tropes inhibits immersion and enjoyment.  In the procedural space, it's understandable if ambitions have not tended to reach past this.  After all, if it's hard to do by hand, it's harder still to automate, right?  Perhaps that's fair; on the other hand, procedural generation has other attributes than being automated, and these may be of benefit.

As a particular example, procedural content generation systems have the benefit of being online; that is, you can keep generating new content as the player goes through the game.  Nothing need be set in stone until it's been shown to the player.  It's hard to relate this kind of freedom to anything experienced by a traditional designer.  It's more like the position enjoyed by the Game Master of a pen-and-paper RPG, who may exercise constant, subtle discretion to the end of providing a (hopefully) satisfying player experience.

Every good Game Master knows how to ad lib; no matter how much you plan, the players will always surprise you.  If the players start walking in the opposite direction from where the quest is "supposed" to be, a good GM will silently adapt the world around them so that it turns out they do wind up where the action is.  By adaptively serving up a narrative that feels like it was carefully planned that way from the beginning, the GM provides the players with a feeling that's greater than just being inhabitants of a fantasy setting -- they're the heroes of the story, as it should be.  The world conspires to draw them into their destiny.  Nobody complains about this (unless it's too hammishly done, but you can get away with surprisingly much when you're willing to "cheat" behind the scenes); it's what we want and expect from a heroic tale.

In roguelike terms, the opposite of what we're talking about would be something like Dwarf Fortress.  DF works incredibly hard to have a fully-operational fantasy world so that when you wander around in it, every little slice feels satisfying and real.  But of course, most players will never see most of the content in that world.  Most of the system is wasted, just to support the parts that you happen to wander through.  True, it's just processor cycles, but the point is that if you can present a player experience without simulating the entire world, you can trim out a lot of fat.  Moreover, you can gain a lot of control; DF can produce some entertaining narratives, but everything in the game is emergent and tied to the integrity of the world model.  You'd be hard-pressed to shoehorn arbitrary structure into that world, in order to steer the player in a more focused direction.

So, can we conceive of a workable alternative model?  Certainly, inroads are being made into online-adaptive PCG; a famous example being the "Director AI" in Left 4 Dead which models player experience in order to orchestrate pacing and challenge.  I believe this principle can be extended much further, into the dynamic, online generation of epic-scale narratives carrying complex plot structure.

As I envision it, the system starts with some ultimate goal, derived from some suitable plot archetype -- Defeat the Evil Menace, Rescue the Princess, Free Our People, Lift the Curse, Find the Maguffin, etc.  As with any good Ultimate Goal, it is of crucial importance but somehow indefinitely deferrable -- there can always be more impediments and side quests thrown in the way of success.  So, we start from that ultimate goal and work backwards, determining what complications exist and setting up subgoals for them.  Each subgoal can involve just as much complexity as the original goal, so in this way we can build up complex structures of interdependent subquests.

Rather than letting it explode infinitely, we would of course tune the generation to our specifications, depending on just how hairy we want to let things get.  And, importantly, the only fixed points in the graph are those that have already been exposed to the player in some way; the rest is open to being tweaked or rewritten at any time, for any reason we may see fit.

There are major challenges to this approach, of course.  First you've got to compose a suitably-large set of plot "chunks" and provide ways for them to fit together variously enough to provide novelty.  Then you need to expose these structures to the player in some sensible fashion, which could be tricky in such a generic system.  I think that for a more static form, such as written fiction, this approach would fail horribly.  But in a roguelike, the player's involvement in the action fills in for a lot of verbiage, and I think an appropriate balance may be struck.  Even accomplishing this, there's still the task of ensuring that what's generated isn't utter hogwash -- there must be some kind of semantic constraints on how you plug Actors and Props into Evil Plots, or you're going to wind up with the Princess kidnapping the Dragon, or being sent on a quest to retrieve the fabled Rusty Dagger of Worthlessness.

So, that's my wall of text.  Any takers?  Anyone know of other significant work in this area, or care to chime in with their own ideas on how to accomplish what I'm talking about?

Pueo

  • Rogueliker
  • ***
  • Posts: 263
  • Karma: +0/-0
    • View Profile
    • Email
Re: Procedural generation of quests and narratives
« Reply #1 on: March 07, 2012, 05:02:33 AM »
I think it's a great goal, but very difficult to achieve.  I think for me, if I can feel like I'm a main character in a book, I'm happy.  Some parts may not make sense, or may look out of sequence, but by the time the final words are written, you realize everything led to perfectly to the finale.
{O.o}
 |)__)
   ” ”   o RLY?

guest509

  • Guest
Re: Procedural generation of quests and narratives
« Reply #2 on: March 07, 2012, 07:11:26 AM »
  Sounds like a solid goal. Pretty tough but goals are meant to be hard.

  As for 'narrative' I like games where I sort of create my own. Give me an overarching quest, a well fleshed out theme and good mechanics and I'll write my own story.

  There are a lot of games out there, like Modern Warfare 3 for example, that sort of force you through a narrative instead of just letting you play. It's like they shuffle you through an overly deterministic play sequence and reward you with cut scenes or some other loss of control. I hate it but many people really like it. A certain segment just really values playing a story instead of writing their own.

Game Hunter

  • Rogueliker
  • ***
  • Posts: 92
  • Karma: +0/-0
    • View Profile
    • Channel, the Roguelike
    • Email
Re: Procedural generation of quests and narratives
« Reply #3 on: March 07, 2012, 03:36:21 PM »
The first (and probably biggest) obstacle to get out of the way is this guy:
Bluntly speaking, most of the quest content I've seen in games is pretty primitive, at least compared to other common narrative forms (books, movies, etc.).  Even without procedural generation, designers are commonly guilty of subjecting players to endless FedEx quests, bounties, etc.  The lame predictability of these simple tropes inhibits immersion and enjoyment.  In the procedural space, it's understandable if ambitions have not tended to reach past this.  After all, if it's hard to do by hand, it's harder still to automate, right?  Perhaps that's fair; on the other hand, procedural generation has other attributes than being automated, and these may be of benefit.
The hardest problem in designing a narrative on the fly is that many players aren't going to anticipate what is expected of them, no matter how many clues are given. The stereotypical MMORPG quests have become the norm precisely because they are almost impossible to fail outright: this has to do with their simplicity and avoidance of any real decision-making. If you want to design a good narrative, you'll need to design a whole slew of open-ended quests. This, all by itself, has some challenging considerations:

  • To what extent do we allow the player to fail a given quest? The only "true failure" could be death, or it can relate to time, context, or a simple lack of power to prevent something from happening.
  • Should a quest's failability depend on its gravity relative to the overarching goal? Making "important" quests harder to fail can be an abrupt change in the narrative: however, not pushing a player toward the goal may make them forever clueless as to its existance or solvability.
  • How many different kinds of failure should be allowed? There are many shades of gray between "completing a quest" and "failing to complete anything related to the quest". Adding these shades, however, can complicate the narrative by a lot, and each case must be considered (especially as to whether or not it will ultimately aid or deter the player from the goal).

And I'm sure there's plenty more than that. Trying to account for all of these things is probably a monster's worth of work: I would probably start by trying to develop (just by hand) an overarching goal that has at least 10 or so quest combinations that still allow the player to succeed, with 30 combinations in total. Obviously the game wouldn't make all of these from the get-go, but there will certainly be a large branching that ultimately has to come back to the goal, and developing a general method in your head as to how this works out while still being interesting is the first step toward procedurally generating it.

I think one of the more interesting ways to apply a character narration without necessarily involving literal "go do this" is to have the game subtly change itself depending on the character's interactions with it. Wipe out a bunch of orcs? They'll probably put a bounty on your head. Save a princess from some bandits? I wouldn't be surprised if royal messengers start searching for you and asking for help. Ally yourself with a black market syndicate? Shopkeepers will get wind of it sometime and either forbid you entirely or give you access to their secret stashes. The design would be to revolve narration around the player's "fame" and let the game account for the various things that the player can do all by themselves, without the need of any context as to the game's political or cultural nuances. It also means that the game will be different only if you decide it to be: taking the same actions would, more or less, produce the same kinds of results (randomness of map generation and world placement aside), which is a win-win for players all of sorts.

But hey, I'd love to see PCG expansion in just about any direction. Certainly developing the narrative (either by "fame" or by intelligently-designed questing) is a great start.

EDIT: whoops, left some of the OP in here unquoted
« Last Edit: March 07, 2012, 05:26:56 PM by Game Hunter »
2012 7DRL Challenge blind-runs!
2013 7DRL Challenge blind-runs too!
I do roguelike LPs, usually blind. I'm always looking for criticism!

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Re: Procedural generation of quests and narratives
« Reply #4 on: March 07, 2012, 03:44:28 PM »
this sounds like a good idea. maybe check out this Extra Credit episode on Pacing. It might help you come up with a format in which to add the quests, by building a smaller set of quests.

on a side note I had been doing something in my new RL where the player chooses their quest. My game has you going into a dark lords tower and coming back out. (Think kids daring each other to ring the spooky house doorbell.) the game starts with men challenging each other. so one might say " I bet you 100 gold you cant make it to floor 5" the player then can select "Your On" to except the bet or "OH yeah..". Selecting "OH yeah.." brings up the next challenge. "OH yeah, I bet 150 gold you cant make it floor 7". the player can never go back to a previouse bet, so its a push your luck style system, but depending on how large your game is, allowing the player to set their own smaller quests might be a good idea.

you might even be able to use this to spawn more quests. if you know the player wanted to do a quest to kill 10 badgers. well on the 10th badger a rift opens up and Badgifur the evil lord of badgers curses you. you can also use the first quest to get to the last quest doing the in between procedural. its one thing if the player is told to go defeat the evil lord, but its another if they decided to go get milk and end up on a quest to defeat the evil lord.

guest509

  • Guest
Re: Procedural generation of quests and narratives
« Reply #5 on: March 07, 2012, 06:23:10 PM »
  Besides being a fan of game design and the roguelike genre I like to write quite a bit. But for some reason I hate story driven games. It's part of what brings me to roguelikes in the first place. I get to create my own narrative.

  But if you were really serious in making procedural story telling I would not be looking at what people are doing right now. There may be stuff out there I am unaware of but everything I've seen just sucks. Plain and simple it blows. hard. I read all the time. That's where I get my story fix. I play games to create my own. To participate in the epic battles instead of read about them or have them overtly guided.

  However, science can solve everything. There have been some very good academic studies about story telling. Most people are used to a screen play style of story telling. The parts of which include:

Beginning (act I):
Where the characters are introduced and emotional attachment is built into the audience.

NOTE: Many stories will start out with an action sequence but this is rarely the turning point of the story. It is generally just used to illustrate the characters. See Commando, where Arnold walks around with a log. Or True Lies were he scuba dives, slides down the snow, meets one of the antagonists, etc...this does not lead to further conflicts it is merely used to illustrate the character.

Plot Point One (end act I): This happens at the 20 minute mark, typically. Where the main character (player in this instance) is flung into the series of events that create the story. Wolverine is saved by the X-Men. That unlucky dude gets face hugged on LV-422. Checkov meets Khan on Ceti Alpha Six/Five (thrusting Kirk into the arc of the story). "This IS Ceti Alpha Five!" An good example of the 'turn'. Perfect. Done in one sentence. Examples of early developments are in the movie 50/50 (that new one where Seth Rogan's buddy gets cancer). The 'turn' on that movie and the end of introduction is right at the 10 minute mark. Think of every movie you've ever seen, and most novels you have ever read, there is almost always a turning point after the introduction of characters that flings the story into the, well, story.

The Middle Acts (act II or acts II-IV): Many call this one act. I like Shakespeare's habit of making it 3 acts. Some people go with a 7 act paradigm. However you want to think of it this section is the meat of the story. In act II something else happens the character must overcome. Then act III is something worse and the character is barely holding on. Then in act IV the final battle is being set up. Arnold is covering himself in mud and screaming "raaaaaaaah" at the Predator. Wolverine is asking his buddies to fly him up to the spinning faulty mutant making machine. Ripley is closing down the hatches and prepping the shuttle for escape from the Soo-lah-go. Kirk is kicking it in the Genesis cave while Spock is prepping the ship to kick the holy bullcrap out of Kahn.

The Climax: It is entirely appropriate that this point of the story shares a name with getting off in sex. It happens at the height of tension. At the penultimate point of the story. To illustrate I quote, "Get away from her you bitch." "You're one ugly mother fucker." "No, no you can't get away, from Hell's heart I stab at the, for hate's sake I spit my last breath at thee."

The Resolution:
Modern story telling makes this piece of a story very small. Short. It ties up loose ends not tied up in the climax. The guy kisses the girl is the basic ending here.

  If somehow you can take this structure and create it procedurally I would love to see it. As for the specifics that this structure can take. I refer you to this article, about basic plots.

http://www.ipl.org/div/farq/plotFARQ.html

  So that is just my addition to the conversation as an heroic fiction and film nut. Feel free to ignore all of it. None of it may apply at all. Fine. I'm not offended. I wish you well in your quest and look forward to sampling your efforts.

-Jo

Darren Grey

  • Rogueliker
  • ***
  • Posts: 2027
  • Karma: +0/-0
  • It is pitch black. You are likely to eat someone.
    • View Profile
    • Games of Grey
Re: Procedural generation of quests and narratives
« Reply #6 on: March 07, 2012, 07:58:04 PM »
The problem with story driven games is they have to be character driven to be really compelling.  In roguelikes the main character is generally a faceless nobody, and the NPCs generally die (or have the potential to die).  "Role-playing" becomes irrelevant as soon as you add rewards for actions, since ultimately people will power game the thing and whatever story you devise gets ignored in the hunt for loot and stat-raising.

Fatherhood is the only example of a roguelike with a good story, because the aims of the story tie in with the aims of the gameplay.  Maximising the survival of your family becomes inherent to your gameplay decisions, and any soul-searching about sacrificing the one child to save the other is tied in with the gameplay crisis inherent in the decision.  There are no pre-set narrative elements or long pieces of text exposition - there is just you and the results of your actions.

Any roguelike about killing orcs and kobolds just isn't going to have the gameplay tied well enough with the story for the story to actually matter.  You'd have to rethink the gameplay as well as the story so that the two fuse together.

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: Procedural generation of quests and narratives
« Reply #7 on: March 08, 2012, 06:23:15 AM »
I typically prefer it in conversation when the person with which I'm sharing an idea with refutes it with constructive criticism, thereby allowing a conversation to organically emerge that in itself becomes the solution to whatever problem the idea was meant to address.

With that in mind, I'm going to stand opposite to the idea presented.

Quote
As I envision it, the system starts with some ultimate goal, derived from some suitable plot archetype -- Defeat the Evil Menace, Rescue the Princess, Free Our People, Lift the Curse, Find the Maguffin, etc.  As with any good Ultimate Goal, it is of crucial importance but somehow indefinitely deferrable -- there can always be more impediments and side quests thrown in the way of success.  So, we start from that ultimate goal and work backwards, determining what complications exist and setting up subgoals for them.  Each subgoal can involve just as much complexity as the original goal, so in this way we can build up complex structures of interdependent subquests.

A teleologically generated game world will emerge with a cohesive and unique narrative, but there are some problems.

Firstly- that the world is teleological. That is, the sub-quests, world, and everything, from the player's perspective, either has something to do with this ultimate goal or not. Even if there is some explicitly and implicitly generated game flavor, the player will always be trying to factor that into the teleology.

Secondly- It won't be character driven. It may feel like that the first playthrough- but with further iterations a 'this is the storyline' pattern will become obvious.

Thirdly- unrelated sub-quests and inane sub-quests become impediments to the goal. They are 'things that must be done' to get to the next chapter. There also tends to be a clear indication of failure and its effect on the the ultimate goal for any given sub-quest. This indirectly promotes save-scumming (if you could save).

Fourthly- Failures are clearly failures and do not impact the progression of the narrative in an interesting way. That is, when we fail- we lost the opportunity to acquire or gain some advantage, but




If your objective is DF depth without the bloat and both a more interesting narrative and a tangible story, then an ultimate goal may not be what you want. It's something that I've been thinking about, but I don't yet have a solid paradigm with which to rationalize a solution- however, here are some of my thoughts on it. They aren't very well collected, but hopefully I can impart the spirit of my idea.


We can procedurally generate a relationship tree by partially generating the properties of entities as they are encountered, and satisfying them later via a dependency queue.

For example- When we generate a monster, do we (as a developer) care what its family is? No. The family hasn't been generated- the monster's origins are unknown, but it must have some personal story of significance.

Typically- the player just assumes that the monster is there to feed us XP in the pursuit of the ultimate goal. But what if we generate the monster with unsatisfied dependencies- such as parents yet to be generated.

We ciykd then put those parents into a dependency queue and generate them in some other room further down the line. We can do this with racial types, racial variance, factions, and essentially everything. This includes flora and fauna, diet, vulnerabilities (pink mushrooms are poisonous to this species- emergent poison making abuse?! I think so- maybe the smoke from burning also blinds them), and be adjusted to include as much depth as desired. Coupled with some good ol' abstractions and maybe throw in some tautologies and you could potentially generate the rules of the game along with the game itself.



So, say we kill Monster A. Further down the line, we run into parent of Monster A, whom we kill. Then we run into Clansmen of the parent of Monster A, whom we kill. And all of a sudden the clan is out to get us. We could then hide in a town where that particular clan is very unpopular. The townspeople see that the Clan is more threatening than usual so the mayor attempts to recruit adventurers. Our hero joins the cause, ensures he is the only survivor of the defense, and becomes the de facto military ruler of the town.


Our world is deterministic and our character's identity emerges from how we play them.


Brogue generates key puzzles so that the the solution and the problem are all on the same level. But what if we generated a problem whose solution shows up later- IE, finding a locked box. We pick the box up and take it with us, but we need a key. The generator may happen to randomly generate a town in the room in which the key is also generated-- it might be generated into the inventory of a a person.


If we have a tree of dependencies satisfied as we explore while creating new unsatisfied dependencies, we don't have to wait for a complete DF-style world to generate to get an even more dynamic range of results.


Snargleplax

  • Rogueliker
  • ***
  • Posts: 50
  • Karma: +0/-0
  • snargleplax
    • View Profile
    • SnargleQuest dev log
Re: Procedural generation of quests and narratives
« Reply #8 on: March 08, 2012, 08:49:50 AM »
The hardest problem in designing a narrative on the fly is that many players aren't going to anticipate what is expected of them, no matter how many clues are given. The stereotypical MMORPG quests have become the norm precisely because they are almost impossible to fail outright: this has to do with their simplicity and avoidance of any real decision-making. If you want to design a good narrative, you'll need to design a whole slew of open-ended quests. This, all by itself, has some challenging considerations:

  • To what extent do we allow the player to fail a given quest? The only "true failure" could be death, or it can relate to time, context, or a simple lack of power to prevent something from happening.
  • Should a quest's failability depend on its gravity relative to the overarching goal? Making "important" quests harder to fail can be an abrupt change in the narrative: however, not pushing a player toward the goal may make them forever clueless as to its existance or solvability.
  • How many different kinds of failure should be allowed? There are many shades of gray between "completing a quest" and "failing to complete anything related to the quest". Adding these shades, however, can complicate the narrative by a lot, and each case must be considered (especially as to whether or not it will ultimately aid or deter the player from the goal).

Yes, probably it's reasonable to assume we must allow for different kinds of failure, with different consequences.  If the player fails the main quest in an obviously permanent way, that should arguably be a game-ender just as sure as permadeath.  The thing to avoid would be letting the player fail, but go on a long time without realizing the game is in an unwinnable state.  So if we're going to let the player keep playing, there must be some way forward (where there's life, there's hope!).  Failures could be associated with an assortment of possible recovery strategies or alternate paths; since we can invent these dynamically, it should always remain possible to solve the dependency tree in some newly-invented way.  Failure can thus become a source of new subquests, reducing this in large part to a matter of exposition.

Actually, there's another important kind of failure to consider, which you mentioned -- failure of the narrative to involve the player.  If the player misses the wanted poster and the trail of blood and wanders off in a random direction instead, we need to decide if we're going to let that be, or if the story is going to go find the player.  And why not just tell a different story at that point?  Some subgraph of the dependency tree remains theoretical until it's been exposed to the player.  Clear out the problematic sections and re-solve, and you've got a new adaptation of the story that's consistent with player actions.  This kind of "ad-libbing" could be performed liberally to provide new opportunities to draw the player into the narrative.

Quote
I think one of the more interesting ways to apply a character narration without necessarily involving literal "go do this" is to have the game subtly change itself depending on the character's interactions with it. Wipe out a bunch of orcs? They'll probably put a bounty on your head. Save a princess from some bandits? I wouldn't be surprised if royal messengers start searching for you and asking for help.

Yes, I've had something a bit like this in mind for the constraint system that would be used to fill actors, props, and settings into various roles defined by "plot chunk" schemas.  We might generate a potential scenario involving the role of a Trusted Ally, or an Old Rival, or what have you.  Such characters could be introduced farther up in the dependency tree (earlier in the story) so as to be in place, and the characters themselves would have to make sense according to whatever's in the game ontology, faction rep being an excellent example.  I'm imagining a bank of existing individuals alongside generators for instantiating new ones of different types as needed; what I'd like to accomplish is interesting crossovers, where characters reappear across plotlines but do so in meaningful ways.

Snargleplax

  • Rogueliker
  • ***
  • Posts: 50
  • Karma: +0/-0
  • snargleplax
    • View Profile
    • SnargleQuest dev log
Re: Procedural generation of quests and narratives
« Reply #9 on: March 08, 2012, 09:54:44 AM »
 Besides being a fan of game design and the roguelike genre I like to write quite a bit. But for some reason I hate story driven games. It's part of what brings me to roguelikes in the first place. I get to create my own narrative.

Really, that's what I'm shooting for.  I don't expect this approach to produce a story that stands well on its own; it's got to be something the player acts out and lives through.  Doing it yourself adds so much compared to just reading something, and the participatory audience is much more forgiving of cliche and simplicity; the complexity is filled in by experience, inviting the player-creative narrative you mention.

Quote
However, science can solve everything. There have been some very good academic studies about story telling.

Indeed.  I found some very interesting stuff last night on the morphology of folklore.  You may yourself be interested to check out Propp's Morphology of the Folk Tale, which presents a more detailed outline he finds common to many archetypal tales.  I found some tantalizing references to at least some initial forays into procedural generation based on this, but not much substantial.  However, some of the referenced papers seem intriguing and I plan to take a look through them.