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

Question

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

Answer 1

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.

Answer 2

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.