An interesting diversion into procedural generation...

Outside of work I've been looking for non-Sitecore things to experiement with recently, and my eye was caught by a bit of interesting game development technology. I came across a discussion of using code to generate game data with a technique called "Wavefunction Collapse". It's a simple concept, but it has some interesting results, so I thought I'd have a go at an implementation myself.

So what is this idea? url copied!

Imagine you have a set of tiles that you want to build a map out of. There are some rules about how the tiles can be layed out, and you want the computer to make use of those rules to generate a random layout of the tiles for you. For example the tiles might be box drawing characters:

The rules for this example are simple: the shapes need to be placed so that the lines join up, generating a path.

Wavefunction collapse is one way to approach this, and the algorithm goes something like this: You make an array, the size of the map you need. Each cell in the array is "a wavefunction" – (the name is stolen from physics and quantum state) it's basically a list of all the possible tiles that could go in that space. To start with that means "any tile".

Then you run a loop over the data:

• Find the wavefunction with the lowest "entropy". That means the array cell with the fewest possible options. If you have multiple wavefunctions with the same value for entropy, then pick one of them at random.
• "Collapse" this wavefunction – based on the weights for each possible tile that remains a choice, pick one tile and discard the others.
• And then you propagate that change to the adjacent tiles. Because you now know what the current tile is, you can look at the surrounding tiles and remove some of their options based on rules which now cannot be true. And that reduces their entropy, in preparation for the next round.

If you keep repeating this process for a while, you end up resolving a single value for more and more cells in your array, until you end up with with a completed map. (Or you get an error condition because the remaining rules can't be resolved – but we'll ignore that edge case to keep this description simple) Slowed down for visibility, it looks something like this:

The blue array cell is the one being processed. Green ones are those whose wavefunction was changed by propagation. And yellow are those considered for propagation, but not changed. Once a cell is resolved, it shows the chosen map tile. For the cells that are unresolved, the value displayed for the wavefunction is the number of choices still available. (rendered in hexadecimal here – to allow for more options to be displayed)

How does it work? url copied!

At its simplest, a `WaveFunction` is just an array of possibilities, and a way to work out "entropy" based on how many of those are valid. And if there's only one choice, we've finished processing this:

public class WaveFunction
{
    public Tile[] Choices { get; set; }
    public int Entropy => Choices.Where(t => t != null).Count();
    public bool IsResolved => Entropy == 1;
}

					

And a tile is a weight plus the character to be displayed:

public class Tile
{
    public int Id {g et; }
    public char Character { get; }
    public int Weight { get; set; } = 1;
}

					

And a rule specifies when a tile is valid in a certain direction, and the weight for that combination:

public class TileRule
{
    public int SourceTileId { get; set; }
    public int Direction; { get; set; }
    public int PossibleTileId; { get; set; }
    public int Weight; { get; set; }
}

					

The rules which drive choices can be manually created, or they can be inferred by looking at an example image and processing it. Weights for tiles and rules can also be inferred from an example – the more times a tile or a rule is found in the source data, the higher its weight.

The map itself is a set of wavefunctions:

public class Map
{
    public int Width { get; set; }
    public int Height { get; set; }

    public bool IsResolved
    {
        get
        {
            for (int x = 0; x < Width; x++)
            {
                for (int y = 0; y < Height; y++)
                {
                    var cell = Cells[x, y];
                    if (!cell.IsResolved)
                    {
                        return false;
                    }
                }
            }

            return true;
        }
    }

    public WaveFunction[,] Cells { get; set; }

    public Map(int w, int h, TileSet tileset)
    {
        Width = w;
        Height = h;

        Cells = new WaveFunction[Width, Height];
        Tileset = tileset;

        for (int x = 0; x < Width; x++)
        {
            for (int y = 0; y < Height; y++)
            {
                var waveFunction = new WaveFunction();
                waveFunction.Choices = tileset.Fetch();
                Cells[x, y] = waveFunction;
            }
        }
    }
}

					

The TileSet contains a list of the tiles, which can be copied to set up each wavefunction.

So each update cycle starts with finding the lowest entropy wavefunction to process, and picks randomly if there are multiple choices:

public Point FindLowEntropyWaveFunction()
{
    var currentTiles = new List<TileOption>();
    for (int x = 0; x < _map.Width; x++)
    {
        for (int y = 0; y < _map.Height; y++)
        {
            var cell = _map.Cells[x, y];
            if (!cell.IsResolved)
            {
                currentTiles.Add(new TileOption() { Location = new Point(x, y), Tile = cell });
            }
        }
    }

    // order tiles by Entropy
    var options = currentTiles
        .GroupBy(t => t.Tile.Entropy)
        .OrderBy(g => g.Key)
        .First();

    TileOption choice;

    // If more than one lowest entropy, pick randomly from them
    if (options.Count() > 1)
    {
        var pick = _rnd.Next(options.Count());
        choice = options.ElementAt(pick);
    }
    else
    {
        choice = options.First();
    }

    return choice.Location;
}

					

