Procedural Stories

Recommended Videos

QuadFish

God Damn Sorcerer
Dec 25, 2010
302
0
0
Callate said:
I'm picturing this in my head and it sounds beautiful. It's not that farfetched really. It's almost like applying NPC AI principles to the game's plot. That kind of logical decision making is what makes AIs work, but at the moment in most games it's a fairly linear sequence where an NPC works out what's visible to it (and possibly it's allies), whether to start attacking anything it sees and where to move to after that. It's a system with only a few states, sometimes as few as whether an NPC is wandering or attacking something. You'd basically need to create an AI that can work out logical plans, which involves a lot more forward thinking than what current AIs do. Otherwise you end up with the same situation as games with "multiple endings", i.e. effectively the same storyline and game with minor changes that don't change the experience very much.

Still, if it worked... wow.
 

Mason Callaway

New member
Mar 15, 2012
6
0
0
I think a form of procedural stories already exists in gaming. It just doesn't exist in digital gaming. If what we are looking for is the ability to create content "on the fly" then we must look no further than the tabletop. In tabletop RPGs the GM/DM serves as the "algorithm" that generates the content. A good GM/DM does create content on the fly in response to his/her player's actions. The first time I played a tabletop RPG (7th Sea if you're curious) our party cut out the final boss entirely because one of our members acted in a way the GM didn't anticipate. In video game terms this would have been a bug, possibly a game crashing one. Our GM went with it and used the extra time to create a new follow-up scene to our sewer adventures wrapping up the story.

I think tabletops excel at this type of procedural gameplay because humans are hard-wired to create scenarios from existing information. It will be interesting to see if computers are ever able to do so effectively, but until then I think we'll have to be content with whatever tabletop gaming we can find.

And this niche, procedural gameplay, which tabletops can offer may be a good reason to start bringing them into the same wider cultural influence digital gaming is starting to enjoy.
 

RhombusHatesYou

Surreal Estate Agent
Mar 21, 2010
7,594
1,916
118
Between There and There.
Country
The Wide, Brown One.
Shamus Young said:
I think rather than procedural stories, we ought to be looking for ways to make emergent ones
The 'problem' with emergent stories is that they rely on the player to construct a coherent narrative out of a bunch of actions/situations/events. That's not an issue for the sort of player who takes all the tools a game can give them and just run with it but if you've ever been on the forums for games that inhabit the more extreme end of the sandbox spectrum and read the number of 'BUT WHAT DO I DO?' threads you know that there are quite a few players that need preset goals or some canned narrative to give them that initial kick in the arse to get them invested into gameplay.

I think the biggest hurdle for emergent stories as far as the average gamer goes is that outside of narrative heavy games NPCs generally lack personality enough for people to emotionally invest in. When your Allies, Rivals and Enemies are all as 1 dimensional as Quest Giver #14 and Random Peasant #431, they're not characters they're cardboard cutouts. Of course trying to build characters that are believably adaptive to the entire AI ecology as well as player agency is going to be challenge enough let alone actually injecting personality into them. Of course, even if a developer was hell bent on having that sort of thing in a game there's the question of budget and resources to be able to do it.
 

bananafishtoday

New member
Nov 30, 2012
312
0
0
Emergent stories are something the core Paradox games (Europa Universalis, Victoria, Crusader Kings) do amazingly well. So well in fact that there's a whole community based around retelling game events as linear stories: AARs. (For instance, I've been working on one off-and-on about a rival faction beating the Ming in the civil war after the Yuan Dynasty collapsed. The game gives enough data and enough room to flesh out all the AIs as characters with personalities and motivations, and whenever anything crazy happens, I can comb through the data to come up with realistic historical forces explaining them.)

Their games are essentially sandboxes once you get good enough that the AIs aren't difficult (though they're never completely toothless.) AIs aren't brilliant, but they often have driving motivations and frequently act in clever ways to further specific goals. Random events can throw wrenches in your careful plans, and the game provide so much info that many of the stories are just crazy things you notice. It all comes together to essentially be a story generation machine.

