NaNoGenMo RecapNaNoGenMo Recap
March 17, 2019
This post is a couple of years late. I started writing it shortly after nanogenmo but then got swept up in life events and work projects and that sort of thing. I wrote about half of this not too long after, but didn't get around to finishing it until now.
If you want to look through the (messy) source code for this project, it's all here: NaNoGenMo Src on Github
Follow me on twitter if you want to see occasional experiments like this one: Follow @joeld42
I took some time out in November 2016 to work on something I've always wanted to try. Computer-Generated Fiction! You may have heard of "NaNoWriMo", where aspiring authors try to write a 50k word novel in a month. (It's great fun, and a great way to learn and become a better writer, I've done it a few times and completed it twice). There is a loosely organized offshoot of this called "NaNoGenMo", led Darius Kazumi, an artist and maker of twitterbots and other clever things. The goal of this is not to generate a story directly, but to write a computer program that can generate a 50k novel by itself.
Obviously, I am not expecting the novel to be very good. But there was a couple of reasons I thought this might be worth doing. One of the other projects I'm working on is a tool for visualizing story structure for screenwriters and novelists, and I thought this might be a good way to get some insight into different ways to represent plot and story structure as data structures. Also, I've got some game ideas that revolve around procedurally generated quests and this seemed like a good way to try out some of those ideas (spoiler: it's harder than I thought).
This post will summarize how my novel generating script worked and attempt to distill some of what I learned along the way. It was a great learning experience.
Here's a sampling of book covers from the script. The covers were one of the most fun parts of this whole thing.
And here's the result. Each book turned out to be about 2-3k words, which is not much of a novel. I considered just tuning things to generate a huge number of scenes, but that was harder than it seemed because it would require either allowing characters to revisit locations, which probably would create big inconsisitancies, or making a huge continent, which has it's own problems and would probably break the map code. So instead, I just generated a bunch of novels until I got 50k words. The final total was 17 books for a total of 52087 words.
How it Works
The generator works by first generating a random map for the adventure. Then it creates a "story path" that goes through a few of the dungeons and ends up back where it started. Then it creates Scenes along this path, along with some extra filler scenes like conversations and walking around town are added at random. For each of these scenes, a set of rules are generated and Tracery is used to generate story text. Finally, the story text is grouped into chapters and typeset into a PDF, and cover, title and author is generated.
Sometimes the markov chain generated names were not good. For example, one quest was called Uckerkovalterbybynashusby-langplagghultalarnesluotoinkylajordtorgidsjo Kyrkjarvnas
Here's a more detail about each section:
The map generator was my favorite part, but that was mostly because I used a bunch of tricks that I already knew, rather than learning new stuff. I was pretty happy with the results, and I'm thinking about expanding it into a standalone fantasy map-making app because it's a lot of fun, and would be useful for people like actual fantasy writers and role playing games.
The map generator goes through a number of steps, I'll detail them here:
Generate seed points.
The whole process starts by generating a handful of random seed points. The only constraint is that these are generated so they are at least a minimum distance from each other. I'm not doing any fancy Poisson distribution stuff, I just re-roll any points that are too close. This could take forever for a tight distribution but the values are tuned so that there's plenty of room and it's no problem.
I initially had some "exclusion zones" were I would choose a few big circles and randomly reject points inside these. The idea is that it would create more irregular points and avoid terrain looking too blobby. However, the landscape generation did a good enough job without this so I disabled that.
Generate Elevation Data
There are very many ways to generate an interesting landscape, but for this I used one of my favorite algorithms because it's so simple, and yet very flexible. Using Perlin-noise or fractal subdivision is great, but overkill for a lot of things. I call this "fault line" terrain generation, not sure if there's a real name for it, but it's simple enough to code up in a few minutes, works on a grid or a sparse set of points, and is pretty flexible and very tunable. It also can generate landscapes with nice, steep cliffs and discontinuties which can be harder to get with a fractal or noise based approach. But mainly it's easy.
The algorithm works like this: Initialize your samples somewhere around your halfway point. Then, generate a random line through your samples. All of the samples on one side of the line you increase the elevation, and on the other side you decrease it. Repeat this many times and you're done. You can get fancy and start with a very large value to change the elevation and fade it over later iterations, but I didn't do that.
After that, I just assign everything below elevation 20 to be "water" and everything above 20 to be land. To guarantee a nice range of elevations, I also rescale the "land" elevation samples so the highest point is alway 40, just to make things simpler.
Terrain Regions and Kingdoms
After the elevation is generated, the points are triangulated. This is the basis of a lot of the terrain stuff, including the "Story Path". Triangulation is a really simple incremental Delauney triangulation. Once we have a triangulation of the points, we know what points are reachable, and we can look at nearby points. The next steps depend on this.
A "Region" is what I called a biome or terrain type. The regions are used to influence a lot of the description text, for example, in the mountains it may describe the groud as "rocks", "narrow path", or "stones" but in a swamp it might use "mud", "mire", "muck", or "fetid soil". The regions are "forest", "desert", "swamp" and "mountain". There's also "lakes" which are like the ocean samples but don't have Port Cities. The lakes are assigned by looking at each contiguous group of water, if it has 4 or less nodes, it is considered a lake.
After finding lakes, I assign "seed" regions. I choose a handful of the land nodes and assign them to be forest, desert or swamp (not mountains). Then, these are propagated, flood-fill style. I walk over all the unassigned nodes, and if it's adjacent to one that is assigned, it gets that region type. This is repeated until there are no changes. It's possible to leave some nodes unassigned, for example if a small island doesn't happen to get a seed node. These are just assigned randomly to fill out the world.
Initally, I assigned all the terrain types this way, but felt like it ended up with big blobs of mountains. Sometimes a whole kingdom would be mountains, and it just felt too uniform. So to make the mountains a little more natural, I assign them by a different method: I start a mountain range at a random location, and then pick a random direction (angle). Then I look at the connected nodes and choose the one closest to the target angle. I'll do this for between 3 to 7 steps, and make from 2 to 10 mountain ranges this way. Often these will just run into the ocean or off the edge of the map, but that's okay. In the end, the mountain ranges seem naturalistic and distinct from the other terrain types. Part of the reason this all works is the map is very coarse, so crude methods like this will still generate interesting results.
That generates the natural terrain. The next step is to generate political boundries of the kingdoms. This is done very similarly. First, I'll generate 2 to 10 kingdoms. Each kingdom has it's own Culture, which will be used later by the name generator so towns within a kingdom will have similar sounding names. Kingdoms also have three fruits that they grow. The fruits are used for a lot of the description text, and having the same fruit occur often in the same kingdom will hopefully help create a sense of place. This is one of the ideas that worked out well and I wanted to expand on it, but only managed fruits for now.
Anyways, each kingdom has a capital city, which is placed on a randomly chosen land node. Once the capitals are placed, these are flood-filled out just like the terrain regions. Any unreached land nodes (usually islands) are randomly assigned a kingdom.
Once the kingdoms are assigned, I randomly create 10 cities. These belong to whatever kingdom they happen to land in. So called "Port Cities" are pretty important to the story generator, because a lot of the plot involves travelling and finding passage to the next place. Also the whole thing can break if there aren't enough reachable places, so having ports helps this. Any city on the coast (adjacent to non-lake water) is flagged as a port city. Then, I add some more port cities to each kingdom as follows: I count the number of empty coastal nodes and choose how many to add based on that (1 or 2 if less than 20 coastal nodes, otherwise 10% of the number of coastal nodes). Then it just picks from these at random.
Aside: A python tip. I found that I often need to choose N items from some (hopefully) larger set without replacement. I ended up using a simple python trick of just shuffling the list and slicing the first N items. This worked remarkably well in lots of situations (coastal cities, fruits, etc) and is very robust (e.g. not having enough items). It's not rocket science but it's definately a nice thing to have in my bag of tricks.
Once the coastal cities are all created, I create "sea lanes", which are just arcs in the graph between coastal cities. I thought I could get away with just connecting all coastal cities, but this ended up feeling like things were jumping around too much and on maps with separated seas (such as ithsmus maps, which are not uncommon) it seemed noticably broken, you couldn't really make sense of the character's path. So I added a reachability check (just a depth-first search) to make sure that each port is reachable from each other before I add a "sea lane".
Next, I generate the Story Path, which is discussed more below. At this point, there are still roads between almost everything on the land. So the next step is pruning the roads. This starts by assuming all cities are reachable from any other, which they should be because of sea lanes. We pick a random city and count the number of reachable nodes. Then, I pick a road at random, and check if that's removed, are the same number of nodes reachable? If so, it can be removed safely, and it is. I do this a whole bunch (in this case, 500 iterations) and that gives me something that approximates a minimum spanning tree.
It's still pretty branchy, however, and there are a lot of "dead end" roads that lead nowhere. If I just removed all of these the map ends up with pretty much nothing but the story path, which seems kind of empty. So we take advantage of this and create a few more cities at some of the dead ends. Then, we prune any dead ends that don't have cities, which ends up with a nice balance of roads and cities.
The Story Path
The Story Path is what's used to create the spine of the plot. It is a loop that meanders across the map and ends up back home where it started. This is a classic trope of epic fantasy novels and storytelling in general. I didn't really make as much use of it as I would have liked to, it would be cool to have the story text have enough detail that when it describes the protagonist's starting town it is altered by the lens of their experience and level. But at least it gives the story a rudimentary sense of closure.
Generating the story path was the one place the sloppy coding did bite me, and this is one of the things that I need to clean up if I wanted to put up a webpage or something with the novel generator. Like everything else, I tried building the story path with the dumbest thing that could possibly work. The story path first chooses a few cities, trying to choose evenly between the kingdoms, and reclassifies these as dungeons. Then it does a brute force search from the starting city to try and find a path through all of these dungeons. Sometimes, this finishes in a second or two. Usually it takes 10-15 seconds. Sometimes it goes for much longer, I'm not sure if there's not a valid path to find, or if it's just too much to search, in any case I usually just stop it and start over after 30 seconds or so. I've got a couple of ugly workarounds for this, first, if it can't find a good path after a million iterations, it picks another starting city, and tries again with fewer dungeons. Also, I have a "fakeFastPath" flag which I use during development that generates a path by picking cities and dungeons at random, the path is nonsensical but quick to generate so it is very useful testing out the story text generation.
Anyways, this is the one part I want to rewrite or eliminate. But when it works, it usually generates good paths that make sense. Sometimes the path is very long and winding, and occasionally it ignores large swaths of the map, but usually the results are reasonable.
Generating place names was one of the most fun parts of this whole thing. I started with a huge list of cities from MaxMind World Cities. From this list, I filtered a lot of stuff out to make things easier, and then used the list of names to generate a Markov Chain. The first thing I tried was just using (nearly) all of the names, but that ended up making names that were just kind of mushy nonsense. Since the dataset had country codes, I tried grouping the training sets by similar (real world) cultures, eg, "old world" was UK and some other English speaking areas, "new world" was US and Canada, "Subcontinent" was cities in India, etc.. I tried a bunch of combinations until I got ones that sounded interesting and also distinct from each other. Unfortunately, I had to exclude a lot of cities that didn't use mainly latin alphabet, I think the results would be more interesting if I had phonetic lists of things like Asian cities.
Tuning the markov generator was pretty important. Using a pretty large number of priors made the words a lot more sensical, but also tended to overfit in a way that it kept generating names from the input set. The number of names used to train with also made a big difference. I tuned these by trial and error, and ended up using 10000 cities and a depth of 5. I set up a check and my target was to generate <30% of existing placenames.
Even so, there are a lot of weird cases with the placename generator. For example, in the list above, you can see that when it picks "X" as a starting letter, it will probably wind up generating "Xanadu" (it occurs twice in that sample list). Or when it chooses "land", it will probably call it "land-o-lake". I did filter out some anacronisms, like a lot of "new world" cities had industrial names like "carbondale" or but they still pop up (like "Uranium City" in the samples above). And I need better controls for the length, occasionally it will generate really long placenames. One particulary bad example I got recently was the quant town of "Uckerkovalterbybynashusby-langplagghultalarnesluotoinkylajordtorgidsjo Kyrkjarvnas". I ended up limiting these but I didn't want to limit it too much because sometimes the long names were interesting.
Here's a sampling of some of the more amusing placenames that it generated that I happened to save.
For Continents and Kingdoms, I needed shorter placenames, and also wanted to avoid names like "Ypaopao Estatesville", so for a simple solution, I just re-rolled names that were more than one word or more than a fixed length and that worked pretty well.
For Port Cities, I just used some quick Tracery rules to have a chance to add prefixed or suffixes like "Miyagam Docks" or "Port Kjirksey".
My plan for character names was to find a list of interesting names, maybe historical or something, or maybe just feed it a bunch of old english text, but I never got around to it. The character names are all just using "Kingdom" names which keeps them short and makes them unlikely to be called "Fjunly Estates". That worked well enough. I also threw in a handful of names from people on Twitter that had followed or commented on the project.
Another tool that was extremely useful for the project was the Corpora dataset from Darius Kazumi. You can find this on github at Corpora on Github. This is a collection of various interesting datasets. One of the most useful ones was a list of fruit, by picking a few random fruit for each region on the map, I could generate interesting sense details to throw into the scenes. The text is pretty noticibly fruit-heavy but I think using this technique with a few more datasets could really add a lot of richness to the world.
Once the story path is generated, the script walks the story path generating scenes. I had originally intended scenes to be about 500-1000 words worth of story text, but they ended up mostly being shorter, usually around 50 words or so, with some exceptions, like combat scenes.
Scenes represent a chunk of story action. A lot of the scenes have a lot less variety than I hoped, my plan was to get it generating coherent stories and then go back and add more variation, but I didn't have enough time to add much.
The rules to generate the scenes were pretty simple. First of all, it starts with a scene of "normal life" and an "inciting incident" scene. Then I walk along the story path. If a scene is in a location that hasn't been visited yet, I insert a "Place Description" scene. Places have a chance to generate "walking around" scenes. When we reach a Sea Lane, a scene is added for ocean travel, and there is a chance of adding an additional scene trying to find a ship. I had planned to do similar overland travel scenes, and add combat and encounters in the wilderness, but didn't get to it.
Dungeons/Quests are currently the only scenes generated out of order. When a dungeon is reached, that finishes a quest. We insert a scene that starts that quest randomly earlier in the story. If it's far away, I randomly add a few "reminder" scenes for the quest where the protagonist thinks or dreams about the object of the quest. There are two kinds of quests: Where the protag is given an item and must bring it to a special place and destroy it, or where they learn of an item and they seek it out, thinking it will help them with their main quest.
Here are some quest items, along with their tags. The tags were meant to add extra rules to the scenes (e.g. an item tagged "egyptian" might trigger a vision with a dog-headed god) I didn't end up making use of them, but it was a neat idea.
One neat note about the item tags, a clever trick suggested by Kate Compton's tracery talk at ProcJam (I wasn't there but I watched the livestream). The tags were generated by simply adding them in brackets to the rules. So the raw results item name such as "Finger Sphere" were something like: "Finger[bone] Sphere[polyhedra][relic]". Then I simply extracted the tags with a regex and stripped them from the name. This was a really useful trick to be able to embed metadata into the textual rules that I'm sure I'll make more use of in the future.
If there's less than five people in the party, then there's a 50% chance that we will insert a "add character" scene whenevery they are in a city. There's a cooldown so we don't do this immediately after just adding someone. The party loses characters when they are killed during combat scenes. This ended up being pretty buggy, there will frequently be scenes discussing "the party" as a group when only the protag is present, or even conversations with themself. If I were to do this over again, this would be one of the things I'd want to do differently.
Once the scenes were planned out, the generator walks over the list of scenes, then generates a list of rules for the scene and then feeds those rules to Tracery. Tracery was really the workhorse of the project, and is a super useful and fun tool. I used several different approaches to generating the scene rules for different kinds of scenes, that was really the main experimentation of the project. It was very interesting to discover the strengths and weaknesses of the different approaches. Overall, I'd say the approaches fell into a spectrum between Templates and Simulation, more on that in a bit.
When generating the rules, I started with a set of "Common Rules" which were just useful stuff I stuck in a giant Tracery block and added to every scene. For example, my favorite common rule was #it_gave_feels#, which I could drop in anywhere I wanted the protagonist to be reflective for a moment (For example, "He felt sad, but didn't dwell.") I also had generic rules to add variety, for example I could say #daytime# and get 'morning', 'evening', or 'afternoon'. One thing that I found was that it wasn't very useful to have very broad rules, it was much better to use this for variations that kept within the same context.
In addition to the common rules, the terrain played a big part in generating rules. Each terrain type would insert a bunch of rules about the weather, the ground, the local wildlife, etc. The most useful of these was #natureThing#, which something like (for "forest") "stump", "lichen", "fern", "#critter#'s den", or "log". Then I could use that in action scenes, saying things like "she crouched beside a #natureThing#", and that would make sense and reinforce the sense of place a bit. I also had seasonal rules so you wouldn't have a snowy scene and then a sweltering hot one, but I think that was a mistake, as I never really noticed it in the text and probably would have been better off throwing them all in there and getting more variety (I did have big dreams of tracking the day and season over the course of the adventure but that was pretty overoptimistic).
Overall, I found the sense detail and descriptive rules to be the most useful. Since a lot of the plot and action needed a lot of context about what was going on, it was hard to generate with the rules, but you can drop "Dewy dew hovered in the verdant air" in anywhere.
The generated story was broken into a list of scenes. I had several algorithms to generate these scenes. Each scene generator got some data about the current state of the story, like who was in the party, where they were, etc, and generated a batch of Tracery rules, which were then evaluated to generate the story text itself.
It was interesting to compare these and see the tradeoffs between being repetitive or having the pre-written text too noticible, versus being just meandering and nonsensical. Here's a breakdown of the different methods I used to generate scenes:
Template scenes were things like the Quests. They were pretty much hardcoded, like a mad-lib, with just a few spots for custimization. These tended to read the most like a real novel, but they were also the easiest to spot repeats. I was thinking maybe I could write enough of these and avoid re-using them within a novel but they are a lot of work to write, since you're pretty much writing straight prose.
I got a little bit of mileage out of these by mixing up the step where the quest-giver gives the item, or reveals the secret of where the item is, but it was still pretty repetitive. I think this might be a more useful approach if I had each quest split into a whole bunch of small steps, but it would still be hard to make them all make sense and you'd still need a ton of them.
The "find a vessel travelling to the next city" scenes are kind of an extension of this idea. In these scenes the party hears of a boat travelleing to where they want to go, but the captain won't let them, and then they "convince" the captain one way or another. These, built with smaller steps, seemed a bit more successful, they were still pretty repetitive but you might not notice this same generator appearing two or three times. However, these were a lot more work to build than the quest scenes.
Scenes like the ocean voyage itself were a lot more descriptive, and I relied more on Tracery to generate interesting scenes with lots of variey. On the other hand, these didn't do much to advance the plot.
Simulation scenes were generated by doing a rudimentary simulation and then "narrating" what was going on in that. There were two main types of simulation scenes. The simplest of these was acutally one of the most effective generators in the whole project. These were "City Scenes" where the protag arrives at a city and wanders around for a bit. It's sort of an "establishing shot" for the location.
These started with a generated description of the city, and then does a number of "idle actions". These were things like walking around, buying fruit, staring at the horizon. These were totally random, but it was interesting to read them as it often created a kind of cause-and-effect feeling in the reader, as they tried to create motivation between the different steps of the little journey through the city. This was definitely one of the things I would expand on, adding more actions and possibilities.
The other case was the only real simulation in the project, which was used for dungeon exploration and combat. This generated the most volume of text but was tedious to read and hard to follow.
The way these worked is they generated a group of monsters, with a leader. The monsters had lists to describe how they moved, what body parts could be hit, etc. Then they all got a random amount of hit points and a very simplified RPG-style combat simulation was run, where the heros and monsters would take turns randomly choosing an opponent, rolling to hit and if they did, damaging one of the monsters. If monsters or heros ran out of hp, they died, and when the lead monster was killed the battle was over. If all the party died, or if the protagonist was killed, there was a special "revive" rule that would dramatically bring them back, as if they had fallen but weren't really dead.
Eventually the battle would end. If the party lost some members they would reflect on this.
While these could be made a lot more interesting with more description and a better simulation rules, I don't think the simulation brought anything to the story. It was complicated and just ended up being a bunch of stuff happening that the reader didn't see. Instead, a better approach might be to generate different profiles of how the tension should rise and fall during a scene, and generate actions to fit that tension. It was fun code to write, at least.
The funnest part of this was coming up with actions and reactions for the Bard characters. That was just silly having a character armed with only a lute or something using it against skeletons and zombies.
The type of scene that was everyone's favorite was a bit of an accident, and also somewhat of a cheat. In the Corpora dataset there happened to be a list of tarot cards and their meanings. Each card had a list of "light" and "shadow" meanings -- ways that the same card could be interpreted in a positive or negative light. For example, The Chariot could be interpreted as 'Basking in the glory of achievement' but also as 'Resting on your laurels'.
I used these to generate dialogue filler between characters in the party. I just picked a random card, and had one character accuse another of one of the negative meanings. They defended themselves with a positive meaning, and went back and forth a few times like this.
These scenes worked out really well, because the tarot meaning had some resonance and because, just like in real writing, having some back-and-forth dialogue between the characters was a nice break in the action.
However, I think these also demonstrated that you need a lot of content even for generated scenes. These scenes were only good because there was a lot of topics and each one had a handful of lines so the reader was unlikely to notice repeats. Like the fruit, this seemed like one of the more successful approaches to generating text: find existing datasets and shoehorn them into the structure, rather than trying to build everything.
Chapters and Typesetting
The typesetting part took all of the generated text, and made the essentials for a fantasy novel: A cover, a map, and typeset the text itself.
The covers got the most attention, they were pretty simple but really fun to come up with. Basically I took a bunch of public domain artwork, and then took some classic book covers from images I found online and masked out where the titles and images were, and then created a set of templates that could mix and match the artwork, frames, and knew where to put the titles and subtitles. I found some fonts that were good fits for the genre. Some of more modern style templates could swap out the color palette and recolor the artwork to give more variety. Finally, I generated some random titles and authors and series names and stuck it all together.
Next it stuck in the maps. I wanted to make these stylized so they looked like a hand-drawn fantasy map but I ran out of time and it just ended up with the debug drawing code that I was using for the map-gen. Still, it helped feel like a real fantasy novel and was a lot of fun to trace the hero's path through the world over the course of the story.
I wanted to put more front matter in, stuff like the publication date, maybe a dedication or an introductory essay or some author blurbs. That would have been a lot of fun to generate but my time was better spent adding more templates for scenes and stuff like taht.
Typesetting the book itself was pretty straightforward, I used the 'fpdf' python library and it just spits out the book a page at a time, adding a footer with page numbers. One thing that was useful here is that I could clean up debug text at this stage (removing TODO stuff) rather than have some smarter way. Another thing that surprised me was how much of a pain it was punctuating the generated text correctly. I basically just gave up on it, and there are sentences everywhere missing a period or having two or three extra. Trying to encode the punctuation in the Tracery rules was really hard, as you didn't know if an optional phrase was going to appear in the end, middle or beginning of a sentence. I think a better approach would be to generate the text without punctuation (but with hints, such as markers for where phrases start and end), and then just punctuate it at the end.
What I Learned
I only spent a month on this, as a side project in evenings and weekends, so I wasn't really expecting to get actual readable novels out of it. But the project gave me a chance to try out a lot of ideas that I had kicking around, and get a sense of what works and what doesn't. Some tips I picked up for procedural generation that I think apply to anything, not just novels:
The best results come from a good mix of content and systems. No matter how clever your generator is, without a lot of content to draw from it's going to end up with repetitive results. But also if you have a huge corpus but a simple system without much knowledge and structure of what it's generating, you're going to get "plausible nonsense" that seems ok at a glance but falls apart quickly. Deep learning approaches might seem like an exception to this, but I think it still applies, as they can build up higher level structure behind the scenes as part of their black box.
The most sucessfull systems were the ones that would mix-and-match two or three systems. This allowed things to create enough variety without feeling repetitive, but also have enough structure to hold together.
A lot of generative writing is the opposite of real writing. Rather then trying to avoid cliches, the generator was most successful where I tried to encode cliches. They gave it a ring of familarity and were recognizable. Also dumping in lots of "purple" descriptive prose helped the text feel more realistic, even if it wasn't anywhere near "good".
But I think overall, the biggest takeaway was that I realized that we're lacking a lot of tools and abstractions in narrative generation, at least when compared to visual image generation. I've done a lot of work in image generation in games and film vfx, and there are many different well-studied representations of a scene at widely different levels of abstraction. A scene might start with a Simulation, which could be represented by some very high level game state about the Player, the AI, where they are, what they are doing, etc. as well as the physical properties of the scene such as mass and velocity and collision volumes.
At a lower level, a game engine maintains a data structure of what items are in the scene and where they are and their properties. This is often represented as a scene graph. Most of what high level game code does is updating this simulation, and rearranging things in a scene graph based on how that simulation has changed. Then the game engine will take that scene graph and decide what the most efficient way to turn it into a bunch of triangles to send to the GPU. Then we have hugely powerful, specialized hardware that boils this down into pixels.
The point of this is if you were doing procedural generation for a visual context -- generating artwork or game levels or something that, you could work at any of these different levels of abstraction. From a cellular automata that worked at the pixel level, to a city generator that works at the simulation or scene graph level, there is a lot of flexibility. Often a generator will work at multiple levels, perhaps using pixel-based algorithms to generate individual textures, shape generators, and whole scene templates.
In narrative generation, we don't have these levels of abstraction. We have things that dump out words. But most of the interesting problems are at the higher levels. How do you represent an argument, or a fistfight? What's the data structure for a love affair? That sounds glib, but I'm serious: think about how many options you have to represent the visual structure of a character, vs. how many options you have to represent their emotional state and relationships. A character in a game today could easily have several hundred megabytes of data storing their shape, surface and movements, and yet storing 4 kilobytes of state data for AI would be considered a lot (and I bet most of it would be related to pathfinding).
So I think before we can really generate interesting and convincing stories, whether these stories are presented as novels, or game missions, or procedural dialogue and backstories in NPCs, we need to figure out better ways of representing narrative at different levels of abstraction. Beforce we tackle generation, we should figure out how to represent and even hand-author stories above the crusing altitude of a word processor. Imagine if we had some kind of data structure to represent the events of a novel in a more general way, even if that was a very granularlist of events, the fascinating projects that that would spark? You could generate and compare the same scenes with different styles, converting events into a florid romance or a reserved New Yorker voice. Or target another language. Or imagine a story editor that worked at the plot level, allowing you to drag around ideas and conflicts and see how that adjusted the story. It would be an amazing tool for writers, even if the task of generating the text from a step outline was left to the writer.
There are some projects out there working on this, such as some of the research in the upcoming Procedural Storytelling in Game Design book (which I am extremely looking forward to reading), and projects like Molly Rocket's 1935.
I've got a couple of things in mind, moving forward. First is playing with ways to do some of the above ideas, in the context of game stories and missions, where you really don't need an in-depth story, just an interesting setup, possibly a twist and some kind of resolution. I think even bookending game levels with something like this would be fun and add a lot of context and depth to gameplay.
I'm also going to look for ways use more to generative stuff into current projects. Working on Neo Cab, I did a little experiment to generate store names using Tracery which was fun and generated some great stores like "Connecticut Milkshake" and "Workout Casino". It didn't fit the serious tone and tight narrative of Neo Cab, and also didn't have any gameplay purpose, so we didn't go further with it but I think this kind of thing can be a great way to fill out game worlds without having to hand-create huge volumes of content.
I've got a couple of side projects that I'm looking at using some of these ideas in, one of them is a road-trip themed word game and am playing with generating short (like a couple of sentences) flavor text at the end of each level, funny events that are good or bad depending on how well you did in the level. I've got another game that's really not out of the idea stage yet, but it centers around sort of story based procedural missions. These wouldn't be the deepest stories -- just some short paragraphs to set up quests like "find the six moonrocks of Haar" or "Slay the kragnon that is attacking our town", along with some NPC dialogue to support that -- but that's about the right level of complexity for the kind of generation I can pull of right now.
It's been really exciting to watch (and take part in) the rise of narrative games recently. Like every other aspect of game production, eventually the bottleneck becomes content: you can't make a huge, sprawling open world without talented environment artists, and you can't make a compelling narrative game without talented writers. And the more interative the narrative is, the tighter the bottleneck, as you end up with many hand-authored story branches that aren't explored by the player. So just like we can use procedural generation as a force multiplier to build terrain, place trees and populate biomes, and generate game environments orders of magnitude larger than could be done by placing every rock and tree, I think we can someday create tools to create narratives, both interactive and linear, that are guided and shaped by writers but can contain more possibilities than anyone could type out in a lifetime.