Algorithms Glossary

A* (A-Star) Search ↗ Pathfinding

Heuristic graph search that finds the shortest path by combining actual cost g(n) with an admissible heuristic estimate h(n). Priority queue sorted by f(n) = g(n) + h(n). Guarantees optimal paths when the heuristic never overestimates.

Agent-Based Model (ABM)

Simulation paradigm where individual entities (agents) follow local rules and interact with neighbours. Emergent macro-behaviour arises from micro-level interactions. Common in crowd, traffic, ecology, and social simulations.

Attractor

A set of numerical values toward which a dynamical system evolves over time. Point attractors stabilise at a single value; limit cycles repeat periodically; strange attractors (e.g. Lorenz) have fractal structure and sensitive dependence on initial conditions. ↗ Lorenz

Barnes-Hut Algorithm ↗ N-Body

Hierarchical tree method (quadtree in 2D, octree in 3D) that reduces N-body gravitational/electrostatic simulation from O(N²) to O(N log N). Distant clusters of particles are approximated as a single body at their centre of mass when the opening angle θ < threshold.

BFS — Breadth-First Search ↗ Pathfinding

Graph traversal that explores all nodes at depth d before depth d+1 using a FIFO queue. Guarantees shortest path in unweighted graphs. O(V+E) time complexity.

Boids ↗ Boids

Craig Reynolds' 1986 flocking algorithm. Each agent obeys three rules: Separation (avoid crowding), Alignment (steer toward average heading), Cohesion (steer toward average position). Combined, these produce naturalistic flock behaviour. Often accelerated with a spatial hash grid.

Brownian Motion

Random walk where a particle's displacement each timestep is drawn from a Gaussian distribution with variance proportional to dt. Models molecular collisions in fluids. Discretely: x += randn() * sqrt(2D·dt), where D is the diffusion coefficient.

Cellular Automaton (CA) ↗ Cellular Automata

Discrete model on a grid where each cell's next state depends on a local neighbourhood rule applied simultaneously to all cells. Conway's Game of Life uses a 3×3 Moore neighbourhood. Elementary CA (1D) uses 3-cell Wolfram codes. Complex global patterns emerge from simple local rules.

Collision Detection & Response ↗ Billiards

Detecting overlap between objects (broad phase: spatial hash, BVH; narrow phase: GJK, SAT) and computing impulse-based responses. For elastic spheres: exchange velocity components along the contact normal using conserved momentum and kinetic energy.

Constraint Solving (XPBD)

eXtended Position-Based Dynamics. Iteratively project particle positions to satisfy geometric constraints (distance, volume, collision). Robust against large time steps, unconditionally stable, used in cloth, soft-body, and ragdoll simulations. ↗ Cloth

DFS — Depth-First Search ↗ Maze

Graph traversal using a stack (or recursion) that fully explores one branch before backtracking. O(V+E). Used for maze generation (recursive backtracking), topological sort, strongly-connected components.

Diffusion-Limited Aggregation (DLA)

Particles undergo random walks until they touch a growing cluster and stick. Produces fractal dendrite structures. The Hausdorff dimension of DLA clusters is ≈ 1.71 in 2D.

Dijkstra's Algorithm ↗ Pathfinding

Single-source shortest path on non-negative weighted graphs. Uses a min-priority queue; expands cheapest unvisited node. O((V + E) log V) with a binary heap. A* is Dijkstra with a heuristic guiding the search toward the goal.

Euler Integration

Simplest explicit ODE integrator: x += v·dt, v += a·dt. First-order accurate — error accumulates O(dt) per step. Energy tends to grow (unstable at large dt). Useful for quick drafts; replace with Verlet or RK4 for accuracy.

Emergence

Macro-level phenomena arising from micro-level interactions with no central controller. Classic examples: flocking (Boids), ant trail formation, traffic jams, consciousness. A key theme in complex systems and agent-based modelling.

Flood Fill

Graph traversal (BFS or DFS) from a seed cell that paints all connected same-valued cells. Used in maze solving, terrain region labelling, paint-bucket tools, and flood simulation. O(N) where N = visited cells.

Force-Directed Layout

Graph layout method where nodes repel each other (Coulomb-like), edges attract connected nodes (spring/Hooke), and the system is iterated to a low-energy equilibrium. Barnes-Hut accelerates the pairwise repulsion from O(N²) to O(N log N).

Fourier Transform (DFT / FFT)

Decomposes a signal into sinusoidal frequency components. The Fast Fourier Transform (Cooley-Tukey) computes the DFT in O(N log N). Fundamental to wave simulation, audio analysis, image convolution, and spectral rendering. ↗ Wave

Frustum Culling

Rendering optimisation that discards objects whose bounding volumes lie entirely outside the camera's view frustum. Tested against six half-planes (near, far, left, right, top, bottom). Three.js performs this automatically when object.frustumCulled = true.

Gerstner Waves ↗ Ocean

Trochoidal wave model where water surface points follow circular orbits. Each wave i contributes a horizontal displacement Q·A·D·sin(k·D·x − ω·t) and vertical A·cos(...). Summing several waves creates realistic open-ocean swells. Used on GPUs via vertex shaders.

