Javascript碰撞引擎，可以很好地运行数百次(可能数千次）碰撞检查

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

本文关键字：碰撞 百次 检查 千次 引擎 很好 运行 Javascript      更新时间：2023-09-26

我正在测试制造一个基于粉末的物理引擎，我很快就遇到了一个问题：大约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>

向上和向下箭头可更改粒子类型。生成粒子的空间。

在检查每个粒子与其他粒子的碰撞时，二次复杂度算法自然不会很好地适应更多粒子。您希望将每个粒子的搜索时间从线性减少到对数或更好。

这里有用的加速度结构可以是固定网格、四叉树或K-d树。

将粒子放入网格结构或层次结构（四叉树）中，而不是检查粒子是否与其他粒子发生碰撞。

对于栅格，只需检查与正在测试碰撞的粒子位于同一栅格单元中的粒子（如果粒子大小为非零，则可能有多个）。

四叉树只是这个概念的扩展，它有一个"自适应"网格，形成了一个层次结构。K-d树是相似的，只是它是一个二叉树，而不是在搜索空间的X/Y分区之间循环的四叉树，并且不必均匀细分（然而，它通常是这三个分区中构建成本最高的）。

这里棘手的部分是，当你的数据非常动态时，比如在这种情况下，你必须能够足够快地构建和更新结构。因此，有时像固定网格这样更简单的结构在这里可以比四叉树更好地工作，因为即使它提供了较低质量的空间查询，也更容易更快地构建。

在任何情况下，这里的任何类型的加速器都应该让你的算法更好地扩展，我建议初学者使用固定网格，如果你需要更快的碰撞查询来换取更多的时间来构建和更新加速器，则使用四叉树。

此外，鉴于到目前为止程序的性质，粒子只受重力的直接向下影响，一种比上述方法更简单的方法是根据粒子的X位置对粒子进行排序（可以使用基数排序在线性时间内进行排序）。然后，你可以进行二进制搜索，找出哪些粒子首先位于X附近，以将你正在进行的测试数量缩小到对数。就搜索查询而言，这可能比固定网格更糟糕，因为它有病理情况，所有粒子都可能在同一个X位置（固定网格将同时考虑X和Y），但这是一种快速的方法。

First（for in array）比for（var i=0；i<array.length i++）慢得多；

不管怎样，你正在进行蛮力对碰撞检测。这永远不会有效率，你需要一个算法来计算每一步只"附近"的粒子。基本上，如果发现一对距离很远，则不会在接下来的X步中计算它们，其中X=距离/maxSpeed（世界中的光速）。

相关文章：