Cave generation

A simple modification of Conway's cellular automata yields a landscape filled with caves. The grid can later be exported and processed using other algorithms to generate meshes or outlines for other programs and libraries using, for example, the marching squares algorithm.
If you wish to generate 3D environments using this techique, I recommend you visit Sebastian Lague's video series on the topic.
Here we'll explore the algorithm and its implementation using python.


The parameters of the Algorithm

  • RES: int - tile size
  • DIMS: (int,int) - Number of columns and rows of tiles that make the grid
  • SCREEN: (int,int) - Dimensions of the screen in pixels
  • FPS: int - Frames per second of animation
  • CHANCE_ALIVE: The initial probability of a tile starting the animation alive or dead
  • TILE: Tile() - Class Tile that represent the basic unit of information in the system
  • GRID: [[TILE, ..., n=DIMS[0]], ..., n = DIMS[1]] - a 2D matrix of TILE with dimensions given by the columns and rows of DIMS
######################################## MODULES ######################################
import pygame
import random
######################################## DD ######################################
RES = 3
DIMS = (300,200)
SCREEN = (DIMS[0] * RES,DIMS[1] * RES)
display = pygame.display.set_mode(SCREEN)
CHANCE_ALIVE = 50
FPS = 60
# DD. TILE
# tile = Tile()
# interp. the tile in the implementation of Moore's landscape generator
class Tile():
    def __init__(self,c,r):
        self.c = c
        self.r = r
        self.x = self.c * RES
        self.y = self.r * RES
        self.state = 1 if random.randint(1,100)<CHANCE_ALIVE else 0
        self.nextState = self.state
        self.rect = pygame.Rect(self.x, self.y, RES, RES)
        self.color = "black"
    
    def draw(self,display):
        self.getColor()
        pygame.draw.rect(display,self.color,self.rect)
    
    def getColor(self):
        if self.state == 0:
            self.color = "white"
        elif self.state == 1:
            self.color = "#1e1e1e"
        # else:
        #     self.color = "blue"

# DD. GRID
# grid = [[TILE, ...], TILE, ...]
# interp. a 2D array of tiles
grid = []
for r in range(DIMS[1]):
    row = []
    for c in range(DIMS[0]):
        tile = Tile(c,r)
        row.append(tile)
    grid.append(row)

# TEMPLATE FOR GRID
# for row in grid:
#   for tile in row:
#       ... tile
def fn_for_grid(fn,*args):
    for row in grid:
      for tile in row:
          fn(tile,*args)

The Algorithm

  • For every TILE in GRID:
    • Calculate TOTAL_N: Add the state of the eight neighbors around this TILE:
      • Does TILE have neighbors UP, RIGHT, DOWN, LEFT?
        • T: Add TILE current state to total_N
        • F: Add 1 (wall) to TOTAL_N
    • Is TOTAL_N > 4 ? TILE next state is 1
    • Is TOTAL_N < 4 ? TILE next state is 0
    • TOTAL_N == 4: 50% change to become a 1 in next state

Let's implement the algorithm using python! 
# MODULE
import pygame
import random

# DD
DIMS = (32,32)
RES = 16
SCREEN = (DIMS[0]*RES, DIMS[1]*RES)
display = pygame.display.set_mode(SCREEN)
FPS = 10
TIME_BEE_REST = 1
TIME_BEE_ACTIVE = 0.5

# DD. TILE
# tile = Tile()
# interp. a tile in the grid
class Tile:
    def __init__(self,c,r):
        self.c = c 
        self.r = r 
        self.x = self.c * RES
        self.y = self.r * RES
        self.state = 0
        self.nextState = 0
        # attr. related to waiting periods of activity
        self.timerInState1 = 0 #Time the bee stays in a state 1
        self.resetTimerInState1 = TIME_BEE_ACTIVE
        self.recoilTimer = 0    #Time the bee rests before activating it again
        self.resetrecoilTimer = TIME_BEE_REST
        # attr. related to pixel rendering and collision detection
        self.rect = pygame.Rect(self.x, self.y, RES, RES)
    
    def draw(self):
        pygame.draw.rect(display,self.getColor(),self.rect)


    def getColor(self):
        if self.state == 0:
            return ("white")
        return "black"
    
# DD. GRID
# grid = [[TILE, ..., n=DIMS[0]], ..., n=DIMS[1]]
# interp. a 2D array of tiles arranged in a grid
grid = []
for r in range(DIMS[1]):
    row = []
    for c in range(DIMS[0]):
        tile = Tile(c,r)
        row.append(tile)
    grid.append(row)

# TEMPLATE FOR GRID
# for row in grid:
#   for tile in row:
#       ... tile





# CODE

def draw():
    display.fill("green")
    for row in grid:
        for tile in row:
            tile.draw()
    pygame.display.flip()
    pygame.time.Clock().tick(FPS)

def update():
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()

        if event.type == pygame.MOUSEBUTTONUP:
            mx,my = pygame.mouse.get_pos()
            for row in grid:
                for tile in row:
                    if tile.rect.collidepoint(mx,my):
                        tile.state = 1
                        tile.getColor()
            



    for row in grid:
        for tile in row:
            r = tile.r
            c = tile.c
            ns = [
                grid[r-1][c-1],grid[r-1][c],grid[r-1][(c+1)%DIMS[0]],
                grid[r][c-1],               grid[r][(c+1)%DIMS[0]],
                grid[(r+1)%DIMS[1]][c-1],grid[(r+1)%DIMS[1]][c],grid[(r+1)%DIMS[1]][(c+1)%DIMS[0]]
                  
                ]
            
            
            # if the bee is ready
                # if at least one neighbor is active, and bee is not resting, activate it
                # reduce the time left for the bee to rest
            # else: 
                # if the timer for staying in state 1 ran out
                    # reset timer to stay in state 1, change state to 0 and put the bee to rest
                # else: update timer to make state 1 closer to 0
            
            if tile.state == 0:
                # if there is at least one neighbor active, and tile is not already active, and bee is not resting, activate
                if sum([n.state for n in ns]) >0 and tile.recoilTimer<0:
                    tile.nextState = 1
                else:
                    tile.recoilTimer -= 0.1
            else:
                if tile.timerInState1 < 0:
                    tile.timerInState1 = tile.resetTimerInState1
                    tile.nextState = 0
                    # put the bee to rest
                    tile.recoilTimer = tile.resetrecoilTimer
                else:
                    tile.timerInState1 -= 0.1

    for row in grid:
        for tile in row:
            tile.state = tile.nextState
            


while True:
    draw()
    update()