This category contains articles suitable for most readers just starting out.
See Intermediate and Advanced for more articles.
Watabou’s Cave Generator is one in a series of RPG-ready map generators that Watabou has created over the years. All his work oozes style, but the cave generator was always the one I found most mysterious.
I discovered that the entire thing was exported with extremely readable javascript, so naturally I started to poke and prod. Let’s go over how it works.
Continue readingI’ve recently seen a lot of demonstrations of why the decimal 0.999… equals 1.
These are endlessly cycling the internet, simply because all the simple explanations aren’t really compelling. You see smart people responding “can’t you just…” or simply not convinced by bare assertion.
The truth is that is that dealing with these things is actually a lot more complex than a glib twitter answer. You should feel uneasy with these explanations. This same subject confused mathematicians of earlier centuries, leading to awkward theories like “infinitesimals”, which ultimately fell out of favour.
I’m going to take you through a proof that 0.999… = 1, with rigour. Rigour is a term used in maths for building from a solid foundation and proceeding from there in sufficiently small steps. Thus, the majority of the article is not the proof but the definitions. How can we talk about infinity in a way that makes sense? The trick, as we’ll see, is to only talk about finite things we already understand, and define infinity in terms of those.
This article is aimed at those with high school level maths. There’s a proof halfway down, but it’s skippable.
Continue reading
I’ve written a lot about Wave Function Collapse. Developed in 2016 by Maxim Gumin, it’s an algorithm for generating tilemaps and pixel textures based on the constraint solving with extra randomization . But did you know most of the key ideas come from a paper written a full decade earlier? Today, we’ll be looking into Model Synthesis, the 2007 PhD dissertation of Paul Merrell, and some of the elaborations he’s designed, particularly Modifying in Blocks.
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.
You are probably familiar with Recursive Subdivision – also known as Binary Space Partitioning – as a procedural generation technique. Like all the best proc gen, it’s a simple idea, that produces complex output. I’m here to discuss some variants that others have used to produce interesting results.
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.
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.
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.
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.
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.