# Advanced Cellular Automata to generate caves

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

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

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

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

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

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

• 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? – Kyle Baran Dec 28 '14 at 2:20
• 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. – Stephane Hockenhull Dec 28 '14 at 3:51
• 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. – Tim Holt Dec 28 '14 at 7:54
• 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). – ashes999 Jan 1 '15 at 17:57
• 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. – mklingen Jan 1 '15 at 19:04

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))
{
}
}
}
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);
bool set = list[index];
if (set)
{
set = false;
}
else
{
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])
{
}
}
}
}
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)
{
}
}
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);
}