procgen

Graph Rewriting for Procedural Level Generation

| Boris

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 →

Dungeon Generation in Binding of Isaac

| Boris

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)

| Boris

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 →

Wave Function Collapse Explained

| Boris

A simple guide to constraint solving

Since developing DeBroglie and Tessera, I’ve had a lot of requests to explain what it is, how it works. The generation can often seem quite magical, but actually the rules underlying it are quite simple.

So, what is the Wave Function Collapse algorithm (WFC)? Well, it’s an algorithm developed by Maxim Gumin based on work by Paul Merrell for generating tile based images based off simple configuration or sample images. If you’ve come here hoping to learn about quantum physics, you are going to be disappointed.

WFC is capable of a lot of stuff – just browse Maxim’s examples, or check out #wavefunctioncollapse on twitter, or see my youtube video.

WFC is explained briefly in Maxim’s README, but I felt it needed a fuller explanation from first principals. It is a slight twist on a much more broad concept – constraint programming. So much of this article is going to explain constraint programming, and we’ll get back to WFC at the end.

Continue reading →

Wave Function Collapse tips and tricks

Dungeon generation with pathing
| Boris

I’ve been experimenting a lot with constraint-based procedural generation these days. Specifically the Wave Function Collapse algorithm (WFC). I’ve even made my own open source library, and unity asset.

WFC is a very flexible algorithm, particularly with the enhancements I’ve designed, but at the same time, I’ve found it’s quite hard to actually get it to produce practical levels useful for computer games. The key difficulty is WFC doesn’t have any global structure to it, all it does it make the output generation look like the input locally, i.e. when viewing small rectangles of output at a time.

In this article, I share what I’ve learned to take your constraint based generators to the next level.

Continue reading →

Dungeon Generation in Enter The Gungeon

| Boris

I’ve been playing a lot of Enter The Gungeon recently. It’s a great, brutally hard, twin stick bullet hell that reminded me a lot of Binding of Isaac. But as I’ve been playing it more and more, I realized that the dungeon design actually shows some subtle genius.

There are many procedural generators out there that produce sensible level layouts that manage pacing and rewards correctly, and there are other generators out there that provide levels that include loops and compact layouts. But it’s hard to find both in a single game. Really, the only other game I’ve heard attempting this is Unexplored.

So, naturally, I broke out the decompiler to reveal all of Gungeon‘s secrets to me. I’ll share with you what I found.

Continue reading →

Dungeon Generation in Diablo 1

| Boris

Diablo 1 is a classic 1996 hack and slash action RPG. It was one of the first popular attempts at bringing roguelikes to the masses, from the niche ascii art. It’s spun a host of sequels, and imitators. It’s known for a dark, moody atmosphere that intensifies as the player descends into the dungeon beneath the town of Tristram. It was one of the first games I played with procedurally generated maps, and it blew me away that generating such convincing areas was even possible.

I recently discovered that thanks to the discovery of various debug symbol files accidentally left lying around, several fans took it upon themselves to reverse-engineer the source code and clean it up into a good guess at what the original game is like. Thus began a week long deep dive into how exactly did lead developer, David Brevik, actually craft these levels. It may have taken away some of the magic of the game, but I learnt lots of techniques I think are applicable to anyone developing a similar game, which I share with you below.

Continue reading →

DeBroglie v0.1

| Boris

Introducting my latest project, DeBroglie.

DeBroglie is a C# library and Windows command line application implementing the Wave Function Collapse algorithm with support for additional non-local constraints, and other useful features.

Wave Function Collapse (WFC) is an constraint-based algorithm for which takes a small input image or tilemap and procedurally generating a larger image in the same style, such as.

DeBroglie is stocked with loads of features to help customize the generation process.

Basically, you can use it to generate cool tile based stuff.