Procedural Puzzle Generation in The Witness

Spoilers for The Witness

I finally got around to playing The Witness last month, and enjoyed most of it a lot. The vast majority of the puzzles are hand crafted by Jonathan Blow and his team, but near the end is an infamous section, The Challenge. The Challenge is the only timed section in the game. To stop you simply memorising the puzzle answers, all puzzles in this section are randomly generated.

The change of pace and style, coupled with the intense music, and with a few curveballs thrown in, makes it one of the most memorable sections of the game.

I was naturally intensely curious as to how this generation works, and fortunately Blow shared all the key code for this section on stream last year. So I naturally got stuck in.

The answer is: they are all incredibly simple. They rely on generate-and-test. I.e. a relatively unsophisticated random generator randomly places puzzle elements, then the result is checked to see if it has a solution. If not, then you simply retry until you get a good one. There’s little attempt at making puzzles too easy, or too hard, as long as they are solvable. I certainly found playing this section, there was a good chance of running into a puzzle that was too hard, or very quick, but as the whole sequence is only six and a half minutes, it’s not too punishing to have to retry a couple of times.

Let’s dive into each puzzle, and what it does specifically. Each puzzle is named lotus_ as that is the codename for this section.

Continue reading →

Dungeon Generation in Unexplored

It’s rare that you see a game that gives top billing in its marketing to the quality of its procedurally generated levels. Normally PCG is sprinkled in a game to add a bit of variety, or to make up for the lack of actual level design. But, for 2017’s Unexplored, the rest of the game is there to justify the stellar levels.

Unexplored presents itself as a fairly standard roguelite – enter a randomly generated dungeon, descend 20 levels and retrive the amulet of Yendor. The gameplay features a realtime combat based around timing and aiming your swings, but otherwise plays things by the book.

https://cdn.akamai.steamstatic.com/steam/apps/506870/ss_af6440b995f113d35999af111e0e0e80aa77c53b.600x338.jpg?t=1574761931

But it doesn’t take long realize why they much such a big deal out of the procedural generation. Unexplored level design takes more after 2D Zelda games than it does Rogue. Instead of just wandering at random, you quickly find that the path forward is blocked, forcing you to solve puzzles, find items and keys, defeat enemies to continue. There’s a huge variety of structure, all randomly generated, but nearly every level is a tightly packed, interesting space.

Full video here
Continue reading →

PhantomGrammar and Ludoscope

Last time, I took inspiration from a game called Unexplored, and wrote about about a system of rule evaluation called Graph Rewriting.

In developing Unexplored and earlier games and academic papers, developer Joris Dormans has over the years developed an entire software library centered around graph rewriting. It’s called PhantomGrammar, and it comes with an accompanying UI called Ludoscope (sadly, neither is publically available currently).

I think it’s worth discussing how it works, as it turns the previous theoretical ideas into something pratical to work with.

Continue reading →

Graph Rewriting for Procedural Level Generation

I’ve been doing this series on how games do level generation for some time, and I have a complete beauty for you.

I’ve spent a lot of time deconstructing Unexplored, a 2017 indie game by Joris Dormans. It just nails procedurally generated zelda-like dungeons, and I had to know for myself how the magic happens. Fortunately, most of the generation logic is written in a custom language, PhantomGrammar, so between that and some help from the developers, I think I’ve got a pretty good idea how it works.

The ideas of Unexplored are so interesting that I felt they deserved an article in it’s own right. The game is centered around a concept called Graph Rewriting, which, while well understood academically, is rarely used in games. I’m going to spend this article talking about that technique alone, then how PhantomGrammar specifically uses and extends it. Finally I will talk about how these techniques are put together in Unexplored to make such sophisticated levels.

Continue reading →

For Keep’s Sake! Explained

I recently entered make a game for PROCJAM 2020. As I was making it purely for fun (there’s no winners in the competition), I focussed thing to make something that expanded my skills and was technically impressive. As such, there’s lots of interesating techniques that I felt were worth briefly explaning here.

Continue reading →

Dungeon Generation in Binding of Isaac

The Binding of Isaac, and its remake, Binding Of Isaac: Rebirth are one of my favourite games of all time. It’s a roguelite twin stick shooter, much like Enter the Gungeon.

The dungeons it generates are particularly iconic. I’ve seen countless tutorials online offering how to do Isaac-like generation, but I was interested in how the original did it. To my suprise, most tutorials get it wrong. In this article I go over how the generation works, including a Javascript demo.

Continue reading →

Level Generation in SLIGE (Doom level generator)

It’s time for another in my series on how games do level generation. Let’s take a look at SLIGE, a random level generator for Doom. The original Doom. That’s right, we’re going back to the early 90s for this one.

Doom was one of the first games designed from the ground up to friendly to modding, and consequently the community around it exploded. In the years following its release, level packs and tools started to circulate for free. It was only a matter of time until someone designed a random level generator.

SLIGE was one of the first. It quickly became infamous because newcomers would often attempt to pass off the level it creates as their own. But they’d inevitably get caught – SLIGE levels have a very distinctive feel, as you can see in the video below.

SLIGE may not be the most sophisticated level generator out there, but its fame caught my eye. It was under development by author David Chess for a number of years, and so has lots to explore. In this article, we’ll delve into how exactly it works.

Continue reading →