Generative grammars as a form of procedural content generation
This discussion started out as just an introductory section as part of a larger discussion on graph grammars (or graph rewriting, if you prefer), but I came to the realization that I really wanted to talk about each a bit more than would make sense for one post, so here we are. Generative grammars have a bit of a limited use in game development, especially since graph grammars can do everything they can do and more, but I came across some interesting uses for them that I think is worth discussing. Plus, the concepts introduced here will carry over into graph grammars nicely, so let’s dive in!
The basics
Generative grammars are a fairly broad area of study, with applications related to language parsers, text prediction, and more, and I’ve found it a little hard to succinctly define the term without getting overly academic, but I think that as far as we’re concerned in regards to game development, we can define the concept simply as a sequence of words (or “sentence”) with rules regarding how and when to replace some words with other words. A bit vague, I know, but bear with me as it’ll make a lot more sense with an example.
(As a side note, if you want to know where the phrase “generative grammar” comes from, one of the definitions of the word “grammar” is the “rules of a language governing the sounds, words, sentences, and other elements, as well as their combination and interpretation.” If we combine that with the word “generative”, then we know we’re doing something in regards to generating words or sentences based on the rules of the “language” we’re using.)
An example
Let’s say we want to generate a small, linear dungeon experience not unlike a Zelda dungeon.
If we wrote out the flow of the level using words, we could start with a basic template “sentence” like the following:
Entrance > Room > Room > Room > Boss > Exit
The Entrance, Boss, and Exit in this case will be fixed, since we know we always want to start with a simple entrance room so the player can take in our awesome atmospheric design for the level, and end with a big, climactic boss fight. But what about Room? That’s not very descriptive or interesting, so let’s look at a few options we have to replace a room with something better. As a good start, could replace our template room with a puzzle of some kind, a combat encounter, or we could have a treasure room to reward the player with gold or a valuable item. And there’s no reason we have to stick with a measly three rooms, so perhaps we could also replace a room with multiple rooms. If we limit ourselves to never replacing Room with more than two words at a time (mostly just so I don’t have to write as much out in the following table), all the possible permutations become:
| Word | Replacement |
|---|---|
| Room | Room |
| Room | Puzzle |
| Room | Combat |
| Room | Treasure |
| Room | Puzzle > Room |
| Room | Puzzle > Puzzle |
| Room | Puzzle > Combat |
| Room | Puzzle > Treasure |
| Room | Combat > Room |
| Room | Combat > Puzzle |
| Room | Combat > Combat |
| Room | Combat > Treasure |
| Room | Treasure > Room |
| Room | Treasure > Puzzle |
| Room | Treasure > Combat |
| Room | Treasure > Treasure |
| Room | Room > Room |
| Room | Room > Puzzle |
| Room | Room > Combat |
| Room | Room > Treasure |
Now we can scan our sentence and replace every instance of the word Room with one of the possible replacements. Since we can potentially add additional rooms with each replacement, we’ll do this scan-and-replace over and over until all instances of the word Room have been replaced. We could alternatively show off our programming chops and do a recursive solution for each replacement that only has to iterate over the sentence once. Either way is fine as long as we end up without any empty rooms in our layout. Since this is a completely random operation, we could end up with something simple (and boring) like this:
Entrance > Treasure > Puzzle > Treasure > Boss > Exit
Or we could end up with something extremely long and grinding, like this:
Entrance > Puzzle > Treasure > Combat > Combat > Treasure > Puzzle > Combat > Puzzle > Combat > Treasure > Puzzle > Puzzle > Combat > Boss > Exit
Not the greatest algorithm, huh? But, here’s where the cool thing about generative grammars comes into play: We can code up any rules we want for replacement. We started with random replacements because that’s easy, but that was completely arbitrary. We could require minimum and maximum dungeon sizes, for instance, and consider these more specific and rule-driven replacements that will create a more “handcrafted” experience:
| Word | Replacement | Rule |
|---|---|---|
| Any word | Mini-Boss + Treasure | Middle-most Room in dungeon |
| Any word | Rest (healing, consumable replacement, etc) | Last room before Boss |
| Treasure | Room | If not preceded by Puzzle or Combat |
| Combat | Easy Combat | Combat in first third of dungeon |
| Combat | Medium Combat | Combat in middle third of dungeon |
| Combat | Hard Combat | Combat in last third of dungeon |
We can get as specific as we want, even making very specific custom content that will be swapped into the level just to add a bit of randomization to it:
| Word | Replacement | Rule |
|---|---|---|
| Puzzle | Bow and arrow time trial | Only possible once the player has the bow |
| Boss | The Great Conqueror | Any late-game dungeon |
| Treasure | The Cool Stick | Required. Any treasure room in the forest dungeon |
Hopefully by now you’ve got a pretty good idea of what this technique can offer: Procedurally generated content that is as random or handcrafted as you want it to be. Going for more of a roguelike experience? Just define some interesting patterns (like Mini-Boss + Treasure) and let the generator work from there. Want to make all of your game’s content manually, but just make each player’s experience slightly different? Get very specific with when and how you do replacements.
Other potential uses
And, of course, this method doesn’t have to be just for deciding how dungeon rooms will be laid out since we can use any strings we want to describe content. We could describe actions the player will take for a quest:
Go to village > Learn of nearby goblin camp > Go to goblin camp > Kill goblins > Go to village > Get reward
We could also generate story beats based on sets of archetypes and patterns:
Go to mysterious house > Discover great secret > Spend time contemplating what to do > Rise to the occasion
Naming people, places, and items is another good use case. We can define basic rules, like Adjective > Noun to get simple names (Vile > Lagoon, for instance) or use geographic properties about the location to make a more cohesive world (Maybe different regions of your world have different dialects, which will affect which rules are valid, for instance).
There’s really no limit to what you can do or describe since everything is just words joined together at the breakpoints you decide. Grammars also come with the benefit of being human readable, and therefore also writable. With a system like this, a non-programmer (such as a level designer or player) could manually write what they want and have the system parse it. Pretty neat!
A really cool quest generator
So now let’s talk about my favorite implementation of generative grammars I’ve come across. There’s a paper, A Prototype Quest Generator Based on a Structural Analysis of Quests from Four MMORPGs (Doran and Parberry, 2011), that is really cool. I highly recommend you check it out for yourself as it’s a pretty approachable read, but here’s the gist of it. The authors analysed hundreds of quest patterns in MMORPGS and used generative grammars to procedurally generate quests of varying complexity and intrigue. They modeled quests as a combination of motivations (Knowledge, Conquest, Reputation, etc) alongside a series of strategies for satisfying that motivation (Spy on someone, kill an enemy, obtain a rare item). Each strategy is then broken down into a sequence of actions that can be replaced to generate content. Each action can then be further broken down into “subquests” that let you layer in complexity.
As an example, maybe the quest starts out as a farmer saying “My finest cow has been stolen, please get it back for me”, but you end up having to investigate the location it was last seen, discover tracks leading to a bandit hideout, kill or negotiate the information of what they did with the cow, buy or steal the cow back, and then protect it from more bandits on your way back to the farmer. Sure, it’s not going to win any awards for writing, but it’s better than constant “There’s a settlement that needs your help” type quests. Plus you could layer in lots of lore and let that drive the decisions you make to help reinforce your worldbuilding. Maybe this part of the world is the only area bandits are found and they’re highly motivated by money, therefore they tend to be behind crimes with a financial lean and their quests always have an option to buy your way out of a situation. Maybe nobody steals animals in the desert province because they have harsher penalties for it, or they’re just more careful about their crimes and you’ll need to do more spying and smooth talking to gather information.
The point is, there’s a lot of ways you could go with this idea if you define the rules, people, and cultures of your world and use that to help drive the generation.
The catch
I lied earlier. There’s one big limit to this method, and that is the fact that it is one-dimensional. There’s no concept of space or non-linearity. You can model non-linear gameplay if you want, but it get’s messy quickly. Consider this example sentence to describe unlocking one door in a dungeon:
Entrance > Enter room A > See Room B is locked > Enter Room C > Get Room B key > Go to Room A > Unlock door to Room B
That’s a lot of words for what is probably a tiny section of our dungeon and once we map out the whole dungeon, it’ll be hard to follow. Sure, we’ll code up a nice parser and let it do the work, but debugging will be painful as well (Situations like “Wait, is a room out of sequence here?” followed by several minutes mentally or physically mapping out the space will happen). Plus, we still have to figure out how to spatially fit everything together and code up rules to make sure we don’t make impossible spaces.
The solution is the multi-dimensional cousin of generative grammars, but I’m going to save that for another post. Just be aware that there is a better, and more commonly used, way to set up spatial and non-linear layouts.
Thoughts on implementation
There’s no code this week, as there’s just too many ways you could code generative grammars, and the use case will really drive the implementation. My immediate thoughts, which I kind of hinted at earlier, would be to start with a list (or linked list if your language doesn’t support dynamically sized arrays like that) of words, or objects representing words if you need to keep some metadata attached to each entry, and just use a simple while loop to iterate the list over and over until all your conditions for generation are met. If you want to get a bit more sophisticated, you could recursively call a replacement function on words that qualify for replacement so that you only have to iterate the list once. You might still need a few more passes in case you want to make adjustments like placing a mini-boss at the middle of the final(ish) dungeon, but again, that’s why I’m not offering a code solution and instead just a general direction I’d start with.
Conclusion
And that’s an introduction to the concept of generative grammars for game development. Hopefully you found it interesting and got some good ideas out of it. At the very least, the concept of rules-based replacement should be something to keep in mind when generating content, as it makes it easy to use whatever generation method you prefer while still providing thoughtful experiences for the player. Next time, we’ll take this concept multi-dimensional and look at graph rewriting techniques.