Autómatas celulares avanzados para generar cuevas

Estoy tratando de hacer cuevas en Unity. Para hacer esto, estoy tratando de usar autómatas celulares. Encontré lo siguiente ( Rouge Basin Cellular Automata for Caves ) que se parece a lo que estoy tratando de lograr.

Sin embargo, el tutorial no es del todo lo que quiero. Quiero algo como lo que produce este sitio web ( Don Jon Caves ) con el ajuste "cavernoso" (ver imagen a continuación).

Como puede ver en la imagen, todo está conectado. He probado numerosos métodos y bibliotecas, sin embargo, nada ha funcionado.

He estado luchando con este problema por un tiempo, y agradecería cualquier orientación que sea.

Gracias

No estoy seguro del enfoque utilizado en el ejemplo que muestra, pero así es como probablemente crearía algo similar ...

Primero, cree un gráfico de red no dirigido, algo como esto ...

Lo generaría a partir de un conjunto de nodos colocados al azar, incluido al menos uno que represente la entrada / salida de su cueva.

Ahora que tiene este gráfico, imagine si primero abriera un conjunto de pasajes a lo largo de cada vértice, solo pasajes rectos simples, no irregulares.

Ahora básicamente tienes una cueva, pero con paredes muy lisas. Se vería algo así en el gráfico anterior ...

Entonces, lo que hay que hacer es tomar esas paredes y "erosionarlas" para crear paredes irregulares e irregulares. Tomando el ejemplo aquí, esto es lo que podrías obtener ...

Y si en el proceso, entras en otra sala, entonces no hay problema: ¡acabas de crear una nueva caverna!

La imagen del gráfico original es de http://mathinsight.org/undirected_graph_definition

Una forma de hacerlo es agrupar todas las cuevas con un conjunto disjunto y luego eliminar todas menos las más grandes

using System.Collections.Generic;
using System.Linq;
using UnityEngine;
public class DisjointSet
{
    private List<int> _parent;
    private List<int> _rank;
    public DisjointSet(int count)
    {
        _parent = Enumerable.Range(0, count).ToList();
        _rank = Enumerable.Repeat(0, count).ToList();
    }
    public int Find(int i)
    {
        if (_parent[i] == i)
            return i;
        else
        {
            int result = Find(_parent[i]);
            _parent[i] = result;
            return result;
        }
    }
    public void Union(int i, int j)
    {
        int fi = Find(i);
        int fj = Find(j);
        int ri = _rank[fi];
        int rj = _rank[fj];
        if (fi == fj) return;
        if (ri < rj)
            _parent[fi] = fj;
        else if (rj < ri)
            _parent[fj] = fi;
        else
        {
            _parent[fj] = fi;
            _rank[fi]++;
        }
    }
    public Dictionary<int, List<int>> Split(List<bool> list)
    {
        var groups = new Dictionary<int, List<int>>();
        for (int i = 0; i < _parent.Count; i++)
        {
            Vector2 p = PathFinder.Instance.TilePosition(i);
            if (PathFinder.Instance.InsideEdge(p) && list[i])
            {
                int root = Find(i);
                if (!groups.ContainsKey(root))
                {
                    groups.Add(root, new List<int>());
                }
                groups[root].Add(i);
            }
        }
        return groups;
    }
}

Aquí es donde creo mi lista de celulares y, a veces, elimino los pequeños. A veces combino varias listas y también uso estas listas para generar y delinear cuerpos de agua y flora (parches de árboles, flores, hierba) y niebla.

private List<bool> GetCellularList(int steps, float chance, int birth, int death)
{
    int count = _width * _height;
    List<bool> list = Enumerable.Repeat(false, count).ToList();
    for (int y = 0; y < _height; y++)
    {
        for (int x = 0; x < _width; x++)
        {
            Vector2 p = new Vector2(x, y);
            int index = PathFinder.Instance.TileIndex(p);
            list[index] = Utility.RandomPercent(chance);
        }
    }
    for (int i = 0; i < steps; i++)
    {
        var temp = Enumerable.Repeat(false, count).ToList();
        for (int y = 0; y < _height; y++)
        {
            for (int x = 0; x < _width; x++)
            {
                Vector2 p = new Vector2(x, y);
                int index = PathFinder.Instance.TileIndex(p);
                if (index == -1) Debug.Log(index);
                int adjacent = GetAdjacentCount(list, p);
                bool set = list[index];
                if (set)
                {
                    if (adjacent < death)
                        set = false;
                }
                else
                {
                    if (adjacent > birth)
                        set = true;
                }
                temp[index] = set;
            }
        }
        list = temp;
    }
    if ((steps > 0) && Utility.RandomBool())
        RemoveSmall(list);
    return list;
}

