I love these sorts of discussions. :)

I would repsond that a video game doesn't necessarily have to allow the player to direct the plot, provided that you provide the illusion of freedom.  As such, it may be interesting to procedurally generate a finite world with distinct objectives and have the player go through a plot that's determined once when they start the game.

My question is what kind of form this story would take.  I'm assuming the story generation algorithm wouldn't be able to pass a turing test so, as you said, dialogue is out.  The idea of "beats" as presented in those links would work fairly well, although I suspect you'd have to follow a somewhat different story structure.  In the case of a roguelike, you might want to take a look at various fantasy and game plot tropes. 

Probably the most appropriate plot for a roguelike is to defeat some huge bad guy, so you could use that as a starting point and then randomly pick a motivation for the main character doing so.  Maybe they're saving the world, maybe they're rescuing someone, etc.  Then figure out what steps are going to be required to defeat this person (or monster).  Maybe you need to travel to various dungeons and collect a set of artifacts.  Perhaps you need to defeat this guy's underlings first.  Maybe you need to enlist the aid of a person or group of people, and in order to do that you have to help them or (if they're from a warrior culture) defeat them in battle.

I guess what I'm getting at is that in this sort of story, the "beats" should vary as well.  That is, you'll probably want to randomly generate the story outline before generating the details about the parts that make it up.  If you follow the exact same set of "beats" every time, you'll probably end up with stories that feel too similar structurally.  (This isn't so much of an issue if you're a human writer, but it's a lot easier to pick up on these sorts of patterns when a computer is doing the writing.)

At the moment, I don't know of any game that generates random plots well, although I can think of a few that sort of attempt it.

• The Sims simulates personal desires, which might result in something resembling a plot, although it's hampered by the fact that any sort of character development (romance, getting a job, etc) seems to require human initiaitve.
• Dwarf Fortress probably does some sort of simulation of how the dwarves feel, but I don't know if cohesive stories form on thier own.
• Skyrim can generate random quests for the player by sending them to various places to pick up various items or defeat bandits or whatever, but the main story is of course scripted, and the random quests can feel kind of fill-in-the-blank if you do enough of them.

Dwarf Fortress has another layer of story generator, too - it comes up with an entire history of the world when you start your game, including nations/cities, conflicts and alliances, and even individual heroes and politicians.  I think it even gets into individual battles, though it's been a while since I played; I know it's a crazy amount of detail that it generates for your expedition's backstory, though.

@pennomi:

When I was thinking about varying the beats in a story, I guess I'm thinking of them more about how a computer would generate steps in an adventure, as opposed to plot points in a story.

Let's pretend to we're randomly generating a plot.

So we start with a big bad, and we decide that he's some sort of evil god who can only be killed with the legendary Mace of Windu.  Of course, a thousand years ago, someone with far too much time on their hands split the Mace of Windu up into eleven parts and hid them in dungeons all over the world.  So in this case, the goal of the adventure would be to collect those seven parts.  Maybe some are in dungeons, maybe some belong to people who want you to go on quests for them, maybe some have fallen into the hands of villains who need to be defeated.

But that's just one story structure.  If the big bad is an army or a curse on the hero or something, that structure won't necessarily work.  To defeat the army of orcs, you might need to go around and gather allies.  To end the curse, maybe you have to explore and try to find out who put it on you and why before you can remove it.  That's what I mean about varying the beats -- in the terms I'm thinking of, a "beat" would be a specific game event; going to a dungeon, doing a story quest, or whatever, because that's how it would make most sense for randomly generating a game plot.  Beats don't necessarily map to plot points the way writers might think of them.

Thoughts?

I'd definitely aree with that approach, although if we're calling what I'm talking about subquests to differentiate them from beats, I'm not clear on how beats would apply to the story generation algorithm.

• Deliver {artifact} to {location}
• Escort {npc}
• Exterminate monsters at {location}
• Defeat {npc} in a sparring match
• Steal {artifact}
• Escape from {location}

That's all I can come up with at the moment.  Some of the above are just variations of yours, I think.

Also, a caveat about escort quests:  Everyone hates them, particularly in games where they move at a fixed speed and don't stay with the party, then get themselves killed.

