使碰撞检测更高效

Question

我正在开发一个 HTML5-canvas 游戏，其中地图是随机生成的 10px x 10px 的图块，玩家可以在这些图块上进行挖掘和建造。瓦片存储在一个对象数组中，一张小地图包含大约 23000 个瓦片。我的碰撞检测功能会每隔运行次（使用 requestAnimationFrame()）检查玩家相对于所有非空气方块的位置，它工作得很好，但我觉得它很密集 CPU。碰撞函数如下（代码来自网上教程）：

function colCheck(shapeA, shapeB) {
    var vX = (shapeA.x + (shapeA.width / 2)) - (shapeB.x + (shapeB.width / 2)),
    vY = (shapeA.y + (shapeA.height / 2)) - (shapeB.y + (shapeB.height / 2)),
    hWidths = (shapeA.width / 2) + (shapeB.width / 2),
    hHeights = (shapeA.height / 2) + (shapeB.height / 2),
    colDir = null;

    // if the x and y vector are less than the half width or half height, they we must be inside the object, causing a collision
    if (Math.abs(vX) < hWidths && Math.abs(vY) < hHeights) {         
        // figures out on which side we are colliding (top, bottom, left, or right)         
        var oX = hWidths - Math.abs(vX),             
            oY = hHeights - Math.abs(vY);         
        if (oX >= oY) {
            if (vY > 0) {
                colDir = "t";
                shapeA.y += oY;
            } else {
                colDir = "b";
                shapeA.y -= oY;
            }
        } else {
            if (vX > 0) {
                colDir = "l";
                shapeA.x += oX;
            } else {
                colDir = "r";
                shapeA.x -= oX;
            }
        }
    }
    return colDir;
};

然后在我的更新函数中运行这个函数以玩家和方块作为参数：

for (var i = 0; i < tiles.length; i++) {
    //the tiles tag attribute determines rendering colour and how the player can interact with it ie. dirt, rock, etc. 
    //anything except "none" is solid and therefore needs collision
    if (tiles[i].tag !== "none") {
        dir = colCheck(player, tiles[i]);
        if (dir === "l"){
            player.velX = 0;
            player.jumping = false;
        } else if  (dir === "r") {
            player.velX = 0;
            player.jumping = false;
        } else if (dir === "b") {
            player.grounded = true;
            player.jumping = false;
        } else if (dir === "t") {
            player.velY *= -0.3;
        }
    }
};

所以我想知道的是，如果我只使用 Math.abs(tiles[i].x - player.x) < 100 和 y 之类的条件检查距玩家一定距离内的图块，这是否会使代码更有效率因为它将针对更少的图块检查碰撞，还是检查额外参数的效率较低？

如果不经过测试就很难说，我该如何确定我的代码有多好运行ning？

Answer 1

but I feel like it's CPU intensive

CPU 的目的是非常快地做很多事情。有数学可以确定您的算法的效率，而且您当前的实现似乎是 O(n)。如果将图块数量减少到一个常数，您将达到 O(1)，这是更好的，但对于您的应用程序来说可能并不明显。要实现 O(1)，您必须保留 X 个最近的图块的索引，并在最近的图块发生变化时增量更新索引。 IE。如果玩家向右移动，您将修改索引，以便删除最左边的一列瓷砖，并在右侧获得一列新的瓷砖。检查碰撞时，您只需遍历索引中固定数量的图块，而不是整个图块集。

...should that make the code more efficient because it will be checking collision against fewer tiles or or is it less efficient to be checking extra parameters?

最好的回答方法是使用分析器，但我希望它能提高性能，尤其是在较大的地图上。这将是一个 O(n) 解决方案，因为您仍然迭代整个图块集，并且您可以想象当您的图块集接近无穷大时，性能会再次开始下降。您提出的解决方案可能是我上面建议的 O(1) 解决方案之间的一个很好的折衷方案。

您不想做的事情是过早地优化代码。最好在实际遇到性能问题时进行优化，并且您应该系统地进行优化，以便获得最大的收益。换句话说，即使你确实有性能问题，碰撞检测也可能不是根源。

how do I go about finding how well my code is running?

优化代码的最佳方法是 attach a profiler and measure which parts of your code are the most CPU intensive. When you figure out what part of your code is too slow, either figure out a solution yourself, or head over to https://codereview.stackexchange.com/ 并非常具体地询问如何改进性能不佳的代码部分，并包括您的探查器信息和相关代码部分.

Answer 2

回应 Samuel 的回答，建议我使用分析器：

地图由大约 23 000 个图块组成：原来的碰撞代码是运行ning 48% 的时间。通过将 if (tiles[i].tag !== "none") 更改为以下内容，检查冲突所花费的时间量下降到 5%。

if (tiles[i].tag !== "none" 
    && Math.abs(tiles[i].x - player.x) < 200 
    && Math.abs(tiles[i].y - player.y) < 200)

地图由约 180 000 个图块组成：最初的碰撞代码是运行ning 60-65% 的时间，游戏性能太低，无法玩。使用更新后的代码，碰撞功能只有运行ning 0.5% 的时间，但性能仍然很低，所以我假设即使检查碰撞的瓷砖更少，但检查它们相对位置的瓷砖太多了对玩家造成游戏运行缓慢。

使碰撞检测更高效

Making Collision Detection more Efficient

javascript

collision-detection

tile

html5-canvas