Sponsored By

Featured Blog | This community-written post highlights the best of what the game industry has to offer. Read more like it on the Game Developer Blogs.

Fortnightly summaries of videogame research. This week: generating puzzles from easily reusable templates!

Michael Cook, Blogger

September 14, 2013

11 Min Read

monkey-island1

When it comes to actually designing games, rather than just talking about doing it (as we often do in The Saturday Papers) simplicity is key. Although there are many weird and wonderful pieces of research out there to read, enjoy and think about, many of them are tricky to implement yourself in a game you might be making solo, or on a tight schedule. But we still look for ways to add a technical twist to our games, whether through procedural generation or some unusual new interaction method. This week on the Saturday Paper: how to generate simple puzzles by just throwing a few dice. Sort of.

We're reading Procedural Generation of Narrative Puzzles in Adventure Games: The Puzzle-Dice System by Clara Fernandez-Vara and Alec Thomson. It describes a puzzle generator that was iterated upon and used in two games: Symon and Stranded in Singapore. By breaking puzzles up into small components with simple connectors the system can easily construct new puzzles for the player, and templates are simple enough that anyone can add new ones - potentially opening up a cool new avenue for user-generated content.

Screen Shot 2013-09-12 at 14.00.19

Before we go on, take a look at either Symon or Stranded in Singapore to get a feel for the kind of puzzle output the system was capable of producing. Symon is earlier work than Stranded, and you'll be able to see this probably in the variation of puzzles on offer (although Symon is secretly my favourite of the two games). If you've played many adventure games you might have noticed that the same structure of puzzle tends to crop up a lot. The Puzzle Dice system, at work in both of these games in different forms, uses this template-based nature of puzzles to its advantage, by specifying templates for puzzles that can vary in their main details to recreate a puzzle multiple different ways. Here's an example of a template, from the earlier version of Puzzle Dice used in Symon:


NPC [state1] wants item1 [state2] to change NPC to [state3] -> player gets [item2]

The square brackets are attached to the word before them, and describe some property of that object. To give an example, here's a concrete version of the above template, as it (can) appear in Symon:


children [asleep] want music box [raspy] to make children [awake] -> get [family photo]

Here you can see the children have a property of being asleep or not, which the music box object is capable of changing, granting the player a new object. The objects, as well as the properties they have, are described in a big object database that a game designer can easily edit. We'll get on to how the system fills in these templates later: first I want to talk about how you go from a single small template to a fully-fledged puzzle adventure game.

Screen Shot 2013-09-12 at 14.21.06

 

 

 

 

 

 


In Stranded In Singapore these puzzles are expressed as lists of events that happen in chronological order. This lets us refer between puzzles to link them together. For example, instead of having a puzzle template simply be getting an object and swapping it for another one, we can link the reward object (the one the player gets for solving the puzzle) to a condition for a later puzzle. Here's an example from the paper that shows what I mean (this is a template that has already been filled in):


Librarian is in the quad → Librarian wants a banana [green] → player gets key to the Library → Professor is in the library → Professor wants a book [old] → player receives a good grade.

The important bit here is the key to the library. It's both the reward for the first puzzle (finding the banana) and the prerequisite for starting the second puzzle (finding an old book for the professor). When you look at this, it seems very simple and obvious - locking a player out of a location until they make progress is Adventure Games 101. But finding a way to describe it neatly so that a computer can reuse it is really important.

So our puzzle games are now sequences of action templates, with some simple parameters that let us vary objects, people, locations and so on. We've got a database with information stored in it that relate to these templates. How do we combine the two to generate fresh puzzles for our players to solve?

Screen Shot 2013-09-12 at 19.19.05

Puzzle Dice starts from the ending, and works backwards. You give it what you want the output of this particular section of puzzles to be, along with any properties it might have, and it searches the database to find matching objects and relationships. Relationships are the way that Puzzle Dice links objects together, through things like actions (combining two items) or interacting with characters (requesting or exchanging items). Once the system finds the required output, it will then work backwards to produce a chain of relationships.

Let's go back to the Professor example above: we start off wanting the output of a good grade. The system then works backwards - what kind of inputs might result in us getting an object in this way, with these properties? Puzzle Dice can look at the puzzle types that it knows of (request puzzles, for instance, which exchange one item for another) and the database of items it has, and fill in the blanks to produce a request puzzle where a Professor character can exchange a book for a good grade. This is then translated to a relationship, linking the Professor, the book and the reward of a good grade in the resulting game. Note that at this point we don't know that the Professor is in the library, or that the library is locked, or anything else - this will all be generated later, as we continue to step backwards along the timeline.

Screen Shot 2013-09-12 at 19.22.39

Clara and Alec developed tools that allowed designed to work directly with these types of data - editing the object database to add new objects with certain properties in, for instance, or describing new puzzle templates that have certain requirements and outputs. But I think the basic idea works well without these tools, and I can imagine implementing it in my own games for a quick and effective solution to puzzle generation. One of their objectives was to separate the act of describing puzzles from programming the game, which meant that game designers could work on puzzles without having to talk to the programmers, which is time consuming in some cases, and impossible in others. But it's a really elegant idea, no matter which way you look at it.

The other interesting side effect of avoiding programming is that the system is a good candidate for user-generated content as well. Objects and properties are relatively simple to define, and given enough basic building blocks to construct puzzle templates out of, you could definitely imagine a sort of Sleep Is Death-style adventure game generator that could help players design a puzzle game by taking descriptions of game worlds and the objects that populate them. If you supply enough basic building blocks in advance, and the right definitions for properties that objects can have, a user could easily tap in their own theme for a game, and filter puzzles themselves to find ones they like.

Where To Find More

Don't forget to check out Symon and Stranded in Singapore on the MIT Gambit site. Clara is currently an Associate Arts Professor at the NYU Game Center in New York City, while Alec is recently graduated from MIT Gambit, and is now a grad student there. Both are very active game developers themselves, as well as producing cool research, and I think of them as having really practical approaches to problems like this. Don't hesistate to approach them to find out more about the work!

Announcement - Meetup in Boston, October 14th!

I'm going to Boston for this year's AIIDE Conference, where I'm also co-organising a workshop. On the evening of the day of the workshop there's going to be an event called DAGGER where there'll be games to play from academia and the local gamedev scene, some snack food to have, and lots of people from both the conference and Boston gamedev to chat to and get to know. It's going to be great!

Click here to grab a free ticket from Eventbrite

Read more about:

Featured Blogs

About the Author(s)

Daily news, dev blogs, and stories from Game Developer straight to your inbox

You May Also Like