maybe I can add some?

• beat{rival} in {competition}(basically, pokemon)
• bring {villian}to justice
• capture {villian}
• redeem {self}
• explore {area}
• survive{event}

I think that could work very well, actually.  It would certainly feel a lot more coherent than just using them completely at random. :)

Also, one other one I thought of:

• Defend {location}

What about taking existing quests/scenes from books, movies, series, other games, and abstract them to a level, where you can replace the actual content (that basically boils down to Actions, Persons, Locations and Items) with randomly picked content from a properly tailored list?

I believe (needs proof), that most players wont notice the reoccurence of such a plot skeleton immediately, unless they dont actively analyse what is going on. So, lets say, have one or two dozens of these, and you can generate 100 quests without things feeling repetitive (assuming good lists with content).

Advantage would be, that it is pretty much agnostic of different settings. If the plot is about a friend, that silently envies you, and then decides to "punish" you for some reason only he percepts, punishing you with stealing something/-one that is of high value for you and then escapes with that and wants to never see you again - this can happen in a scifi setting with a hunt from planet to planet, as well as in a fantasy world.

------

I tried something similar as mentioned so far in this thread too, it was more a plotgenerating aid for storywriting though, so I picked a semi-automatic approach here, probably pretty similar to what Pennomi calls "really rough and stupid". I found it somewhat useful, since I left it to the user to spot the "red line" in the random noise and discard the rest. What of course doesnt work for a game.

I still think the approach is good, it just has to contain more information. So far, the examples mentioned only what is interesting to the player, but they have to be extended to show (even if just internally) the full context.

Trying to expand the aforementioned example here, to see if it actually makes sense:

{artifact} stolen by {villain} from {owner} because of {wants artifact's power | want to prevent others from using artifact's power}

Now, we could evaluate the relation of the player to both persons (villain / owner), to see who he is more friend to, and create a quest based on that, what could be a) bring artifact back to owner or b) help villain, basically avoid that a) happens. Afterall, the owner could be a black magician, that terrorizes a whole region because of the mighty bookmark, and the dragon just wants that things calm down and the tributes he receives yearly come back to the level before the magician appeared. Or the magician is a friendly person who guarded the bookmark, but the dragon was too strong for him, and is the one who brings havoc.

As soon as the quest target stands, there can be some stepstones on the way to it. Some generic elements are e.g. "helpers", "helpers of the antagonist" or "competitors" (and way more). These can appear in random constellation, order and number.. and done is the quest?
Maybe there should be a climax in the end, where a good guy dies and the evil guy stands infront of the player or so... also, dramatic things usually happen roughly in the middle of a plot, where things temporarily look really bad for the player/protagonist, to make it more intense and give him a reason to "really really" want to fulfill the quest, a kind of forging.

This is a slightly different direction than what this discussion is taking, but I think it's on topic enough to be worth adding.

One of the things that stops computers from being able to write coherent plots is a lack of "common sense".  Apparently there's a project going on at MIT right now called ConceptNet, which is a large collection of concepts and how they relate to one another.  Apparently it's licensed CC-BY-SA, which means that it's free to use and fit for inclusion in FOSS projects.  The download is over half a gigabyte compressed, so it contains an incredible amount of information.

What drew my attention to this is an article I saw on slashdot about how apparently ConceptNet has roughly the IQ of a 4-year-old, which may not sound particularly impressive, but is actually a pretty big deal in terms of artificial intelligence.  (Caveat:  ConceptNet still does dramatically worse than average on reasoning skills, but better on vocabulary and comparisons.)

Anyway, the point is, that "common sense" required to write decent plots isn't completely finished just yet, but it's out there in a form that people can at least play around with.  Maybe in 5 to 10 years, the database will be at a point where it can handle some more complicated reasoning tests.

I like free-roaming gameplay, but I don't care about whether or not I change the story's outcome.  It just isn't that big of a deal unless I'm playing a game that focuses on its story above all else, like a choose-your-own-adventure book.

