我正在编写一个应用程序，该应用程序需要在数百个不断运动的粒子之间执行 n 体模拟。该应用程序具有实时要求，因此执行模拟的算法需要快速。
我已经对此事进行了大量研究，得出的结论是 Barnes Hut 算法最适合我的需求，它对于大型粒子集似乎非常有效。
http://arborjs.org/docs/barnes-hut 非常清楚地解释了算法的工作原理，但正如标题所暗示的那样，我想知道是否需要为每次迭代重新创建树，考虑到模拟中使用的粒子总是动态运动的。如果确实需要重新创建树，如何以最有效的方式（就处理能力和内存而言）进行重建。
通常对于基于运动的索引，在发生移动后索引没有“更新”，您必须重建整个索引。
巴恩斯小屋树是一样的，必须重建。这是我在网上找到的一个示例，其中包含该过程的代码大纲。
这是对 KD-Tree 之类的东西进行构建优化的原因之一，我相信 Barnes Hut 也有同样的效果。另外，我确信有关于动态更新的研究，但大多数时候这些实现比简单的重建要困难得多。
很晚才回答这个问题。猜猜我那时从未解决过这个问题。但并不是说我已经研究了一段时间，我可以分享一些见解。@greedybuddha 所说的大部分是正确的，但它们是防止每次步骤都完全创建树的技巧和技术。像往常一样，这些技术有自己的开销（内存占用等）和必要的权衡。此外，可能无法在所有情况下都应用它们。
预先分配足够的内存来处理给定深度的八叉树。仅当所有时间步都完成时才释放内存。例如，假设对于您要使用的所有 n 体输入数据集，您知道八叉树的深度永远不会超过 10。在这种情况下，很容易计算出八叉树可能有多少个最大节点（通常是几何级数总和）。通过为每个八叉树节点做一些记账（每个节点的有效子索引），很容易重用这个缓冲区来填充八叉树节点，而无需在每个时间步分配/取消分配八叉树节点。显然，这里可能的开销是您可能会浪费大量内存，但是通过不进行每个时间步的分配/解除分配来获得性能通常的方法是限制八叉树级别的数量是允许每个叶节点有多个主体（最后一级八叉树或八叉树网格的最小单元格大小）
仅在需要时创建一个新的八叉树：可以考虑八叉树对于某些系列（突发）时间步长不改变然后它改变并且模式重复的情况。仅当物体位置在时间步长突发中变化不大时才会发生这种情况，从而八叉树结构在该突发期间保持不变。And in what situation will bodies move slowly - when the chosen timestep size is pretty small, forces exerted + initial momentum on bodies is small. 如何动态地计算出这样的爆发是一个难题。这是一个更棘手的技术，我不知道有什么简单的方法来做到这一点。这需要对时间步长粒度、物体的初始速度/加速度以及物体正在处理的力类型有一定的了解。