ALGORITHM LAB · 算法实验室
有限的规则，无尽的形态。
背景里的每一种颜色都来自同一个简单过程：从一个格子出发，随机向尚未连接的邻居伸出一条边，直到连通整个平面——得到一棵随机生成树。颜色只表示它离起点有多远。
随机遍历生成树
“An algorithm must be seen to be believed.”
算法必须亲眼看见，才能令人信服。
Donald E. Knuth · 《计算机程序设计艺术》第一卷 · 1968
THE GALLERY · 展厅
它们不是录好的动画，而是算法本身在你的浏览器里一步步执行。可以切换算法、调整参数、重新开始，也可以直接在画布上动手。
01排序 · SORTING
一列被 Fisher–Yates 洗牌彻底打乱的数，柱高与颜色都代表数值。每种排序算法都在用自己的策略消灭“逆序对”：冒泡和插入一次只修正相邻的一对；希尔排序先做远距离的粗调；快速排序选一个枢轴把序列一分为二；归并排序先分后合；堆排序则借助一棵藏在数组里的二叉树。
白色闪光是正在比较或写入的位置。打开声音，可以“听见”算法的节奏——灵感来自 The Sound of Sorting。
# Lomuto 划分：快速排序的核心
partition(a, lo, hi):
pivot ← a[hi]; i ← lo
for j in lo … hi−1:
if a[j] < pivot:
swap(a[i], a[j]); i ← i + 1
swap(a[i], a[hi])
return i02迷宫 · SPANNING TREES
一座“完美迷宫”就是网格上的一棵生成树：任意两格之间恰好只有一条路。Wilson 算法用擦除回路的随机游走生成均匀生成树——所有可能的迷宫出现的概率完全相等；随机深度优先会钻出又长又深的走廊；随机遍历则像珊瑚一样四处分叉。
品红色是正在进行的游走或生长前沿。生成结束后，颜色从中心向外泛开，标记每一格沿迷宫到中心的距离；白线是离中心最远的那条路。
# Wilson：均匀生成树
tree ← { 任意一格 }
for each cell c not in tree:
walk ← 从 c 随机游走，直到碰到 tree
擦除 walk 中形成的回路
tree ← tree ∪ walk03寻路 · PATHFINDING
广度优先搜索一视同仁地向四面扩散；Dijkstra 按已走的代价扩展，会绕开代价为 5 的紫色沼泽；贪心最佳优先只盯着终点，快，但未必最短；A* 把两者相加：f(n) = g(n) + h(n)。只要启发函数 h 从不高估剩余距离，A* 依然保证最优，同时少走许多冤枉路。
拖动青色起点或品红终点；在空地上按住拖动可以画墙或擦墙。颜色的等高带表示到起点的代价。
# A*：按 f = g + h 出队
open ← 优先队列 { start }
while open 非空:
n ← open.pop_min()
if n = goal: break
for m in neighbors(n):
g′ ← g[n] + cost(m)
if g′ < g[m]:
g[m] ← g′; parent[m] ← n
open.push(m, g′ + h(m))04采样 · POISSON DISC
纯随机撒点既会扎堆也会留白。泊松圆盘采样要求任意两点的距离不小于 r，又要尽量填满空间——这种“蓝噪声”分布常见于渲染抗锯齿、点画风格和植被摆放。Bridson 算法借助边长 r/√2 的背景网格，让每次检查只涉及常数个邻居，整体只需线性时间。
品红点是仍在“繁殖”的活跃点，线条连接每个点和生出它的父点，颜色表示代数。切到“均匀随机”对比：半径 r/2 的圆盘会大量重叠。点击画布，从那里重新开始。
# Bridson 快速泊松圆盘采样
active ← [ x₀ ]
while active 非空:
p ← active 中随机一点
在环 [r, 2r] 内生成 k 个候选 q
if 某个 q 与已有点距离都 ≥ r:
加入 q; active.push(q)
else: active.remove(p)05傅里叶 · EPICYCLES
把一条闭合曲线看成复平面上随时间运动的点，离散傅里叶变换就能把它拆成一组以不同频率旋转的圆——本轮。把这些旋转向量首尾相接，最末端的笔尖便重新画出原来的形状。少数几个大圆承担了绝大部分“能量”，圆越多，细节越清晰。
在画布上按住拖动，画一条你自己的曲线；滑块改变参与重建的圆的数量。
# 离散傅里叶变换与重建
for k in −N/2 … N/2−1:
X[k] ← (1/N) Σₙ z[n]·e^(−2πi·kn/N)
按 |X[k]| 从大到小排序
pen(t) ← Σₖ X[k]·e^(2πi·kt)06元胞自动机 · GAME OF LIFE
1970 年，数学家 John Conway 设计了“生命游戏”，经 Martin Gardner 在《科学美国人》专栏介绍后风靡一时。每个细胞只看身边 8 个邻居：活细胞有 2 或 3 个活邻居就存活，死细胞恰有 3 个活邻居就诞生，其余一律死亡。规则简单到一行就能写完，这个系统却是图灵完备的。
白色是新生细胞，越古老颜色越深；暗红的余晖是刚刚逝去的生命。在画布上拖动可以播种。
# 每一代，所有细胞同时更新
for each cell:
k ← 周围 8 格中活细胞数
next ← (k = 3) or (alive and k = 2)07群体 · BOIDS
1986 年，Craig Reynolds 只用三条局部规则就模拟出了鸟群：分离——避开挤得太近的同伴；对齐——朝同伴的平均方向飞；聚合——向同伴的中心靠拢。没有领头鸟，也没有全局计划，整体的秩序从个体之间的局部互动中“涌现”出来。
把鼠标移到画布上驱散鸟群，或拖动滑块调整三条规则的权重。颜色表示飞行方向。
# 每只 boid 只看感知半径内的邻居
for each boid b:
N ← neighbors(b, r)
a ← w₁·separation(N) + w₂·alignment(N)
+ w₃·cohesion(N)
b.v ← limit(b.v + a, vmax)
b.p ← b.p + b.v08分形 · MANDELBROT
对复平面上的每个点 c，从 z = 0 开始反复计算 z ← z² + c。若 z 永远有界，c 就属于 Mandelbrot 集（黑色）；否则按它逃逸的快慢着色。这一行迭代定义了一条无限复杂的边界：无论放大多少倍，都会出现新的螺旋、触须和缩小的自身。
点击放大 3 倍并以该点为中心，右键缩小。放大到约 10¹³ 倍时会碰到双精度浮点数的极限。
# 逃逸时间算法
z ← 0; n ← 0
while |z| ≤ R and n < max:
z ← z² + c; n ← n + 1
color ← palette(n + 1 − log₂ ln|z|)TIMELINE · 年表
从泥板与羊皮纸上的演算，到今天每秒运行数十亿次的程序，一些想法穿越了整个文明史。
《几何原本》中的辗转相除法，求两数的最大公约数；它的扩展形式至今仍用于 RSA 密钥生成。
他的名字被拉丁化为 Algoritmi，最终演变成了 algorithm 这个词。
高斯在计算小行星轨道时已用到与 FFT 相同的思路，只是生前没有发表。
Alan Turing 用一台想象中的机器，给出了“可计算”的精确定义。
John von Neumann 提出先分后合的排序方法，分治思想由此深入人心。
George Dantzig 为线性规划给出了实用解法，至今仍是运筹学的基石。
Kruskal 与 Prim 先后给出贪心构造最小生成树的算法。
Dijkstra 发表单源最短路径算法；同年 Hoare 构思出快速排序，1961 年发表。
Cooley 与 Tukey 让 DFT 从 O(N²) 降到 O(N log N)，数字信号处理从此起飞。
Hart、Nilsson 与 Raphael 为机器人 Shakey 的路径规划提出 A*。
John Conway 的元胞自动机登上《科学美国人》，同年 Gosper 找到滑翔机枪。
Rivest、Shamir 与 Adleman 发表公钥密码体制，安全性建立在大数分解之难上。
Benoit Mandelbrot 在 IBM 用计算机绘出这一分形的高分辨率图像。
Craig Reynolds 用三条局部规则模拟鸟群，开启了群体智能的计算机图形学。
用擦除回路的随机游走，比覆盖时间更快地生成均匀随机生成树。
Brin 与 Page 把整个网络看成一条马尔可夫链，用它的平稳分布衡量网页的重要性。
Robert Bridson 给出任意维度下线性时间的蓝噪声采样算法。
CREDITS · 参考与致敬
本站所有展品均由原生 JavaScript 与 Canvas 实现，不使用框架，不加载任何第三方资源，也没有任何追踪。下面这些文章和项目给了它最多的灵感。