Online Interactive Fiction Engine

The goal of this project is to have a lean and mean system for playing online IF games that runs as a simple php script and does not require any special software to be installed on the server or on the client system. To make the game playable that means that the scripts need to be small and fast, and this means staying on the right side of the 80/20 line.

I've heard it said that in software engineering 80% of the effort, 80% of the code, and 80% of the time is spent implementing 20% of the features. The scripting language is meant to be used for writing interactive fiction games, not for programming aerodynamic computations or printing payroll checks. The scripting language will not be a general purpose programming language. Features that are common and expected in languages like C or Java will not necessarily be present in this scripting language, especially if they are features that fall on the wrong side of the 80/20 line.

Features that are present in many other IF programming languages may likewise not be present if those features are used only rarely. This means that if an IF author wants to use some rare exotic feature then he may have to write a few extra lines of code. But better that than penalizing all those authors who don't use that rare feature by making their execution slower. As a hypothetical example, suppose that the script interpretor could be made 10% smaller by making every statement use a function call syntax. Then instead of writing x=x+1; or even x++; the author would have to write Incr(x); If that were the case then I would go with the function call syntax, disallowing all algebraic expressions. But, realistically, how often does an IF game need expressions like sqrt(3*(x+y*cos(theta)/2.3));? And if more complex expressions are needed the author can always nest function calls like Set(x,Sum(x,Mul(y,3));

In many cases this may mean doing things a little differently than they are done in conventional IF languages. Hopefully that will not prevent this system from being every bit as capable as any other IF game engine. Bear that design philosophy in mind in the discussions that follow and you will understand why I always choose the minimal server code approach.

The design of an online game engine is, or at least should be, completely different from a system written to reside in a single personal computer. For one thing there's the issue of persistence. In a stand-alone computer the game continues to reside in the computer while waiting for the player's next move. The game, having been loaded only once, has available to it all the rooms and all the objects the players will ever encounter in playing the game. These objects are normally organized in some vast data structure such as an object tree or a huge collection of strings and arrays.

This is not the case with a server-based program. The program is present in the server only long enough to process one single user command, and then the program simply goes away. Each time the user enters a new command and sends that command to the server, the server loads a fresh copy of the game and processes that single player command, and then goes away again. So why would such a game program need to load tons of data about rooms the player is not presently in, or objects the player does not presently have access to?

The overall structure of the game will be very modular. Code and data will be loaded into the server if and when it is actually needed. If the player does some action that takes place in a single room then only that room is loaded. If the player's move is to leave that room to enter another room then only those two rooms will be loaded.

I collected a dozen walkthroughs for an assortement of games written by other people, and tabulated the command formats. The results are as follows:

Command Format	Examples	Count	Percent	Cumulative Percent
verb + object	Examine box. Take marble.	2588	44.0%	44.0%
direction	east. sw. up.	1797	30.6%	74.6%
verb	wait. inventory.	909	15.4%	90.0%
verb + object + prep + object	put the marble in the box. Ask clerk for the note.	570	9.7%	99.7%
All Others	Mary, give me the book Put the hot coals in the bucket with the tongs.	20	0.3%	100.0%

Given the above statistics, I will design the parser to handle nearly all of the commands including the more exotic Put the hot coals in the bucket with the tongs. Anything not covered by the original parser should be covered by the ability to extend the parser tables to handle special cases.

The parser needs to be able to figure out what kind of action the player is asking for, (which script function to call) and which objects are to be involved in that action (what parameters to pass to the script function). Acquiring these two pieces of information requires that the sentence be disected into its component parts. Here we are not talking about the traditional categories of verbs, nouns, and adjectives. In fact, we don't really care about concepts like "parts of speech". Leave those to the theoretical linguists. All we care about is extracting a function name and a list of parameters.

The first step in that process is to split the command sentence into slices. We do that with a splits array. The splits array contains a few split words, a function name, and a parameter order. The sentence is broken into pieces wherever a split word is found. For example:

Of course in that example we had the forethough to pick the right split words entry right from the start. But what happens if we pick the wrong split words entry:

There can be little doubt which is the correct set of split words. Other arrays will contain single split words for commands like "drop the book" and sets of three split words for commands like "put the hot coals into the bucket with the tongs".

Now that the two parameters have been split out from the command we still need to determine which objects in the game world that those parameters refer to. For this we use statistical matching, considering only those objects which are in the same room with the player, including items in his inventory of possessions.

First the articles "the", "a", and "an" are discarded and the remaining words are matched against sets of words that apply to each object. Each set of words is scored based on how many of the command words it matches. If one and only one object's word list satisfies 100% of the command words then that is the object refered to. If two or more object's word lists satisfy the command words then the command is ambiguous and the player needs to be more specific. For example:

