The procedural content generation in Mainframe uses a very simple mechanism, which is both more powerful and trickier to implement and use than I expected at the outset. That mechanism is tagging. You tag bits of content, and then somewhere else you say you want something with a given set of tags.
One of my theses about interactive storytelling is that selecting, adapting, and combining bits of authored content is an approach that is powerful, underexplored, and pragmatic, in that it offers a smooth learning curve from simple and known to, I hope, complex and new. Mainframe is, among other things, an experiment with this approach.
Tagging is one of the more interesting ways to select content. I first saw it used in 2008 as the interface between the AI and the audio system in LMNO. Back then I was mostly impressed by how it reduced the production dependency between AI and audio.
In 2010 and 2011, I worked on an unreleased Diablo-like that used tagging to procedurally generate levels. I did a lot of work on the level design and tool chain. At GDC in 2012, I saw Elan Ruskin's talk about the dynamic dialog system used at Valve, which used an advanced tagging approach to allow writers to create dialogues. In 2012, we used tagging to select texts in a mobile game. I remember vividly how the actual tagging logic consisted of one line of code, but it took three of us a day to write that line. (It was a LINQ expression in C#, if you're curious.)
The system in Mainframe is really simple. The core logic is this function:
def tags_are_matched(_desired_tags, _available_tags):
for desired_tag in _desired_tags:
if desired_tag not in _available_tags:
return False
return True
(Python nerds: I know this can be written in one line.)
All it does is check for a given thing whether that thing has all the tags we want. Very simple. For the Diablo-like, we added a "nice to have" qualifier, and I really wanted a "NOT this tag" qualifier. But in Mainframe this was perfectly sufficient.
Liz could write something like:
<injectOption tags='option, containers' />
and the engine will look through all of the scenes for one with the tags 'option' and 'containers', and will then inject a link leading to that scene into the current scene.
A nice little feature in Mainframe which made a big difference is that a desired tag can be a reference to a variable, as well as just a literal tag. So this line:
<injectOption tags="computer_talk, $flesh_act" />
makes the engine look for a scene that has the tags 'computer_talk' and whatever the current value of the 'flesh_act' variable is. (To understand why it's called 'flesh_act' you have to play the game...) This allowed us to change the game depending on the act of the main storyline the player is in.
Instead of scenes the engine can also inject 'blocks'. Liz mainly used this to inject flavor text depending on game state, but we also used it to factor out common logic, like this:
<!-- Used to init variables when the player respawns. -->
<block tags="pc_init">
<!-- reset all values other than main story act & total data -->
<action act="set $has_mcguffin 0" />
<action act="set $is_fed 0" />
<action act="gen_data" />
<action act="set $sacrifice 0" /> <!-- player has not sacrificed body parts for data -->
<action act="set $injury none" /> <!-- player's current injury, in case we do others -->
<action act="set $commands 0" /> <!-- used for PC to use computer 3x before needing more data -->
</block>
You can see the 'action' element there, used to modify the game state.
Despite me having used tagging before, I still learned a couple of interesting things during the development of Mainframe.
The subtleties of picking
"Pick a scene with the right tags" sounds easy, but there are a lot of subtleties. We didn't want the content to be picked in the order it was defined in, nor did we want every player to see the same content order every time. So we needed randomness.
Our requirements for random picking, combined with the fact that Mainframe is a web-based game without a database, made for a ton of subtle errors. I spent more time debugging and rewriting that part than anything else, and it required cryptographic techniques plus me actually cracking open Knuth's Art of Computer Programming, probably for the first time in my life. I have a draft for a blog post on that lying around, so I won't go into great detail here.
I wrote a class called TaggedCollection, which contains a set of tagged items, be they scenes, blocks, names for the data you find in the game, or whatever. When the get_item_by_tags() method is called, I create a list of items that have the desired tags, then I shuffle it, and pick the next item. I can't store that list (long story), so I regenerate it every time. (It's a game jam, who cares about performance, the lists are very short.) I store a random seed and an index per desired tag set, per player.
Shuffling is OK but not great. The chances of getting the same item twice in a row are low but not zero. If you have three injectOptions in a scene, like we do, you can sometimes see the same item twice, because the list is exhausted, reshuffled, and an item at the end is now at the start. The solution I am currently planning to implement for this is to turn those three injectOptions into a dedicated command, at a higher level of abstraction. This would also give us some other advantages, like being able to control death (some scenes kill the player).
The most intriguing effect of this approach is that rendering the scene modifies state, because of those indices that get increased.
(So what happens when the player reloads the game in their browser? Fun. Fun is what happens.)
I don't know any other game engine that does that: you always want to separate rendering from updating, and in general you want to keep a firm grip on your mutable state. My day job has made me dig deep into Facebook's Flux pattern and immutable data structures, so I am very conscious of state mutation these days.
This is really the most interesting thing I learned about tagging, and I haven't yet decided what I want to do about it, if anything.
Tagging as a programming language feature
Internally - I intend to describe this in more detail in a future blog post - the engine data structures resemble an Abstract Syntax Tree or AST. So it is possible to imagine all the data as a program that produces an interactive fiction game, and the engine is the runtime for that program.
Now, if you follow that train of thought, blocks and scenes become like procedures, because they can contain logic, including logic that modifies game state. Tagging then leads to a programming model where adding or removing a procedure can indirectly affect the behavior of the entire program. If you look at the data as a program that is very strange!
Tagging in production
This was something I had already encountered in the 2011 Diablo-like, and back then I wrote a pretty elaborate tool that read in all the content and analyzed it to make sure all tag demands could be fulfilled. It emulated the server level generation algorithm to make sure we could never break the server through bad tagging. I hooked it into the continuous integration server, because I take it as a personal insult when a bug occurs that is hard to find for a human, but easy for a computer.
What all of this means, apart from that I have minor OCD, is that you need special tools to guarantee correctness when you use tagging. It's not witchcraft, but it does take some effort. I would want to expand that to show not just unfulfilled demands, but also unused content and places that are overly sparse or dense.
Another big issue with this system, and with procedural content in general, is test coverage and state manipulation during development. There is a bunch of stuff in Mainframe that I added but have never been able to really test, because of the random element and the lack of any functionality to directly pick content and affect state. The game is simple enough that I don't think there are any real errors, and we ran spellcheckers over the raw text, but this is a weakness that would cause trouble when scaling to bigger games, and properly implementing this testing and development support functionality is not trivial.
Tagging as story generation
The way we pick tagged content in Mainframe is just one of many. It can be interesting to pick scenes in order rather than shuffled. It can be interesting to stop picking scenes once they've all been shown. It depends on the content. Lots of patterns are possible.
There is an element that can be found in many board games that I like a lot: the event deck. They are simply decks of cards, shuffled at the start of a game, and under certain conditions the top card gets revealed and whatever is on there "happens": players get items, monsters get introduced, stuff blows up, etc. There are lots of variations, and many games have multiple decks.
Event decks are story engines. They represent the progress of time, external events that keep happening, mounting tension, advancing plots. By being shuffled they introduce a random element, and through their design or through other rules, they give the designer some control over the experience.
Tagging is like an event deck. In Mainframe, whenever the player chooses to go on a mission for data, the top three cards from the event deck are revealed (links to the next three scenes tagged "mission" are injected). Because this tagging is done based on the current act, there are effectively five decks. Some scenes are tagged with multiple acts, so they appear in multiple decks. It is very simple conceptually, but quite powerful.
Because the tag can come from a dynamic variable, it is possible to imagine more complex decks. It is also possible, with the higher level injection command I described above, to generally use more complex logic. Because really what is happening is that we look at the player input, at the current state (representing what the player has done), and at the content we have available, and we pick the most appropriate thing to show next. That logic is core to interactivity (it's part of Chris Crawford's definition of interactivity), and, in a game like Mainframe, it heavily involves storytelling logic. We want certain things to come up sooner, others later. We want things to come to the fore or recede to the background, based on what the player has done. We want the odds of certain things to increase based on state - for instance, in Mainframe, it would have been nice to control the odds of the player dying, or the odds of the player encountering... certain things.
All of that starts with a five line function, something that can be understood by analogy with a deck of cards. That is why I get so excited by content selection algorithms, tagging, and event decks, and I hope to dig deeper into them.