Javascript 数百次（可能数千次）碰撞检查运行良好的碰撞引擎？

Question

我正在测试制作一个基于粉末的物理引擎，但我很快运行遇到了一个问题：我的计算机在大约 150 个粒子后加载的碰撞检查太多。我需要一个物理引擎，它能够加载比这更多的碰撞，可能有数千个，并且其中一些粒子将进行多次碰撞检查。立即检查所有粒子是否与所有其他粒子发生碰撞，它们都是 2x2 正方形。对更好的碰撞系统有什么建议吗？

var ctx = document.getElementById("c").getContext("2d");
var powder = {};
var mouseX = 0;
var mouseY = 0;
var click = false;
var select = 0;
var types = {
  0: "green",
  1: "blue",
  2: "brown",
  3: "grey"
}
document.onmousemove = function(mouse) {
  mouseX = mouse.clientX - document.getElementById('c').getBoundingClientRect().left;
  mouseY = mouse.clientY - document.getElementById('c').getBoundingClientRect().top;
};

function newPowder(x, y, type, id) {
  var temp = {
    x: x,
    y: y,
    type: type,
    checked: false,
  };
  powder[id] = temp;
};

function choose(a, b) {
  if (Math.random() > 0.5) {
    return a
  } else {
    return b
  }
}
document.onkeydown = function(event) {
  if (event.keyCode === 40) { //Down
    select--;
  } else if (event.keyCode === 38) { //Up
    select++;
  } else if (event.keyCode === 32) { //space
    click = true;
  };
  if (select > 3) {
    select = 3;
  } else
  if (select < 1) {
    select = 0
  };
}
document.onkeyup = function(event) {
  if (event.keyCode === 32) {
    click = false
  };
};
var interval = setInterval(function() {
  ctx.clearRect(0, 0, 500, 500);
  if (click) {
    newPowder(Math.round(mouseX / 2) * 2, Math.round(mouseY / 2) * 2, select, Math.random() * 50);
  };
  for (var key in powder) {
    var toContinue = false;
    drawDot(powder[key].x, powder[key].y, types[powder[key].type])
    if (powder[key].type == 3) {
      continue
    }
    if (powder[key].onGround == false) {
      for (var key2 in powder) {
        if (getDistanceBetweenEntity(powder[key], powder[key2]) < 3) {
          if (collisionCheck(powder[key2].x, powder[key2].y, 2, 2, powder[key].x, powder[key].y + 2, 2, 2)) {
            powder[key].onGround = true
            if (powder[key2].type == 2 && !powder[key].checked) {
              powder[key].checked = true;
              powder[key].x += choose(choose(2, -2), 0);
            };
          };
        };
      };
    };
    if (toContinue) {
      continue;
    }
    if (powder[key].x > 500 || powder[key].y > 500) {
      delete powder[key];
      continue;
    }

    if (!powder[key].onGround) {
      powder[key].y += 2;
      checked = false;
    } else if (powder[key].type == 1) {
      powder[key].x += choose(2, -2);
    }
    powder[key].onGround = false;
  };
}, 0);

function rectangleContainsPoint(x1, y1, width, height, x, y) {
  if (width <= 0 || height <= 0) {
    return false;
  }
  return (x >= x1 && x <= x1 + width && y >= y1 && y <= y1 + height);
};

function drawDot(x, y, color) {
  ctx.save();
  ctx.fillStyle = color;
  ctx.fillRect(x, y, 2, 2);
  ctx.restore();
}

function collisionCheck(x1, y1, width1, height1, x2, y2, width2, height2) {
  if (x1 < x2 + width2 && x1 + width1 > x2 && y1 < y2 + height2 && height1 + y1 > y2) {
    return true;
  };
};
getDistanceBetweenEntity = function(entity1, entity2) {
  var vx = entity1.x - entity2.x;
  var vy = entity1.y - entity2.y;
  return Math.sqrt(vx * vx + vy * vy);
};

<!DOCTYPE html>
<html>

<head>
</head>

<body>
  <canvas id="c" width="500px" height="500px" style="border:1px solid #000" onclick="click = true"></canvas>
</body>
<script src="script.js" type="text/javascript"></script>

</html>

向上和向下箭头更改粒子类型。 Space 生成粒子。

Answer 1

首先（for in array）比 for (var i = 0; i < array.length i++);

反正你是在做强力对碰撞检测。这永远不会有效，您需要一种算法来计算每一步仅 "nearby" 个粒子。基本上，如果发现一对彼此相距很远，则不会在接下来的 X 步中计算它们，其中 X = distance / maxSpeed（您的世界中的光速）。

Answer 2

Naturally a quadratic complexity algorithm isn't going to scale very well with more particles where you check for collision of every particle against every other particle. You want to reduce the search time per particle from linear to logarithmic or better.

Acceleration structures useful here could be a fixed grid or a quad tree or K-d tree.

Instead of checking for a particle collision against every other particle, put your particles into a grid structure or hierarchy (quad tree).

For the grid, simply check the particles residing in the same grid cell(s) as the particle you are testing for collision (there could be multiple if the particle has a non-zero size).

The quad tree is simply an extension of this concept with an "adaptive" grid that forms a hierarchy. The K-d tree is similar, except it's a binary tree instead of a 4-ary tree which cycles between X/Y partitions of the search space, and doesn't have to subdivide evenly (however, it is typically the most expensive to construct among these three).

The tricky part here is that when your data is very dynamic, as in this case, you have to be able to build and update the structure fast enough. So sometimes a simpler structure like the fixed grid can work better here than the quad tree since it's easier to build that more quickly even though it provides lower-quality spatial queries.

In any case, any kind of accelerator here should make your algorithm scale a whole lot better, and I would suggest the fixed grid for starters, and the quad tree if you need even faster collision queries in exchange for increased time building and updating the accelerator.

Also given the nature of your program so far where the particles are only affected by gravity in a straight downward fashion, an even simpler way than the above methods is to sort your particles by their X position (can use radix sort to do this in linear time). Then you can do a binary search to find which particles are first in the X proximity to narrow the number of tests you are performing to logarithmic. This is potentially even worse than the fixed grid in terms of search query since it has pathological cases where all particles could be in the same X position (a fixed grid would account for both X and Y), but it's a quick way to do it.

Javascript 数百次（可能数千次）碰撞检查运行良好的碰撞引擎？

Javascript collision engine that runs well with hundreds(possibly thousands) of collision checks?

javascript

performance

collision-detection