Genetic Algorithm (GA) ↗ Genetic

Metaheuristic inspired by natural selection. A population of candidate solutions is evolved with selection (fitness-proportional), crossover (recombine parent genes), and mutation (random perturbation). Converges toward optimal or near-optimal solutions without gradient information.

Gray-Scott Model ↗ Reaction-Diffusion

Reaction-diffusion system of two chemical species U and V. U is produced uniformly (feed rate f); U+2V→3V (autocatalytic); V is removed (kill rate k). Varying f/k produces spots, stripes, mazes, solitons, and other Turing-like patterns.

Hash Grid (Spatial Hashing)

Maps 3D world coordinates to a flat hash table via hash(cell) = (ix·p1 XOR iy·p2 XOR iz·p3) mod tableSize. Enables O(1) average-case nearest-neighbour queries, replacing O(N²) pairwise checks. Used in Boids, SPH, and cloth collision. Requires rebuilding each frame if particles move.

Instanced Rendering

GPU technique to draw N copies of the same geometry in a single draw call by supplying per-instance transform/colour buffers. In Three.js: InstancedMesh(geo, mat, count). Essential for scenes with thousands of particles, trees, or crowd agents.

Inverse Kinematics (IK)

Computes joint angles in a bone chain to place an end-effector at a target position. FABRIK (Forward And Backward Reaching IK) alternates forward and backward passes until convergence. No matrix inversion required — robust and fast for real-time simulations. ↗ Mechanisms

Jacobi Iteration

Iterative method for solving linear systems Ax = b. Each variable is updated using values from the previous iteration in parallel. Used in fluid pressure projection and cloth constraint solving. Converges for diagonally dominant matrices; Gauss-Seidel (sequential update) converges faster but is less parallelisable.

k-d Tree (k-dimensional tree)

BSP tree that recursively partitions space by alternating split axes. O(log N) average nearest-neighbour queries and range searches. Efficient for static point clouds; spatial hash grids are faster for dynamic particles that move each frame.

Leapfrog / Störmer-Verlet Integration

Symplectic second-order integrator: v_{n+½} = v_{n-½} + a·dt, x_{n+1} = x_n + v_{n+½}·dt. Energy oscillates but does not drift over long simulations — ideal for N-body, orbital mechanics, and molecular dynamics. ↗ Orbital

L-System (Lindenmayer System) ↗ L-Systems

Formal grammar-based rewriting system that models plant growth and fractal geometry. An axiom string is repeatedly expanded by production rules (e.g. F→FF+[+F-F-F]-[-F+F+F]). The resulting string is interpreted as turtle-graphics commands to draw branches and leaves.

Lorenz System ↗ Lorenz

Three coupled ODEs (dx/dt = σ(y−x), dy/dt = x(ρ−z)−y, dz/dt = xy−βz) first studied by Edward Lorenz in 1963. With σ=10, ρ=28, β=8/3 the solution is chaotic — a strange attractor shaped like a butterfly. The founding system in chaos theory.

Marching Cubes

Algorithm extracting a triangle mesh from a scalar field (isosurface). Each cube of 8 voxels has a 256-case lookup table mapping field sign combinations to triangle configurations. Used in terrain, fluid surface, and medical imaging rendering. The original 1987 algorithm has 15 distinct triangle patterns.

Monte Carlo Methods

Solve problems using random sampling. In physics rendering, cast random rays and average results to approximate global illumination. In simulation, sample probability distributions to model stochastic processes. Error scales as 1/√N regardless of dimensionality — advantage over deterministic quadrature in high dimensions.

N-Body Simulation ↗ N-Body

Compute gravitational (or Coulomb) forces between all N particles. Naïve: O(N²) pairs. Barnes-Hut: O(N log N) with octree. Fast Multipole Method: O(N) but complex. Leapfrog integration conserves energy well over long timescales.

Noise Functions (Perlin, Simplex)

Coherent pseudo-random functions that vary smoothly in space/time. Perlin noise interpolates gradient vectors on a cubic lattice. Simplex noise uses simplicial grid — fewer artefacts and faster in higher dimensions (O(N²) vs O(2^N)). Used for terrain, clouds, and organic textures. ↗ Terrain

Octree / Quadtree

Hierarchical spatial partitioning. Quadtrees divide 2D space into four equal quadrants; octrees do so in 3D. Each node subdivides when it contains more than a threshold number of objects. Supports O(log N) point queries and O(k + log N) range queries. Core data structure in Barnes-Hut and frustum culling.

ODE — Ordinary Differential Equation

An equation relating a function to its derivatives: dx/dt = f(x,t). Most physics simulations reduce to a system of ODEs. Solved numerically by integrators: Euler (1st order), Verlet (2nd order, symplectic), RK4 (4th order, general purpose).

Particle System

A large collection of small primitives (quads, points, sprites) each with position, velocity, lifetime, and visual properties. Spawned from an emitter, evolved each frame, and removed when dead. Used for fire, smoke, sparks, galaxies, and rain. GPU particle systems update transforms in compute shaders or transform feedback. ↗ Fireworks

Ping-Pong Rendering (Double Buffering)

