Graphs and grids

Why you need this

Every 2D technique in this cluster says some version of "a tile depends on its neighbors". Cellular automata count wall neighbors. Wave Function Collapse removes tile options from a cell when a neighbor changes. Markov random fields define a whole probability model out of neighbor pairs. To read any of those pages you need a precise word for "neighbor", a fixed coordinate convention, and one algorithm, flood fill, that finds which cells are reachable from which. All three come from graphs.

The idea

A graph is a set of vertices (also called nodes) and a set of edges, where each edge joins two vertices. That is the whole definition. Vertices are the things; edges are the "is next to" or "can reach" relation between things.

Edges come in two flavors.

• Undirected: the edge A-B means the same as B-A. Two rooms joined by an open doorway.
• Directed: the edge A to B does not imply B to A. A one-way drop from a ledge to the floor below. Directed edges are drawn as arrows.

A path is a sequence of vertices where each consecutive pair is joined by an edge. A cycle is a path that starts and ends at the same vertex without repeating an edge. A connected component is a largest group of vertices that can all reach each other by some path. A cave with two separate chambers and no tunnel between them has two connected components.

Storing a graph

Take four vertices A, B, C, D with undirected edges A-B, B-C, C-A, and C-D. There are two standard ways to store this.

An adjacency list keeps, for each vertex, the list of vertices it touches.

Vertex	Neighbors
A	B, C
B	A, C
C	A, B, D
D	C

An adjacency matrix is a square table with one row and one column per vertex. Entry (row, column) is 1 when the two vertices share an edge and 0 otherwise. For an undirected graph the matrix is symmetric across its diagonal.

	A	B	C	D
A	0	1	1	0
B	1	0	1	0
C	1	1	0	1
D	0	0	1	0

The list is compact when most vertices have few neighbors. The matrix answers "are A and D adjacent?" in one lookup but stores a 0 for every pair that is not adjacent. In this graph A-B-C-A is a cycle, A-B-C-D is a path, and all four vertices are one connected component. Add vertices E and F with a single edge E-F and the graph now has two components.

Worked example

A grid is a graph

A tilemap that is $W$ tiles wide and $H$ tiles tall has $W \times H$ cells. Name each cell by its coordinates $(x, y)$, where $x$ counts columns from 0 at the left and increases to the right, and $y$ counts rows from 0 at the top and increases downward. The top-left cell is $(0, 0)$ and the bottom-right cell is $(W - 1, H - 1)$. On a $4 \times 3$ grid the cells are:

	x=0	x=1	x=2	x=3
y=0	(0,0)	(1,0)	(2,0)	(3,0)
y=1	(0,1)	(1,1)	(2,1)	(3,1)
y=2	(0,2)	(1,2)	(2,2)	(3,2)

Now treat every cell as a vertex and every "shares a side" relation as an undirected edge. That is a graph. You never store the adjacency list, because it is implied by the coordinates: the neighbors of $(x, y)$ are $(x + dx, y + dy)$ for a fixed table of offsets $(dx, dy)$.

Two neighborhoods

Say which one you mean every time. Generators behave very differently under the two.

The von Neumann neighborhood has 4 neighbors, the cells sharing a side.

Name	dx	dy
Up	0	-1
Right	1	0
Down	0	1
Left	-1	0

The Moore neighborhood has 8 neighbors, the cells sharing a side or a corner. It is the von Neumann table plus the four diagonals.

Name	dx	dy
Up-left	-1	-1
Up	0	-1
Up-right	1	-1
Left	-1	0
Right	1	0
Down-left	-1	1
Down	0	1
Down-right	1	1

For cell $(2, 1)$ on the grid above, the von Neumann neighbors are $(2, 0)$, $(3, 1)$, $(2, 2)$, $(1, 1)$. The Moore neighbors add $(1, 0)$, $(3, 0)$, $(1, 2)$, $(3, 2)$.

What happens at the edge of the map

Cell $(0, 0)$ has no cell above it. Something has to be decided for the offsets that point off the grid, and each choice changes what the map looks like.

Option	Rule	What you see
Clamp	Replace an out-of-range coordinate with the nearest valid one, so $(0, -1)$ becomes $(0, 0)$.	Edge cells see themselves as a neighbor. Patterns smear outward along the border and edges look thicker than the interior.
Wrap (torus)	Take coordinates modulo the size, so $(0, -1)$ becomes $(0, H - 1)$.	The map tiles seamlessly. A cave that runs off the right side continues on the left. Good for repeating backgrounds, wrong for a bounded level.
Outside is wall	Any off-grid cell counts as a fixed value, usually wall or water.	The border fills in solid, so the playable area is naturally enclosed. This is the usual choice for caves.
Outside is missing	Skip the neighbor entirely, so edge cells have fewer neighbors.	Rules that count neighbors behave differently at the border than inside. A corner cell has only 3 neighbors, so under a "5 of 8" rule it can never become wall and the corners always open up.

