Graph grammars and L-systems

Why you need this

Tiles do not know about story. A dungeon needs the key to be reachable before the door it opens, a boss room after the key, and an optional side branch with treasure. If you fill a grid first and hope those properties fall out, they will not. Grammars generate the structure first, as a string or a graph, with rules that guarantee the properties by construction. The layout and fill stages then dress that structure in chunks and tiles. This page covers two grammars: L-systems, which rewrite strings and draw branching shapes, and graph grammars, which rewrite graphs and produce mission structure.

The idea

A grammar is an alphabet of symbols, a starting symbol (the axiom), and rewriting rules of the form "replace this with that". Applying the rules repeatedly grows the start into something large. The randomness, when there is any, comes from choosing among several rules for the same symbol with a draw $u \sim \mathrm{Uniform}(0, 1)$ from a seeded generator, so the same seed grows the same structure.

L-systems

An L-system (Lindenmayer system, 1968, invented to model plant growth) rewrites a string. Every symbol in the string is replaced at the same time, in parallel, once per iteration. The classic example is the algae system:

• Alphabet: $\{A, B\}$
• Axiom: $A$
• Rules: $A \to AB$ and $B \to A$

Turtle interpretation. A string is only useful if something reads it. The usual reader is a turtle: a pen at a position with a heading. F means move forward one unit drawing a line, + means turn left by a fixed angle, - means turn right, [ saves the current position and heading on a stack, and ] pops back to it. With the rule F -> F[+F]F[-F]F and a 25 degree angle, three iterations draw a plant: a trunk with branches, each branch a smaller copy. Read the same string as a river, and [ ] are tributaries; read it as a cave, and each F is a corridor segment and each bracket a side passage. The string is the structure; the reader decides what it looks like.

Stochastic L-systems. Give one symbol several rules with probabilities that sum to 1:

Rule	Probability
F -> F[+F]F	0.5
F -> F[-F]F	0.3
F -> FF	0.2

For every F in the string, draw $u$ from the seeded generator and pick the rule whose cumulative range contains it: $u = 0.62$ falls in $[0.5, 0.8)$, so the second rule. The same seed reproduces the same plant; a different seed gives a sibling from the same family.

Graph grammars

A graph grammar rewrites a graph: nodes with labels, joined by edges. A rule's left side is a node or a small subgraph; its right side is a bigger subgraph that replaces it, with instructions for how the new piece reconnects to the old neighbors. For mission structure the start graph is two nodes, Start -- Goal, and rules such as:

Rule	Left side	Right side
extend	an edge a -- b	a -- Corridor -- b
room	Corridor	Corridor -- Room -- Corridor
lock-and-key	an edge a -- b	a -- Lock -- b, plus a -- Key hanging off a
boss	the edge into Goal	... -- Boss -- Goal
branch	any Room	the same Room with a new Treasure node attached

Lock-and-key is the canonical rule. It puts the key on the near side of the lock, so any path from Start to the lock passes a place from which the key is reachable. The generator never has to check that the level is solvable afterward, because no rule can produce an unsolvable one. That is the whole argument for structure first.

Worked example

Algae for five steps. Apply both rules to every symbol at once:

Step	String	Length
0	A	1
1	AB	2
2	ABA	3
3	ABAAB	5
4	ABAABABA	8
5	ABAABABAABAAB	13

To get step 3 from step 2, read ABA symbol by symbol: A becomes AB, B becomes A, A becomes AB, and the pieces concatenate to AB A AB = ABAAB. The lengths are the Fibonacci numbers, because each step's string is the previous step's string followed by the string from two steps back.

A six-node mission graph in three steps. Every step picks one rule with the seeded generator and applies it to one place.

Step 0, the axiom:

Start -- Goal

Step 1, lock-and-key on the edge Start -- Goal. The lock goes on the edge; the key hangs off the near node:

Start -- Lock -- Goal
  |
 Key

Step 2, extend on the edge Start -- Key, so the key is not in the first room:

Start -- Lock -- Goal
  |
 Room -- Key

Step 3, boss on the edge Lock -- Goal:

Start -- Lock -- Boss -- Goal
  |
 Room -- Key

Six nodes: Start, Room, Key, Lock, Boss, Goal. Read it as a player would: enter, take the side passage through a room to find the key, come back, open the lock, fight the boss, finish. No rule was allowed to put the key past the lock, so no check was needed. A fourth step applying branch to Room would add optional treasure without touching the critical path.

