# How to guarantee that player fits rooms of a cave created by Cellular Automata?

I've implemented a cellular automata algorithm to generate a cave for my game and now I need my player object, which occupies 3x3 tiles in total, to be able to pass between the rooms.

The problem is that some of the rooms automatically created by cellular automata do not have the necessary width/height for the object to pass (example: a 2 x 3 tiles corridor).

How can I transform the result from the cellular automata so that I guarantee that the player is able to pass in any of the rooms? The idea is that this can be done in real time so that I can do an endless game.

This was done in GDScript but any examples in any other language, like C# for Unity, are welcome.

Update

As said in the comments, I could make a map where each cell would correspond to a 3x3 on the final map but, my problem is that I need the 1x1 tiles because my player should lose a life when hitting the walls (and that way I can create some kind of "spikes" based on the walls).

Given that, how can I add 1x1 tiles to the map created from the 3x3 and still guarantee that the player fits the cave's "corridors"?

Update 2

The only rules I currently have for CA are:

• If total neighbour walls > 4, the cell becomes a wall
• If total neighbour walls < 4, the cell becomes empty
• Else, remains as it is

The total number of iterations for the CA is 2

Solution

I was able to do this the way that DMGregory said:

• First I run the CA after building the map as I did before in order to add the "empty space adjacent to wall" cells (now on called EmptyNextToWall) to the map
• Then I run the CA with the following rules, until none of them are verified (it did not pass 5 iterations on my scenarios):
• If my current cell is EmptyNextToWall and has more than 4 EmptyNextToWall adjacent to it, make it an Empty cell
• If my current cell is EmptyNextToWall and the adjacent diagonals are a Wall and a EmptyNextToWall, make it an Empty cell
• If my current cell is EmptyNextToWall and there's no Empty cells around it, make it an Empty cell
• If my current cell is a Wall and there's at least one adjacent Empty cell, make it an EmptyNextToWall
• If my current cell is EmptyNextToWall and there's no adjacent Walls, make it an Empty cell
• why not scale it up, so that a 1x1 tile is scaled up to a 3x3 ? so you can use that cellular automata to make it that a 1x1 player could move through it, you scale it up to a 3x3? how could that not working – Serverfrog Apr 29 at 14:40
• I would assume that simple upscaling by a factor of 3 might result in corridors and rooms being much bigger than intended, and a different level of detail. Then you'd have the same problem but on the other end of the size spectrum, unless I'm missing something here. – Christian Apr 29 at 14:50
• @Serverfrog because I want to have some smaller "walls" that will cause the player to lose a life when hitting them. So it's a bit like what Christian said. The details would be different and in this case affect my gameplay intention – Cristiano Santos Apr 29 at 15:13
• You could upscale the cellular automata to larger than the player’s size, then fill in the cells with random selections of handmade tiles that allow movement through them. If you wanted you could change which tiles are chosen based on which kind of larger blocks are beside the current square. Say, select from tiles that are not passable to the north and east in a north-east corner. – Ryan1729 Apr 30 at 4:24
• Maybe something like what Ryan1729 said. Run the your algorithm on a 3x3 scale, than use some detail adding algorithm that "rounds the edges" on 1x1 scale. – Nikaas Apr 30 at 5:48

A (binary) cellular automaton can't "see" features larger than its kernel size / neighborhood.

If we consider the case of "a passage too small for a 3x3 character to fit," that could be a wall, followed by two open spaces, then another wall — ie. it's a feature that's 4 tiles wide.

So if you're using a cellular automaton with a 3x3 kernel / neighborhood, then your cell update logic can't detect the difference between this case and a wall next to unlimited open space. It can't see all the way from one wall to the opposite wall over a 2+ tile gap to know that it's too narrow and choose to fill it in / carve it wider as a result.

So, one option is to widen your kernel. A 5x5 kernel will let you detect passages 3 tiles wide with a wall on either side, and carve out/fill in spaces narrower than this.

The downside is that the automaton gets a little more complex: needing more rules to handle the greater set of variations in its neighbourhood, and more taps/samples per cell to evaluate the next state.

Another potential option is to move beyond the binary, by adding more cell values. Then each cell could store one of:

• 0: "wall"
• 1: "empty space adjacent to wall"
• 2: "empty space touching only empty space"

This is effectively a simplified distance field. The 2 values form a mask of locations your 3x3 character's center point could occupy as it navigates the map, and the 1 values form a "shoulder" outlining the walls.

Now even a CA with a 3x3 neighborhood can detect the difference between a 3-wide passage:

[ 0   1   2 ] 1   0
0 [ 1   2   1 ] 0
0   1 [ 2   1   0 ]


and a 2-wide passage:

[ 0   1   1 ] 0   0
0 [ 1   1   0 ] 0
0   1 [ 1   0   0 ]


(Here using square brackets to denote the left & right edge of the kernel as it scans across a feature)

Again the trade-off here is complexity: your cell storage needs more bits, and your cellular automaton rules need more cases to handle the various permutations of open cells adjacent/not adjacent to walls. You also need to ensure your rules maintain (or eventually re-establish) the invariant that no 2s are found adjacent to a 0.

• So, in the 2nd option, if a cell is a 1 and all adjacent cells are 0 or 1, it needs to be converted to a 2 and then, cells that are 0 and have at least one adjacent cell with 2 need to be converted to a 1? And I need to run this until those cases are no longer found in order to ensure that my player fits every passage? – Cristiano Santos May 1 at 11:05
• Not strictly, no. A cell that has neighours that are 0 might remain 1. If a 1 cell has no 2 neighbours, then it's in a narrow passage and you might want to fill it in to a 0 to close that passage fully. It all depends on the particular cellular automaton rules you choose. I'd suspect there are several valid choices that produce different forms for your map. Since we don't know what CA rules you're using currently, we can't suggest which rules would give similar results with this new CA. – DMGregory May 1 at 11:11
• I updated the question with my current rules (which are basic ones for the moment). Still processing a bit about how to do this since I'm new to Procedural Generation and CA – Cristiano Santos May 1 at 13:55

After generating the terrain, remove every block that's a border (adjacent to an "air" tile),this will make sure that even 1 wide gaps become walkable.

• In image processing this is called a "dilation" or "erosion" operation (depending on whether you view the navigable cells as positive or negative space) – DMGregory Apr 30 at 22:35
• This might create new small corridors if 2 empty spaces of the cave are separated by 2 wall tiles no? Because if I understood it correctly, it would dilate in a form of a cross and 2 crosses next to each other for a corridor of 2 x 1 tiles? – Cristiano Santos May 1 at 10:30