Automates cellulaires avancés pour générer des grottes

J'essaie de faire des grottes dans Unity. Pour ce faire, j'essaie d'utiliser des automates cellulaires. J'ai trouvé ce qui suit ( Rouge Basin Cellular Automata for Caves ) qui ressemble à ce que j'essaie d'accomplir.

Cependant, le tutoriel n'est pas entièrement ce que je veux. Je veux quelque chose comme ce qui est produit par ce site Web ( Don Jon Caves ) avec le réglage "caverneux" (voir l'image ci-dessous).

Comme vous pouvez le voir sur l'image, tout est connecté. J'ai essayé de nombreuses méthodes et bibliothèques, mais rien n'a fonctionné.

Je me bats avec ce problème depuis un certain temps et j'apprécierais tout conseil.

Merci

Je ne suis pas sûr de l'approche utilisée par l'exemple que vous montrez, mais voici comment je procéderais probablement pour créer quelque chose de similaire ...

Tout d'abord, créez un graphe de réseau non orienté, quelque chose comme ça ...

Vous le généreriez à partir d'un ensemble de nœuds placés au hasard, dont au moins un qui représente votre entrée / sortie de grotte.

Maintenant que vous avez ce graphique, imaginez que vous ouvriez d'abord un ensemble de passages le long de chaque sommet - juste de simples passages droits, pas irréguliers.

Maintenant, vous avez essentiellement une grotte, mais avec des murs très lisses. Cela ressemblerait à quelque chose comme ça dans le graphique ci-dessus ...

Donc, la chose à faire est alors de prendre ces murs et de les "éroder" pour créer des murs rugueux et irréguliers. En prenant l'exemple ici, voici ce que vous pourriez obtenir ...

Et si au cours de ce processus, vous érodez dans une autre salle, alors pas de problème - vous venez de créer une nouvelle caverne!

L'image du graphique d'origine provient de http://mathinsight.org/undirected_graph_definition

une façon de le faire est de regrouper toutes les grottes avec un ensemble disjoint, puis de supprimer tout sauf le plus grand

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;
    }
}

c'est ici que je crée ma liste cellulaire et parfois j'enlève les petites, je combine parfois plusieurs listes et j'utilise également ces listes pour générer et décrire des plans d'eau et de flore (parcelles d'arbres, de fleurs, d'herbe) et de brouillard

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;
}

voici le code qui supprime les petits groupes de la liste

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;
}

ou si vous n'enlevez pas les petits, mettez simplement vos affaires dans la plus grande grotte

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);
}