javascript - 为什么我的四叉树没有提高性能？

Question

我有一个 boids 植绒模拟设置。它最初的工作原理是让每个 boid 循环通过每个 boid，以便它们都不断知道彼此的位置，以便判断它们是近还是远，但后来我切换到四叉树设计，这样 boid 只需循环通过实际上在附近的生物。但是，它对模拟的 FPS 几乎没有任何改进。就好像我还在循环遍历每一个 boid。

我的实施中有一些错误吗？repo在这里，相关代码主要在 main.js、quadtree.js 和 boid.js 中。直播网站在这里

Answer 1

您没有看到四叉树的明显性能提升的原因是您的模拟的性质。目前，默认分离会导致大量 boid “收敛”到同一位置。

由于空间分区，同一位置的许多对象将抵消可能的加速。如果所有对象都在相同或接近的位置，则该区域中的 boid 将被迫检查该区域中的所有其他 boid。

您可以通过使用默认设置观察或分析您的应用程序来向自己证明您的 Quadtree 正在工作。现在将分离调到最大。您会在视觉上或通过剖析看到，随着 boids 分布得更均匀，FPS 显着增加。这是因为四叉树现在可以通过其空间分区来阻止计算。

使用默认低分离：

最大分离：

您可以在第二张图片中看到性能是如何提高的。另请注意，另一位评论者的猜想是四叉树 ( insert) 的构造一直在占用，这是错误的。

虽然在某些应用程序中，您可能能够在事物移动时更新四叉树，因为在此模拟中，每个组成部分都会移动每一帧，从头开始重建四叉树的工作量较少，然后取出每个对象并将其重新插入到新位置。

跳过平方根而只使用距离平方的建议很好，因为这会给你带来更多的性能。