Triangle Grids

Ah, the triangle grid. Square grids are virtually ubiquitous, laying out out everything from the pixels in an image to houses in a city block. The hex grid has a decent showing too, particularly in board games. But triangle grids – regular tilings of the 2d plane with equilateral triangles – just don’t seem popular. I’ve seen claims they are useless, or that the maths is hard. But I’m here to prove both of these are wrong: the maths is actually easier than working with hexes, and triangles have all sorts of neat advantages.

I’ve worked out all the maths in my reference code on github, but it’s worth explaining why and how to use these grids.

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

Lock and Key Dungeons

Lock 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.

In Metroid 1, you cannot exit through the hole at the right (the lock) until collecting the morphball upgrade (the key)

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

Compressed Sparse Fibers Explained

I was browsing the Apache Arrow docs and spotted a term unfamiliar to me. Intrguied, I discovered that Compressed Sparse Fibers are a new technique for representing sparse tensors in memory. After reading up a bit, I thought I’d share with you what I’ve learnt. The technique is so new (well, 2015..) it is not mentioned on Wikipedia, and I found virtually nothing elsewhere. There’s a very limited number of ways to handle sparse data, so it’s always interesting to see a new one.

Don’t worry, I’d also never heard of a sparse tensor before, so I’m going to explain things right from the beginning, assuming you have a basic CS background, and don’t mind me going a little quickly.

Continue reading

New Discord Server

Let’s face it, running your own WordPress blog is a sign you are woefully out of date. I can see plenty of readers, but never hear from them.

So I’ve created a Discord server. Feel free to log on and ask me support questions about my projects, suggest new article ideas, or just to hang out.

Don’t worry, the blog isn’t going anwhere. I think the jump might kill me if I leaped fully into the 21st century.

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