Jan 24

Random Story Generation Part 2: GearHead-1’s Core Story

To briefly recap part one, one way to create a random story generator is to write a whole lot of story fragments, arrange a subset of the fragments into a list, and count on your player’s sense of closure to assemble the list into a coherent story. In this part I’m going to look at how GearHead-1 did this.

It isn’t really correct to describe the GearHead-1 Plots as story fragments; instead, each one is a complete (though usually quite short) story. For now I’m going to skip talking about the basic Plots (which comprise most missions and random events) and instead just concentrate on the core story plots.

The core story is the series of Plots leading from the player’s introduction in Hogye to the eventual battle with Typhon. The choice of plots is based on three variables: the identity of the PC’s enemy, the mystery that confounds the PC, and the bad thing that happened to the PC. The possible states are:

PC Enemy

  • Unknown (Or, no enemy yet)
  • Character
  • Faction

PC Mystery

  • Resolved
  • Unknown (Or, no mystery yet)
  • Family Secret
  • PC has Amnesia
  • PC is not Human
  • Searching for Item

PC Misfortune

  • Resolved
  • Unknown (Or, no misfortune yet)
  • PC’s Family Died
  • PC is Incriminated
  • PC is Seeking Revenge
  • PC is Former Member of Enemy Faction
  • PC has a Lost Love

The PC’s starting scenario sets the initial values for these variables. For instance, if the player starts as a defector from Luna, the enemy is set to Faction, the mystery is set to Unknown, and the misfortune is set to Former Member of Enemy Faction. These three variables are collectively referred to as the context.

Only one core story Plot exists at a time. When a new core story Plot is needed, the master list is checked for Plots that match the current context. One of the matches is chosen at random. To continue the example above, from the Lunar defector beginning there are five possible first episodes: the PC could be pursued by a bounty hunter (which requires that the enemy be a faction), a price could be placed on the PC’s head (which has the same requirement), the PC could be sent to rescue a kidnapped professor (which requires that the enemy be a faction and the mystery be unknown), the player could be sent to intercept a secret plan (which requires that the mystery be unknown and the PC an ex-member of the enemy faction), or the PC could be accused of being a member of the enemy faction (which requires that the PC be an ex-member of the enemy faction).

Completion of a core story Plot will result in at least one of the context variables changing. For instance, completing the “Accused!” plot will change the misfortune variable to Resolved. The next Plot will be generated from the new context. This story generation method is similar to a Markov Chain, though I’ve been told that it isn’t exactly one.

There are several problems with the GearHead-1 core story generator. First off, there’s nothing to prevent the story from repeating itself. It can get trapped in a loop, and Plots which don’t alter the context can appear several times in a row. Second, it may be possible to arrive at a dead end- a context which has no available plots. Third, the context variables don’t hold a lot of information- having Aegis Overlord as your enemy is identical to having a local bandit gang or a supposedly law-abiding corporation as your enemy. Next time I’ll talk about how GearHead-2 solved some of these problems… and made one of them much worse.

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

acrylicclaymore

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

gh2_newtitlescreen

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.

s320_grass

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.

out_shuffle

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.

out_markovchain

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.

out_topleftchain

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.

out_xtopleftchain

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

Older posts «