Anyway, it is easy to come up with your own plot points and make some flowcharts.  Then, you could simply plan some pathes.  Give the player two or three plot lines that could be driven by choices in the game. Then, you get the illusion of freedom that pennomi was talking about.  It takes a lot of work, so most developers stay clear of multiple plot points unless it's a kind of replayability bonus, like a "get through the game in less than 5 hours to see the secret ending" kind of challenge.

Just throwing in a silly idea here- how about, before the player can go and kick some bad guy ass, he/she must down x amount of pints to get over the pain of losing his/her parent/village/pet/sword/clothes.etc

Well as in all things, it depends on the games and what the point of them is. Some games do have choices, but others have straight forward stories, but they're so deep that the need for choices isn't required.

So I'm gonna share some thoughts related to the genre I'm tackling into (procedural RPGs / roguelikes).

I think that "what is a main quest" should depend on what the player considers to be relevant: if he just wants to rescue his sister or slay the evil lich threatening mankind (who might or not be the one who kidnapped her in the first place, depending on the random generator) or take his place, that's up to him.

When he thinks he's done with that game, he should take some kind of conclusive action ("close the Chaos Gate AND leave the  Drakalor Chain", like in ADOM) or raise an army of undead that take over the world or reach the nirvana.

My examples are pretty D&Dish, and I'm focusing more on what could be used to feed the generator, as you guys have already provided a nice list of story/quest/event types.

---

1 - The setting

1.1 - Procedural world with random stuff provides general quests:

1.1.a: is there a settlement near a forest?

 - chance of wolfs attacking children: "the damn wolfs are taking our children to the woods and devouring them!" <<deal with hostile person/group/beast>>

1.2 - Character background:

(Something like ADOM or Dwarf Fortress or any roguelike with procedural character background generator...)

1.2.a: if you're an orc with somehow good alignment, blame humans (or elves) for something:

1.2.a.1: slavers raided your village when you were young

1.2.a.2 (clue) a randomly placed clue tells you that a randomly chosen human settlement is to blame for that; if you don't explore enough the world you might never find this (possibility of branching into multiple indirect clues that can take the player here, if desired, would be a waste not to avenge the family lol)

1.2.a.2 (possible quests trigger): <<deal with hostile person/group/beast>> (kill, imprison, enslave)

1.2.b if you're an orc with somehow evil alignment: pursue that one single children that escaped when you raided some village.

1.2.c: if you're an elf, with somehow chaotic alignment: when you were younger you fell in love with (some gender?)(some race?). At the time, the elders forbade you from following your heart.

1.2.c.1 (clue) a randomly placed common friend is found, which spent some time with both you and your loved one ages ago. He/she tells you that he heard from your love whereabouts. He/she points you to the direction of "your love". 

1.2.c.2 (possible quests trigger): <<find a person>> (went to the astral plane; got kidnapped; got killed; that's a  doppelganger!)

---

Alignment could restrict quest options, or instead your choices could shape current alignment - which could open certain types of quest and not others (mix restrictive paths x dynamic alignment depending on the quest type / relevance). Alignments could actually be just a label that results from what you've done so far in your life (some Q&A like ADOM character generator (questions mode), but that actually shapes the personality and not the skills):

"In your childhood slaves were forced to work in your neighborhood. Many of the slaves were too young, too old or too weak to work effectively. The forcemasters mistreated them and abused them all the time. Will you..."

Nothing really new here.

The real challenge is to implement it in a way that feels "natural"/fluid, right?

It really depends on what kind of game we are talking about. As for a "radonly" generated plot welll ...

You can even make it so the "generator" starts as the Charater is created based on a couple of factors like:

Character's Age

Young - The story becomes :

Coming of age story , Overcoming Inner demons , Treasure Hunt etc.

Adult- The story becomes :

Redeption , Loss or gain of Fame , Search for Identity etc.

Elderly - The Story becomes :

Transformation , Descent in to madness , Overcoming fear of death etc.

+ ADD some acuall random ones based on well nothing : )

Natural Dissaster , Race against Time , Survival , Discovery , Rivality etc.

EXAMPLE:

  The protagonists is a young boy/girl who desires to explore some Ruins that appeared due to a recent natural desaster.He/she  becomes taped in the ruins as a result of an Rival and hes/hers survival depends on making it out of the ruins before another natural dissaster occurs.