1

我有一个简单的草图（在Processing中），基本上是一堆点四处游荡，如果它们相互接触，它们就会战斗（每个都有一个力量值，每次获胜都会增加，如果相等，获胜者是随机选择的）

它适用于大约 5000 个 12 像素“僵尸”（有半秒的轻微减速，而僵尸最初会相互碰撞），问题是当僵尸变得更小时，它们不会相互碰撞其他一样快，而且减速可以持续更长的时间..

代码非常简单——基本上每个僵尸都是一个类，它有一个 X/Y 坐标。每一帧所有的僵尸都被轻推一个像素，随机转动lurching角度（或不转动）。我认为缓慢的最大原因是碰撞检测 - 每个僵尸检查每隔一个（所以僵尸 1 检查 2-5000，僵尸 2 检查 1,3-5000 等..）

我想保持一切简单和“简单处理”（不使用外部库，这可能更高效、更容易，但我觉得它对学习没有多大用处）

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);
  }
}
4

5 回答 5

4

你得到了自己O(n^2)的复杂性，这正在扼杀你的算法。正确的是，每个移动的僵尸都必须与所有其他僵尸检查是否发生碰撞，这会将您带到二次复杂度。

一个方向可能是创建一个代表您的屏幕的矩阵，而不是遍历所有其他僵尸，只需更新当前僵尸在矩阵上的位置，并检查是否有另一个僵尸已经占据了同一个单元格。

于 2009-01-07T08:44:48.850 回答
1

就像 1800 INFORMATION 说的那样，您需要以某种方式减少比较次数。

将比赛区域分成多个区域是个好主意。我想将当前位置与区域边界进行比较并从适当的集合中添加/删除僵尸所花费的时间是值得的。假设他们通常会直线前进，他们不应该过于频繁地改变区域。

尽管区域之间可能发生冲突，但我们遇到了问题。为了支持这个想法，您可以将屏幕分成 4 个区域，然后再分成 9 个区域。想想一个覆盖在十字架上的井字游戏。这是一幅糟糕的图画，但是：

    |  ! |
    |  ! |
----+--!-+----
    |  ! |
====|==x=|====
----+--!-+----
    |  ! |
    |  ! |

这样，每个僵尸同时位于两个区域中，并且一个方案中的每个边界都被另一个区域覆盖。你甚至不必再次检查所有相同的僵尸，因为要么我们死了，要么他们死了。所以唯一的双重处理是单次others[i].dead检查。

我可以很快看到的另一件事是，即使您已经死了，您仍然会遍历其余元素：

  if (i == id || dead || others[i].dead){
    continue;
  }

它可能不会节省很多处理时间，但如果您：

  if (dead) return;

反而。

另外作为旁注，您是否要根据距离检查直径或半径？

于 2009-01-07T09:08:31.923 回答
1

您的基本碰撞检测算法具有O(n^2)复杂度。

您需要一些可以减少比较次数的方法。

已经提到的一种方法是将比赛场地划分为区域/区域，并且仅当僵尸在同一区域/区域中时才检查碰撞。这是对实体进行拓扑排序（按距离）的尝试。你想要的不是简单地通过地理来区分这些僵尸，而是对它们进行排序，以便它们仅在它们“接近”彼此时进行比较。你想忽略空白区域。

考虑您的区域的树结构。当一个区域的僵尸数量超过一定数量N时，您可以将区域拆分得更小，直到区域半径接近您的碰撞距离。使用地图查找区域，并检查给定区域（以及任何“足够近”的区域）中的所有僵尸。

您可能希望N <= log(n) ...

于 2009-01-15T22:59:54.743 回答
0

也许您应该将比赛场地划分为多个区域，并且只检查同一区域内的僵尸之间的碰撞。您需要减少比较次数。

于 2009-01-07T08:38:18.007 回答
0

它让我想起了这个线程：不知道可能是什么问题！. 碰撞检测帮助我指向维基百科的碰撞检测文章。
四叉树似乎经常用于 2D 分区。

于 2009-01-07T17:10:35.493 回答