AABB 碰撞解决滑边
AABB collision resolution slipping sides
所以，我目前正在通过尝试为我的游戏引擎制作一个简单的物理引擎来重新发明轮子（并学到很多东西）。我一直在网上搜索，试图（但未能）解决我当前的问题。关于这个主题有很多资源，但我发现的 none 似乎适用于我的情况。
问题简而言之：当两个矩形发生碰撞时，碰撞解决方案在某些角上无法按预期工作。它失败的方式因矩形的尺寸而异。我正在寻找的是一种 "shortest overlap" 的碰撞解决方案或其他相当简单的解决方案（我愿意接受建议！）。（向下滚动以获得更好的解释和插图）。
警告：以下代码可能效率不高...
首先，这是我的物理循环。它只是循环遍历所有游戏实体并检查它们是否与任何其他游戏实体发生碰撞。它效率不高（n^2 和所有这些），但它现在有效。
updatePhysics: function(step) {
// Loop through entities and update positions based on velocities
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled) {
switch (entity.entityType) {
case VroomEntity.KINEMATIC:
entity.pos.x += entity.vel.x * step;
entity.pos.y += entity.vel.y * step;
break;
case VroomEntity.DYNAMIC:
// Dynamic stuff
break;
}
}
}
// Loop through entities and detect collisions. Resolve collisions as they are detected.
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled && entity.entityType !== VroomEntity.STATIC) {
for (var targetID in Vroom.entityList) {
if (targetID !== entityID) {
var target = Vroom.entityList[targetID];
if (target.physicsEnabled) {
// Check if current entity and target is colliding
if (Vroom.collideEntity(entity, target)) {
switch (entity.collisionType) {
case VroomEntity.DISPLACE:
Vroom.resolveTestTest(entity, target);
break;
}
}
}
}
}
}
}
},
下面是实际碰撞检测的代码。这似乎也可以正常工作。
collideEntity: function(entity, target) {
if (entity.getBottom() < target.getTop() || entity.getTop() > target.getBottom() || entity.getRight() < target.getLeft() || entity.getLeft() > target.getRight()) {
return false;
}
return true;
},
这就是问题开始出现的地方。我希望实体只是 "pushed" 在目标实体之外，并将速度设置为 0。只要实体和目标都是完美的正方形，这就可以正常工作。如果假设实体（gif 中的玩家形象）是一个矩形，那么当最长边（X 轴）与目标（正方形）发生碰撞时，碰撞将 "slipp"。如果我调换播放器尺寸，使其变短变宽，那么 Y 轴就会出现同样的问题。
resolveTestTest: function(entity, target) {
var normalizedX = (target.getMidX() - entity.getMidX());
var normalizedY = (target.getMidY() - entity.getMidY());
var absoluteNormalizedX = Math.abs(normalizedX);
var absoluteNormalizedY = Math.abs(normalizedY);
console.log(absoluteNormalizedX, absoluteNormalizedY);
// The collision is comming from the left or right
if (absoluteNormalizedX > absoluteNormalizedY) {
if (normalizedX < 0) {
entity.pos.x = target.getRight();
} else {
entity.pos.x = target.getLeft() - entity.dim.width;
}
// Set velocity to 0
entity.vel.x = 0;
// The collision is comming from the top or bottom
} else {
if (normalizedY < 0) {
entity.pos.y = target.getBottom();
} else {
entity.pos.y = target.getTop() - entity.dim.height;
}
// Set velocity to 0
entity.vel.y = 0;
}
},
Y 轴上的碰撞适用于这些形状
X 轴上的碰撞以这些形状滑动
我该怎么做才能解决这个打滑问题？在过去的 5 天里，我一直在反对这个问题，所以如果有人能帮助我朝着正确的方向前进，我将不胜感激！
谢谢:)
-- 编辑：--
如果只向左侧或右侧的一个方向移动，也会发生打滑
-- 编辑 2 工作代码：--
有关工作代码的示例，请参阅下面的答案！
问题可能是您正在纠正 X 和 Y 基于相同位置的碰撞：
- 玩家在某个位置。让我们检查碰撞。
- 玩家的右下角与对象的左上角重叠。
X位置已更正：玩家向左移动。- 玩家的右下角与对象的左上角重叠。
Y位置已更正：球员上移。- 最终结果：玩家向上和向左移动。
您可能需要 "get" 再次检查玩家的位置。
您犯的重要逻辑错误是这一行：
if (absoluteNormalizedX > absoluteNormalizedY) {
This only works if both entities are square.
为您的 X 滑动示例考虑一个接近极值的情况：如果它们几乎在拐角处接触：
虽然图表有点夸张，但您可以看到 absoluteNormalizedX < absoluteNormalizedY 在这种情况下 - 您的实施将继续解决垂直碰撞而不是预期的水平碰撞。
另一个错误是无论碰撞发生在哪一侧，您总是将相应的速度分量设置为零：如果它与碰撞法线方向相反，您必须仅将分量归零，否则您不会能够离开表面。
解决这个问题的一个好方法是在进行碰撞检测时也记录碰撞面：
collideEntity: function(entity, target) {
// adjust this parameter to your liking
var eps = 1e-3;
// no collision
var coll_X = entity.getRight() > target.getLeft() && entity.getLeft() < target.getRight();
var coll_Y = entity.getBottom() > target.getTop() && entity.getTop() < target.getBottom();
if (!(coll_X && coll_Y)) return 0;
// calculate bias flag in each direction
var bias_X = entity.targetX() < target.getMidX();
var bias_Y = entity.targetY() < target.getMidY();
// calculate penetration depths in each direction
var pen_X = bias_X ? (entity.getRight() - target.getLeft())
: (target.getRight() - entity.getLeft());
var pen_Y = bias_Y ? (entity.getBottom() - target.getUp())
: (target.getBottom() - entity.getUp());
var diff = pen_X - pen_Y;
// X penetration greater
if (diff > eps)
return (1 << (bias_Y ? 0 : 1));
// Y pentration greater
else if (diff < -eps)
return (1 << (bias_X ? 2 : 3));
// both penetrations are approximately equal -> treat as corner collision
else
return (1 << (bias_Y ? 0 : 1)) | (1 << (bias_X ? 2 : 3));
},
updatePhysics: function(step) {
// ...
// pass collision flag to resolver function
var result = Vroom.collideEntity(entity, target);
if (result > 0) {
switch (entity.collisionType) {
case VroomEntity.DISPLACE:
Vroom.resolveTestTest(entity, target, result);
break;
}
}
// ...
}
为了提高效率，使用位标志而不是布尔数组。然后可以将解析器函数重写为：
resolveTestTest: function(entity, target, flags) {
if (!!(flags & (1 << 0))) { // collision with upper surface
entity.pos.y = target.getTop() - entity.dim.height;
if (entity.vel.y > 0) // travelling downwards
entity.vel.y = 0;
}
else
if (!!(flags & (1 << 1))) { // collision with lower surface
entity.pos.y = target.getBottom();
if (entity.vel.y < 0) // travelling upwards
entity.vel.y = 0;
}
if (!!(flags & (1 << 2))) { // collision with left surface
entity.pos.x = target.getLeft() - entity.dim.width;
if (entity.vel.x > 0) // travelling rightwards
entity.vel.x = 0;
}
else
if (!!(flags & (1 << 3))) { // collision with right surface
entity.pos.x = target.getRight();
if (entity.vel.x < 0) // travelling leftwards
entity.vel.x = 0;
}
},
请注意，与您的原始代码不同，上面的代码还允许 角 发生碰撞 - 即沿两个轴解析速度和位置。
我的工作代码
因此，在了不起的@meowgoesthedog 的一些帮助和指导下，我终于走上了正确的轨道，找到了我要找的东西。问题（正如@meowgoesthedog 指出的那样）是我的代码实际上只适用于正方形。解决方法是检查碰撞体的交点，并根据最短交点求解。 注意：如果您需要对小而快速移动的物体进行精确的物理处理，这可能不是合适的解决方案。查找相交深度的代码基于此：https://github.com/kg/PlatformerStarterKit/blob/0e2fafb8dbc845279fe4116c37b6f2cdd3e636d6/RectangleExtensions.cs which is related to this project: https://msdn.microsoft.com/en-us/library/dd254916(v=xnagamestudio.31).aspx。
这是我的工作代码：
我的物理循环没有太大变化，除了一些函数的一些更好的名字。
updatePhysics: function(step) {
// Loop through entities and update positions based on velocities
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled) {
switch (entity.entityType) {
case VroomEntity.KINEMATIC:
entity.pos.x += entity.vel.x * step;
entity.pos.y += entity.vel.y * step;
break;
case VroomEntity.DYNAMIC:
// Dynamic stuff
break;
}
}
}
// Loop through entities and detect collisions. Resolve collisions as they are detected.
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled && entity.entityType !== VroomEntity.STATIC) {
for (var targetID in Vroom.entityList) {
if (targetID !== entityID) {
var target = Vroom.entityList[targetID];
if (target.physicsEnabled) {
// Check if current entity and target is colliding
if (Vroom.collideEntity(entity, target)) {
switch (entity.collisionType) {
case VroomEntity.DISPLACE:
Vroom.resolveDisplace(entity, target);
break;
}
}
}
}
}
}
}
},
碰撞检测也保持不变。
collideEntity: function(entity, target) {
if (entity.getBottom() < target.getTop() || entity.getTop() > target.getBottom() || entity.getRight() < target.getLeft() || entity.getLeft() > target.getRight()) {
return false;
}
return true;
},
这是基本解决问题的代码。代码中的注释应该很好地解释了它的功能。
getIntersectionDepth: function(entity, target) {
// Calculate current and minimum-non-intersecting distances between centers.
var distanceX = entity.getMidX() - target.getMidX();
var distanceY = entity.getMidY() - target.getMidY();
var minDistanceX = entity.halfDim.width + target.halfDim.width;
var minDistanceY = entity.halfDim.height + target.halfDim.height;
// If we are not intersecting at all, return 0.
if (Math.abs(distanceX) >= minDistanceX || Math.abs(distanceY) >= minDistanceY) {
return {
x: 0,
y: 0,
};
}
// Calculate and return intersection depths.
var depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX;
var depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY;
return {
x: depthX,
y: depthY,
};
},
这是更新后的解析函数。现在在确定碰撞轴时考虑相交深度，然后在确定解析方向时使用相交深度的符号作为碰撞轴。
resolveDisplace: function(entity, target) {
var intersection = Vroom.getIntersectionDepth(entity, target);
if (intersection.x !== 0 && intersection.y !== 0) {
if (Math.abs(intersection.x) < Math.abs(intersection.y)) {
// Collision on the X axis
if (Math.sign(intersection.x) < 0) {
// Collision on entity right
entity.pos.x = target.getLeft() - entity.dim.width;
} else {
// Collision on entity left
entity.pos.x = target.getRight();
}
entity.vel.x = 0;
} else if (Math.abs(intersection.x) > Math.abs(intersection.y)) {
// Collision on the Y axis
if (Math.sign(intersection.y) < 0) {
// Collision on entity bottom
entity.pos.y = target.getTop() - entity.dim.height;
} else {
// Collision on entity top
entity.pos.y = target.getBottom();
}
entity.vel.y = 0;
}
}
},
谢谢大家的帮助！
所以，我目前正在通过尝试为我的游戏引擎制作一个简单的物理引擎来重新发明轮子（并学到很多东西）。我一直在网上搜索，试图（但未能）解决我当前的问题。关于这个主题有很多资源，但我发现的 none 似乎适用于我的情况。
问题简而言之：当两个矩形发生碰撞时，碰撞解决方案在某些角上无法按预期工作。它失败的方式因矩形的尺寸而异。我正在寻找的是一种 "shortest overlap" 的碰撞解决方案或其他相当简单的解决方案（我愿意接受建议！）。（向下滚动以获得更好的解释和插图）。
警告：以下代码可能效率不高...
首先，这是我的物理循环。它只是循环遍历所有游戏实体并检查它们是否与任何其他游戏实体发生碰撞。它效率不高（n^2 和所有这些），但它现在有效。
updatePhysics: function(step) {
// Loop through entities and update positions based on velocities
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled) {
switch (entity.entityType) {
case VroomEntity.KINEMATIC:
entity.pos.x += entity.vel.x * step;
entity.pos.y += entity.vel.y * step;
break;
case VroomEntity.DYNAMIC:
// Dynamic stuff
break;
}
}
}
// Loop through entities and detect collisions. Resolve collisions as they are detected.
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled && entity.entityType !== VroomEntity.STATIC) {
for (var targetID in Vroom.entityList) {
if (targetID !== entityID) {
var target = Vroom.entityList[targetID];
if (target.physicsEnabled) {
// Check if current entity and target is colliding
if (Vroom.collideEntity(entity, target)) {
switch (entity.collisionType) {
case VroomEntity.DISPLACE:
Vroom.resolveTestTest(entity, target);
break;
}
}
}
}
}
}
}
},
下面是实际碰撞检测的代码。这似乎也可以正常工作。
collideEntity: function(entity, target) {
if (entity.getBottom() < target.getTop() || entity.getTop() > target.getBottom() || entity.getRight() < target.getLeft() || entity.getLeft() > target.getRight()) {
return false;
}
return true;
},
这就是问题开始出现的地方。我希望实体只是 "pushed" 在目标实体之外，并将速度设置为 0。只要实体和目标都是完美的正方形，这就可以正常工作。如果假设实体（gif 中的玩家形象）是一个矩形，那么当最长边（X 轴）与目标（正方形）发生碰撞时，碰撞将 "slipp"。如果我调换播放器尺寸，使其变短变宽，那么 Y 轴就会出现同样的问题。
resolveTestTest: function(entity, target) {
var normalizedX = (target.getMidX() - entity.getMidX());
var normalizedY = (target.getMidY() - entity.getMidY());
var absoluteNormalizedX = Math.abs(normalizedX);
var absoluteNormalizedY = Math.abs(normalizedY);
console.log(absoluteNormalizedX, absoluteNormalizedY);
// The collision is comming from the left or right
if (absoluteNormalizedX > absoluteNormalizedY) {
if (normalizedX < 0) {
entity.pos.x = target.getRight();
} else {
entity.pos.x = target.getLeft() - entity.dim.width;
}
// Set velocity to 0
entity.vel.x = 0;
// The collision is comming from the top or bottom
} else {
if (normalizedY < 0) {
entity.pos.y = target.getBottom();
} else {
entity.pos.y = target.getTop() - entity.dim.height;
}
// Set velocity to 0
entity.vel.y = 0;
}
},
Y 轴上的碰撞适用于这些形状
X 轴上的碰撞以这些形状滑动
我该怎么做才能解决这个打滑问题？在过去的 5 天里，我一直在反对这个问题，所以如果有人能帮助我朝着正确的方向前进，我将不胜感激！
谢谢:)
-- 编辑：--
如果只向左侧或右侧的一个方向移动，也会发生打滑
-- 编辑 2 工作代码：-- 有关工作代码的示例，请参阅下面的答案！
问题可能是您正在纠正 X 和 Y 基于相同位置的碰撞：
- 玩家在某个位置。让我们检查碰撞。
- 玩家的右下角与对象的左上角重叠。
X位置已更正：玩家向左移动。- 玩家的右下角与对象的左上角重叠。
Y位置已更正：球员上移。- 最终结果：玩家向上和向左移动。
您可能需要 "get" 再次检查玩家的位置。
您犯的重要逻辑错误是这一行：
if (absoluteNormalizedX > absoluteNormalizedY) {
This only works if both entities are square.
为您的 X 滑动示例考虑一个接近极值的情况：如果它们几乎在拐角处接触：
虽然图表有点夸张，但您可以看到 absoluteNormalizedX < absoluteNormalizedY 在这种情况下 - 您的实施将继续解决垂直碰撞而不是预期的水平碰撞。
另一个错误是无论碰撞发生在哪一侧，您总是将相应的速度分量设置为零：如果它与碰撞法线方向相反，您必须仅将分量归零，否则您不会能够离开表面。
解决这个问题的一个好方法是在进行碰撞检测时也记录碰撞面：
collideEntity: function(entity, target) {
// adjust this parameter to your liking
var eps = 1e-3;
// no collision
var coll_X = entity.getRight() > target.getLeft() && entity.getLeft() < target.getRight();
var coll_Y = entity.getBottom() > target.getTop() && entity.getTop() < target.getBottom();
if (!(coll_X && coll_Y)) return 0;
// calculate bias flag in each direction
var bias_X = entity.targetX() < target.getMidX();
var bias_Y = entity.targetY() < target.getMidY();
// calculate penetration depths in each direction
var pen_X = bias_X ? (entity.getRight() - target.getLeft())
: (target.getRight() - entity.getLeft());
var pen_Y = bias_Y ? (entity.getBottom() - target.getUp())
: (target.getBottom() - entity.getUp());
var diff = pen_X - pen_Y;
// X penetration greater
if (diff > eps)
return (1 << (bias_Y ? 0 : 1));
// Y pentration greater
else if (diff < -eps)
return (1 << (bias_X ? 2 : 3));
// both penetrations are approximately equal -> treat as corner collision
else
return (1 << (bias_Y ? 0 : 1)) | (1 << (bias_X ? 2 : 3));
},
updatePhysics: function(step) {
// ...
// pass collision flag to resolver function
var result = Vroom.collideEntity(entity, target);
if (result > 0) {
switch (entity.collisionType) {
case VroomEntity.DISPLACE:
Vroom.resolveTestTest(entity, target, result);
break;
}
}
// ...
}
为了提高效率，使用位标志而不是布尔数组。然后可以将解析器函数重写为：
resolveTestTest: function(entity, target, flags) {
if (!!(flags & (1 << 0))) { // collision with upper surface
entity.pos.y = target.getTop() - entity.dim.height;
if (entity.vel.y > 0) // travelling downwards
entity.vel.y = 0;
}
else
if (!!(flags & (1 << 1))) { // collision with lower surface
entity.pos.y = target.getBottom();
if (entity.vel.y < 0) // travelling upwards
entity.vel.y = 0;
}
if (!!(flags & (1 << 2))) { // collision with left surface
entity.pos.x = target.getLeft() - entity.dim.width;
if (entity.vel.x > 0) // travelling rightwards
entity.vel.x = 0;
}
else
if (!!(flags & (1 << 3))) { // collision with right surface
entity.pos.x = target.getRight();
if (entity.vel.x < 0) // travelling leftwards
entity.vel.x = 0;
}
},
请注意，与您的原始代码不同，上面的代码还允许 角 发生碰撞 - 即沿两个轴解析速度和位置。
我的工作代码
因此，在了不起的@meowgoesthedog 的一些帮助和指导下，我终于走上了正确的轨道，找到了我要找的东西。问题（正如@meowgoesthedog 指出的那样）是我的代码实际上只适用于正方形。解决方法是检查碰撞体的交点，并根据最短交点求解。 注意：如果您需要对小而快速移动的物体进行精确的物理处理，这可能不是合适的解决方案。查找相交深度的代码基于此：https://github.com/kg/PlatformerStarterKit/blob/0e2fafb8dbc845279fe4116c37b6f2cdd3e636d6/RectangleExtensions.cs which is related to this project: https://msdn.microsoft.com/en-us/library/dd254916(v=xnagamestudio.31).aspx。
这是我的工作代码：
我的物理循环没有太大变化，除了一些函数的一些更好的名字。
updatePhysics: function(step) {
// Loop through entities and update positions based on velocities
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled) {
switch (entity.entityType) {
case VroomEntity.KINEMATIC:
entity.pos.x += entity.vel.x * step;
entity.pos.y += entity.vel.y * step;
break;
case VroomEntity.DYNAMIC:
// Dynamic stuff
break;
}
}
}
// Loop through entities and detect collisions. Resolve collisions as they are detected.
for (var entityID in Vroom.entityList) {
var entity = Vroom.entityList[entityID];
if (entity.physicsEnabled && entity.entityType !== VroomEntity.STATIC) {
for (var targetID in Vroom.entityList) {
if (targetID !== entityID) {
var target = Vroom.entityList[targetID];
if (target.physicsEnabled) {
// Check if current entity and target is colliding
if (Vroom.collideEntity(entity, target)) {
switch (entity.collisionType) {
case VroomEntity.DISPLACE:
Vroom.resolveDisplace(entity, target);
break;
}
}
}
}
}
}
}
},
碰撞检测也保持不变。
collideEntity: function(entity, target) {
if (entity.getBottom() < target.getTop() || entity.getTop() > target.getBottom() || entity.getRight() < target.getLeft() || entity.getLeft() > target.getRight()) {
return false;
}
return true;
},
这是基本解决问题的代码。代码中的注释应该很好地解释了它的功能。
getIntersectionDepth: function(entity, target) {
// Calculate current and minimum-non-intersecting distances between centers.
var distanceX = entity.getMidX() - target.getMidX();
var distanceY = entity.getMidY() - target.getMidY();
var minDistanceX = entity.halfDim.width + target.halfDim.width;
var minDistanceY = entity.halfDim.height + target.halfDim.height;
// If we are not intersecting at all, return 0.
if (Math.abs(distanceX) >= minDistanceX || Math.abs(distanceY) >= minDistanceY) {
return {
x: 0,
y: 0,
};
}
// Calculate and return intersection depths.
var depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX;
var depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY;
return {
x: depthX,
y: depthY,
};
},
这是更新后的解析函数。现在在确定碰撞轴时考虑相交深度，然后在确定解析方向时使用相交深度的符号作为碰撞轴。
resolveDisplace: function(entity, target) {
var intersection = Vroom.getIntersectionDepth(entity, target);
if (intersection.x !== 0 && intersection.y !== 0) {
if (Math.abs(intersection.x) < Math.abs(intersection.y)) {
// Collision on the X axis
if (Math.sign(intersection.x) < 0) {
// Collision on entity right
entity.pos.x = target.getLeft() - entity.dim.width;
} else {
// Collision on entity left
entity.pos.x = target.getRight();
}
entity.vel.x = 0;
} else if (Math.abs(intersection.x) > Math.abs(intersection.y)) {
// Collision on the Y axis
if (Math.sign(intersection.y) < 0) {
// Collision on entity bottom
entity.pos.y = target.getTop() - entity.dim.height;
} else {
// Collision on entity top
entity.pos.y = target.getBottom();
}
entity.vel.y = 0;
}
}
},
谢谢大家的帮助！