我正在为在屏幕上走动的小动物写一个模拟。我遇到的一个问题是，它们有时会靠得太近——我想解决这个问题的一个方法是有一个特定的阈值距离，当任何两个生物靠得比这个距离近时，一个力会把它们推开。
然而，在我实现这一点之前，我想知道除了暴力解决方案之外，是否还有其他已知的算法。
我一直在研究一些不同的算法，其中一个值得注意的是barnes-hut算法，它在时间上运行-但是，我不确定这是否能解决这个问题。
如有任何帮助，我们将不胜感激
最佳答案
Barnes Hut和变体是实现这一点的常用方法，但是我不会为您的用例实现完整的算法，因为它看起来太过杀伤力了。我可能只是将平面划分成一个正方形网格，比如20 x 20，并为每个细胞保留一组当前位于细胞内的所有生物。然后，对于每一个生物，只要看看它的细胞和8个（或5个在边上，或3个在角上）相邻的细胞，在一个细胞的长度内使用一个降到零的力。
有一个明显的权衡-一个更精细的网格意味着需要考虑的生物对更少，但你将不得不更频繁地将它们从一个细胞移动到另一个细胞。小于力范围的单元长度是无用的，因为您不仅要考虑8个相邻单元，而且还要考虑力范围内超出它们的单元。