Like... in the China game, two of my rivals' kings had "random" deaths in quick succession... and were replaced by members of my main rival's dynasty. The sudden family link made the AIs completely change the way they behaved in war and diplomacy, turning a six-country free-for-all into two large rival blocs. Or... Japan was stuck in a centuries-long civil war, and I used the turmoil to invade and take Kyushu/Shikoku. One of the minor powers made peace with me while I was still fighting and immediately turned on their neighbors, eventually building a strong enough base of power to end the civil war and unify all of Honshu.

And there's tons of small-scale drama going on that's easy to miss, but when you notice it, it's great. Like in a CK2 game where I was playing as a Muslim nation, there was a common-born woman in one of my vassal's courts. Her stats were all incredibly high, but her being a commoner made her somewhat undesirable for marriage (marrying often lets you ally the groom/bride's parents if they're dukes/sheikhs/whatever.) She ended up being married off to a landless noble whose brother was an emir. Then she murdered her husband. Being in the emir's court made the AI see her as a great match b/c of her stats... so her brother-in-law made her his second wife. Then she had a son. Then she murdered the other wife's son. Then she murdered the other wife. But this time she got caught and was executed.

Stories like that are what make me keep going back for more.

Edit:
RhombusHatesYou said:
The 'problem' with emergent stories is that they rely on the player to construct a coherent narrative out of a bunch of actions/situations/events. That's not an issue for the sort of player who takes all the tools a game can give them and just run with it but if you've ever been on the forums for games that inhabit the more extreme end of the sandbox spectrum and read the number of 'BUT WHAT DO I DO?' threads you know that there are quite a few players that need preset goals or some canned narrative to give them that initial kick in the arse to get them invested into gameplay.
Grand strategy games do a great job of setting out clear goals for new players while being sandboxes for the more experienced. For new players, it can be challenging enough to just not die. Then everything grows out of that: "I can pursue x, y, or z strategy to be stronger or be less of a target so I don't get my ass kicked." As they improve, they have more freedom to set bigger, over-arching goals for themselves. And once they're really good, the game becomes so easy that they can either self-impose challenges to keep things tough, or they can do whatever they please to construct stories.

Of course, the genre isn't for everyone. Plus they can be really sink-or-swim (or rather "study-the-wiki-or-sink"), and the complicated UIs and the enormous amounts of data can make them seem really arcane or impenetrable. But yeah. They provide literally zero narrative guidance ("here's like 300 countries, pick one and do whatever") and instead use their mechanics to force goal-oriented play.
 

OniaPL

New member
Nov 9, 2010
1,057
0
0
Irridium said:
This is the kind of thing Civilization and Mount and Blade does really well. They drop you in, there's a bunch of ways to win, and you choose what you want to do and see what happens.

Dwarf Fortress also lends itself spectacularly to this sort of thing. When you get past the admittedly high barrier of entry, at least. But if you do, there's plenty of "fun" to be hand.
Too bad that the dreadful part of gathering relation points with other lords when you plan to start a rebel faction / make your own nation is so tedious. You need several lords to join you, and that means huge amounts of shitty quests for the lords.
 

garykac

New member
Feb 2, 2013
1
0
0
Joccaren said:
A lot of the problem is that NPCs don't really have conversations. They have some pre-set lines for quests, but that's most of it. You can't get any good dialogue, which leaves you leaving the details of the story vague, or having a poorly written one. You can't have any good idle conversations with NPCs.
+1 to this. I don't think you can get really good procedural stories unless you can generate procedural dialog.

I wrote a brief paper on this a few years ago while I was at MSR: "Using Natural Language to
Manage NPC Dialog" http://research.microsoft.com/apps/pubs/default.aspx?id=69325

The general idea is that you create a backstory for each NPC using natural language; parse it into abstract "logical forms" (LFs) to create a knowledgebase (KB) for each character. At runtime, these KBs are analyzed to find relevant chunks, which are then ranked and generated back into (grammatically correct) English utterances. Sadly, this process is non-trivial - rather than a simple translation of static text, it requires a parser and a generation engine for each language you want to support.

Story was handled in this system by tagging some nodes in the KB with tokens that represented significant items, ideas or knowledge. The dependency graph of these tokens was used to help drive the story.

