On Making Up Stuff as You Go Along

I just finished playing Dreamfall: The Longest Journey.

First off, this game is awesome. If you’re interested in the story of the The Longest Journey universe, you will definitely find this to be a very compelling game, if a bit short.

I mention it, however, because games such as Dreamfall, Indigo Prophecy, and Shadow of Destiny are screaming for dynamically generated content. I mean this in the sense that is described in Story Director and Interactive Narrative technology in general. In the Story Director methodology, a story author has a sequence of dramatic points that he wishes the audience to experience. He might even have a specific, scripted plan for how the audience should reach those dramatic points. This is, of course, what is done normally in games. In order to make this work, however, the player is prevented from doing anything that really interferes with the story author’s plan, often in a totally unnatural way. By “unnatural”, I mean you see the following sort of thing:

• Totally fake characters : If the story line requires that the player meet with character X at location L, then X is waiting at L forever, until the player gets there. i.e., characters have no lives outside of talking to you. When they’re not talking to you, they’re waiting to talk to you.
• Artificially static environments : If a scripted path going from one plot point to another plot point requires character X to go through a doorway, then that doorway better be clear in order for the plot to continue. So now, you can’t have too many computer controlled characters walking around because they might be in the way, and you can’t have the building be destroyed or made inaccessible by the player accidentally setting an explosion off nearby

The result of all this is the human player is painfully aware they’re in a fake reality, and immersion is broken. To address this problem, Story Director technology retains immersion by recovering from an author’s plan made broken through unpredictable user interaction. It does this like so: The author specifies a list of important plot points that the audience must experience, and possibly an initial plan for getting from one plot point to the next. If the user does something that breaks the plan, then a Story Director creates a new plan, that meets the same plot points.

This makes the following situation possible. Suppose you (the player) are about to meet an informant in an alley way, to get some vital information so that the story continues. Upon getting there, the two of you are jumped by some thugs. For some reason, you fail to act quickly, and your informant is killed, before telling you the vital info. Now the system recovers, and finds a new way to get that information to you: The informant’s brother/girlfriend/wife/boss/pet panda sends you a letter, or you have to track down the informant’s sources yourself resulting in a whole new section of the game opening up.

Now your actions have consequences. Now your actions have meaning within games in virtual worlds.

Can game designers tackle the prospect of run-time generated story content?

Does Search Win in the End?

A great many AI problems can be phrased simply as a search through a domain of elements for one that meets criteria C. The planning problem is certainly this way. As a simple example, suppose one has an environment (an MDP, for some generality), with finite horizon:

S = (finite) set of states A = (finite) set of actions T = T(s, a, s') =Pr(s' | a, s) R = R(s, a) Horizon = Z steps

Given this formulation, there are finitely many policies to examine. The naive solution would be to enumerate them, see what reward each one got you, and then take the policy that gave you the biggest reward. Of course, we don’t do this because, for any remotely realistic domain, this search space is so huge as to make this process intractable. To actually solve this problem, people developed Value Iteration, or Linear Programming or what have you. These methods allow you to efficiently cut through the giant search space.

The interesting thing is, 15, 20, or 25 years from now, that search space won’t seem nearly as large as it seems to us today. Computers will be much, much faster, and can simply plow through that enormous search space in the blink of an eye. No sophisticated methods of cutting through the space such as Value Iteration (VI) will be necessary. Using VI and using brute force search will be the difference between .20 and .25 milliseconds.

The question is, then, if the constant advance of computer technology will eventually make planning methods totally irrelevant.