Index of every page on this site: llms.txt
All skills
jame581 avatar

/procedural-generation

@426e8ab
by Jan Mesarčjame581/godotprompter979 stars
63
Run it yourself

Use when implementing procedural generation — noise-based terrain, BSP dungeons, cellular automata caves, wave function collapse, and seeded randomness in Godot 4.3+

Use this Skill: https://skilld.dev/gh/jame581/godotprompter/procedural-generation

Nothing lands on disk. Nothing to clean up.

Fork this Skill

Edit a local copy. It keeps the author and licence.

referenceswave-function-collapse.md

≈1.9k tokens on demand. Your agent reads this file only when SKILL.md points to it.

Wave Function Collapse (WFC)

Reference for skills/procedural-generation/SKILL.md — tile-set constraint solver. Concept overview and simplified algorithm in GDScript + C#.

← Back to SKILL.md


5. Wave Function Collapse (WFC) — Concept

WFC generates patterns by collapsing tile possibilities based on adjacency constraints. It produces visually coherent results from a small set of rules.

Core Algorithm (Simplified)

class_name SimpleWFC
extends RefCounted

# Each cell holds a set of possible tile indices
var grid: Array[Array] = []   # grid[y][x] = Array[int] (possible tiles)
var rules: Dictionary = {}     # rules[tile_id] = {"up": [...], "down": [...], "left": [...], "right": [...]}
var rng := RandomNumberGenerator.new()

func setup(width: int, height: int, tile_count: int, gen_seed: int) -> void:
    rng.seed = gen_seed
    grid.clear()
    for y in height:
        var row: Array[Array] = []
        for x in width:
            var possibilities: Array[int] = []
            for t in tile_count:
                possibilities.append(t)
            row.append(possibilities)
        grid.append(row)

func collapse() -> bool:
    while true:
        # Find cell with fewest possibilities (lowest entropy)
        var min_cell := Vector2i(-1, -1)
        var min_count := 999
        for y in grid.size():
            for x in grid[y].size():
                var count: int = grid[y][x].size()
                if count > 1 and count < min_count:
                    min_count = count
                    min_cell = Vector2i(x, y)

        if min_cell == Vector2i(-1, -1):
            return true  # all collapsed — success

        # Collapse: pick a random possibility
        var cell: Array[int] = grid[min_cell.y][min_cell.x]
        if cell.is_empty():
            return false  # contradiction — no valid tiles
        var chosen: int = cell[rng.randi() % cell.size()]
        grid[min_cell.y][min_cell.x] = [chosen]

        # Propagate constraints to neighbors
        _propagate(min_cell)

    return true

func _propagate(pos: Vector2i) -> void:
    var stack: Array[Vector2i] = [pos]
    while not stack.is_empty():
        var current: Vector2i = stack.pop_back()
        var current_tiles: Array[int] = grid[current.y][current.x]

        for dir in [Vector2i(0, -1), Vector2i(0, 1), Vector2i(-1, 0), Vector2i(1, 0)]:
            var neighbor: Vector2i = current + dir
            if neighbor.x < 0 or neighbor.y < 0 or neighbor.y >= grid.size() or neighbor.x >= grid[0].size():
                continue

            var dir_name: String = _dir_to_name(dir)
            var allowed: Array[int] = []
            for tile in current_tiles:
                if rules.has(tile) and rules[tile].has(dir_name):
                    for allowed_tile in rules[tile][dir_name]:
                        if allowed_tile not in allowed:
                            allowed.append(allowed_tile)

            var neighbor_tiles: Array[int] = grid[neighbor.y][neighbor.x]
            var new_tiles: Array[int] = neighbor_tiles.filter(func(t: int) -> bool: return t in allowed)

            if new_tiles.size() < neighbor_tiles.size():
                grid[neighbor.y][neighbor.x] = new_tiles
                stack.append(neighbor)

func _dir_to_name(dir: Vector2i) -> String:
    if dir == Vector2i(0, -1): return "up"
    if dir == Vector2i(0, 1):  return "down"
    if dir == Vector2i(-1, 0): return "left"
    return "right"

C#

