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

8

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).entrez la description de l'image ici

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

satvikb
la source

Réponses:

4

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 ...

Graphique de réseau non dirigé

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 ...

Lignes de grotte

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 ...

Grotte érodée

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

Tim Holt
la source
Il est assez facile de placer les nœuds au hasard, mais quel type de métrique est utilisé pour les connecter? Les gens choisissent-ils généralement n nœuds? Ou peut-être doivent-ils être proches l'un de l'autre?
Kyle Baran
Si vous avez besoin d'une distribution semi-régulière avec une grille parfaite, randomisez les positions des nœuds à +/- une certaine distance. Si cela ne suffit pas, ajoutez des exceptions aléatoires qui doublent la distance aléatoire. Vous pouvez ajouter une épaisseur aléatoire aux lignes de connexion en utilisant une texture de nuage de plasma pour choisir l'épaisseur d'une manière apparemment organique.
Stephane Hockenhull
1
La connexion des nœuds est un autre problème distinct. Voici une question qui en discute -> mathematica.stackexchange.com/questions/11962/… Même si les lignes se croisent, la méthode est toujours valide.
Tim Holt
Cela dépend vraiment des exigences. Si vous êtes d'accord avec quoi que ce soit, vous pouvez le faire assez simplement. Si vous voulez une approche compliquée, vous pouvez même calculer un arbre couvrant minimum et faire terminer les couloirs s'ils atteignent un autre couloir (j'ai fait quelque chose de similaire dans un roguelike Ruby que j'ai écrit une fois).
ashes999
Je générerais ce graphique comme une feuille de route probabaliste . Commencez par créer un ensemble d '"obstacles" considérés comme infranchissables. Cela peut être fait en utilisant Perlin Noise. Ensuite, placez N nœuds de façon aléatoire et uniforme dans l'espace libre. Connectez chaque nœud à ses K nœuds les plus proches de sorte que la connexion soit dans l'espace libre. Le résultat est susceptible d'être connecté et aura l'air très organique.
mklingen
1

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);
}
Rakka Rage
la source