Aquí está el código que elimina los grupos pequeños de la lista

private void UnionAdjacent(DisjointSet disjoint, List<bool> list, Vector2 p)
{
    for (int y = -1; y <= 1; y++)
    {
        for (int x = -1; x <= 1; x++)
        {
            if (!((x == 0) && (y == 0)))
            {
                Vector2 point = new Vector2(p.x + x, p.y + y);
                if (PathFinder.Instance.InsideEdge(point))
                {
                    int index = PathFinder.Instance.TileIndex(point);
                    if (list[index])
                    {
                        int index0 = PathFinder.Instance.TileIndex(p);
                        int root0 = disjoint.Find(index0);
                        int index1 = PathFinder.Instance.TileIndex(point);
                        int root1 = disjoint.Find(index1);
                        if (root0 != root1)
                        {
                            disjoint.Union(root0, root1);
                        }
                    }
                }
            }
        }
    }
}
private DisjointSet DisjointSetup(List<bool> list)
{
    DisjointSet disjoint = new DisjointSet(_width * _height);
    for (int y = 0; y < _height; y++)
    {
        for (int x = 0; x < _width; x++)
        {
            Vector2 p = new Vector2(x, y);
            if (PathFinder.Instance.InsideEdge(p))
            {
                int index = PathFinder.Instance.TileIndex(p);
                if (list[index])
                {
                    UnionAdjacent(disjoint, list, p);
                }
            }
        }
    }
    return disjoint;
}
private void RemoveSmallGroups(List<bool> list, Dictionary<int, List<int>> groups)
{
    int biggest = 0;
    int biggestKey = 0;
    foreach (var group in groups)
    {
        if (group.Value.Count > biggest)
        {
            biggest = group.Value.Count;
            biggestKey = group.Key;
        }
    }
    var remove = new List<int>();
    foreach (var group in groups)
    {
        if (group.Key != biggestKey)
        {
            remove.Add(group.Key);
        }
    }
    foreach (var key in remove)
    {
        FillGroup(list, groups[key]);
        groups.Remove(key);
    }
}
private void FillGroup(List<bool> list, List<int> group)
{
    foreach (int index in group)
    {
        list[index] = false;
    }
}
private void RemoveSmall(List<bool> list)
{
    DisjointSet disjoint = DisjointSetup(list);
    Dictionary<int, List<int>> groups = disjoint.Split(list);
    RemoveSmallGroups(list, groups);
}
private bool IsGroupEdge(List<bool> list, Vector2 p)
{
    bool edge = false;
    for (int y = -1; y <= 1; y++)
    {
        for (int x = -1; x <= 1; x++)
        {
            if (!((x == 0) && (y == 0)))
            {
                Vector2 point = new Vector2(p.x + x, p.y + y);
                if (PathFinder.Instance.InsideMap(point))
                {
                    int index = PathFinder.Instance.TileIndex(point);
                    if (!list[index])
                    {
                        edge = true;
                    }
                }
            }
        }
    }
    return edge;
}

o si no quitas pequeños, solo pon tus cosas en la cueva más grande

private List<int> Biggest(List<bool> list)
{
    DisjointSet disjoint = DisjointSetup(list);
    Dictionary<int, List<int>> groups = disjoint.Split(list);
    RemoveSmallGroups(list, groups);
    IEnumerator<List<int>> enumerator = groups.Values.GetEnumerator();
    enumerator.MoveNext();
    List<int> group = enumerator.Current;
    return group;
}

...

public int TileIndex(int x, int y)
{
    return y * Generator.Instance.Width + x;
}
public Vector2 TilePosition(int index)
{
    float y = index / Generator.Instance.Width;
    float x = index - Generator.Instance.Width * y;
    return new Vector2(x, y);
}