 慢 6 倍：碰撞检测「O(n) 一定更快」的实测复盘)
做 Canvas 小游戏、粒子动画或物理 Demo 时但凡搜“碰撞检测怎么优化”教程几乎都会甩给你一句话用空间哈希把 O(n²) 砍成 O(n)动辄快几十上百倍。于是很多人连几十个物体的小场景也先搭一套网格。可我拿 Node 跑了一遍基准结论有点反直觉——粒子不到 2000 个的时候这套“先进”网格反而比最朴素的双重循环更慢N128 时甚至慢了 6 倍多而它做的实际距离检测次数只有对手的 1/800。背景为什么这件事值得写碰撞检测是算法动画的底层刚需判断哪些粒子/精灵互相接触。最朴素的写法是双重循环对每对 (i, j) 算一次距离平方复杂度 O(n²)。当教程告诉你“O(n²) 在 n10⁴ 时要做 10⁸ 次检测、根本跑不动”时它没说后半句——在你的场景里n 到底有没有到 10⁴社区里流传的加速比50×~1000×见 fastCollisionChecking 与各类空间哈希教程几乎都来自“几千到上万、且碰撞半径很小分布很稀疏”的设定。一旦离开这个舒适区“O(n) 一定比 O(n²) 快”这条共识就开始漏风。本文用一次本机实测把漏风的地方钉死。解剖暴力与网格到底差在哪两种做法的“工作量”不在一个维度上暴力双重循环对 ij 全量算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 世界、粒子半径 r10、固定随机种子保证可复现。对每个 n 跑 5 轮预热 11 轮取中位数墙钟并校验网格(2r)与暴力报出的真实碰撞数完全一致保证不是“算得快但算错了”。# 复现命令managed node node _bench_20260829.js # 输出下方表格并写出 _bench_results.json实测墙钟msnaive 暴力grid 网格 2rn暴力检测次数网格检测次数暴力(ms)网格(ms)网格/暴力1612010.00640.01260.51×3249610.01720.03000.57×64201610.00170.04140.04×1288128100.00810.05220.16×25632640220.02320.10740.22×5121308161140.08990.23090.39×10245237764580.39320.51330.77×2048209612818951.48771.10451.35×4096838656074856.26882.46122.55×8192335503362955624.98265.49254.55×图2两条曲线在对数坐标下相交于约 n2048。在此之前网格全程落在暴力上方更慢之后才把差距拉开到 8192 时网格快 4.55×——但此时暴力也才 25ms单帧压力本就不大。最刺眼的是检测次数与墙钟的背离N128 时网格只算了 10 次距离暴力 8128 次仅 1/813却慢了 6.4 倍N1024 时网格检测次数只有暴力的 1/1143墙钟却仍慢 1.3 倍。“少干活”在 n 太小的时候根本换不回“搭台子”的代价。图3左两柱是检测次数对数刻度网格相对暴力几乎贴地右两柱是对应墙钟网格反而更高。这张图就是“O(n) 一定更快”这条共识在小 n 段破裂的直观证据。解读交叉点为什么这么晚把数据拆开看三件事叠加把交叉点推到了近 2000常数因子的绝对体量。暴力的内层只是一个dx*dxdy*dy加一次比较现代 JIT 对两层紧凑循环优化极好网格每帧要new Map、算Math.floor(x/cs)、拼接cx,cy字符串做键、查表、遍历桶数组。这些在 n 小时是主导成本。检测次数省下的“量”还不够大。均匀稀疏分布下网格检测次数稳定约为暴力的 1/1100听着吓人可暴力在 n1024 时也就 0.39ms——省下的 0.12ms 还抵不过建表开销。网格的收益是“比值”暴力的代价是“绝对值”。n 越小暴力的绝对值越可忽略网格的固定台子越显得贵。只有当 n 大到暴力自身开始吃紧几千以上省下的比值才兑现成真实加速。换句话说复杂度描述的是“增长的斜率”不是“今天谁更快”。在小规模区间斜率更陡的那条线起点更低反而一直在下面。局限哪些事没解决cellSize 的严重错配才是真雷区。本文在均匀稀疏分布下比较了 2r 与 4r差距很小15%因为密度低时两种桶都空。但若cellSize 2r会漏检碰撞几何不成立若远大于 2r 桶里塞满粒子会退化为 O(n²)——选错尺寸的代价比“上不上网格”更致命。极端聚集会打回原形。所有粒子挤进少数格子如大量重合点时3×3 邻格退化成全量配对。本文的 8 高斯团N2048只是“中等聚类”网格仍快 1.3×真正让网格失效的是“点几乎重合”的退化分布那种情况应考虑 BVH / k-d 树mysimulator.uk 教程也承认空间哈希最适合“大致均匀”的分布。本基准是静态一帧的建表查询成本。真实动画里粒子每帧移动网格要每帧重建若物体极少移动也可增量更新摊薄开销——这是另一个维度的话题不在本次实测范围内。未覆盖 3D 与 GPU。3D 网格查询 3×3×327 个邻格、常数更高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. · GitHubGitHub 组织主页wangzifan396-wzf (WangZi) · GitHub
粒子仅 128 个，空间哈希网格就比暴力 O(n²) 慢 6 倍：碰撞检测「O(n) 一定更快」的实测复盘
做 Canvas 小游戏、粒子动画或物理 Demo 时但凡搜“碰撞检测怎么优化”教程几乎都会甩给你一句话用空间哈希把 O(n²) 砍成 O(n)动辄快几十上百倍。于是很多人连几十个物体的小场景也先搭一套网格。可我拿 Node 跑了一遍基准结论有点反直觉——粒子不到 2000 个的时候这套“先进”网格反而比最朴素的双重循环更慢N128 时甚至慢了 6 倍多而它做的实际距离检测次数只有对手的 1/800。背景为什么这件事值得写碰撞检测是算法动画的底层刚需判断哪些粒子/精灵互相接触。最朴素的写法是双重循环对每对 (i, j) 算一次距离平方复杂度 O(n²)。当教程告诉你“O(n²) 在 n10⁴ 时要做 10⁸ 次检测、根本跑不动”时它没说后半句——在你的场景里n 到底有没有到 10⁴社区里流传的加速比50×~1000×见 fastCollisionChecking 与各类空间哈希教程几乎都来自“几千到上万、且碰撞半径很小分布很稀疏”的设定。一旦离开这个舒适区“O(n) 一定比 O(n²) 快”这条共识就开始漏风。本文用一次本机实测把漏风的地方钉死。解剖暴力与网格到底差在哪两种做法的“工作量”不在一个维度上暴力双重循环对 ij 全量算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 世界、粒子半径 r10、固定随机种子保证可复现。对每个 n 跑 5 轮预热 11 轮取中位数墙钟并校验网格(2r)与暴力报出的真实碰撞数完全一致保证不是“算得快但算错了”。# 复现命令managed node node _bench_20260829.js # 输出下方表格并写出 _bench_results.json实测墙钟msnaive 暴力grid 网格 2rn暴力检测次数网格检测次数暴力(ms)网格(ms)网格/暴力1612010.00640.01260.51×3249610.01720.03000.57×64201610.00170.04140.04×1288128100.00810.05220.16×25632640220.02320.10740.22×5121308161140.08990.23090.39×10245237764580.39320.51330.77×2048209612818951.48771.10451.35×4096838656074856.26882.46122.55×8192335503362955624.98265.49254.55×图2两条曲线在对数坐标下相交于约 n2048。在此之前网格全程落在暴力上方更慢之后才把差距拉开到 8192 时网格快 4.55×——但此时暴力也才 25ms单帧压力本就不大。最刺眼的是检测次数与墙钟的背离N128 时网格只算了 10 次距离暴力 8128 次仅 1/813却慢了 6.4 倍N1024 时网格检测次数只有暴力的 1/1143墙钟却仍慢 1.3 倍。“少干活”在 n 太小的时候根本换不回“搭台子”的代价。图3左两柱是检测次数对数刻度网格相对暴力几乎贴地右两柱是对应墙钟网格反而更高。这张图就是“O(n) 一定更快”这条共识在小 n 段破裂的直观证据。解读交叉点为什么这么晚把数据拆开看三件事叠加把交叉点推到了近 2000常数因子的绝对体量。暴力的内层只是一个dx*dxdy*dy加一次比较现代 JIT 对两层紧凑循环优化极好网格每帧要new Map、算Math.floor(x/cs)、拼接cx,cy字符串做键、查表、遍历桶数组。这些在 n 小时是主导成本。检测次数省下的“量”还不够大。均匀稀疏分布下网格检测次数稳定约为暴力的 1/1100听着吓人可暴力在 n1024 时也就 0.39ms——省下的 0.12ms 还抵不过建表开销。网格的收益是“比值”暴力的代价是“绝对值”。n 越小暴力的绝对值越可忽略网格的固定台子越显得贵。只有当 n 大到暴力自身开始吃紧几千以上省下的比值才兑现成真实加速。换句话说复杂度描述的是“增长的斜率”不是“今天谁更快”。在小规模区间斜率更陡的那条线起点更低反而一直在下面。局限哪些事没解决cellSize 的严重错配才是真雷区。本文在均匀稀疏分布下比较了 2r 与 4r差距很小15%因为密度低时两种桶都空。但若cellSize 2r会漏检碰撞几何不成立若远大于 2r 桶里塞满粒子会退化为 O(n²)——选错尺寸的代价比“上不上网格”更致命。极端聚集会打回原形。所有粒子挤进少数格子如大量重合点时3×3 邻格退化成全量配对。本文的 8 高斯团N2048只是“中等聚类”网格仍快 1.3×真正让网格失效的是“点几乎重合”的退化分布那种情况应考虑 BVH / k-d 树mysimulator.uk 教程也承认空间哈希最适合“大致均匀”的分布。本基准是静态一帧的建表查询成本。真实动画里粒子每帧移动网格要每帧重建若物体极少移动也可增量更新摊薄开销——这是另一个维度的话题不在本次实测范围内。未覆盖 3D 与 GPU。3D 网格查询 3×3×327 个邻格、常数更高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. · GitHubGitHub 组织主页wangzifan396-wzf (WangZi) · GitHub
