使碰撞检测更高效

Making Collision Detection more Efficient

我正在开发一个 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) < 100y 之类的条件检查距玩家一定距离内的图块,这是否会使代码更有效率因为它将针对更少的图块检查碰撞,还是检查额外参数的效率较低?

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

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/ 并非常具体地询问如何改进性能不佳的代码部分,并包括您的探查器信息和相关代码部分.

回应 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% 的时间,但性能仍然很低,所以我假设即使检查碰撞的瓷砖更少,但检查它们相对位置的瓷砖太多了对玩家造成游戏 运行 缓慢。