I only had a chance to create a small demo before I left MSR, so I only handled basic Question/Answering interactions. But it certainly could have been expanded to include more complex dialog interactions.
 

deathbeforedecaf

New member
Oct 26, 2008
31
0
0
Realistic random storytelling with NPCs will happen when you get NPCs acting in a realistic way. An NPC who has a life independent of the player,who doesn't just hang around the one spot(like a blacksmith who never eats, goes to the toilet,showers,rests,meets up with friends,travels or even sells any of his goods to anybody else but the player).NPCs need to be true individuals with their own problems, goals, moral systems, skills,etc and they need to interact with other NPC's just as much, if not more than they interact with the player.Its not so much making procedural stories as letting complex character interactions create those stories.

Good article Shamus, really like your procedural city.
 

Squilookle

New member
Nov 6, 2008
3,581
0
0
I think rather than procedural stories, we ought to be looking for ways to make emergent ones. Instead of a static story about a hero who does something heroic, it might be better to simply generate some starting parameters and drop the player into a sandbox style world. When the player enters town they discover that Anna has a crush on Bob. Carl is insanely jealous of Anna and would kill her if he saw her with another man. Dave is business partners with Anna and needs her help to succeed. Ellen hates Dave but likes Anna. Fred is looking for someone to steal Carl's prized sword. And so on. The player is then free to act or not act as they see fit. Their version of the town will be different from someone else's, and the decisions they make will form a unique story.
Once again, Mount and Blade Warband laughs in the face of the poor plebs that think such things have not been tried yet. Mount and Blade has pretty much exactly this system already up and running beautifully.

I personally think emergent stories are fascinating, and could be the future of game writing, taking advantage of the medium's unique ability to change and interact with itself.

I even think a whole new medium of entertainment could be possible with this system. We just need to try it out.
 

DjinnFor

New member
Nov 20, 2009
281
0
0
Shamus Young said:
Procedural Stories

Storytelling by algorithm might work, but you might not really want it to.

Read Full Article
Creating procedurally generated stories take two prime ingredients:

