Analyzing the Gnomish Mine Generation in NetHack

Originally discussed on BorisTheBrave.Com

While NetHack features various interesting level generation techniques, the Gnomish Mines stand out due to their implementation of Cellular Automata. This specific approach allows the game to shift away from the standard ~~rigid square rooms~~ and instead create an organic, cavernous atmosphere.

The High-Level Workflow

The generation process follows a linear pipeline to transform a random grid into a playable cave system:

Initialization: Randomly designate $40\%$ of all cells as floor tiles.
Refinement: Execute four distinct passes of Cellular Automata.
Connectivity: Bridge any isolated cave pockets using additional corridors.

Deep Dive: Cellular Automata Logic

The system evaluates each cell based on its 8-neighbor hood (the surrounding tiles). Let $N$ be the number of adjacent floor tiles.

The Pass Rules

The following table outlines how the state of a cell changes during the first three passes:

Pass	Floor Neighbors ( $N$ )	Resulting State	Purpose
1	$0 \le N \le 2$	$\to$ Rock	Clustering
	$3 \le N \le 4$	$\to$ Unchanged
	$5 \le N \le 8$	$\to$ Floor
2	$0 \le N \le 4$	$\to$ Unchanged	Unknown
	$N = 5$	$\to$ Rock
	$6 \le N \le 8$	$\to$ Unchanged
3	$0 \le N \le 2$	$\to$ Rock	Erosion
	$3 \le N \le 8$	$\to$ Unchanged

Implementation Nuances

There is a critical distinction in how these updates are applied to the grid:

In-Place Updates: During the first pass, each cell is updated immediately. This means the new state of a cell affects the calculation of its subsequent neighbors.
Buffered Updates: For all subsequent passes, the system uses a buffer. It calculates the new values for the entire grid first, then updates the map all at once to prevent "flop-flopping" (where a cell rapidly toggles between rock and floor).

# Pseudo-code for a buffered CA pass
new_grid = current_grid.copy()
for cell in current_grid:
    n = count_floor_neighbors(cell)
    if pass_rules(n) == "rock":
        new_grid[cell] = ROCK
    elif pass_rules(n) == "floor":
        new_grid[cell] = FLOOR
current_grid = new_grid

Visualizing the Pipeline

Final Observations

Pass 1 acts as a "clustering" phase, pulling random noise into cohesive open areas. Passes 3 and 4 serve as standard erosion routines to clean up the edges. However, Pass 2 remains an enigma.

"It turns cells to rock if they have exactly 5 floor neighbors... I'm still struggling to understand what purpose this is intended to achieve."

Related Content:

Chain of Thought For Humans
Mesh Welding with Spatial Hashing
Jittered Voronoi Grids