The chosen tile can then be resolved, paying attention to the tile weight:

public void Resolve(Point tile)
{
    var cell = _map.Cells[tile.X, tile.Y];

    // find indexes of non-zero items
    options.Clear();
    for (int i = 0; i < cell.Choices.Length; i++)
    {
        if (cell.Choices[i] != null)
        {
            for (int c = 0; c < cell.Choices[i].Weight; c++)
            {
                options.Add(i);
            }
        }
    }

    var pick = _rnd.Next(options.Count());
    var index = options.ElementAt(pick);

    // null out the ones not picked
    for (int i = 0; i < cell.Choices.Length; i++)
    {
        if (i != index)
        {
            cell.Choices[i] = null;
        }
    }
}

					

And then that change can be propagated to the remaining tiles:

public void Propagate(Point tile)
{
    stack.Push(tile);

    while (stack.Count > 0)
    {
        var point = stack.Pop();
        var cellWaveFunction = _map.Cells[point.X, point.Y];

        var d = Point.Empty;
        foreach (Point adjPos in _helper.Deltas)
        {
            d = point.Sum(adjPos).Wrap(_map);

            var adjWaveFunction = _map.Cells[d.X, d.Y];

            bool changed = false;
            for (int i = 0; i < adjWaveFunction.Choices.Length; i++)
            {
                if (adjWaveFunction.Choices[i] != null)
                {
                    if (!TilePossible(cellWaveFunction, adjWaveFunction.Choices[i], adjPos))
                    {
                        adjWaveFunction.Choices[i] = null;
                        changed = true;
                    }
                }
            }

            if (changed)
            {
                stack.Push(d);
            }

            if (adjWaveFunction.Choices.Where(t => t != null).Count() == 0)
            {
                throw new Exception("Map cannot be solved.");
            }
        }
    }
}

					

Starting at the current point, it looks around in all the defined directions. For each one, it looks to see if any of the choices at that location is now impossible, based on the current rules. If so, that item gets removed from the target wavefunction's choices, and the updated wavefunction gets added to the "list of places than need processing further". The loop continues until it's run out of things to change.

The TilePossible() method checks the target wavefunction to see whether the rules allow that state - so it can be removed if not allowed.

And this overall loop continues until either all the wavefunctions are reduced to a specific value (Entropy equals 1) or we hit an impossible state.

What I find particularly interesting about this is that the rules can come from different sources. The generation logic relies on the TileRule class above - and you can write these by hand if you want. For example, here's the definition of a simple three-tile ruleset:

public TileSet Generate(IDirectionHelper dh)
{
    var ts = new TileSet(dh);

    var one = ts.NewTile('█',1);
    var two = ts.NewTile('╬',1);
    var three = ts.NewTile('┼',1);

    ts.AddBidirectionalTileRules(one, one, 1, Directions.North, Directions.South, Directions.East, Directions.West);
    ts.AddBidirectionalTileRules(one, two, 1, Directions.North, Directions.South, Directions.East, Directions.West);

    ts.AddBidirectionalTileRules(two, two, 1, Directions.North, Directions.South, Directions.East, Directions.West);
    ts.AddBidirectionalTileRules(two, three, 1, Directions.North, Directions.South, Directions.East, Directions.West);

    ts.AddBidirectionalTileRules(three, three, 1, Directions.North, Directions.South, Directions.East, Directions.West);

    return ts;
}

					

And that generates something like:

This simple example has bidirectional rules (if a rule is valid left-to-right then it is also valid right-to-left) but that doesn't have to be true – rules can work in a single direction only.

But what's really interesting is that you can infer rules from an existing data set. The video example above comes from taking simple "this character has exits east and south" type data, and using that to build a ruleset. But you can also take a text file, and iterate through it to work out what characters can be adjacent to each other, and build a ruleset from that instead. You can also infer weights from how often you see any character, or any relationship between adjacent characters.

For example, inferring rules from the following text:

/---\  +---+
|   |  |   |
|   |  |   |
\---/  +---+

					

Can render something like:

Which saves the effort of writing the rules directly. And you can extend the same process to pixels in an image, or tiles in a 2d or 3d map. The versatility is really interesting to me.

My fiddling about with this can be downloaded from github if you want to play too. It's not very efficient code – it was written to understand the behaviour rather than to be optimised for real use. But it can still generate some interesting patterns. And there's plenty more to read on this topic if this has piqued your interest.

↑ Back to top