性能 – 模拟分离力量n个物体

我正在为在屏幕上走动的小生物写一个模拟.我遇到的一个问题是它们有时会变得太近 – 我认为解决这个问题的一种方法就是有一定的阈值距离,当任何两个生物比这个距离更近时,力就会将它们分开.

然而,在我实现它之前,我想知道除了暴力解决方案之外是否还有任何已知的算法.

我一直在研究一些不同的算法,其中一个值得关注的是Barnes-Hut算法,该算法及时运行 – 但是,我不确定这是否适合这个问题.

任何帮助表示赞赏

Barnes-Hut和变体是执行此操作的常用方法,但我不会为您的用例实现完整算法,因为它似乎有点过分.我可能只是将平面划分为正方形网格,比如20 x 20,并为每个单元格维护一组,当前所有生物都位于单元格内.然后,对于每个生物,只需查看其细胞和相邻细胞的8(或侧面5或角落中的3),并使用在一个细胞长度内下降到零的力.

有一个明显的权衡 – 更精细的网格意味着需要考虑更少的生物对,但是你必须更频繁地将它们从一个细胞移动到另一个细胞.细胞长度小于力的范围是没有用的,因为你不仅要考虑8个邻居,还要考虑超出它们的力量范围内的细胞.