# Messy results from simple cellular automata algorithm?

I wrote something that will first randomly populate a square a with grass tiles, and then from there it will calculate tile types from each tile's surrounding tiles. My ultimate goal is generate a terrain that somewhat resembles an island.

My first step:

Then I use cellular automata / box filtering to smooth out the terrain (thanks Arcane Engineer):

where results are far from smooth, at least according to some examples I've seen online.

Here's the code:

private void SetupTiles()
{
//get reference positions
int centerRow = chunk.size / 2;
int centerCol = chunk.size / 2;

// Loop through the chunk and add tiles
for(int row = 0; row < chunk.size; row ++)
{
for(int col = 0; col < chunk.size; col ++)
{
//Water - 0
//Grass - 1

//Create TILE
//default tile is water
Tile tile = new Tile(col, row, chunk.tileSize, tileType.Water, GetRandomWaterTexture());
//since the island is smaller than chunk,
//check if current index is within island size.
if(row >= border && row < (chunkSize-border) && col >= border && col < (chunkSize-border))
{
//Randomly assign tiles type
//TODO: This random system is not very good...
if(MathUtils.random(100)>50)
{
tile.texture = GetRandomGrassTexture();
tile.type = tileType.Grass;
}
}

chunk.tiles[row][col] = tile;
}
}

//Initialize smoothedChunk with water
//At this point, chunk is randomly filled with grass, and smoothedChunk is just water.
for(int i = 0; i < chunkSize; i++)
{
for(int j = 0; j < chunkSize; j++)
{
Tile tile = new Tile(i, j, 8, tileType.Water, GetRandomWaterTexture());
smoothedChunk.tiles[i][j] = tile;
}
}

//TODO: Smoothed island is not really smooth...
//Smooth out chunk
SmoothMap();
//Set centre tile for camera positioning
centreTile = chunk.GetTile(centerRow, centerCol);
}

private void SmoothMap ()
{
//first loop, get surrounding tiles for each tile in chunk
//we are excluding the outer most edge
for(int r = 1; r < chunkSize-1; r++)
{
for(int c = 1; c < chunkSize-1; c++)
{
//if current tile is not null
if(chunk.tiles[r][c] != null)
{
//Get its surrounding tiles.
//At this point, smoothedChunk is still empty.
chunk.tiles[r][c].surroundingTiles = GetSurroundingTiles(r, c, chunk);
//Debug info
//System.out.println("Position: " + chunk.tiles[r][c].row + ", " + chunk.tiles[r][c].col);
//System.out.println("Current tile type: " + chunk.GetTileCode(r, c));
//System.out.println("Neighboring tiles: " + chunk.tiles[r][c].surroundingTiles);
//System.out.println();
}
}
}

//second loop, smooth tiles according to their surrounding tiles
for(int r = 1; r < chunkSize-1; r++)
{
for(int c = 1; c < chunkSize-1; c++)
{
//Write into smoothedChunk
//can the threshold be a variable?
if (chunk.tiles[r][c].surroundingTiles >= 4)
{
smoothedChunk.tiles[r][c].texture = GetRandomWaterTexture();
smoothedChunk.tiles[r][c].type = tileType.Water;
}
else if (chunk.tiles[r][c].surroundingTiles < 4)
{
smoothedChunk.tiles[r][c].texture = GetRandomGrassTexture();
smoothedChunk.tiles[r][c].type = tileType.Grass;
}
}
}

//copy tiles over from smoothedChunk to chunk,
//because we still want to use chunk for everything.
for(int i = 0; i < chunkSize; i++)
{
for(int j = 0; j < chunkSize; j++)
{
chunk.tiles[i][j] = smoothedChunk.tiles[i][j];
}
}
//don't know the difference between the loop above and
//chunk = smoothedChunk;
}


Does anybody have any idea why my results are so... unsatisfactory?

If I could achieve something like this I would be really happy (excluding the color variation):

• I am not familiar with this method - I find it odd - however, after reading your code, I think you should do it multiple times. I think something like 5 to 8 times should work. The more iterations, the larger connected land masses you should have, – Theraot Feb 20 '18 at 4:35
• See this, and this. – Engineer Feb 20 '18 at 5:33
• This is also related. – Roflo Mar 23 '18 at 22:45

You require more effective smoothing methods. Google "cave generation" and you will find many. Also if you haven't already begun, some research on cellular automata will be beneficial.

This issue boils down to the way in which you treat each cell in your SmoothMap algorithm. At the moment all you do is count neighbours around the current cell, provided the current cell is itself already land, and act accordingly. This is a naive generation algorithm, and not the most intelligent way of adjusting the map because all you are doing is evaluating count and not structure.

Counting neighbours (Quantitative analysis)

