Discrete Procedural Models

Lattice-Based Models

Nagel-Schreckenberg model of traffic. Discretize a traffic lane into cells of 7.5 meters length. Discretize time. At every time step jump to the most forward point possible without reaching the old position of the followed car or jumping more than v_max cells. Use some random breaking (i.e., sometimes jump one cell less).

1D Cellular Automata (CA). Consider an infinitely long string of cells. Each cell is either black or white. (This can be generalized to a finite or even infinite set of states per cell.) A rule is given how to compute the color of the cells after one time step. This rule is to be applied to all cells at once, not sequentially. Example (Stephen Wolfram's rule 30): Consider a cell and its left and right neighbors. If exactly two of those three cells are white, turn the center cell black in the next step. Do the same if the left neigbor is white and the cell and its right neighbor are black. The result is a seemingly random pattern interspersed with triangles.

2D Cellular Automata. like the 1D case, but now a infinitely extended planar array of cells.

Example: Game of Life. Each cell is either "alive" or "dead". Rules to compute the next timestep: Count how many of your eight nearest neigbors are alive. Then:

die if the count is less than 2 or greater than 3,
survive if the count is 2,
survive (or be reborn) if the count is 3.

See: Nvidia shader demos, Cinema 4D plug-in

Diffusion-Limited Aggregation (DLA). An infinitely extended 2D grid consists of cells that are either empty or occupied. At the beginning, let some cells be occupied.

Add an occupied cell far from the already occupied ones.
Move its content over the grid through a random walk.
Freeze this cell when it makes contact to one of the existing occupied cells.
Repeat indefinitely.

Result: a structure resembling a lightning, an ice crystal, or a fracture pattern.

And lots else.

Grammar-Based Models

Most prominent: L-Systems (inventor: Aristid Lindenmayer). Similar to formal languages (such as expressed in EBNF), but with parallel rewriting instead of sequential rewriting. Combined with gemetrical meaning and stack-like recovery of former states. Results in self-similar plant-like structures.

Typical symbols for turtle-like graphics:

F Move a step forward in the current direction; draw a line

f Move a step forward in the current direction, but don't draw

+ Turn left by a fixed angle (often 30°)

- Turn right by a fixed angle

[ Push state (position, direction, ...) to stack

] Pop state (position, direction, ...) from stack

Example:
Axiom: F
Rule: F -> F[-F]F[+F][F]

Example with an invisible symbol I:
Axiom: I
Rule 1: F -> FF
Rule 2: I -> F[+I]F[-I]+I

Example with parametrized symbols; draw G in different color:
Axiom: F₁
Rule F_n -> G_n[+F_n*0.7][-F_n*0.7]

Example with randomness:
Axiom: F
Rule 1: F -> F[+F]F[-F]F
Rule 2: F -> F[+F]F
Rule 3: F -> F[-F]F
Apply rules 1, 2, 3 each with a probability of 1/3.

Nice current work: Prusinkiewicz et al., The Use of Positional Information in the Modeling of Plants

F	Move a step forward in the current direction; draw a line
f	Move a step forward in the current direction, but don't draw
+	Turn left by a fixed angle (often 30°)
-	Turn right by a fixed angle
[	Push state (position, direction, ...) to stack
]	Pop state (position, direction, ...) from stack