In the past weeks, I've written a story/descriptions generator for players, NPCs or even locations. Steve Breslin, our storywriter, has helped to design the system, and so will be the one to try to explain it in today's journal (in better english than I could :) ):

Introduction

As you may have heard, we've been working on a story generator. We're releasing a prototype today, and you can download it here

The purpose of this article is to introduce you to the thing, explain the theory, its intended use, some development notes, and some of the practical stuff -- and then invite you to read the manual and play with it a bit.

As you may know, natural language generation (NLG) is one of those programming concepts around which science fiction has woven circles of mysticism, along with greatly inflated expectations and misplaced hopes. Still, NLG is capable of a lot, if by 'a lot' we mean the NL expression of information according to carefully detailed rules and pre-written natural phrases.

For the purposes of story generation, this means that the computer program does not invent or "make up" the events that happen in the story -- the individual events are pre-written by the human designer. Nor does the program invent phrases to express these events -- those phrases are also pre-written by the designer. The program's job is simply to take these elements, the events and the phrases, and automatically combine them in a way that's presentable -- according to rules defined by none other than, yes, the designer.

So, as you would expect, automatic story generation does not make things easier for the human designer -- this you'll see firsthand if you decide to experiment with it. But once the system is in place, the program can automatically generate thousands of unique stories, by combining pre-defined elements in various ways.

You're probably wondering how the game will use the system, so let me start with that....


Player history

The character creation system for Infinity will give the player basic control over their character's background: which scion they start in, their age and gender, and perhaps some other options to provide a greater level of detail. More specific options have not been finalized, but they may include , for example, a peaceful or tumultuous childhood, social class, perhaps the specific home world, and perhaps the profession which the character pursued up to the beginning of game play.

After selecting the parameters, the player can then "roll" the character, and the history generator then designs a story based on the parameters supplied by the player, but filling the story in with numerous additional historical details. If the player doesn't like the history, he can roll again with the same parameters, or change them however suits, and roll again. The purpose of this setup is to give the player a good level of control over the character's history, supplying a rich back-story, which the system can use to make the history relevant to the game experience.

As a quite separate project, it would be feasible to allow custom stories written by the player, but we would have to give up the idea that the character history might influence game events. In order to make them relevant, we would either have to force the player to write their character's history using a narrow and very picky subset of English, and spend a month writing a basic NL interpreter; or we allow players relatively free reign in describing their character (although warning not to expect the game to understand it precisely), and take a few years to write a powerful NL interpreter. Anyway, for now we're concentrating on automatic generation of a short story for the character.

While the history isn't written by the player, we want it to be a history which the player feels comfortable adopting. So we'll try to incorporate as much variability into the stories as possible. -- Keeping in mind that the player can adjust the parameters and re-roll the story until it is satisfactory.

For example, the character could just have graduated from a university, or is perhaps an up-and-coming pirate, or has had trouble with a criminal organization. The really neat part -- each of these contextual and historical details could possibly influence missions the player engages in later on.

The purpose of this is not, of course, to strongly determine the future of the character, and there aren't character skills (as there would be if the game were an RPG). We want the player to be free to be and do whatever he or she wants, and not limited by character attributes or history. The history will not limit the player's options: the players/characters are always free to cut whatever path they like. Gameplay will be enriched a bit, but the character will not be scarred or pigeonholed by their back-story.

So yes, events that happened in the PC's childhood or history will add interest to the play.

