Wave Function Collapse

using MagicBook.Algorithms.Randomness;

// A tile and what it shows on each of its four edges. Two tiles may sit next to each
// other when the edges that touch carry the same label. Tiles with a higher weight
// are picked more often.
public sealed record Tile(char Symbol, string Up, string Right, string Down, string Left, double Weight = 1);

public static class WaveFunctionCollapse
{
    // How often the whole grid is started over before giving up.
    private const int Attempts = 40;

    private enum Removed { Nothing, Something, Everything }

    // Fills a grid with tiles so that all neighbours fit together.
    // border, if given, is the edge label the outside of the grid has to show.
    public static Tile[] Fill(Tile[] tiles, int width, int height, ulong seed, string? border = null)
    {
        var random = new Pcg(seed);

        // A guess can paint the grid into a corner, so that somewhere no tile fits any
        // more. Instead of taking single guesses back, the whole grid is started over.
        for (var attempt = 0; attempt < Attempts; attempt++)
        {
            var result = TryFill(tiles, width, height, random, border);

            if (result is not null)
                return result;
        }

        throw new InvalidOperationException("No arrangement found. The tiles probably do not fit together.");
    }

    private static Tile[]? TryFill(Tile[] tiles, int width, int height, Pcg random, string? border)
    {
        // possible[cell * tiles.Length + tile] answers one question: can this tile
        // still go into this cell? At the start everything is still allowed everywhere.
        var possible = new bool[width * height * tiles.Length];
        Array.Fill(possible, true);

        if (border is not null && !ApplyBorder(possible, tiles, width, height, border))
            return null;

        // Before the first guess the rules are applied everywhere once: tiles that can
        // never find a fitting neighbour drop out right away.
        var pending = new Stack<int>();

        for (var cell = 0; cell < width * height; cell++)
            pending.Push(cell);

        if (!Propagate(possible, tiles, width, height, pending))
            return null;

        while (true)
        {
            var cell = MostConstrained(possible, tiles.Length, width * height, random);

            // Nothing left to decide: every cell has exactly one tile.
            if (cell < 0)
                return Result(possible, tiles, width * height);

            Collapse(possible, tiles, cell, random);
            pending.Push(cell);

            if (!Propagate(possible, tiles, width, height, pending))
                return null;
        }
    }

    // The cell with the fewest options left is the safest place for the next guess:
    // there the risk of choosing something impossible is smallest.
    // Returns -1 once every cell is decided.
    private static int MostConstrained(bool[] possible, int tileCount, int cells, Pcg random)
    {
        var fewest = int.MaxValue;
        var candidates = new List<int>();

        for (var cell = 0; cell < cells; cell++)
        {
            var options = CountOptions(possible, tileCount, cell);

            if (options <= 1)
                continue;

            if (options < fewest)
            {
                fewest = options;
                candidates.Clear();
            }

            if (options == fewest)
                candidates.Add(cell);
        }

        return candidates.Count == 0 ? -1 : candidates[random.Next(candidates.Count)];
    }

    // Picks one of the remaining tiles at random and drops all the others.
    private static void Collapse(bool[] possible, Tile[] tiles, int cell, Pcg random)
    {
        var total = 0.0;

        for (var tile = 0; tile < tiles.Length; tile++)
        {
            if (possible[cell * tiles.Length + tile])
                total += tiles[tile].Weight;
        }

        // Walk along the weights until the drawn value is used up.
        var drawn = random.NextDouble() * total;
        var chosen = 0;

        for (var tile = 0; tile < tiles.Length; tile++)
        {
            if (!possible[cell * tiles.Length + tile])
                continue;

            chosen = tile;
            drawn -= tiles[tile].Weight;

            if (drawn <= 0)
                break;
        }

        for (var tile = 0; tile < tiles.Length; tile++)
            possible[cell * tiles.Length + tile] = tile == chosen;
    }

    // Whenever a cell loses options its neighbours can lose some as well. This keeps
    // passing the consequences on until nothing changes any more.
    private static bool Propagate(bool[] possible, Tile[] tiles, int width, int height, Stack<int> pending)
    {
        while (pending.Count > 0)
        {
            var cell = pending.Pop();

            for (var direction = 0; direction < 4; direction++)
            {
                var neighbour = Neighbour(cell, direction, width, height);

                if (neighbour < 0)
                    continue;

                switch (Reduce(possible, tiles, cell, neighbour, direction))
                {
                    case Removed.Everything:
                        return false;

                    case Removed.Something:
                        pending.Push(neighbour);
                        break;
                }
            }
        }

        return true;
    }

    // Removes every tile from the neighbour that cannot sit next to anything the
    // cell still allows.
    private static Removed Reduce(bool[] possible, Tile[] tiles, int cell, int neighbour, int direction)
    {
        var changed = false;
        var left = 0;

        for (var candidate = 0; candidate < tiles.Length; candidate++)
        {
            if (!possible[neighbour * tiles.Length + candidate])
                continue;

            var fits = false;

            for (var tile = 0; tile < tiles.Length && !fits; tile++)
                fits = possible[cell * tiles.Length + tile] && Fits(tiles[tile], tiles[candidate], direction);

            if (fits)
            {
                left++;
                continue;
            }

            possible[neighbour * tiles.Length + candidate] = false;
            changed = true;
        }

        if (left == 0)
            return Removed.Everything;

        return changed ? Removed.Something : Removed.Nothing;
    }