You can get a bit further with neighbour-counting alone, than you are at present: Consider even cells that are currently water (unlike at the moment where you only consider land cells for neighbour-comparison). If it has a certain number of neighbours that are land, then fill this central cell with land as well. This in itself gives much more smoothing: it fills up tiny ponds with land.

If you can make what you want with just neighbour-counting, I suggest you do so, as it is a lot simpler than what follows below, BUT structural analysis (below) can provide much more control.

Expansion / dilation and contraction / constriction

You can see this in my other answer which I posted in the comments. It is perhaps not the most efficient way, but it is one alternative to smoothing and creating more rounded forms. It works, and is relatively simple. But there is a considerable loss of fine details, maybe more than you want.

Structural evaluation of neighbours (Qualitative analysis)

As I said in my previous answer to you, if you want to smooth and keep joins between islands etc. more effectively, you need to re-examine how you work with neighbours.

What you need now is a function that can go around in a circle (say clockwise from north) and examine each group of adjacently-populated neighbours. For example:

* * *
0 X *
* * 0


Here you can see that there is a group of 4 adjacent neighbours toward the northeast side, and 2 toward the southwest. Your algorithm might produce something like

0 * *
0 X 0
0 0 0


You can see that what we've done here is to erode by taking the "ends" off each segment - we took both ends (1 & 1) off the strip of length 2 at the southwest, leaving just water. We took both ends off the strip of length 4 at the northeast (1 & 1) leaving just 2.

Another way might be to say anything 2 or bigger always survives, so

0 * 0
0 X *
* 0 *


would become just

0 0 0
0 X *
0 0 *


Also, you'll notice I've been putting an X at the current position (to say we don't care what's there) but what if that becomes important to the adjacency in the previous example? Now this

0 * 0
0 * *
* 0 *


actually becomes

0 * 0
0 * *
0 0 *


instead, preserving a sort of land-bridge, as compared with the previous example which does not.

To allow you to find groups of adjacent neighbours, in order, use something like this:

Vector2 offsets[] = new Vector2[]
{
//CLOCKWISE:
new Vector2( 0,-1), //north
new Vector2(+1,-1), //northeast
new Vector2(+1, 0), //east
new Vector2(+1,+1), //southeast
new Vector2( 0,+1), //south
new Vector2(-1,+1), //southwest
new Vector2(-1,-1), //west
new Vector2(-1,-1)  //northwest

};

...

//walk clockwise around neighbours and find (start of) adjacent groups
for (int d = 0; d < 8; d++)
{
Vector2 offset = offsets[d];
Tile neighbour = tiles[centre.x + offset.x, centre.y + offset.y];
//etc.
}


I think you will perceive that there are many ways to work on this. Ideally, take your time, play, experiment and familiarise yourself with different ways of recognising different neighbour segments and how to evaluate them structurally and then act on those structures.

Box filters: A reminder

Remember that box filters don't have to be 3x3. They can be 2x2, 5x5 or whatever you want (nxn). Be aware however, that the larger n is, the higher the cost of the algorithm across the grid. That means it will be slower to run. But you can potentially get more control with a higher n.

Remember to do filter-passes interactively as in the previous code I gave you, e.g. hit spacebar to see how it looks at each step, rather than just running the filter 8x and hoping for the best. Then you can eventually settle on your final numPasses figure to hardcode in.

NOTE: I haven't gone to the extent of writing code for you as I did last time, because now you need to explore and really understand the cellular automata you are working with, and experiment yourself with the code to achieve those goals, in order to fine tune the generation algorithm to get the exact look and feel that you want. I'm happy to provide pointers. Besides that, cellular automata are a powerful tool and are worth gaining a deeper insight into for any game dev.

Repeat applications of b678/s345678 (aka the 4-5 rule) is probably the most common solution. Usually, the algorithm iterates until the output doesn't change from the previous step, though you may want to stop before that depending on your needs. As per the comments, increasing the number of iterations of your code may give you better results. It's not clear to me whether or not your rules guarantee an eventual stable result, so initially I'd recommend manually adjusting the iterations.

It's very common to pair a 'pure' cellular automata (CA) algorithm with some additional logic in order to get reliable, high quality results. Generally speaking the options usually fall into one of two categories (or a combination thereof):

Constructive techniques apply some logic either before or after the CA runs in order to constrain the result in some manner. For instance, you might start with the b678/s345678 CA to generate your initial island system. After that that you might check it for connectivity & use additional logic to merge subsets of islands until you get an acceptable result.

Generate and test techniques rely on statistics & probability to get a desired outcome. Essentially, you run your CA & then examine the result. If it's meets your criteria, you accept the result. Otherwise you rerun the CA. In order to make this a little more deterministic, you might create up to N different solutions & select the best one.

The other approach is to make the CA less naive by evaluating more than just the neighbor count; it may be arguable as to whether or not it's still a CA at that point. Again, the goal is to find ways to constrain the results to fit your needs. Since situations vary, you'll need to do some research & some experimenting.