This topic hasn't cropped up much at GameDev in the past few years, but if you go back further in the archives of the design and writing forum there are several interesting threads about it - I remember posting in most of them. (I'm talking mainly about type #3 and type #5, along with some other options that aren't mentioned. One of the other major options is the "groundhog day" or "time loop" framing device, where the player can replay the game as a new game+ and different options will be unlocked due to previous playthroughs and choices in the current playthrough. Another major option is the "schedule/location structure". In this example the game has 3 or more permanent locations, and the game is divided into days or chapters; the player can only choose one location to be at for each day/chapter. Again, the player's actions on previous days/chapters affect what is currently available in each location.

The Holy Grail of quest design, devs have been looking for this for decades, no one found it so far :)

I recommend checking "GearHead" (a roguelike) it's rumoured to got it right. It's the only semi/partial successful attempt I have heard of (I have not played it myself, unfortunatelly, since the game is not my thing :().

I think, the only reasonable (dev wise) solution is to use blocks of the story (probably what you described as 5) that are randomly merged together. Like this maybe:

* You have the quest giver "king, chancellor"

* There is the villian "dragon, wizard, orcs invasion"

* There is the problem "princess missing, item stolen, raid, princess seduced"

* Each villian has a tactic/property/action, for example dragon has "PERSON imprison in a cave in order to eat", "ITEM store in the cave (only if shiny object) and never use", "RAID burn village/town (recurring)", "SEDUCE - illegal"

And then it creates a storyline like "the king gives a quest to rescue a princess [imprisoned in a cave] and prevent the princess being [eaten by] the dragon".

It makes sense only if you use it to generate several quests in same gameplay (reuse of blocks).

Also probably a higher level of quests which is "chain of quests" would be desired. Like each quest should have "compatibility hardpoints" (I love these terms I just had to invent :D) which means what it connects to (could be also probability, not necessarily 0/1).

So, in the first quest (of the chain) you rescued the princess and also found an artifact in the cave. So now you trigger "visit hermit to learn about the artifact". And next goes "dump the artifact to a volcano". Note these quest in the chain had nothing to do with each other, yet they can create a logical flow of a storyline (restricted by compatibility system).

Probably also some sort of "past quests memory" system might be useful here to give an impression of "logic and connectivity", like in the first quest you rescue the princess from a droagon and in the 5th you learn that it was a wizard that sent this dragon because he was in love with the princess and wanted to win her heart by rescuing her so he set things up (and your rescue messed his plot) - so the future quests could be fed varables from past quests (in same chain).

I think a useful tool for this is to keep track of what is, and isn't, known about the world by the player. They're in the city of Green Vale. If they're arrested, maybe the king offers them pardon in exchange for a quest. If they hang out in seedy taverns, maybe a business man approaches them to "send a message" to one of the senators. Until it matters, the government is undefined. Once one of those quests are offered, the government is set and the other is no longer valid. The hermit outside of town could be a powerful wizard, or the heir to the throne, or a disgraced city guard, depending on where the story goes. So every variable is a set of possible outcomes, that will be reduced as the world is revealed.


If the game wants to pursue a narrative involving a lost royal heir, it checks that this locale is a kingdom, and checks to see if any known characters could be a lost heir, and if not decides if it wants to introduce a new character for this purpose.


Chekov's Gun provides a good guide for managing the story. If a mad king or an artifact or a love interest is revealed, conventional story telling dictates it play a role in the story. If the game has a preset 'desired length', it can add or resolve elements to move towards an ending where everything is wrapped up.


Controlling the introduction and resolution of elements really changes the feel of a story, so some simple variables can be used to tell different types of stories. Introducing many elements early and trying to find plot continuations that resolve multiple threads would create sweeping epics. Introducing a few elements early and progressing them deeply produces a sort of mythic feel: "young person discovers powerful artifact and sets off to stop great evil". Resolving elements quickly and then introducing new ones produces more of a serial: each session is a mostly self contained story focused around the player.


When I've GM'd, I try to have contingency plans in place: ok, if they offer to help the prince he'll send them on this quest. If they turn him in to his father, he'll think it's a plot and they'll have to escape. If they go totally off the rails, I've got this stand-alone adventure in my back pocket I can send them on. That might be a necessary piece, having the game define the branch points, and pre-search that the branches seem to progress the story.


If you annotate plot devices with thematic notes, you could even control tone through the game. A game designer could create a 'lovecraftian' module by choosing "low character count, prefer elements labeled "scary, gloomy, weird, eldritch, horror", use one "eldritch evil boss", prefer "ambiguous, horror, unhappy" endings. Then a content creator could draw a lovecraftian monster, or a gloomy tileset, or script out an ending where a monster dies, the heroes leave, and the screen pans over to a brood of monster eggs they failed to notice, label it appropriately and have it get pulled into this story but not a heroic epic.

"Narrative Legos" .... Have you seen what Legos(tm) have turned into the last coupla decades? Not quite the universal building blocks they started as, and now very specialized with huge numbers of unique parts to build up cohesive/detailed exactly built Objects. Game plotline building blocks unfortunately are not as simple as the way 'old' Legos(tm) fit together - too many factors are required to make such produce a cohesive story. Its still too much a pattern of template 'super-blocks' with a hierachy of substitutable sub-blocks being knitted together.

Anyway, Ive considered this kind of mechanism for mission/quest/story development in large genre sandbox MMORPG -- with a (hopefully) future primary feature of Player Creation (thus needing the 'building blocks' and good tools to easily manipulate them by all levels of user abilities).

Mentioned was least cost/effort of production several times ... minimal new 'hard' asset creation. For that (in your situation) I would make use of changing NPC motives (opponents vs helpers), with different actions/interactions towards NPCs/Player because of those motives, reordering/pathing Player through available terrain scenes (different doors/keys/scene links) and differences of 'fetch' objects to achive different sub-goals. Audio Dialog (needed to explain/advance 'plot') unfortunately is one of the costly assets (if you can maximize substitution of textual assets then it is alot cheaper).

If there are already large numbers of assets (like from a preexisting solo game) then addons of mix-n-match shortstories combinatorically reusing subsets of those assets for a multitude of shorter story plots might be done (the plotlines still have to be cohesively composed) and have only a few 'special' NEW scenes/assets to make each story unique.

Combat is usually one of the more general mechanisms these games have and thus might (easily) allow severely different variations of scenes by changing the mix of opponent types, their numbers, their placement, the enemy's weapons+tactics, and what props/tools the Player can make use of. As combat often is the most common interaction type of many games, this may fulfill a majority of the replay variability you want (apart from a plotline that leads/drives you between combats scenes). Possibly Terrain blockage props/obstacles (variously) added to existing scenes might be used to shift the tactics of a particular playthrough (as cover, or forcing player movement paths, etc..) -- depends on how 'baked' levels must be for the game engine. Combat scenes could be remade for many differently played (but plotwise independant) scenes using "procedural generation" to do the combinatoric variations, with logic for option selection/validation/balance. If the game has generic (combat AI driven) 'friendlies' NPCs, then they are another variability element.

For a larger, more SandBoxy scope, Some kind of AI strategy abstract faction/entity mechanism with an overall influence/power map controlling/defining mob spawns and opponent/friendly/resource strength which is in reaction to a players game actions (ie - player attacks+wins in an area and the mapwise balance shifts, causing shift of localized response by the AI elsewhere). Relatively simple AI moving about of symbolic force pieces (concentrations of power) would then control the combat factors for the scenes the player subsequently goes through (the 'scene' variability of the paragraph above). Players gaining allies(resources) or vanquishing enemy resources or bypassing them(stealth) cause different flow of the overall game. Possibly the games AI 'macro' direction doesnt react quickly, so the player can use speed to advantage, etc... Add some 'farming' of resources to offset it being purely shoot-em-up play... Add possibility of multiple factions (AI entities) which depend on player actions to become friends/foes/obstacles.

I'm interested as well, I'm not doing procedural story per se, but I want variation in the notes that I scatter around my game. So changes like which NPCs are killed in which order, what they're killed by, etc, but without disrupting the flow of the story. Ensuring that any required NPCs survive, time inequalities between certain events are maintained, etc.

The current approach I'm looking into would almost be a grammar, but with large pre-written chunks, conditions, and variables set when you enter certain nodes. Possibly pulling out certain pre-requisite stuff like the characters into a header to avoid emergent logical inconsistencies based upon which nodes are triggered in which order.