1. A Procedurally Generated World:
-I teased the basic concept in another thread [http://www.escapistmagazine.com/forums/read/6.396138-The-Theme-Park-MMO-Is-Dead-Enter-the-Sandbox#16118099]
-The key goal is to create a world where some kind of conflict can occur procedurally and where the player would be free to attempt to resolve this conflict; you indicated as much in your article
-The primary way you'd do this is to make each individual NPC an actual character in their own right. Simulate reality as much as possible then add a little extra drama or some higher stakes.
-Other important things include a diversity of choice so that the player can approach solving the conflict in pretty much any way they can think of.

2. A Generic Monomyth template:
-Create a Call to Adventure procedurally using an interesting plot hook that involves requiring the players active participation to solve some problem.
-The "problem" can be as diverse and complex as you want it. Traditional "slay monsters because they're bad", or "fetch me xyz" are of course the low-hanging fruit. There could be political squabbles, labor shortages, an evil villain, etc. etc. You can even go for internal conflict if you so choose.
-Consider each of the Monomyth's stages [http://en.wikipedia.org/wiki/Monomyth] and consider designing your procedurally generated world in such a way as to incorporate many of these concepts in diverse ways.

Some other stuff to take into account:
-Generally, the bigger the implications, the longer the time scale. A bunch of different love triangles might erupt in violence dozens of times a day in large cities. Meanwhile a brainwashed or manipulated-by-evil-advisor king of the empire can only happen so often before things become a little ridiculous. The rate of the passage of time should be malleable so that things seem to develop over an adequate amount of time while also keeping the player entertained.
-One way to resolve a lot of potential problems is to go for a roguelike game with an overarching story (optionally also procedurally-generated) that counts as a game completion if resolved and where any failure along the way is of course to restart the roguelike and reset your progress and character.
-If you really want to nail things down you'll probably have to build game versions of psychological profiles for individual NPCs that affect their behavior as well as metarules for what kind of motivations they tend to have and how they accomplish those goals
-You'll probably need to procedurally generate dialogue, and you'll have to figure out some kind of system that works for your game because it's the interface that connects all the simulation and data behind the NPCs with the player.
 

Vault101

I'm in your mind fuzz
Sep 26, 2010
18,855
15
43
call me simple but I think we need to focus on better writing and implemtation of story/narrative in games rather than having endless choices
j-e-f-f-e-r-s said:
As for procedural stories: no. Just no.

There's a reason literary scholars call it the craft of storytelling.
I have to agree.....thats the reason the elder scroll games just don't do anything for me its not "my" job to come up with the story
 

Yossarian1507

New member
Jan 20, 2010
680
0
0
Hey, Shamus is back, awesome!

Personally, I think the best kind of story in games with random content is... Having little to no story at all. Why? Because then you are making up the best story in your mind.

I remember playing old Championship Manager games (2001/2002 is still the best one period, I'm playing it to this day) and imagining my half time speeches during important games, depending on my position in the league, form of my players etc.

Other example more close to the people who are not playing sport games? X-Com Enemy Unknown. Don't tell me you didn't make the personalities of your soldiers based on stuff that happened during missions, or some kind of revenge plot after one of your best veterans died in combat. I remember saluting to the end credits, because the "chosen" soldier was my favorite guy, and why he was my favorite? Because after a certain mission went fubar, he was one of the two survivors, and he was a rookie at the time, going to the battle with hardened vets (not to mention he became the best pal of the other survivor etc). He then became an assault guy and averaged something like 5 kills per mission. He was the bravest soldier I've ever seen in a work of fiction, and it was all in my head. Amazing.

FTL? Same thing. Hell, I had my own stories for my recruit assassins in AC: Brotherhood.

Trying to have some kind of complicated story in the random generator seems like a recipe for a disaster because with some many random variables it can become a mess really fast, but if you'll keep it simple then you'll have one of the greatest story ever created, and it was created by you. And the best part? If you'll play the game again, you'll have another, different story, but just as awesome.
 

Hagi

New member
Apr 10, 2011
2,739
0
0
I think a major problem with these emergent stories is their heavy reliance on templates. Once you're playing for a while you start recognizing them and characters and events just turn into copies of each other with minor changes instead of actual unique instances.

At those points playing them tends to become less about experiencing the emergent story and more about gaming the system, for me at least.

Once I know that if I put template A into situation B he will perform action C which benefits me greatly I'm just going to seek out characters with template A, use the same actions I know will put them into situation B so that they'll perform action C. They've turned into mindless automatons instead of rational characters.
 

triggrhappy94

New member
Apr 24, 2010
3,373
0
0
Shamus is back!

Interesting article--kind of reminds me of the randomly-generated quests in Skyrim.
Watching a random-generator try to turn out a more complex story would be fun, probably disasterous, but a fun disaster. It'd be like watching the glitches in Oblivion freak out.

I also want to say I'm a fan of the Spoiler Warning Show. I'm planning on getting caught up after I finish watching Desert Bus and finish The Walking Dead game.
 

Voltano

New member
Dec 11, 2008
374
0
0
j-e-f-f-e-r-s said:
Yay, Shamus is back. Nice to see another Experienced Points up on the Escapist.

As for procedural stories: no. Just no.

There's a reason literary scholars call it the craft of storytelling.

Good stories, really good stories, are about more than a procession of events. Genuinely great stories are about the things happening behind the events. Great stories are about subtext, thematic content, symbolism... in short, meaning beyond the simple events that are portrayed. And quite simply, that is not something that you can reduce down to an algorithm for a computer to follow. A story simply enough for a computer to come up with from scratch is a story any hack writer could have come up with in two minutes.
If a good story is defined by the subtext - meaning it takes some critical analysis of the story to understand some kind of hidden message or analogy coming from the story - then that implies any story could be "good" if interpreted a different way from a person. In layman's terms, "What is one man's junk is another man's treasure."

Emergent storytelling isn't just making the player define the story based upon their actions. It could work like that, but the main idea of emergent storytelling is a series of events that can work in the form of a story crafted from the core mechanics of the game.

Most stories in video games come from a Narrative engine, which has a pre-scripted set of events crafted by some person (hack writer from Capcom or Angelic writer from BioWare). From here the right voice clips, events, and cutscenes (technically called 'narrative events') are displayed to the player while pausing the game loop. Some games might give the illusion of input in these stories to create agency, but this just leaves to the cheap morale choice systems or pre-scripted, "Choose Your Own Adventure" structures found in a BioWare game. You want to stop the possessed kid from summoning undead by confronting the demon possessing the kid in "Dragon Age: Origins"? You could sacrifice his mother, or get the mages to send one of your party members in. Turn to page 45 for the sacrifice, or turn to page 6785 for the mages' help.

Now emergent storytelling isn't always good on the surface. Yes it is a bunch of events strung together to form some narrative created by algorithms, but who's to say there is no meaning to them? It could lead to some immersion-breaking events like watching NPCs talking about the deals at their store in "Oblivion". But then there can be exciting moments like how a mage in a roguelike game was able to take down an Ancient Rainbow Dragon with a vorpal dagger. Hell, emergent storytelling can even be found in narrative-heavy games from BioWare's library, such as what events I can tell you that lead my main character to defeat Malak in KOTOR at the final round.

If "good" stories come from subtext, thematic content, symbolism, or meaning beyond the simple events that are portrayed - then who adds that? The writer? The writer shouldn't be so blunt with them, otherwise there is no critical analysis from the player required to find them. Plus that is just the writer "telling" the reader/player there is some meaning to the events, instead of just "showing" it.

I believe all this is interpreted from the reader/player encountering this story which finds it engaging - and that is what makes a good story. If the reader/player is not engaged in the story, then the writer has already failed in making a 'good' story. Everyone has a favorite author, but there might be some stories from that author which doesn't work so well with that person, compared to some other works. Most people on the Escapist might agree that "Pokemon" and "Twilight" series all have terrible stories, yet there are still children who find them engaging and women of various ages who enjoy their teen romance story. Are they engaged in the wrong story for them?

Emergent storytelling is no different. It might not be so engaging for some people because they can see where template A is leading to template C and have already accomplished this task for the fourth time in their playthrough. Yet for others, its an exciting adventure they can tell at dinner or with friends while they create a new character in "Skyrim" or talk about how they defeated the final boss in "FTL".
 

Phuctifyno

New member
Jul 6, 2010
417
0
0
Sgt. Sykes said:
I don't think sandbox is the thing we're looking for. IMHO you either want sandbox, OR story. I mean sure there are games such as the sandbox GTA IV with a story of its own, but the story element is basically a game of its own, while the sandbox is either just a distraction, or basically a another game of its own.
The GTA series might have been closer to what you're talking about if they'd stuck with the template from GTA II and expanded on that concept. I'm referring to the three gangs that had a "paper, rock, scissors" relationship, which the player was allowed to choose alliances for by choosing who to do jobs for and gaining respect in return (gaining respect in one gang would cause you to lose respect in the gang to the left while remaining neutral to the gang to the right). The only linear sense of progress was in how much money you made. Being a PS1 era game, it was handled pretty mechanically, and your choices didn't really have any effect on gameplay. If they could revive that idea and thouroughly dramatize it, I think they'd be on the right track.

In other words, leaving it as a sandbox but making every task within the box have significant dramatic weight, so by experimenting, exploring, and trying to break the mould like you would in a regular sandbox, you are always advancing story. In the game's development, there would have to be major coordination between the programmers and the writers, since the story-telling would be happening right in the code. In fact, it wouldn't be a true sandbox, but a story-tree that's complex enough to appear as one. I can see how this would be difficult to build.

So for example: What if you were working your way up in a gang and decided spontaneously to shoot the mob boss in the head? Most games wouldn't let you (think essential npcs's in Elder Scrolls) because it would break whatever story is planned out. But in this imaginary game, you can kill anybody at any time, and the environment has to respond. So if your respect level with that gang is low, that gang turns on you and you will always be in peril when near them (though there are two other gangs left that you might find sanctuary in), or if your respect level is high, another high ranking gang member might appreciate the position you just opened up and takes over (and rewards you some perks for your help), or if your respect level is maxed out, maybe you can take the throne yourself(and become a prime target for the two other gangs). etc etc etc.

Also, cinematicaly roll credits on every game over.
 

Vault101

I'm in your mind fuzz
Sep 26, 2010
18,855
15
43
Yossarian1507 said:
Hey, Shamus is back, awesome!

Personally, I think the best kind of story in games with random content is... Having little to no story at all. Why? Because then you are making up the best story in your mind.
.
making it up in your head is good and all but if the game doesnt respresent your story then whats the point? you may as well just play with action figures
 

ThunderCavalier

New member
Nov 21, 2009
1,475
0
0
Honestly, while the idea is nice, it also seems to be going in the wrong direction in terms of trying to provide a complex storytelling experience. While the motif of having a different story sounds interesting, in reality it's going to boil down to the same "Do X thing for Y person" or "X person has Y relationship with persons Z, Q, and 7." Gamers, even the most dense and oblivious, eventually notice these kind of patterns and grow sick of them, and if a game gets some particular exposure, then the patterns practically become spelled out for everyone to see. It didn't take long for everyone to realize that there were, like, two or three quests in World of Warcraft with different skins.

It honestly seems outlandish to think that a computer could tell a compelling and interesting story without the use of sci-fi AI and whatnot. Templates I can see, sure, but in reality, we're just making a slightly more complex variation of "X person needs you to kill Y amount of Z because he wanted you to."
 

Jachwe

New member
Jul 29, 2010
72
0
0
j-e-f-f-e-r-s said:
Yay, Shamus is back. Nice to see another Experienced Points up on the Escapist.

As for procedural stories: no. Just no.

There's a reason literary scholars call it the craft of storytelling.

Good stories, really good stories, are about more than a procession of events. Genuinely great stories are about the things happening behind the events. Great stories are about subtext, thematic content, symbolism... in short, meaning beyond the simple events that are portrayed. And quite simply, that is not something that you can reduce down to an algorithm for a computer to follow. A story simply enough for a computer to come up with from scratch is a story any hack writer could have come up with in two minutes.
Voltano said:
Emergent storytelling isn't just making the player define the story based upon their actions. It could work like that, but the main idea of emergent storytelling is a series of events that can work in the form of a story crafted from the core mechanics of the game.
Except we are not talking about emergent but procedural storytelling and as jeffers notes there is the argument of all stories are formulaic but wants to rebuttle it by pointing out exceptional works like Pulp Fiction that come to mind when the tradiotional formula of storytelling wasn't applied.
Voltano said:
If "good" stories come from subtext, thematic content, symbolism, or meaning beyond the simple events that are portrayed - then who adds that? The writer? The writer shouldn't be so blunt with them, otherwise there is no critical analysis from the player required to find them. Plus that is just the writer "telling" the reader/player there is some meaning to the events, instead of just "showing" it.

I believe all this is interpreted from the reader/player encountering this story which finds it engaging - and that is what makes a good story. If the reader/player is not engaged in the story, then the writer has already failed in making a 'good' story. Everyone has a favorite author, but there might be some stories from that author which doesn't work so well with that person, compared to some other works.
So first of jeffers is right that not all stories are formulaic. Voltano makes the valid point that the story is evaluated in the eyes of the reader/gamer/etc. but does not spell outwhat is way of thinking should lead one to: The death of the author. The Death of the Author written by Roland Barthes 1967 presents a theory that the intent of the author is not important when analysing and interpreting a story thus the author of a text is nothing but the projection of the reader. This is structuralism. Now from that point of view one story can be told many different ways. The hero's journey is one of the most famous. It always gets labled as formulaic but there is a reason why that formula is working so well even if the writing of the story itself is not that good. It is because of the structure of the story that correlates with latent needs and wishes of the human spirit. If a formulaic story is told well everyone likes the story i.e. Star Wars. Even if the story is not told well it can happen that there is the latent power that just makes the story loved by millions of people i.e. Bram Stoker's Dracula.
So yes procedural storytelling must be a formulaic one or otherwise a computer cannot create it but the story being formulaic does not mean there is no merit to the story told. And here comes the crazy idea for these kind of stories in a game. Just tell only one story in different clothing. Lets say take a setting of medieval fantasy like Dragon Age and put it in a science fiction setting like Mass Effect (are you on to me?) switch out some names like Morrigan and Liara (a mage and biotic are just wizards and they both have mother issues), the protagonist is the same tabula rasa chosen one that is either jesus, a prick or both but nontheless the hero who saves the day , maybe switch the order of events and defeat the evil either archdemon or reaper and people will love it.
 

Phuctifyno

New member
Jul 6, 2010
417
0
0
Sgt. Sykes said:
Phuctifyno said:
you can kill anybody at any time, and the environment has to respond. So if your respect level with that gang is low, that gang turns on you and you will always be in peril when near them (though there are two other gangs left that you might find sanctuary in), or if your respect level is high, another high ranking gang member might appreciate the position you just opened up and takes over (and rewards you some perks for your help), or if your respect level is maxed out, maybe you can take the throne yourself(and become a prime target for the two other gangs). etc etc etc.
You summed up nicely what I had in mind just couldn't put into words really.

I still think the pinnacle of procedural "storytelling" (maybe because there aren't many games like that) is the Enemy Engaged helicopter sim series. Both games technically only had 3 massive areas (such as almost the whole Cuba). Upon starting a new campaign, the game would randomly generate the whole battlefield/scenario (and it really took quite a few minutes on the computers of '99). After doing that, it would automatically generate tactical and strategic missions, on both sides of course.

So after starting the campaign, both sides usually only had recon missions. When some of the recon teams found an enemy convoy, the game would generate, say, tank busting missions. When any side was running out of units or an airfield was destroyed, transport or support missions could be generated. And the player always had the option to chose any of the available missions (if a featured helicopter was available) or generate their own.

It was utterly awesome. A helicopter sim mated with an RTS, everything generated automatically and logically.

10 years later I still have memories of playing this. At one point I played the hardest campaign on hardest difficulty. After several months of playing one campaign, the enemy raided my bases and blew up every one of my helicopters. So the game generated some transport missions - fly packs of new choppers from one side of Cube to the other. An 8-hour flight. At first I left the AI to fly those, but they were never able to reach the target, always getting shot down en route. So I took one such mission (using autopilot and time-speedup most of the time). Found it to be non-survivable and finally gave up on the campaign :-/

Another spectacular campaign loss was when I escaped the bombardment of my base, ignoring the designated defense missions and trying to reach a distant farpoint in an attempt to create a new base there. Not only was mine the only remaining helicopter, I got hit badly mid-flight and crashed right at the farpoint trying to land.

Of course, these being real military games (*smirking at COD*) there didn't have to be much storytelling to go by. All that was needed were the strategic map and automatically-generated radio chatter to tell the story. It would be infinitely harder to create something like this in an RPG especially with a try story. But man, I'd like such a game.
That sounds like a great game, though maybe a tough sell to "the kids these days, amirite?". But yeah, that's exactly what I'm talking about - to take something like that and maybe spin it more personal, or individual at least. Things would have to stay within reason (there's no point in having an option for the character to go to college and become a doctor and work in a hospital if the game is about cops and crime, or learn how to play golf if the game is mainly a flight sim), but if a game is ostensibly an open-world sandbox, you should be able to really take the reigns of the story, not just follow it around the map like a scavenger hunt.

Notice how a lot of the significance and drama in your recounting comes from your own investment/imagination? That's the thing that I think would scare most developers away from doing something like this, because "the kids these days, amirite?" don't have imaginations. Not really true, but enough to scare them. It's easy enough for a program to move plot variables around into infinty, but to make them feel like they have dramatic weight (to an audience not willing/able to do that themselves) is trickier. A possible answer would be cinematic cut-scenes generated on the spot, with the program having been taught how to use different music pieces, camera angles, voice tones, editing, etc. depending on context. We're already starting to see pre-rendered cut-scenes being replaced with in-game because the hardware's catching up, so that's something I think would be neat.

I have faith that we'll see something like it in the near future. While not completely successful in execution (of this particular topic), the recent Bioware and Bethesda games have been a step in the right direction. With a few major tweaks, Skyrim could have done this pretty well.