Thursday, June 1, 2017

BlockFractal: generator of blocky fractal-like shapes

The frabjous isle of North Osia
BlockFractal is an algorithm that generates blocky fractal-like shapes.  The idea is to make something that would be suitable for a continent, island, or lake, in a procedurally generated 2d tile-based game.  The demo page shows the generated shape with a Google-Maps-like interface, where you can zoom and pan around.

First it generates a random place name, like New Gharnia, Superior Iukauton, or Twuq'eros.  That name is used as a random seed to generate a random fractal.  You can enter your own place name, and you can control two properties of the fractal generation.

One is "iterations".  This sets how many times the BlockFractal algorithm is run on the initial seed shape.  The initial shape is a simple square, but each iteration adds finer and finer random detail to it.  Drag the iterations slider around to see how the shape was built.

The other is "variation".  This basically affects the craziness of the shape.  Low variation produces a simpler but blockier shape.  High variation produces a shape with many more twists and turns.  Somewhere in the middle seems to be pretty good for continent-looking shapes.

Seed square
Iteration in progress
New shape after first iteration

There's a thorough description of the algorithm at the Algorithm Overview page on the github site, but basically it goes like this:  Take the initial seed shape (a 2x2 square in the first of the three example images above), double it, and then for each unit edge make a random decision to leave it be or to move it "inward" or "outward".  That produces a new shape which is more complicated, and around twice as big, as the last one.

The frumious land of Yixonia
Repeat this algorithm as many times as you like, though it does take twice as much memory with each iteration, so to avoid memory issues I stopped the demo at 9 iterations.

There are a few edge cases to consider, for instance I don't want the path to intersect itself.  If you're curious the Algorithm Overview page has more details.

The resulting shapes make me think of Koch snowflakes and quadric fractals.  Also, check out Brainfilling Curves, for some similar and amazing shapes.

As you play with the demo, imagine if this were the high-level map of a top-down RPG or roguelike game.  I like the idea of scattering some different biomes and rivers around, randomly placing some cities and towns, and maybe using some Delaunay triangulation to connect them with roads.

No comments:

Post a Comment