Crossposted from Games by ANGELINA
Puzzles in videogames, especially point-and-click adventures, are strange things. Mysteries and puzzles in movies are all about ingenuity, wits and thinking outside of the box. In games, though, they're about working out what the designer thought was the right solution and finding whatever combination of items is hardcoded to unlock the next Plot Door. Not only does it suck to find your perfectly reasonable solution wasn't the one the developers put in, but having one route to the goal kills any hope of replayability, too. This week on the Saturday Paper, we look at a system that aims to fix both problems at once, by generating puzzles based on real world ideas of cause and effect.
We're reading Smart Terrain Causality Chains for Adventure-Game Puzzle Generation by Isaac Dart and Mark Nelson. The paper describes a new way of generating puzzles for point-and-click adventure games by simulating real-world systems like combustion and carefully planning which items to give the player. The best part is the idea has already been implemented by the authors in a Unity game that you can play for yourself, and the paper even includes some experiments and discussion for how procedural puzzles might be best used. Let's dive in!
Let's start with that title; what is smart terrain and what are causality chains? The former is a phrase that's older than this paper by some margin. Popularised by Will Wright, the term is used to describe items with an awareness of their functionality, like most things in Wright's series The Sims. Objects that make up a smart terrain - like everything in The Sims from the TV to the neighbours - know what actions they can perform, or what actions can be performed on them, like being switched off, used to prepare a meal, or greeted. In your average point-and-click adventure, items aren't very smart at all. Instead they normally have a few specific use-cases in mind that are part of a tightly-designed route through a game. Even if you can use a crowbar to open one door, you might find it magically doesn't work on the next one you find.
If you've played a lot of games like this, you might have wondered if it would be possible to just define the sorts of actions you can perform with a particular item, and let the player figure a solution out themselves. This is precisely what smart terrain causality chains add - they describe chains of actions that can be performed to turn a starting set of items into a solution to a puzzle. For the work in this paper, the kinds of cause and effect involved is often related to physical properties, such as turning ice into water by applying heat to it. As you'll see, though, the technique is general enough to apply to just about any kind of cause and effect you can think of.
Here's how the system works: you start off with a list of actions that can be performed on particular objects. Each action has a cause and an effect. Here are two examples from the paper:
You can probably work out what each one says. A sprinkler has an 'activate' action that is caused by smoke and has the effect of producing water. Paper has a 'burn' action that is caused by fire and produces smoke. You can also begin to see how chains can be built up, by linking the effects of one action to the cause of another. If the player needs water, they can find a way to burn a piece of paper near a sprinkler system. Because there's no complex judgement needed here - just matching fields up in a database - we can easily use an AI planner to find chains of cause and effect, even in reverse.
This is exactly what Isaac and Mark's system does. It starts with an objective, and works backwards to find chains of actions that lead to the objective being satisfied. In their demo game, the primary puzzle objective is to disable an electronic lock. The system looks at what things can cause the disable action on a lock - such as water - and then moves backwards looking for actions that cause water to appear. Once it finds a chain of items of a particular length, it places the objects in the game world and the puzzle is ready.
One particularly nice aspect of the paper was the evaluation performed on their demo game, Space Dust. The authors realised that one of the consequences of their new system was that it could produce puzzles with multiple solutions, but would that make things easier or more confusing for the player? They offered both types of puzzle to a collection of players and got their feedback. Most people found that having more solutions was easier, which I think makes sense to me. I like the idea of a game detecting that someone is having trouble solving a puzzle, and your sidekick suddenly "discovering" an item behind a rock somewhere that opens up a new solution chain to make things easier.
You might have played Symon, an experimental game from MIT's GAMBIT lab, which played with similar ideas. I like both projects because they're developing new ways of approaching something that is about as genre-defining as it gets. A lot of the time, procedural content generation is a way of performing tasks that humans can already do, but this is more about using technology to rethink design decisions that have been accepted for years and years.
This more flexible approach to puzzle design has lots of potential applications, not least because it's not just point-and-clickers that use item chain puzzles - in fact I've been playing Arkham City this week and realising how much games like this rely on items to defeat bosses or traverse game worlds. I also can't help but think back to last week's post on constraint solvers and see a connection here too. Constraint solvers could use information about the causality chains involved in solving a puzzle, and arrange the items in sensible orders and locations, as well as satisfying constraints like "food items must be found in kitchens or dining rooms".
Above all else, you should be excited about this work because it's a step towards allowing us to design games that would be difficult to do by hand. Having multiple solutions to a puzzle opens the possibility for the player to be carrying leftover items further into the game - which might inadvertently solve a puzzle in a way a human designer might not be expecting or just have not considered. The opposite is even worse - if a player burns an important bit of paper before they've used the secret message that was written on it, for instance. But using constraint solvers and planners, we can build tools that can give the player lots of choice and pathways through the game, while still making sure that nothing undesirable happens and certain crucial puzzles aren't skipped. Often we see procedural generation as 'putting people out or jobs', tongue-in-cheek or not. On the contrary, this work shows how new technology can help us work smarter.
Where To Find More
You can read the original paper here as well as an expanded version here, thanks to Isaac. Mark also wrote up a web-friendly condensed version here, which I really like the style of. I know I say this a lot, but this paper is readable! You can really skim through it and learn a lot more about the system than I could fit into this post. And of course you can download the Unity game that the paper was based on right here. The objective is to find your way to an entrance on the ship, but to do so you'll need multiple tries - hence needing to escape from the brig over and over again, with a different puzzle each time. I think it's a great demonstration for the tech.
Isaac went on to co-found Preliminal Games, a London startup working on an unannounced title that apparently uses his work on smart terrain causality chains! I'm very excited to see what comes of that. Mark Nelson is Assistant Professor at ITU Copenhagen, alongside Julian Togelius whose Mario work we saw a few weeks back.
Thanks to Mark and Isaac for helping me write this piece this week, and to Rob (@MGPNightShift) of the Mature Gamer Podcast community forums and Darren Grey for taking the time to proofread it too. Don't forget to drop in on our Reddit thread in /r/gamedev, and catch me on Twitter to tell me what you think of the piece.
AIIDE is a really great conference every October, and this year it's in Boston. There's a bunch of great workshops being organised that you can find here, but refI want to mention a couple in particular that I know a little about. The first is AI & Game Aesthetics, a workshop I'm co-organising with Antonios Liapis and Cameron Browne. We're looking for relatively short submissions (just 4 pages) about interesting work relating to intelligent systems and all manner of aesthetic and subjective issues in game development. Check out the topics here and please submit if you've made a game, a tool or performed an experiment that might be relevant!
Another workshop is the 2nd Workshop on Intelligence in the Design Process. This is being organised by Adam Smith and Gillian Smith, two great researchers from the US, as well as Mark Nelson - the co-author of today's Saturday Paper! Be sure to check out their list of topics here, too, and consider submitting something.