    // Directions are 0 up, 1 right, 2 down, 3 left. b sits in that direction from a.
    private static bool Fits(Tile a, Tile b, int direction) => direction switch
    {
        0 => a.Up == b.Down,
        1 => a.Right == b.Left,
        2 => a.Down == b.Up,
        _ => a.Left == b.Right,
    };

    private static int Neighbour(int cell, int direction, int width, int height)
    {
        var x = cell % width;
        var y = cell / width;

        (x, y) = direction switch
        {
            0 => (x, y - 1),
            1 => (x + 1, y),
            2 => (x, y + 1),
            _ => (x - 1, y),
        };

        return x < 0 || y < 0 || x >= width || y >= height ? -1 : y * width + x;
    }

    // The outside of the grid has to show the given label, otherwise the pattern
    // would be cut off at the border.
    private static bool ApplyBorder(bool[] possible, Tile[] tiles, int width, int height, string border)
    {
        for (var cell = 0; cell < width * height; cell++)
        {
            var x = cell % width;
            var y = cell / width;
            var left = 0;

            for (var tile = 0; tile < tiles.Length; tile++)
            {
                if (!possible[cell * tiles.Length + tile])
                    continue;

                var allowed = (y > 0 || tiles[tile].Up == border)
                    && (x < width - 1 || tiles[tile].Right == border)
                    && (y < height - 1 || tiles[tile].Down == border)
                    && (x > 0 || tiles[tile].Left == border);

                possible[cell * tiles.Length + tile] = allowed;

                if (allowed)
                    left++;
            }

            if (left == 0)
                return false;
        }

        return true;
    }

    private static int CountOptions(bool[] possible, int tileCount, int cell)
    {
        var options = 0;

        for (var tile = 0; tile < tileCount; tile++)
        {
            if (possible[cell * tileCount + tile])
                options++;
        }

        return options;
    }

    private static Tile[] Result(bool[] possible, Tile[] tiles, int cells)
    {
        var result = new Tile[cells];

        for (var cell = 0; cell < cells; cell++)
        {
            for (var tile = 0; tile < tiles.Length; tile++)
            {
                if (!possible[cell * tiles.Length + tile])
                    continue;

                result[cell] = tiles[tile];
                break;
            }
        }

        return result;
    }
}

const int width = 62;
const int height = 24;

// Every tile says for each of its four edges whether a path leaves there ("1")
// or whether there is a wall ("0"). Two tiles fit when the edges that touch agree.
Tile[] tiles =
[
    new(' ', "0", "0", "0", "0", Weight: 0.6),
    new('│', "1", "0", "1", "0"),
    new('─', "0", "1", "0", "1"),
    new('┌', "0", "1", "1", "0"),
    new('┐', "0", "0", "1", "1"),
    new('└', "1", "1", "0", "0"),
    new('┘', "1", "0", "0", "1"),
    new('├', "1", "1", "1", "0"),
    new('┤', "1", "0", "1", "1"),
    new('┬', "0", "1", "1", "1"),
    new('┴', "1", "1", "0", "1"),
    new('┼', "1", "1", "1", "1", Weight: 0.4),
];

// The outside of the grid is a wall, otherwise paths would run off the map.
var maze = WaveFunctionCollapse.Fill(tiles, width, height, seed: 2024, border: "0");

for (var y = 0; y < height; y++)
{
    for (var x = 0; x < width; x++)
        Console.Write(maze[y * width + x].Symbol);

    Console.WriteLine();
}

const int width = 62;
const int height = 30;

// The same algorithm, only different tiles. Each tile is a square made of four
// quarters that are either water or land, and there is a character for every
// one of the sixteen combinations.
const string quarters = " ▗▖▄▝▐▞▟▘▚▌▙▀▜▛█";

var tiles = new Tile[16];

for (var i = 0; i < tiles.Length; i++)
{
    // Bit 8 is the top left quarter, then top right, bottom left, bottom right.
    var topLeft = (i & 8) != 0 ? 'L' : 'W';
    var topRight = (i & 4) != 0 ? 'L' : 'W';
    var bottomLeft = (i & 2) != 0 ? 'L' : 'W';
    var bottomRight = (i & 1) != 0 ? 'L' : 'W';

    // The label of an edge is simply the two quarters lying on it. Tiles fit
    // together exactly when the quarters they share agree, so a coastline can
    // never break apart.
    tiles[i] = new Tile(
        quarters[i],
        Up: $"{topLeft}{topRight}",
        Right: $"{topRight}{bottomRight}",
        Down: $"{bottomLeft}{bottomRight}",
        Left: $"{topLeft}{bottomLeft}",

        // Tiles of pure water or pure land are far more likely, which turns the
        // result into a few large islands instead of scattered pixels.
        Weight: i is 0 or 15 ? 9 : 1);
}

// Water all around the map, so the islands do not touch the border.
var map = WaveFunctionCollapse.Fill(tiles, width, height, seed: 1848, border: "WW");

for (var y = 0; y < height; y++)
{
    for (var x = 0; x < width; x++)
        Console.Write(map[y * width + x].Symbol);

    Console.WriteLine();
}