Jan 16

Random Story Generation Part 1: Nothing More Practical Than A Good Theory

A visual depiction of how a Markov Chain story generator works.

I’ve decided to document my experiments in random story generation, in the hope that these notes will be helpful to other developers and hobbyists. This first post will define some of the terms I’ll be using and introduce some of the theory.

My first idea for a random story generator came during a literary criticism class I took during university. We were learning about reader response criticism, which is a model that focuses on the interaction between reader and text. In RRC it doesn’t make sense to say that a text has an inherent meaning; instead, meaning is something that is actively constructed by the reader through the process of reading. The author of the text, and whatever they intended the text to mean, doesn’t enter into it. If we don’t need to worry about authorial intent, why bother with an author at all?

The next piece of the puzzle came from Scott McCloud’s explanation of closure in Understanding Comics. A comic consists of a sequence of separate images; the reader uses closure to combine these images into a coherent story. I realized that the same would apply to a series of short narrative arcs in a computer game. Even without intentional connections between the arcs, the player’s sense of closure would interpret them as a meaningful story.

Finally, Vladimir Propp’s narrative functions provided a way to arrange these arcs so that the reader/player would be likely to interpret them as a coherent story. Propp analyzed Russian folk tales and discovered that all of their plots could be constructed from a finite list of story events which always appear in the same order.

From all this I got the idea to create a big list of story fragments, then use some kind of algorithm to arrange them into reasonably intelligible sequences. Turns out that’s pretty much how all procedural story generators work, even today.

I named the smallest narrative chunk a Plot, which I will capitalize to differentiate from the regular use of the word. A Plot modifies the game world for as long as it is active; it might alter an NPC’s dialogue options, or add an encounter to the world map. In GearHead-1 the Plots are quite coarse, defining an entire mission or a chapter of the core story. In GearHead-2 the Plots are much smaller; a single combat mission might consist of four linked Plots- one for the NPC offering the mission, a separate Plot defining the mission’s combat encounter, a Plot that is activated if the PC wins the mission, and another that is activated if the PC loses. The Plots in Dungeon Monkey Eternal are even more finely grained.

Using lots of small Plots is much better than using few large Plots. First off, if a quest is composed of multiple Plots, it means that the player won’t know how it ends just because they’ve seen this beginning before. Second, it allows reuse of code, which is a huge advantage for both bug control and refactoring. Instead of every mission having to define its own combat encounter, they can just call for a standard combat encounter Plot. Third, it greatly increases the number of combinations your system can generate, and in general you want your random plot generator to be able to generate a really really big number of combinations.

There are numerous ways to arrange Plots, including Markov Chains and context free grammars. The important bit is to have some way to describe the context of a Plot, so that Plots which belong together get placed together. Next time I’ll describe how the GearHead-1 core story context system works. Let me know in the comments if you have any questions.

Dec 15

Painting Fantasy Portraits

To practice both painting and faces, I’ve started doing fantasy portraits. Once I get enough of them I’ll upload the set to OpenGameArt.org and maybe incorporate them into Dungeon Monkey Eternal.

I wanted to do the pictures in traditional media because in my mind that’s how classic fantasy portraits are supposed to be done. Obviously I am not going to achieve the same kind of look as Larry Elmore or Jeff Easely but I have confidence that with enough practice I can do something that isn’t entirely terrible.

The dwarf at the top of this post was the first one I did. It’s in watercolor, which I think was a mistake, and I won’t be using that again (maybe). The human was second, and the orc was third. These were done in acrylics. Both the dwarf and orc are modeled on my own face. The human is based on a photo from atistatplay.deviantart.com.

Dec 13

There’s a new open source FreePascal scifi roguelike in town…

Well actually, it isn’t exactly new. After receiving a letter from ZeniMax, Kornel has shortened the name of this beloved game and released the source. If you have never played D*** the Roguelike before, now is a great time to give it a try.

Dec 08

Dungeon Monkey Eternal now installable

I’ve made two quick changes to Dungeon Monkey Eternal. First, I’ve cleared most of the source files out of the root directory. Second, I’ve added a working setup.py packaging file. The good news is that it should now be much easier to pack the game for Linux distros, create an executable version for Windows, and otherwise move the game around. The bad news is that this update breaks all previous save files.

