Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
October 26, 2014
arrowPress Releases
October 26, 2014
PR Newswire
View All
View All     Submit Event





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Prose Generation Techniques for Small Platforms
by Ron Newcomb on 01/06/11 09:02:00 pm   Featured Blogs

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

 

One odd omission in the interactive fiction authoring tool Inform 7 is its inability to instantly change the story away from second person present tense. This job is left to extensions. Over the years the original extension to do this became such a maintenance nightmare for its writer that this past November I rewrote it from the ground up, keeping in mind the tight memory restrictions of the target platform: the Z-machine, a virtual machine suitable for cell phones. What follows is some optimization techniques for light prose generation for similarly constrained platforms.

To support changing the viewpoint and tense at runtime, the new set of messages contained embedded functions to fetch the appropriate pronouns, auxiliary verbs, etc. at the moment of printing. Coded naively, that's a function with a lot of if-statements. So the first trick used was bitfields. A bit is the smallest unit of computer memory, being either a zero or a one at any given time. (Hence a 16-bit computer uses that many bits to represent a single number.) A bitfield gives each individual bit a separate meaning, so every combination of circumstance can be represented as a single number. For example, conjugation has the first bit representing present (0) and past (1) tense; the second bit represents the perfect aspect, and the third bit the continuous aspect. All eight combinations are represented as a single number zero through seven, and answering runtime questions like "is this verb conjugation in the continuous?" or "is this past-perfect tense?" is very efficient.

A second optimization used those bitfields as a row number in a lookup table. For example, the declension bitfield combines viewpoint with case.  There are eight viewpoints: second person, third person feminine, first person plural, etc.  There are five supported cases: subjective ("I", "we", etc.); objective ("me", "us"); possessive ("mine", "ours"); reflexive ("myself", "ourselves"); plus the oddball possessive adjective ("my", "our").   Combined, they give the appropriate pronoun for the current position within the containing sentence and for the current viewpoint of the story.  Out of those forty combinations, a single lookup finds the correct pronoun.  No if-statements needed.

Third was an interesting inversion of making the exception the rule. Verbs have several inflected forms: the present ("-s"), past ("-ed"), present participle ("-ing"), and past participle ("-en", frequently identical to the past). Irregular verbs do not follow the suffix rule, so must be listed and looked up similar to the pronouns. But, by treating the standard suffixes as a single irregular verb themselves, the irregular verb's code handled regular verbs as well:  the rule became an exception. And this code is mildly recursive: when printing the present form of the irregular "take", the text may or may not need the -s suffix for subject-verb agreement. So, the irregular verb TAKE appends (or not) the 'irregular suffix verb' as appropriate. 

Future tense is a curious case of function not following form. Semantically, future tense is a tense, to be grouped with past and present tenses. But syntactically, English indicates future tense via the word will placed in front of the verb phrase. This categorizes future tense with other modals such as could, would, and should (which can be handy for games). Indeed, a quick dictionary search shows that would is the past tense of will just as could is the past tense of can. Since one bit was already defined as past/present tense, two additional bits were added to the bitfield for the modalities can/could, will/would, and shall/should (not to mention "none of the above").

The astute reader may wonder whether I (or why I did not) treat entire verb phrases as a lookup similar to the pronouns, with entries like "could have been carried" preceding "could have been being carried" and the like. Memory is the reason. The bitfield allowed a bit for "not", a bit for mood (inquisitive versus indicative), and a bit for voice (active versus passive). The commonest question words who, when, why, etc. were allowed another 3 bits. All told, such a lookup table would have tens of thousands of rows, each being multiple letters (bytes) long, and with a lot of repetition. While I can't say I'm completely happy with the code that disentangles it all, it is at least fairly concise.

Of course, this extension had more constraints than just memory. Source-level backward compatibility with the original extension entices authors to switch. Both extensions have a "light" version for authors who need only to rewrite messages, not alter the tense and viewpoint, so my new extension has two different directions for "backward" compatibility. Inform itself now supports source-level code replacement, and this was put to good use. The popular Plurality extension somewhat overlaps the prose generation features, so a self-censoring section looks for Plurality's inclusion to avoid duplicating functionality.  Similarly, source-level replacement removed the original set of messages stuck in second person present tense. The latter step alone saved an astounding 10K.

And if all that weren't enough, the new extension needed to be very easy to use because writers comprise much of Inform 7's audience.  Writers do not put up with whiny, needy code. For this, a pre-release version in the forums produced many excellent corrections and suggestions, the best of which involved renaming key features to something much more writer-friendly.

The final result can be seen here.  Comments and suggestions are always welcome.


Related Jobs

Red 5 Studios
Red 5 Studios — Orange County, California, United States
[10.24.14]

Graphics Programmer
Red 5 Studios
Red 5 Studios — Orange County, California, United States
[10.24.14]

Gameplay Programmer
Gearbox Software
Gearbox Software — Plano, Texas, United States
[10.24.14]

Server Programmer
Forio
Forio — San Francisco, California, United States
[10.24.14]

Web Application Developer Team Lead






Comments


Lars Doucet
profile image
These are the kinds of computer-sciencey, practical knowledge articles I so miss on Gamasutra :)



How difficult would it be to to localize this algorithm to other languages, given the differences

in grammar details like case and declension?

Ron Newcomb
profile image
Me too. Thanks.



Not too difficult. I tried using terms from linguistics such as declension and inflection which apply to all languages. The main thing is to arrange matters so that the number of each thing is a nice power of 2. This helps keep things in tidy bitfields, and hence tidy 1D arrays. Inform does have a single feature I found invaluable for this: embedded functions within strings. An off-the-cuff example:



"[if the subject is plural]s[end if]"

"ed"

"ing"



These all typecheck as text, even though some are pointers to char arrays and one is a pointer to function. But Inform's standard print statement can magically disambiguate between the two on pointer value alone. (I think all the char arrays are lumped into a string table, so if the pointer falls within that memory range it's string, not function.)



The other thing is to, as much as possible, imagine the longest conjugation possible, like "could not have been being X", and write a function that asks an 'if' for each word, in order. (Granted, order is more important in English than others.) So printing a whole conjugation is always the same straightforward function, informed by global variables or what have you.



And always be on the lookout for when syntactic category and semantic category differ, such as English's future tense. Linguists are primarily concerned with the latter, so the former may not be called out in what you read. My code would have been much nastier if I had lumped the 3 tenses together rather than just the nice 2, one needing checking at the beginning of the verb phrase, and the other 2 at the end. Exceptions like that destroy compact code.


none
 
Comment: