英文:
Is there a way to reduce complexity when modelling interactions between nodes in a simulation engine?
问题
我正在用Java和JavaFX UI构建一个模拟器。
我的想法是，我可以创建许多Person对象（在数组中），这些对象将包含（x，y）坐标，以便在屏幕上渲染定位。在每个时间步骤中，我将遍历数组，并对Person对象应用一些操作，以计算它们的下一个位置（基于当前速度等）。到目前为止还不错...
然而，我还想对Person对象之间的交互建模（例如确保它们不能重叠，而只会彼此弹开）。我唯一能想到的方法是为了比较每个人的x，y值与其他每个人的值，我需要遍历数组中的每个人，例如：
Person [] population = initialisePopulationArray(); //帮助函数，只设置初始值
//在我渲染新位置到屏幕上之前发生的时间步骤
void step(){
//对位置进行基本初始计算 O(n)
for(Person person: population){
updatePosition(person); //基于轨迹等
}
//确定新位置是否意味着人们重叠并解决 O(n ^ 2)
for(int i=0; i<population.length; i++){ //对于每个人
Person person = population[i];
for(int x=i+1; i<population.length-(i+1); i++){ //与每个其他人进行比较
compareAndResolve(person, population[x]; //一些函数来比较和解决任何问题
}
}
}
正如您所看到的，这会产生指数复杂性 - 在这样的模拟中是否只能是这种情况，还是我错过了更好的方法？
非常感谢您的任何帮助！！！
英文:
I am building a simulation in Java w/JavaFX UI.
The idea is that I can create many Person objects (in an array) which will contain (x,y) co-ordinates to denote positioning for rendering on the screen. At each step in time I will iterate through the array and apply some to the Person objects to calculate their next position (based on current velocity etc). So far so good...
However, I also want to model interactions between Person objects (make sure that they can't overlap for instance and would just bounce off each other). The only way that I can see to do this is by iterating over the array for each Person to compare their x,y values against every other person e.g.
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
}
}
}
As you can see this gives exponential complexity - is this just the way it has to be in a simulation like this or is there a better way that I have missed?
Any help would be greatly appreciated!!!
答案1
得分: 1
如果两个人的距离超过某个距离 d，则它们不进行交互，您可以将您的世界划分为大小为 d x d 的正方形区块。然后，您只需检查同一区块或相邻区块中的每个人与其他人之间的情况。
在Java中，您可以使用例如 Hashmap<java.awt.Point, List<Person>> 来跟踪每个区块中有哪些人。
英文:
If two people don't interact as long as they are farther apart than some distance d, then you can divide your world into squares of size d x d. Then you only have check each person against other people in the same or adjacent squares.
In Java you could use, for example, a Hashmap<java.awt.Point, List<Person>> to keep track of which people are in each square.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论