What kind of methods are best used managing complex story lines in a game? A simple story is basically linear line with stops, so that would not be that difficult, but a more complex one is basically an elaborate directed graph, with certain requirements to move between nodes. So how does one effectively store and maintain a complex game storyline that has multitude of paths and goals?
Depends on exactly how your system is put together. If it's simple branching, then just treating it as a linear story with some flags to tell exactly what path you're on (or if you prefer to visualize this way, a binary tree structure where each node is a story choice point and the current place in the story is a pointer to one of the nodes). A slightly more involved story with multiple paths that can cross over each other could be modeled as a directed acyclic graph using the same technique.
What if you have multiple story arcs going on simultaneously, like a typical "open world" quest system where the player may have several quests at once? If the quests don't interact with one another, you can just treat each of them as its own separate linear or branching mini-tree. What if they do modify each other? Here's my preferred option:
A modified directed graph, where each node represents a quest. Here you have two basic kinds of arrows between nodes: "activate" and "deactivate". In this way, completing a quest might open up new quests, and it also might invalidate old quests that no longer make sense (for example if you're given a set of quests, each of which is to help a different side of some warring factions, completing one quest might auto-hide the other quests if you want to force the player to pick one side and stick with it). You'll also want to store in each node its current status: active (currently visible to the player), inactive (has never been visible to the player), completed (player has finished the quest), failed (player has seen the quest but it was later inactivated, for example by the completion of a separate competing quest).
Amusing side note: every system that works for a quest/storyline, also works for an individual conversation tree with an NPC, and vice versa. So if you find a suitable conversation system for your game, ask yourself if it's worth modifying that for the story system as well.
The Neverwinter Nights toolset includes an interesting attempt to solve this problem, known as the Plot Wizard. It didn't originally ship with the toolset, so you may need to try it again if you did some module development years ago. Here's a lengthy tutorial that goes over the different components designed to engineer an RPG plot.
The basic summary is that the "plot wizard" allows you to construct storyline and quests from the top down. For instance you can tell it to generate the relevant scripting for a "fetch 10 things" quest, which leads into a fedex, which leads into a custom scripted thing. The wizard will then generate a series of linked components that are tied to the plot script, and then allows you to place them in the world. This allows you to easily move NPCs or enemies around in the world without breaking any scripting connections.
I don't know of any other commercial games that use this technique (most seem to use a ton of one off variables that are checked via scripts), but I've always felt this was a reasonable base for building a complete rpg or adventure-style game.