Wave Function Collapse

using MagicBook.Algorithms.Randomness;

// Eine Kachel und was sie an ihren vier Kanten zeigt. Zwei Kacheln dürfen nebeneinander
// liegen, wenn die berührenden Kanten dieselbe Beschriftung tragen. Kacheln mit höherem
// Gewicht werden öfter gezogen.
public sealed record Tile(char Symbol, string Up, string Right, string Down, string Left, double Weight = 1);

public static class WaveFunctionCollapse
{
    // Wie oft das ganze Raster neu begonnen wird, bevor aufgegeben wird.
    private const int Attempts = 40;

    private enum Removed { Nothing, Something, Everything }

    // Füllt ein Raster so mit Kacheln, dass alle Nachbarn zueinander passen.
    // border ist, falls angegeben, die Kantenbeschriftung, die nach außen zeigen muss.
    public static Tile[] Fill(Tile[] tiles, int width, int height, ulong seed, string? border = null)
    {
        var random = new Pcg(seed);

        // Eine Entscheidung kann das Raster festfahren, sodass irgendwo keine Kachel mehr
        // passt. Statt einzelne Entscheidungen zurückzunehmen, beginnt das Raster von vorn.
        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] beantwortet genau eine Frage: Darf diese Kachel
        // noch in diese Zelle? Am Anfang ist überall noch alles erlaubt.
        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;

        // Vor der ersten Entscheidung laufen die Regeln einmal über alles: Kacheln, die
        // nirgends einen passenden Nachbarn finden können, fallen sofort heraus.
        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);

            // Nichts mehr zu entscheiden: Jede Zelle hat genau eine Kachel.
            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;
        }
    }

    // Die Zelle mit den wenigsten Möglichkeiten ist der sicherste Ort für die nächste
    // Entscheidung: Dort ist das Risiko einer unmöglichen Wahl am kleinsten.
    // Liefert -1, sobald jede Zelle entschieden ist.
    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)];
    }

    // Würfelt eine der verbliebenen Kacheln aus und verwirft alle anderen.
    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;
        }

        // Die Gewichte entlanglaufen, bis der gezogene Wert aufgebraucht ist.
        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;
    }

    // Verliert eine Zelle Möglichkeiten, können das auch ihre Nachbarn. Das reicht die
    // Folgen so lange weiter, bis sich nichts mehr ändert.
    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;
    }

    // Entfernt aus dem Nachbarn jede Kachel, die zu keiner der noch erlaubten Kacheln
    // der Zelle passt.
    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;
    }

    // Richtungen sind 0 oben, 1 rechts, 2 unten, 3 links. b liegt in dieser Richtung von 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;
    }

    // Nach außen muss das Raster die angegebene Beschriftung zeigen, sonst wäre das
    // Muster am Rand abgeschnitten.
    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;

// Jede Kachel sagt für ihre vier Kanten, ob dort ein Weg herausführt ("1")
// oder eine Wand steht ("0"). Zwei Kacheln passen, wenn die berührenden Kanten gleich sind.
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),
];

// Der Rand des Rasters ist eine Wand, sonst liefen Wege aus der Karte heraus.
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;

// Derselbe Algorithmus, nur andere Kacheln. Jede Kachel ist ein Quadrat aus vier
// Vierteln, die Wasser oder Land sind, und für jede der sechzehn Kombinationen
// gibt es ein Zeichen.
const string quarters = " ▗▖▄▝▐▞▟▘▚▌▙▀▜▛█";

var tiles = new Tile[16];

for (var i = 0; i < tiles.Length; i++)
{
    // Bit 8 ist das Viertel oben links, dann oben rechts, unten links, unten rechts.
    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';

    // Die Beschriftung einer Kante sind einfach die beiden Viertel, die daran liegen.
    // Kacheln passen genau dann, wenn die gemeinsamen Viertel übereinstimmen, deshalb
    // kann eine Küstenlinie nie auseinanderbrechen.
    tiles[i] = new Tile(
        quarters[i],
        Up: $"{topLeft}{topRight}",
        Right: $"{topRight}{bottomRight}",
        Down: $"{bottomLeft}{bottomRight}",
        Left: $"{topLeft}{bottomLeft}",

        // Kacheln aus reinem Wasser oder reinem Land sind viel wahrscheinlicher, dadurch
        // entstehen wenige große Inseln statt verstreuter Pixel.
        Weight: i is 0 or 15 ? 9 : 1);
}

// Rundherum Wasser, damit die Inseln den Rand nicht berühren.
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();
}