在模拟引擎中对节点之间的交互进行建模时，有没有办法降低复杂性？

Question

我正在 Java w/JavaFX UI 中构建模拟。

我的想法是我可以创建许多 Person 对象（在一个数组中），这些对象将包含 (x,y) 坐标以表示在屏幕上呈现的定位。在每个时间步骤中，我将遍历数组并将一些应用于 Person 对象以计算它们的下一个位置（基于当前速度等）。到目前为止一切顺利...

但是，我还想对 Person 对象之间的交互进行建模（例如确保它们不能重叠并且只会相互反弹）。我能看到的唯一方法是遍历每个人的数组，将他们的 x、y 值与其他每个人进行比较，例如

Person [] population = initialisePopulationArray(); //Helper function to just set initial values

//A step in time occurs just before I render the new positions on screen
void step(){

   //Do basic initial calculation on positions O(n)
   for(Person person: population){
      updatePosition(person); //Based on trajectory etc
   }

   //Determine if new positions mean that people are overlapping and resolve O(n ^ 2)
   for(int i=0; i<population.length; i++){ //For every person
      Person person = population[i];

      for(int x=i+1; i<population.length-(i+1); i++){ //Compare against every other person
         compareAndResolve(person, population[x]; // Some function to compare and resolve any issues
      }

   }
}

如您所见，这带来了指数级的复杂性 - 这只是在这样的模拟中必须采用的方式还是我错过了更好的方式？

任何帮助将不胜感激！！！

Answer 1

如果两个人只要相距d就不再互动，那么你可以将你的世界分成大小为d x d的正方形。然后你只需要检查每个人与相同或相邻方块中的其他人。

在 Java 中，您可以使用 Hashmap<java.awt.Point, List<Person>> 来跟踪每个方格中的人员。

在模拟引擎中对节点之间的交互进行建模时，有没有办法降低复杂性？

Is there a way to reduce complexity when modelling interactions between nodes in a simulation engine?

java

algorithm

simulation

graphics

time-complexity