企业官网建设流程全解析

做 Canvas 小游戏、粒子动画或物理 Demo 时，但凡搜“碰撞检测怎么优化”，教程几乎都会甩给你一句话：用空间哈希把 O(n²) 砍成 O(n)，动辄快几十上百倍。于是很多人连几十个物体的小场景也先搭一套网格。可我拿 Node 跑了一遍基准，结论有点反直觉——粒子不到 2000 个的时候，这套“先进”网格反而比最朴素的双重循环更慢，N=128 时甚至慢了 6 倍多，而它做的实际距离检测次数只有对手的 1/800。

背景：为什么这件事值得写

碰撞检测是算法动画的底层刚需：判断哪些粒子/精灵互相接触。最朴素的写法是双重循环，对每对 (i, j) 算一次距离平方，复杂度 O(n²)。当教程告诉你“O(n²) 在 n=10⁴ 时要做 10⁸ 次检测、根本跑不动”时，它没说后半句——在你的场景里，n 到底有没有到 10⁴？

社区里流传的加速比（50×~1000×，见 fastCollisionChecking 与各类空间哈希教程）几乎都来自“几千到上万、且碰撞半径很小（分布很稀疏）”的设定。一旦离开这个舒适区，“O(n) 一定比 O(n²) 快”这条共识就开始漏风。本文用一次本机实测，把漏风的地方钉死。

解剖：暴力与网格到底差在哪

两种做法的“工作量”不在一个维度上：

• 暴力双重循环：对 i<j 全量算dx²+dy²，总检测次数恒为n(n-1)/2，写起来就是两层for，没有任何额外数据结构。
• 均匀空间哈希网格：把世界切成cellSize = 2r的格子，用哈希表把粒子按格子归桶；查询时只扫自己格子 + 周围 8 个邻格（3×3）。理论上每帧只需 O(n) 次检测。

图1：左为暴力——每个粒子要和其余 n-1 个全部配对，检测次数随 n 平方膨胀；右为网格——先按格子归桶，再只查 3×3 邻格，检测次数近似与 n 成正比。但“归桶 + 9 格扫描”每帧都有固定开销。

关键陷阱就藏在右边：网格不是免费的。它每帧都要建哈希表、算格子坐标、做哈希、遍历 9 个桶——这些“常数开销”在小 n 时比那点省下来的距离计算还贵。复杂度符号 O(·) 只描述增长趋势，从不承诺“此刻谁更快”。

实证：一次本机基准

环境：Node v22.22.2 / Windows，固定 2000×2000 世界、粒子半径 r=10、固定随机种子保证可复现。对每个 n 跑 5 轮预热 + 11 轮取中位数墙钟，并校验网格(2r)与暴力报出的真实碰撞数完全一致（保证不是“算得快但算错了”）。

# 复现命令（managed node） node _bench_20260829.js # 输出下方表格并写出 _bench_results.json

实测墙钟（ms，naive = 暴力，grid = 网格 2r）：

图2：两条曲线在对数坐标下相交于约 n=2048。在此之前网格全程落在暴力上方（更慢），之后才把差距拉开；到 8192 时网格快 4.55×——但此时暴力也才 25ms，单帧压力本就不大。

最刺眼的是检测次数与墙钟的背离：N=128 时网格只算了 10 次距离（暴力 8128 次，仅 1/813），却慢了 6.4 倍；N=1024 时网格检测次数只有暴力的 1/1143，墙钟却仍慢 1.3 倍。“少干活”在 n 太小的时候根本换不回“搭台子”的代价。

图3：左两柱是检测次数（对数刻度，网格相对暴力几乎贴地），右两柱是对应墙钟（网格反而更高）。这张图就是“O(n) 一定更快”这条共识在小 n 段破裂的直观证据。

解读：交叉点为什么这么晚

把数据拆开看，三件事叠加把交叉点推到了近 2000：

1. 常数因子的绝对体量。暴力的内层只是一个dx*dx+dy*dy加一次比较，现代 JIT 对两层紧凑循环优化极好；网格每帧要new Map、算Math.floor(x/cs)、拼接"cx,cy"字符串做键、查表、遍历桶数组。这些在 n 小时是主导成本。
2. 检测次数省下的“量”还不够大。均匀稀疏分布下，网格检测次数稳定约为暴力的 1/1100，听着吓人，可暴力在 n=1024 时也就 0.39ms——省下的 0.12ms 还抵不过建表开销。
3. 网格的收益是“比值”，暴力的代价是“绝对值”。n 越小，暴力的绝对值越可忽略，网格的固定台子越显得贵。只有当 n 大到暴力自身开始吃紧（几千以上），省下的比值才兑现成真实加速。

换句话说：复杂度描述的是“增长的斜率”，不是“今天谁更快”。在小规模区间，斜率更陡的那条线起点更低，反而一直在下面。

局限：哪些事没解决

• cellSize 的严重错配才是真雷区。本文在均匀稀疏分布下比较了 2r 与 4r，差距很小（<15%），因为密度低时两种桶都空。但若cellSize < 2r会漏检碰撞（几何不成立），若远大于 2r 桶里塞满粒子会退化为 O(n²)——选错尺寸的代价比“上不上网格”更致命。
• 极端聚集会打回原形。所有粒子挤进少数格子（如大量重合点）时，3×3 邻格退化成全量配对。本文的 8 高斯团（N=2048）只是“中等聚类”，网格仍快 1.3×；真正让网格失效的是“点几乎重合”的退化分布，那种情况应考虑 BVH / k-d 树（mysimulator.uk 教程也承认空间哈希最适合“大致均匀”的分布）。
• 本基准是静态一帧的建表+查询成本。真实动画里粒子每帧移动，网格要每帧重建；若物体极少移动，也可增量更新摊薄开销——这是另一个维度的话题，不在本次实测范围内。
• 未覆盖 3D 与 GPU。3D 网格查询 3×3×3=27 个邻格、常数更高；GPU 上用计数排序（前缀和）做紧凑哈希又是另一套账，结论不能直接外推。

结论与下一步

可复用的方法论：别为复杂度符号提前优化。先问“我的 n 实际多大”——几百个物体的常见场景，朴素双重循环又快又稳；只有当 n 稳定上千、且你确实感到每帧吃力时，再上空间哈希，并务必把 cellSize 卡在 ≥2r。用“检测次数”判断算法优劣会误导你：小 n 段少干活不等于更快，固定开销才是裁判。

开源地址：

• 矩阵门户：GitHub - wangzifan396-wzf/WB: nano-tools: 1310 single-file, zero-dependency, local-first web utilities in one portal. Offline and private, nothing leaves your browser. Binary & protocol parsers, crypto, dev, audio, visualization, productivity. · GitHub
• 单文件工具聚合器：GitHub - wangzifan396-wzf/nano-workbench: Single-file tabbed launcher for the nano-tools matrix - one tab, 382 curated tools (of 1310), instant switching. Zero-dep. Part of nano-tools. · GitHub
• GitHub 组织主页：wangzifan396-wzf (WangZi) · GitHub