Graphs are a data structure we’ve already talked a lot. Today we’re looking at extension of them which is both obvious and common, but I think is rarely actually discussed. Normal graphs are just a collection of nodes and edges, and contain no spatial information. We’re going to introduce rotation graphs (aka rotation maps) that contain just enough information to allow a concept of turning left or right – i.e. rotation.
Continue reading
I’ve been doing a lot of experiments with WaveFunctionCollapse, which as we’ve covered before, is essentially a constraint solver turned into a procedural generator.
The underlying solver WaveFunctionCollapse came with is called Arc Consistency 3, or AC-3 for short. But AC-3 is actually one of a whole family of Arc Consistency algorithms. Today, my solver and most others uses AC-4, a more advanced algorithm. Let’s talk a bit about how those both work.
Continue reading
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.
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.
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
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 readingLock and key dungeons are, well, video game levels with locks preventing progress, and collectable keys that let you proceed.
The concept is a lot broader than it sounds. Locks/keys aren’t necessary physical objects, but anything that works in a similar way, which can often be quite abstract.
Once you are familiar with the pattern, you begin spotting it everywhere. It’s most prominent in puzzle games and metroidvanias, but it’s applicable to any game which has an authored progression path.
In this article, we’ll look at lock and key dungeons, then how to analyse and design them.
Continue reading
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