8
\$\begingroup\$

I am trying to make caves in Unity. To do this, I am trying to use cellular automata. I found the following (Rouge Basin Cellular Automata for Caves) that resembles what I am trying to accomplish.

However, the tutorial is not entirely what I want. I want something like what is produced by this website(Don Jon Caves) with the "cavernous" setting (see image below).enter image description here

As you can see in the image, everything is connected. I have tried numerous methods and libraries, however nothing has worked.

I have been struggling with this issue for a while, and I would appreciate any guidance what so ever.

Thanks

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

I am not sure the approach used by the example you show, but here is how I'd probably go about creating something similar...

First, create an undirected network graph, something like this...

Undirected network graph

You'd generate it from a set of randomly placed nodes, including at least one that represents your cave entrance/exit.

Now that you have this graph, imagine if you were to first open up a set of passages along each vertex - just simple straight passages, not irregular.

Now you've basically got a cave, but with very smooth walls. It would look something like this from the above graph...

Cave lines

So the thing to do then is take those walls and "erode" them to create rough and irregular walls. Taking the example here, this is what you might get...

Cave eroded

And if in the process, you erode through into another hall, then no problem - you've just created a new cavern!

The original graph image is from http://mathinsight.org/undirected_graph_definition

\$\endgroup\$
6
  • \$\begingroup\$ It's easy enough to place the nodes randomly, but what sort of metric is used to connect them? Do people usually pick n nodes? Or maybe they have to be certain closeness together? \$\endgroup\$
    – Kyle Baran
    Dec 28, 2014 at 2:20
  • \$\begingroup\$ If you need a semi-regular distribution start with a perfect grid, then randomize the node positions +/- some distance. If that's not enough add some random exceptions that double the random distance. You can add some random thickness to the connecting lines using a plasma cloud texture to pick the thickness in a seemingly organic way. \$\endgroup\$ Dec 28, 2014 at 3:51
  • 1
    \$\begingroup\$ Connecting the nodes is another separate problem. Here's one question that discusses it -> mathematica.stackexchange.com/questions/11962/… Even if the lines cross, the method is still valid. \$\endgroup\$
    – Tim Holt
    Dec 28, 2014 at 7:54
  • \$\begingroup\$ It really comes down to requirements. If you're okay with whatever, you can get this done fairly simply. If you want a complicated approach, you can even calculate a minimum spanning tree and have corridors terminate if they hit another corridor (I did something similar in a Ruby roguelike I wrote once). \$\endgroup\$
    – ashes999
    Jan 1, 2015 at 17:57
  • \$\begingroup\$ I would generate this graph as a Probabalistic Road Map. Start by creating a set of "obstacles" that are considered impassable. This can be done using Perlin Noise. Then, place N nodes randomly and at uniform in the free space. Connect each node to its K nearest nodes such that the connection is in free space. The result is likely to be connected, and will look very organic. \$\endgroup\$
    – mklingen
    Jan 1, 2015 at 19:04
1
\$\begingroup\$

one way to do this is to group all the caves with a disjoint set and then remove all but the biggest

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

here is where i create my cellular list and sometimes remove the small ones i combine multiple lists sometimes and also use these lists for generating and outlining bodies of water and flora (patches of trees, flowers, grass) and fog

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

here is the code that removes the small groups from the list

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

or if you don't remove small just put your stuff in biggest cave

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);
}
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .