使碰撞检测更高效
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) < 100
和 y
之类的条件检查距玩家一定距离内的图块,这是否会使代码更有效率因为它将针对更少的图块检查碰撞,还是检查额外参数的效率较低?
如果不经过测试就很难说,我该如何确定我的代码有多好 运行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% 的时间,但性能仍然很低,所以我假设即使检查碰撞的瓷砖更少,但检查它们相对位置的瓷砖太多了对玩家造成游戏 运行 缓慢。
我正在开发一个 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?
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% 的时间,但性能仍然很低,所以我假设即使检查碰撞的瓷砖更少,但检查它们相对位置的瓷砖太多了对玩家造成游戏 运行 缓慢。