如何使这个Processing.org草图更有效率？
https://stackoverflow.com/questions/419577
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一个简单的草图（在处理中），基本上是一堆点四处游荡，如果它们进入彼此接触他们的战斗（每个人都有一个力量值，每次他们获胜时增加，如果等于获胜者是随机选择的）
适用于大约5000个12像素<！> zombies <！> （有一个半秒的轻微减速，而僵尸最初相互碰撞），问题是当僵尸变小时，它们不会相互快速碰撞，减速可以持续更长时间。
代码非常简单 - 基本上每个僵尸都是一个具有X / Y坐标的类。每个框架的所有僵尸都被轻推一个像素，随机转动lurching度（或不）。我认为缓慢的最大原因是碰撞检测 - 每个僵尸检查每隔一个（因此僵尸1检查2-5000，僵尸2检查1,3-5000等等。）
我想保持一切简单，<！> quot; plain Processing <！> quot; （不使用外部库，这可能更有效，更容易，但我发现它对学习没有用）
int numZombies = 5000;
Zombie[] zombies = new Zombie[numZombies];
void setup(){
size(512, 512);
noStroke();
for(int i = 0; i < numZombies; i++){
zombies[i] = new Zombie(i, random(width), random(height), random(360), zombies);
}
}
void draw(){
background(0);
for(int i = 0; i < numZombies; i++){
zombies[i].move();
zombies[i].display();
}
}
class Zombie{
int id; // the index of this zombie
float x, y; // current location
float angle; // angle of zombies movement
float lurching = 10; // Amount angle can change
float strength = 2;
boolean dead = false; // true means zombie is dead
float diameter = 12; // How big the zombie is
float velocity = 1.0; // How fast zombie moves
Zombie[] others; // Stores the other zombies
Zombie(int inid, float xin, float yin, float inangle, Zombie[] oin){
id = inid;
x = xin;
y = yin;
angle = inangle;
others = oin;
}
void move(){
if(dead) return;
float vx = velocity * sin(radians(180-angle));
float vy = velocity * cos(radians(180-angle));
x = x + vx;
y = y + vy;
if(x + vx < 0 || x + vx > width || y + vy < 0 || y + vy > height){
// Collided with wall
angle = angle + 180;
}
float adecide = random(3);
if(adecide < 1){
// Move left
angle=angle - lurching;
}
else if(adecide > 1 && adecide < 2){
// Don't move x
}
else if(adecide > 2){
// Move right
angle = angle + lurching;
}
checkFights();
}
void checkFights(){
for (int i=0; i < numZombies; i++) {
if (i == id || dead || others[i].dead){
continue;
}
float dx = others[i].x - x;
float dy = others[i].y - y;
float distance = sqrt(dx*dx + dy*dy);
if (distance < diameter){
fight(i);
}
}
}
void fight(int oid){
Zombie o = others[oid];
//println("Zombie " + id + "(s: "+ strength +") fighting " + oid + "(s: "+ o.strength +")");
if(strength < o.strength){
kill();
o.strength++;
}
else if (strength == o.strength){
if(random(1) > 0.5){
kill();
o.strength++;
}
else{
o.kill();
strength++;
}
}
}
void kill(){
dead = true;
}
void display(){
if(dead) return;
ellipse(x, y, diameter, diameter);
}
}
解决方案
就像1800信息所说，不知怎的，你需要减少比较次数。
将比赛区域划分为区域是一个好主意。我想象一下将当前位置与区域边界进行比较所需的时间，并从适当的集合中添加/删除僵尸是值得的。假设它们通常是直线的，它们不应该过于频繁地改变区域。
虽然区域之间可能发生碰撞但我们遇到了问题。为了捎带这个想法，你可以将屏幕划分为4个区域，然后再划分为9个区域。想象一个覆盖在十字架上的井字棋盘。这是一个糟糕的图画，但是：
| ! |
| ! |
----+--!-+----
| ! |
====|==x=|====
----+--!-+----
| ! |
| ! |
这样每个僵尸同时在两个区域中，并且一个方案中的每个边界都被另一个区域覆盖。你甚至不必再检查所有相同的僵尸，因为要么我们已经死了，要么他们会死。因此，唯一的双重处理是单个others[i].dead检查。
我能够迅速看到的另一件事是，即使你已经死了，你仍然可以遍历其余元素：
if (i == id || dead || others[i].dead){
continue;
}
它可能无法节省大量处理，但如果您：
，它肯定可以删除一些指令 if (dead) return;
代替。
另外作为附注，你想要根据距离检查直径或半径吗？
其他提示
你自己O(n^2)复杂，这就是你的算法。移动的每个僵尸都必须检查所有其他僵尸是否正确，如果它们发生碰撞会导致二次复杂性。
一个方向可能是创建一个代表你的屏幕的矩阵，而不是迭代所有其他僵尸，只需更新当前僵尸在矩阵上的位置，并检查另一个僵尸是否已占据同一个单元格。
您的基本碰撞检测算法具有 O（n ^ 2）复杂度。
您需要一些可以减少比较次数的方法。
已经提到的一种方法是将比赛场地划分为区域/区域 仅当僵尸在同一区域/区域时检查碰撞。这是一次尝试 在拓扑上（按距离）对实体进行排序。你想要的是分开这些 僵尸不仅仅是按地理位置，而是对它们进行排序，以便只在比较时进行比较 他们彼此“亲近”。你想忽略空白区域。
考虑您所在地区的树状结构。当一个区域有超过一些 N 的僵尸时，你可以将该区域分割得更小，直到区域半径接近你的碰撞距离。使用地图查找区域，并检查给定区域中的所有僵尸（以及任何“足够接近”的区域）。
您可能希望 N <！> lt; = log（n）......
也许您应该将比赛场分成区域，并且只检查同一区域内的僵尸之间的碰撞。你需要减少比较次数。
它让我想起了这个主题：不知道可能是什么问题!! 。 碰撞检测帮助我指向维基百科的碰撞检测文章。
Quadtrees 似乎经常用于2D分区