Commanded Object	Object 1	Object 2	Object 3	Object 4	Object 5	Winner
box	0%	0%	100%	100%	0%	ambiguous
small box	50%	0%	100%	100%	50%	ambiguous
tin box	0%	0%	50%	100%	0%	Object 4
small tin box	33%	0%	67%	100%	33%	Object 4
small metal box	33%	0%	67%	100%	67%	Object 4
tin thing*	50%	50%	50%	100%	50%	Object 4

So far this works just fine, but there are some cases where splitting doesn't separate the parameters correctly. Consider the command: Give the crusty old man the little red book. The presence of articles make it clear where to split those two object references, but suppose the player left out the articles: Give crusty old man little red book. Since we cannot rely on the presence of articles, and since we will discard all the articles anyway, we need a reliable way to decide which words belong to which object.

There are only so many ways that the group of words crusty old man little red book can be split, so we generate a list of all 10 word sequences and score each one against all the objects present. The result looks like this:

And we have a winner. We know which function to call and we know which objects to pass to that function:
DoGiveTo('crusty old man','little red book');, or as it would happen internally:
DoGiveTo(1,2);

Suppose you are writing a game involving cooking and you need some new verbs like "mince", "boil", "bake", and so on. The library of verbs can be easily exgtended by providing the new script function and putting its name into a split words entry. For example, to handle boil soup in a kettle over a medium flame will require new split words entries something like:

The above three entries would handle boil soup in a kettle over a medium flame, boil soup over a medium flame in a kettle, and over a medium flame boil soup in a kettle sending the parameters to the DoBoilOver() function in the correct order in each case.

In the same way, the parser can be extended to do things like resolving pronouns. If your game really needs for the player to be able to type Open the wood box and put the marble into it then you can always add a verb function and a new split words entry:

This solves the problem of "resolving pronouns", except that we didn't really "resolve" anything, and the system still doesn't know, or care, what a pronoun is. And doing it this way puts us on the right side of the 80/20 line.

You can play with the parser live at: this link.

To introduce new objects into the game requires that the system knows how to find those objects and to distinguish between similar objects. For this reason, any objects that can possibly exist in the same location together must all have unique word lists to identify them. If two objects can never be found together in the same room then they do not have to have unique word lists. For example, suppose every room in your adventure has a table that cannot be moved. All of these tables can simply be called "table" with no danger of confusion, because "table" will only ever refer to objects in the same room with your player character.

After we've given the object a name we need to list its capabilities. Every object in the game can have any one of a number of capabilities. Generally speaking saying that an object has a certain capability is the same as saying that a certain group of verbs can be used in a certain way with that object. For example, if an object can be opened and closed then we say it has the capability canClose, which is just another way of saying that it can use the Open() and Close() functions. To say that an object has the capability canLock means that the functions Lock() and Unlock() can be used with it. But what about a key? That's an object that is associated with those same two functions, but you can't lock a key. To make an object be a key we give it the capability canDoLock. That means that the key can be used with the Lock() and Unlock() functions, not as the target of the action, but as the instrument of action.

Any object can be given any list of capabilites depending on what that object needs to be able to do. A chest might have the capabilites: isContainer, canClose, canLock, but be too heavy to pick up or move, so it would lack the canTake capability. And since it's too small for a person to climb into, it would also lack the canEnter capability. On the other hand, the chest might be made of glass, in which case we would give it the isTransparent capability.

When the author defines new functions for a particular game then in addition to providing the split words entry (the verbs and prepositions used to invoke the function) the author also has to specify which capability an object must have to be the target, object, or instrument of that function. And if the game requires some new capability (say canDisolve, for example) then the author can easily add such new capabilites to the game.

Many IF programming system have some form of advanced disambiguation built in. If the player types the command "open the door" and there are two doors in the room, how does the game know which door the player is talking about? In some systems, like TADS, for example, the parser will check to see if one or the other of the doors is already open, and then apply the command to the other door. It does this by requiring the door definition to include code to verify that the door can be opened. If the door's own verify code reports back that the door cannot be opened because it's already open, or because it's locked, then the parser will choose the other door.

This is a very slick system, and works well, but given my own design goals I have to ask how much code it takes, and whether the convenience is really worth the code burden. The simple-minded solution to advanced dismabiguation is simply to ask the player "which door?" and let the player respond. Whether that is an adequate solution or not depends on how often the situation comes up. If it's something that happens once in every thousand moves then to stay on the right side of the 80/20 line it's not worth worrying about.

My plan is to write the parser without any such advanced features and try it out in actual practice to see just how badly missed those special features are. And remembering that the interface for the game is a web browser, many of those situations could be avoided completely by making words in the room description clickable links. If the room description says that there is a door to the north and a door to the east and both of those phrases are clickable then ambiguity would not arise in the first place.