I’ve also been making some progress with GearHead2, and hope to make a new release of that game before the new year.


Nov 23

My Secret Life as a Mad Scientist

Just in case you were wondering what I was doing all October.

Nov 21

ITM-01 Claymore


Once it was king of the battlefield; now its name is synonymous with obsolete. The Claymore is the oldest mecha design still in common use on Earth. This longevity comes from its rugged durability and ease of manufacture.

The standard ITM-01 configuration comes with a heavy autocannon, a shield, twin light autocannons in the torso, and twin five-slot missile launchers in the legs. The launchers are typically stocked with crude but effective high explosive rockets. This can sometimes cause a problem as an ammo explosion in the leg can leave the mecha immobilized.

After the night of fire destroyed most factories on Earth, the Claymore was one of the first designs to resume production. It can be built from plans without need for special materials, tools, or techniques. Because of this it was a mainstay of most defense forces during the exodus era, and remains a common sight throughout the dead zone to the present day.

Unlike the Buru-Buru, which has a large community of enthusiasts, there is little romanticization of the Claymore. On Earth, there have been few attempts to update the Claymore with modern technology. Certainly, most of the workshops that produce Claymores lack the skills to change the design, and so just keep following the ITM-01 specifications.

On Mars it’s a different story. Here, the Claymore has been incrementally modified and developed into a wide variety of new mecha. The Longsword battroid used by the Martian Commonwealth Loyalists is a fifth generation descendant of the Claymore.

The picture was made using Jo Sonja acrylics on Canson acrylic & oil paper. One good thing about painting a mecha, as opposed to simply drawing it, is that you have to really consider it as a three dimensional thing rather than just worrying about lines on paper. I’m pretty happy with how it turned out.

Nov 18

Good Week for GearHead2 Development


I’ve managed to get a lot of stuff done with GearHead-2 this week. The resizeable interface seems to be working all over. The expanded gender and romance options from GearHead1 have been incorporated. Several bugs have been fixed. Work on a new title screen has begun. No promises, but maybe there will be a new release next week.

Nov 16

Jupiter Hell on Kickstarter

Korlel Kisielewicz has just started a kickstarter for his new game, Jupiter Hell. It’s an old-school roguelike with a modern interface and graphics. If you enjoyed DoomRL, then you should definitely check this one out.

Nov 08

Procedural Texture Generation

Last week I mentioned that I’ve been playing around with procedural texture generation. The method I’ve been using takes an image sample, analyzes it, and then tries to reproduce its texture in several ways. For example, take this picture of grass from the public domain West’s Textures set.


The source image shouldn’t have too many colors in it, so before feeding it to the texture generator I edited it in Gimp and posterized it down to around 10 colors.

The first texture generation method is shuffle, which just takes all the pixels from the source image and spits them back out in random order. This is good for generating a noisy texture which has the same color composition as the original, but the output lacks structure.


Next, I tried a markov chain, which records left-to-right pixel patterns from the original and tries to replicate these in the output. This one has a bit more structure to it, but the generated texture often appears streaky.


Next I tried another markov chain type algorithm, but instead of checking the state of the previous three pixels it examines the pixel above, behind, and to the upper left of the pixel to be drawn.


Finally, I tried an extended version of the above algorithm, which looks at more nearby tiles and falls back to a previous algorithm if an unknown seed case is encountered. Sometimes this seems to improve the results and sometimes it doesn’t.


You can see the Python script I used below the fold. Read the rest of this entry »

Nov 03

GearHead2 New Shopping Interface


I’ve ported the new GH1 SDL shopping interface to GH2. A few things still need to be modified- the item images don’t show up yet because the GH1 code I copied and pasted doesn’t use them, and the descriptions for some item types don’t seem to be working right. Next stop: the character creation and training interfaces.

Also, I’ve been trying to procedurally generate new ground sprites using colors taken from old Sunrise mecha cartoons. This is grass. I’m not sure how it’s working yet; I want to see it in action before I judge.


Older posts «