Flood fill: finding one connected region

Flood fill starts at one cell and visits every cell of the same value that can be reached through neighbors. It is breadth-first search on the grid graph. This version uses the von Neumann neighborhood and stores the grid as a flat array where cell $(x, y)$ lives at index $y \cdot W + x$.

function floodFill(grid, W, H, sx, sy) {
  const target = grid[sy * W + sx];
  const seen = new Uint8Array(W * H);
  const queue = [[sx, sy]], region = [];
  seen[sy * W + sx] = 1;
  for (let head = 0; head < queue.length; head++) {
    const [x, y] = queue[head];
    region.push([x, y]);
    for (const [dx, dy] of [[0, -1], [1, 0], [0, 1], [-1, 0]]) {
      const nx = x + dx, ny = y + dy;
      if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
      const i = ny * W + nx;
      if (seen[i] || grid[i] !== target) continue;
      seen[i] = 1;
      queue.push([nx, ny]);
    }
  }
  return region;
}

Run it on a 5-wide, 3-tall grid where 1 is wall and 0 is floor:

1 0 0 1 0
1 1 0 1 0
0 0 0 1 1

Starting at $(1, 0)$ it returns the six floor cells on the left: $(1, 0)$, $(2, 0)$, $(2, 1)$, $(2, 2)$, $(1, 2)$, $(0, 2)$, and nothing else, because the column of walls at $x = 3$ blocks the way. The two floor cells at $(4, 0)$ and $(4, 1)$ are a second connected component. To find all components, loop over every cell and start a fill at each one not yet in seen.

In a map generator

Graphs show up at every stage of the pipeline described on the hub page.

• Catalog: the tile catalog is itself a graph. Vertices are tile ids, and a directed edge from tile $a$ to tile $b$ labelled "right" means $b$ may sit to the right of $a$. Wave Function Collapse consumes exactly this.
• Layout: a dungeon plan is a graph of rooms before it is a grid of tiles. Locks, keys, and critical paths are path and cycle statements.
• Fill: cellular automata count neighbors in a Moore neighborhood with outside treated as wall. Flood fill then keeps the largest floor component so the player cannot spawn in a sealed pocket.
• Regime over time: regions that share a border are neighbors in a coarse graph, and a flood or fire regime spreads along its edges.
• Export: the flat index $y \cdot W + x$ is exactly how a tile layer is stored in the JSON manifest.

"A tile depends on its neighbors" is a graph statement: the value at a vertex is a function of the values at the vertices it shares an edge with, and nothing else. Change the edge set (switch von Neumann for Moore, or wrap the borders) and you change the generator without touching the rule.

Common mistakes

• Mixing up $x$ and $y$ when indexing. The flat index is $y \cdot W + x$, not $x \cdot H + y$. Get it backwards and a $64 \times 40$ map renders as a shredded diagonal smear.
• Forgetting to say which neighborhood. A rule tuned for 8 neighbors applied to 4 produces a map that is almost entirely one value, because the counts never reach the thresholds.
• Clamping when you meant "outside is wall". The border of a cave grows a thick rind two or three cells deep instead of a clean one-cell wall.
• Wrapping by accident. A negative coordinate fed into a JavaScript modulo stays negative, so (-1) % W is -1, not W - 1. Islands appear cut off at one edge and continued on the other, or the code reads undefined.
• Recursive flood fill on a big map. A recursive version calls itself once per cell and overflows the call stack somewhere around a few thousand cells. Use the queue version above.
• Treating diagonal contact as connected for movement. Two floor cells that touch only at a corner are Moore neighbors but a player who moves in four directions cannot pass between them. Use von Neumann for reachability and Moore for smoothing.

Cost

For a general graph with $V$ vertices and $E$ edges, an adjacency list uses $O(V + E)$ memory and an adjacency matrix uses $O(V^2)$. A grid needs neither, since neighbors are computed from coordinates in constant time. Flood fill visits each cell at most once and checks each of its $k$ neighbors, so the time is $O(k \cdot W \cdot H)$ with $k = 4$ or $8$, and the seen array is $O(W \cdot H)$ memory. On a $256 \times 256$ map that is about 65 thousand cells and a quarter million neighbor checks, which runs in a few milliseconds. It starts to hurt when you flood fill every chunk every frame; fill once per generation instead and cache the component labels.

Going further

• Breadth-first search and depth-first search in any introductory algorithms text; flood fill is the former on a grid.
• Dijkstra's algorithm, which is breadth-first search with weighted edges, for path costs across terrain.
• Union-find (disjoint set union), a faster way to label connected components when you only need labels and not the cells in order.
• Cellular automata, the first technique page that uses neighborhoods and flood fill together.
• Tilemaps and autotiling, where neighbor bits pick which tile art to draw.