What The Heck is a Fractal and How Does It Apply to Games?

Procedurally generated games are a big deal these days. Minecraft, Dwarf Fortress, Terraria, and No Man’s Sky, are the famous ones, but there’s no shortage of endlessly replayable and different-every-time games if you go looking for them. And the word “fractal” often gets used when talking about how these games are made or generated. I’ve gotten questions in emails and there’s this Reddit thread talking about these worlds and fractals.

So what is a fractal and what does it have to do with these games?

Fractal is one of those annoying slippery words like “barbecue”. Barbecue is a kind of food. It’s also how you cook the food. It’s also the appliance you use to cook the food. It’s also the party where the food is served. In the same way, fractal is a kind of pattern, but it’s also the system used to generate the pattern, and it’s also the branch of mathematics used to invent those systems, and so on. I’m not going to waste your time and my column space haggling over “proper” definitions. Let’s just accept that this word is used sloppily when it used by non-mathematicians, and really sloppy when used by programmers. We’re here to talk about game development, not mathematics or linguistics.

Broadly, a fractal is a (typically visual) pattern that contains smaller patterns. If you “zoom in” on any part of the image you’ll see details that are just as complex as the whole. Imagine a typical 8×8 chessboard pattern. You get close to one of the white squares and see that it is actually a grid of 8×8 squares. And when you look at one of the smaller squares, you see that it is also made up of smaller squares, and so on.

While not strictly part of the definition, we also associate fractals with the idea of “infinite complexity from complete simplicity”. Let me walk you through my favorite example: The Sierpinski triangle.

Put three dots on a piece of paper and number them 1, 2, 3. Put your pencil on one of these points. Now do this:

1) Choose one of the three points at random.
2) Using a ruler, find the position exactly halfway between your pencil and the chosen point.
3) Move your pencil to that position and put a dot there.
4) Repeat.

From these directions, you might expect that you’d get a random bunch of dots. Maybe the dots would be clustered in the middle of the page? But no. This actually creates a fractal. You’ll have three large triangles, each of which is surrounded by three smaller triangles, each of which is surrounded by three smaller ones, etc. The pattern goes on to infinity. If you want to see the smaller-detail triangles, just start with a larger piece of paper. (Note that I’m not really suggesting you do this. Doing it by hand with a ruler and pencil will take hours. But with a computer you can do this in a handful of milliseconds.)

So that’s one example of a fractal. Some super-simple rules that generate a repeating pattern of unlimited complexity. Granted, it’s a really visually boring pattern, but it’s still interesting to get so much order from such a seemingly random activity. For a more intense example of fractals in action, we can look at the most famous fractal of them all: The Mandelbrot Set. Unlike the Sierpinski triangle, the Mandelbrot Set is a pattern of infinite complexity and variation. It contains spirals made up of crescents made of curly edges made of zig-zags made of loops. The math is a bit more complex, but the process can still fit on an index card.

So how is this related to procedural games? Barely. While fractals are captivating, they aren’t terribly useful for generating game space. I’d be very surprised if there was any real fractal math going on under the hood in these games. When people call them “fractal”, they’re really saying it reminds them of that “infinite zoom” thing you can do in a real fractal. In No Man’s Sky, you can go from a galactic view, to a single star system, to a single planet, to a continent, to a region, to a single landing spot for your spaceship. And the game is so staggeringly vast and full of stars and planets that you might be the only player to ever stand in that spot. So it feels kind of fractal-ish.

But unlike a real fractal, these layers of detail aren’t the work of a single overarching algorithm. While I don’t know anything about the code of No Man’s Sky, I have dabbled in generating landscapes quite a bit and I’ll say this thing is a fractal in the sense that it has an endless amount of content that can be observed at many different scales, but not a fractal in the sense that it’s all the product of a single bit of math. There’s likely a system for generating stars, another for planets, another for terrain, another for plants, and so on.

To me, the interesting challenge in these systems is balancing the need for endless content with the need for interesting content. Anyone with a basic grasp of computer graphics programming can make a landscape of random rolling hills. You can make small hills that stretch off to the horizon, going on forever but never repeating. The problem is, that’s boring. Sure, every little hill is slightly different, but from the player’s perspective once you’ve seen one hill you’ve seen them all. With no landmarks, you don’t feel like you’re going anywhere.

So the developer will add some random detail, like a mountain. That can really spice things up. But if you make mountains too common then they become just as dull and repetitive as the hills and if you make them too rare then they don’t add much to the world. So you add more details: Ravines, lakes, oceans, beaches, fjords, plains, etc. But of course adding features like this takes time. So you’ve got a three-way tradeoff going here: Size of the world, diversity of the world, and programmer time. While making the math happen to generate hills and valleys is the “science” part, finding the right balance is where the “art” comes in.

So that’s procedural generation and fractals. Not as related as you might think, but both are pretty interesting areas of study. Now if only AAA developers would take an interest.

Shamus Young is a programmer, critic, comic, and crank. Have a question for the column? Ask him! [email protected].