public partial class SimpleWFC : RefCounted
{
    // grid[y][x] = list of possible tile indices
    private List<int>[][] _grid = [];
    // rules[tileId]["up"|"down"|"left"|"right"] = list of allowed neighbour tile ids
    private Godot.Collections.Dictionary<int, Godot.Collections.Dictionary<string, Godot.Collections.Array<int>>> _rules = new();
    private RandomNumberGenerator _rng = new();

    public void Setup(int width, int height, int tileCount, ulong genSeed)
    {
        _rng.Seed = genSeed;
        _grid = new List<int>[height][];
        for (int y = 0; y < height; y++)
        {
            _grid[y] = new List<int>[width];
            for (int x = 0; x < width; x++)
            {
                _grid[y][x] = new List<int>();
                for (int t = 0; t < tileCount; t++)
                    _grid[y][x].Add(t);
            }
        }
    }

    public bool Collapse()
    {
        while (true)
        {
            // Find cell with fewest possibilities (lowest entropy)
            var minCell = new Vector2I(-1, -1);
            int minCount = 999;
            for (int y = 0; y < _grid.Length; y++)
                for (int x = 0; x < _grid[y].Length; x++)
                {
                    int count = _grid[y][x].Count;
                    if (count > 1 && count < minCount)
                    {
                        minCount = count;
                        minCell = new Vector2I(x, y);
                    }
                }

            if (minCell == new Vector2I(-1, -1))
                return true;  // all collapsed — success

            // Collapse: pick a random possibility
            var cell = _grid[minCell.Y][minCell.X];
            if (cell.Count == 0)
                return false;  // contradiction — no valid tiles
            int chosen = cell[(int)(_rng.Randi() % (uint)cell.Count)];
            _grid[minCell.Y][minCell.X] = [chosen];

            // Propagate constraints to neighbors
            Propagate(minCell);
        }
    }

    private void Propagate(Vector2I pos)
    {
        var stack = new Stack<Vector2I>();
        stack.Push(pos);
        while (stack.Count > 0)
        {
            var current = stack.Pop();
            var currentTiles = _grid[current.Y][current.X];

            foreach (var dir in new[] { new Vector2I(0, -1), new Vector2I(0, 1), new Vector2I(-1, 0), new Vector2I(1, 0) })
            {
                var neighbor = current + dir;
                if (neighbor.X < 0 || neighbor.Y < 0 || neighbor.Y >= _grid.Length || neighbor.X >= _grid[0].Length)
                    continue;

                string dirName = DirToName(dir);
                var allowed = new HashSet<int>();
                foreach (int tile in currentTiles)
                    if (_rules.TryGetValue(tile, out var tileRules) && tileRules.TryGetValue(dirName, out var allowedTiles))
                        foreach (int allowedTile in allowedTiles)
                            allowed.Add(allowedTile);

                var neighborTiles = _grid[neighbor.Y][neighbor.X];
                var newTiles = neighborTiles.Where(t => allowed.Contains(t)).ToList();

                if (newTiles.Count < neighborTiles.Count)
                {
                    _grid[neighbor.Y][neighbor.X] = newTiles;
                    stack.Push(neighbor);
                }
            }
        }
    }

    private static string DirToName(Vector2I dir)
    {
        if (dir == new Vector2I(0, -1)) return "up";
        if (dir == new Vector2I(0, 1))  return "down";
        if (dir == new Vector2I(-1, 0)) return "left";
        return "right";
    }
}

For production WFC, consider the community addon godot-constraint-solving (Asset Library: "Wave Function Collapse (WFC)"), which adds backtracking, rule learning from an example map, TileMapLayer/TileMap support and flat GridMap layers — full 3D generation is not implemented.


Source: SKILL.md on GitHub

No rule matched.

skilld matched fixed text patterns in SKILL.md and file names. Patterns miss obfuscated code.

skilld run checks every file with the same patterns. It asks for approval before it loads a Skill with a behavior marked Needs approval.

1 warning29d3 checks · Risk SAFE
  • Gen Agent Trust Hub29d

    The skill provides instructional material and code samples for procedural generation algorithms in Godot 4.3+. No malicious patterns or security risks were identified.

  • Socket29d

    No alerts

  • Snyk29d

    Risk: MEDIUM · 1 issue

Signed by skilld at 426e8ab. This ties the file your Agent reads to that commit on GitHub. It does not review the instructions.

Last checked against GitHub 6 days ago.

Activeupdated last month

README badge

README badge for jame581/godotprompter/procedural-generation