Technique for GPU-computed simulations where state is stored in two render targets (A and B). Each frame reads from one and writes to the other, then swaps. Avoids reading and writing the same texture simultaneously. Used in reaction-diffusion, fluid, and sand simulations on the GPU.

Prey-Predator (Lotka-Volterra) ↗ Prey-Predator

System of two coupled ODEs: ẋ = αx − βxy (prey), ẏ = δxy − γy (predators). Solutions are closed periodic orbits in phase space. Extended with spatial diffusion or agent-based models for more realistic population dynamics.

Quaternion

4-component number q = w + xi + yj + zk representing a 3D rotation. Unit quaternions avoid gimbal lock, interpolate smoothly via SLERP, and compose with multiplication. Three.js: new THREE.Quaternion().setFromAxisAngle(axis, angle). For physics, integrate angular velocity as q += 0.5·Ω⊗q·dt.

Reaction-Diffusion ↗ Reaction-Diffusion

PDE system where two or more chemicals diffuse and react. General form: ∂u/∂t = Dᵤ∇²u + f(u,v). Turing (1952) showed these systems can spontaneously break symmetry to form stable spatial patterns. GPU implementations use ping-pong textures with a reaction kernel in the fragment shader.

RK4 — Runge-Kutta 4th Order

Classical explicit integrator with 4-stage weighted averaging: k1=f(y,t), k2=f(y+k1·dt/2, t+dt/2), k3=f(y+k2·dt/2, t+dt/2), k4=f(y+k3·dt, t+dt); y += (k1+2k2+2k3+k4)·dt/6. 4th-order accuracy, 4 function evaluations per step. Suitable for the Lorenz system, double pendulum, and n-body.

SDF — Signed Distance Field

A function sd(p) that returns the distance from point p to the surface of a shape — negative inside, positive outside. SDFs compose via smooth-min (blend), union (min), intersection (max), subtraction (max/neg). Used for ray-marching, collision detection, and font rendering. ↗ GLSL Patterns

SIR Model ↗ SIR

Compartmental epidemiological model: Susceptible → Infected → Recovered. ODEs: dS/dt = −βSI, dI/dt = βSI − γI, dR/dt = γI. Basic reproduction number R₀ = β/γ. If R₀ > 1 an epidemic grows. Extended models add Exposed (SEIR), vaccination, age structure, or spatial spread.

SPH — Smoothed Particle Hydrodynamics ↗ Fluid

Meshless Lagrangian fluid method. Fluid properties are interpolated by summing weighted contributions from neighbouring particles: A(r) = Σ(mⱼ/ρⱼ)·Aⱼ·W(r−rⱼ,h). The smoothing kernel W is typically cubic spline. Forces computed from density, pressure (Tait EOS), and viscosity gradients.

Spatial Hash Grid

See Hash Grid. Efficient O(1) cell lookup for dynamic particle data. Rebuild each frame by clearing the table and re-inserting all points.

Symplectic Integration

Geometric integrators that exactly preserve a modified Hamiltonian (total energy). Leapfrog/Verlet and Störmer-Verlet methods are symplectic. They bound energy error over exponentially long times — critical for orbital mechanics and molecular dynamics where non-symplectic methods accumulate drift.

Travelling Salesman Problem (TSP) ↗ TSP

NP-hard combinatorial optimisation: find the shortest tour visiting all cities exactly once. Exact solutions are infeasible beyond ~20 cities. Common heuristics: nearest-neighbour, 2-opt and 3-opt local search, Lin-Kernighan, genetic algorithms, ant colony optimisation, and simulated annealing.

Turing Instability

Mechanism by which a spatially uniform steady state is destabilised by diffusion in reaction-diffusion systems. Originally proposed by Alan Turing in 1952 to explain morphogenesis (stripe/spot patterns in animal coats). Requires an activator (slow diffusion) and inhibitor (fast diffusion).

UV Mapping

2D parameterisation of a 3D mesh surface onto the unit square [0,1]². Each vertex carries (u,v) coordinates that index into a texture. Three.js provides UV attributes on all built-in geometries; custom geometries set geometry.setAttribute('uv', ...).

Verlet Integration

Position-based integrator: x_{n+1} = 2x_n − x_{n-1} + a·dt². Velocity is implicit (difference of positions). Simple, second-order accurate, and time-reversible. Velocity Verlet stores v explicitly: v_{n+1} = v_n + ½(a_n + a_{n+1})·dt. Standard choice for cloth, soft-body, and molecular dynamics. ↗ Cloth

Voronoi Diagram

Partition of the plane into cells defined by the nearest seed point. Cell boundaries are equidistant between two seeds. Computed in O(N log N) via Fortune's sweep algorithm. Used in terrain tectonic modelling, biological cell growth, and procedural texture generation. ↗ Tectonic Plates

Wave Equation ↗ Wave

2nd-order hyperbolic PDE: ∂²u/∂t² = c²∇²u. Discretised as u(x,t+dt) = 2u(x,t) − u(x,t−dt) + c²·dt²·Δu using finite differences. The Courant number c·dt/dx must be ≤ 1 for numerical stability (CFL condition).