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

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

Wave Function Collapse Explained

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

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