Erweiterte zellulare Automaten zur Erzeugung von Höhlen

Ich versuche Höhlen in der Einheit zu bauen. Dazu versuche ich, zellulare Automaten zu verwenden. Ich habe Folgendes gefunden ( Rouge Basin Cellular Automata for Caves ), das dem ähnelt, was ich erreichen möchte.

Das Tutorial ist jedoch nicht ganz das, was ich will. Ich möchte so etwas wie das, was von dieser Website ( Don Jon Caves ) mit der Einstellung "höhlenartig" produziert wird (siehe Bild unten).

Wie Sie auf dem Bild sehen können, ist alles miteinander verbunden. Ich habe zahlreiche Methoden und Bibliotheken ausprobiert, aber nichts hat funktioniert.

Ich habe eine Weile mit diesem Problem zu kämpfen, und ich würde mich über jede Anleitung freuen.

Vielen Dank

Ich bin mir nicht sicher, welchen Ansatz das von Ihnen gezeigte Beispiel verwendet, aber hier ist, wie ich wahrscheinlich vorgehen würde, um etwas Ähnliches zu schaffen ...

Erstellen Sie zunächst ein ungerichtetes Netzwerkdiagramm, etwa so ...

Sie würden es aus einer Reihe zufällig platzierter Knoten generieren, einschließlich mindestens eines, der Ihren Höhleneingang / -ausgang darstellt.

Nachdem Sie dieses Diagramm erstellt haben, stellen Sie sich vor, Sie würden zuerst eine Reihe von Passagen entlang jedes Scheitelpunkts öffnen - nur einfache gerade Passagen, nicht unregelmäßig.

Jetzt hast du im Grunde eine Höhle, aber mit sehr glatten Wänden. Aus der obigen Grafik würde es ungefähr so ​​aussehen ...

Dann müssen Sie diese Wände nehmen und "erodieren", um raue und unregelmäßige Wände zu schaffen. Nehmen Sie das Beispiel hier, das ist, was Sie bekommen könnten ...

Und wenn Sie dabei in eine andere Halle erodieren, ist das kein Problem - Sie haben gerade eine neue Höhle geschaffen!

Das ursprüngliche Diagrammbild stammt von http://mathinsight.org/undirected_graph_definition

Eine Möglichkeit, dies zu tun, besteht darin, alle Höhlen mit einem disjunkten Satz zu gruppieren und dann alle außer den größten zu entfernen

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

Hier erstelle ich meine Mobilfunkliste und entferne manchmal die kleinen. Manchmal kombiniere ich mehrere Listen und verwende diese Listen auch, um Gewässer und Pflanzen (Flecken von Bäumen, Blumen, Gras) und Nebel zu erzeugen und zu skizzieren

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

Hier ist der Code, der die kleinen Gruppen aus der Liste entfernt

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

oder wenn Sie nicht klein entfernen, legen Sie Ihre Sachen einfach in die größte Höhle

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