The first effect is a "bonus/penalty" inferred from the history. For example, the character could be born in a rich trader family, so as a "bonus" the player would begin the game with a small hauler (different than another player's starter ship). Of course, for every positive there is a negative, so if you get a better startup ship, you might have a "problem" added to your history, to balance things out -- some bounty hunter after you, or a debt that can only be paid by running a dangerous mission as a "favor" for a creditor.

All of this will also influence your reputation, how other factions see you, etc. Again, this can be easily overturned by in-game action; this is just the initial population of startup parameters. Later in the game, some missions might be triggered and influenced based on your history. So maybe you'll be contacted by a NPC you've met in your childhood, that will give you some special missions/jobs: "Ah! I knew you parents!" When doing a mission for a company that your storyline parents worked for; or "We found out who killed your brother..."; you can imagine.

Again, the character will be really determined by what the player does in-game; the history is just a base start, a neat way to encourage player/character empathy early on. If you originate from a dominant Deltan military family, but your heart is in trade and ending up in a Starfold smuggling corp would be great for you, then go for it: no problem. The story does not set limits on player action.


Designing the Algorithm

Figuring out a good NLG program is something like tricking the devil. There are so many pitfalls, so many constraints. You can't just target normal speech, and write an algorithm for that. That's too vague and too wide. The very form of idea and expression must be targeted and designed for automatic generation. It's a delicate marriage of the story concept + the form of expression, balanced with the algorithm we use to make it all happen.

It is technically possible to perform the operation in two passes: first, determine the events of a story; then, follow syntactic rules to give English expression to the events. The second pass requires writing a robust syntax-based NLG engine, which would require many months if not years of work.

Fortunately, it's much easier if each event declares its own NL expression. Thus, we can use much simpler rules to join the pieces of language together. This does not really increase the story designer's work, and it greatly decreases the engine programmer's work.

Our next main question: what is the structural form of the kind of story we'd like to tell, adjusted to the limitations of the algorithm? What we're aiming at is a story form which is going to sound good, and be flexible enough for automation, with multiple story elements which fit well within the form.

We assume we're going to present the story chronologically, so to begin with, the character's history begins in some initial situation -- some preliminary data (say, gender and place of birth). Then, the possible range of "first" events in the story are determined by the initial situation. All proceeding events follow from what comes before, progressing in chronological order (and of course there's an element of fortune).

As a preliminary conclusion, we can say that story elements have preconditions and chronological order.

Thinking about the idea of preconditions, or simply "Conditions," we'll see that it is pretty straightforward. Let's say that the person who is writing events for the story generator has decided to go for an event along the lines of "the player character enters the Deltan military." The designer is probably assuming that the player is born in the Deltan Federation, or at least living in Deltan space by the time of the event. The designer will probably want to arrange things so that this story element does not appear in stories which locate the player character outside of Deltan space. The designer can do this by setting a precondition. The Condition basically says, "this story element is only viable when the player character is in Deltan space." We're constructing the story in order, so the Condition makes sure that each event is logically consistent with the material that came before.

The idea of chronological order is pretty interesting. The simplest version of chronological order would be a system where there's one sentence per chronological event; so for example the first event (and the first sentence in the presentation) tells about the birth planet, the second event/sentence tells about parents and early childhood, the third event/sentence tells about the next highly-specifically defined event-type or concept, and so on. If we did it this way, each 'event' would declare which chronological slot it fits into, and these slots are static -- they're strictly determined ahead of time. The stories would be "randomized," and would be logically coherent (in the sense that, at each point, logical preconditions are not violated), but they would not be particularly variable. This would be acceptable for our purposes, but we decided to kick it up a notch.

The more flexible form we decided upon not only increases the variability of the story, but also makes the algorithm applicable for a wider range of uses (beyond player story generation). Instead of a strictly predetermined form, we allow each element to determine what kinds of elements are permitted to come next. So we assign each story element a type (or "Name"), and then each individual element decides which element types can come next.


NPC history and Planet description

We would like to invite you to use the prototype to write auto-generated stories for NPCs. If, after you play around with the story generator, you are interested in exploring the capabilities of the engine, you could for instance design from scratch a separate 'descriptive' project, such as describing planets.

The prototype includes the main engine and supporting files, an XML datafile which you can use as a template for your story, and a readme file which explains the language of the XML file. There's no reason to get too far into the language in this development journal entry -- please refer to that readme file if you're interested in playing with the generator. However, I would like to mention here the basic concepts at work.

One major point of interest is the scripting language. It is relevant during three phases, the "Operation" phase, which is executed if an element is chosen to be a part of the story; and "Condition" and "Probability" phases, which determine the possibility and likelihood of any elements' inclusion in the story. In the "Operation" phase, you can invent variables for recording events or facts (familyIsWealthy = true) and perform calculations (initialWealth = initialWealth + 40), so that later elements can evaluate these variables in the "Condition" or "Probability" phase.

Another major feature is that you can also assign pieces of text (AKA 'strings') which can be substituted in the pieces of story-text associated with each element. In other words, the story can be parameterized. Say, $birthplanet is a variable string, so you can assign any planet name (birthplanet = "Ourados"), and then as a story element you can write "you were born on $birthplanet"; any time you want to refer back to the birth planet in the story, you can use that variable. (And of course you can evaluate the variable in a "Condition" or "Probability" phase.)

Using precisely the same technique -- but with built-in variables -- you can make your story variable by grammatical person (first, second or third person singular: I, you, or he/she/it).

By way of a second technique, you can enable your story to support automatic pronoun substitution. So, if the same noun (e.g., your father) happens twice within a single sentence or in adjoining sentences, the engine will substitute the second instance with the appropriate pronoun (e.g., he).

The phrases associated with each element are intended to be simple grammatical sentences. This is important because the engine uses special combination rules to conjoin event-phrases in an appropriate way, depending on their "Type." For example, if two elements are both labeled "positive," and the engine conjoins the sentences, the conjunction will be in the 'and' category; if one event is labeled "positive" and the other labeled "negative," then the conjunction will be in the 'but' category. Wherever necessary, you can also override automatic sentence-combination by declaring an element as a mandatory new sentence.


Closing remarks

The system is still in the prototype phase. If you play with it for a while, you will probably come up with some ideas we can use. Please let us know if you discover any capabilities which you think would be particularly useful, or if you find any problems.

In any case, you will soon discover that you need a lot of self-discipline to remember the "flow" of how each element relates to the previous and next, so that it all hangs together when assembled. There's no real cure for that, but don't mind too much; that challenge comes with the territory.