From graph to space. A graph has no coordinates. Laying it out means assigning each node a position, then a shape:

1. Walk the graph from Start, placing each node in a chunk of a coarse grid adjacent to its parent, trying directions in seeded-random order and skipping occupied chunks. If nothing fits, back up one node and try another direction.
2. Each node becomes a room (a rectangle inside its chunk) or a whole chunk, sized by its label: Boss large, Corridor thin.
3. Each edge becomes a doorway between the two chunks, on the shared border. A Lock node's doorway gets the locked-door tile; the Key node's room gets the key object.
4. The fill stage then paints tiles inside each chunk, with the doorways fixed so the connections survive.

Layout is where the effort goes. A graph with a cycle, or with a node of degree 5, may not fit a grid without corridors that snake around; most generators restrict rules to keep the graph a tree plus a few shortcut edges, or allow corridors to bend.

In a map generator

Grammars live in the layout stage, upstream of everything else.

• The mission graph decides chunk types and required connections. The output is a list of chunks, each with a type (Room, Corridor, Boss) and the set of borders that must be open, plus objects the fill must place (key, locked door).
• The biome chain decorates them. A Markov chain over biomes runs along the critical path so that the dungeon shifts from crypt to cavern to lava as you go, one biome per chunk, without breaking the graph.
• WFC or cellular automata fill them. Wave Function Collapse with the chunk's biome tile subset paints walls and floors inside each room, with doorways pre-fixed; cellular automata do the same for cave-shaped nodes. The L-system path of a river or a cave branch becomes a list of cells the fill must keep as water or open, in the same way.
• Export writes the tile arrays plus a manifest listing the rooms, doors, and key positions, so the game can hook up its own lock logic.

As data, an L-system is a string and a rule table; a graph grammar is a node list, an edge list, and a rule table. Both are small enough to live in the parameter file next to the seed.

Common mistakes

• Rewriting in sequence instead of in parallel. Replacing the first A, then re-scanning the new string and replacing again, grows far faster than intended and produces a different shape. Build the next string from the old one and swap.
• A key rule that can place the key anywhere. If the rule attaches Key to a random node instead of the near side of the lock, half the levels are unsolvable. Symptom: a locked door with no key on the player's side. Keep the guarantee inside the rule.
• Too many iterations. An L-system string doubles or worse per step; ten iterations of a three-symbol rule is 59,049 segments, far beyond any level. Cap the iterations, or stop rewriting symbols once their segment length falls below a tile.
• A graph that will not lay out. The rules produce a node with six neighbors, or a cycle, and the grid embedding fails or overlaps rooms. Symptom: rooms drawn on top of each other, or a corridor that leaves the map. Restrict the rules, add a backtracking layout, or allow corridors to route around.
• Unseeded rule choice. A stochastic rule picked with Math.random() makes the mission graph differ per run for the same seed, and the rest of the pipeline inherits that.
• Drawing the turtle string directly as tiles. A 25 degree turn does not land on a grid. Rasterize the turtle's line segments into cells, or use 90 degree turns for grid-native structure.

Cost

Let $n$ be the number of iterations, $r$ the number of symbols on the longest right-hand side, and $L_n$ the string length after $n$ steps. Because every symbol is replaced every step and at least one rule grows the string, $L_n$ grows exponentially, up to $O(r^n)$ in the worst case (each of the $r$ new symbols itself becomes $r$ symbols next step). Time and memory to produce it are $O(L_n)$, so the exponent is what you budget, and in practice $n$ is 3 to 6. A graph grammar with $m$ rule applications on a graph of $V$ nodes costs $O(m \cdot V)$ to find matches naively, which is cheap because $V$ is tens, not thousands. The expensive part is layout: embedding a graph in a grid with backtracking is exponential in the worst case, and generators keep it tractable by keeping the graph nearly a tree and the grid coarse.

Going further

• The lock-and-key grammar work on mission graphs and space graphs, the origin of the structure-first dungeon idea.
• Parametric L-systems, where symbols carry numbers (segment length, thickness) that the rules can change.
• Shape grammars, the same idea applied to building facades and city blocks.
• Space-filling and planar graph layout algorithms, for turning a mission graph into non-overlapping rooms.
• Context-sensitive L-systems, where a rule applies only if the neighbors match, which is the string version of a cellular automaton.