游戏邦在:
杂志专栏:
gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

阐述基于Swept AABB的碰撞检测和反应开发方法

发布时间:2013-07-13 14:36:39 Tags:,,,,

作者:BrendanL.K

作为游戏开发的一部分,碰撞检测因其极大的复杂度而让开发者倍感头疼,不得不借助第三方物理API。程序员大多理解轴基准边界盒(AABB)算法,但不太理解如何过渡到更复杂的算法如SAT和GJK。Swept AABB作为中介,可以显示在法向AABB中发生的许多问题,有助于理解高级碰撞检测中的核心概念。

注:阅读本文的前提是你了解AABB算法。本文还涉及少量向量运算,但不会太复杂。文中用C/C++写成的案例可以轻易地转换成其他语言。

什么是“Swept”?

一开始,我们可能看不到AABB有一个基本的大问题。请看下面3个例子:

current pos(from gamedev.net)

current pos(from gamedev.net)

例1是一个法向AABB碰撞。深蓝框位于框架的开端。绿框位于框架的末端。淡蓝框是碰撞后方框将出现的位置。灰色带是用于测试碰撞的静止(不可移动的)障碍。这是一个正常的碰撞。方框被移到距离碰撞发生的最近点。这就产生了AABB的预期结果。

current pos 2(from gamedev.net)

current pos 2(from gamedev.net)

例2是一个类似的碰撞,但终点是距离更远且方向相反。如你所见,AABB已经把反应框放在障碍的另一边。从逻辑上说,这是不合理的,因为它居然神奇地通过了障碍对象。

current pos 3(from gamedev.net)

current pos 3(from gamedev.net)

例3中的终点没有与障碍发生碰撞。AABB将假定没有发生碰撞,然后将方框顺利得像完全没有发生碰撞似地移动障碍的另一边。

那么,什么时候会发生这些问题?

当对象快速移动和/或程序以低帧率运行时,通常会发生上述问题。为了避免这些问题,我们必须预测方框在框架之间的移动位置。这就是Swept的概念。

Swept AABB的执行

在执行时,我们假设方框具有位置(左上角)和高宽属性。在考虑Swept时,我们还要记住速度。

注:对象的速度是指这个对象每秒内移动的距离。如果我们将这个速度乘以时间增量,就可以得到这个对象在框架内必须移动的距离(位移)。

我们把方框定义如下:

// describes an axis-aligned rectangle with a velocity
struct Box
{
// position of top-left corner
float x, y;

// dimensions
float w, h;

// velocity
float vx, vy;
};

vx和vy指速度,w和h指方框的宽度和高度。

这个函数将执行如下测试:

float SweptAABB(Box b1, Box b2, float& normalx, float& normaly)

第一个参数是移动中的方框,第二个是将被再次测试的静止的方框。最后两个参数组成碰撞表面的法向。它将用于之后的碰撞反应。

注:法向是指对象边缘面对的方向。你可以用垂直于表面的箭头表示法向。

当碰撞发生时,返回值是介于0到1的数字。值为0表示移动开始,1表示移动结束。如果我们得到的值为1,则可以认为没有发生碰撞。0.5表示碰撞发生在框架中间。这也将用于之后的碰撞反应。

current pos 4(from gamedev.net)

current pos 4(from gamedev.net)

现在,开始算法前,我们必须找到各轴发生碰撞所需要的距离和时间。

float xInvEntry, yInvEntry;
float xInvExit, yInvExit;

// find the distance between the objects on the near and far sides for both x and y
if (b1.vx > 0.0f)
{
xInvEntry = b2.x – (b1.x + b1.w);
xInvExit = (b2.x + b2.w) – b1.x;
}
else
{
xInvEntry = (b2.x + b2.w) – b1.x;
xInvExit = b2.x – (b1.x + b1.w);
}

if (b1.vy > 0.0f)
{
yInvEntry = b2.y – (b1.y + b1.h);
yInvExit = (b2.y + b2.h) – b1.y;
}
else
{
yInvEntry = (b2.y + b2.h) – b1.y;
yInvExit = b2.y – (b1.y + b1.h);
}

xInvEntry和yInvEntry都表示对象彼此之间的最近边缘的距离有多远。xInvExit和yInvExit是指对象的远边的距离。你可以把它想象成射穿对象的子弹;子弹从xInvEntry和yInvEntry进入,从xInvExit和yInvExit出来。这些值是反时限的,直到它击中轴上的另一个对象。我们现在将使用这些值来计算速度。

// find time of collision and time of leaving for each axis (if statement is to prevent divide by zero)
float xEntry, yEntry;
float xExit, yExit;

if (b1.vx == 0.0f)
{
xEntry = -std::numeric_limits<float>::infinity();
xExit = std::numeric_limits<float>::infinity();
}
else
{
xEntry = xInvEntry / b1.vx;
xExit = xInvExit / b1.vx;
}

if (b1.vy == 0.0f)
{
yEntry = -std::numeric_limits<float>::infinity();
yExit = std::numeric_limits<float>::infinity();
}
else
{
yEntry = yInvEntry / b1.vy;
yExit = yInvExit / b1.vy;
}

这里,我们所做的是根据对象的速度区分xEntry、yEntry、xExit和yExit。当然,如果任意轴上的速度都是0,那么它将错误。当各轴上各自发生碰撞时,这些新变量产生介于0到1的值。

下一步是找到哪个轴先发生碰撞。

// find the earliest/latest times of collision
float entryTime = std::max(xEntry, yEntry);
float exitTime = std::min(xExit, yExit);

entryTime将告诉我们碰撞首次发生的时间,而exitTime则显示对象从另一边离开的时间。这些值还有其他用途,但现在我们只需要用它计算碰撞是否发生。

// if there was no collision
if (entryTime > exitTime || xEntry < 0.0f && yEntry < 0.0f || xEntry > 1.0f || yEntry > 1.0f)
{
normalx = 0.0f;
normaly = 0.0f;
return 1.0f;
}

if语句查看是否存在碰撞。如果碰撞时间不介于0到1之间,那么显然框架内没有发生碰撞。另外,碰撞第一次发生的时间永远不会晚于离开另一边的时间。当语句检查失败,那么我们就知道没有发生碰撞。我们指定1表示没有碰撞。

如果存在碰撞,那么我们的最后一步就是计算被碰撞边缘的法向。

else // if there was a collision
{
// calculate normal of collided surface
if (xEntry > yEntry)
{
if (xInvEntry < 0.0f)
{
normalx = 1.0f;
normaly = 0.0f;
}
else
{
normalx = -1.0f;
normaly = 0.0f;
}
}
else
{
if (yInvEntry < 0.0f)
{
normalx = 0.0f;
normaly = 1.0f;
}
else
{
normalx = 0.0f;
normaly = -1.0f;
}
}

// return the time of collision
return entryTime;

因为我们的方框的都是轴对齐的,我们可以假设只有4个可能的法向(游戏邦注:方框的四条边各有一个法向)。这个简单的测试将计算并返回碰撞进入时间。

这就是Swept AABB所使用的全部代码,但它在某些情况会发生错误!那是因为我们必须执行broadphase算法(下面会说到)。但现在,我们还要看看碰撞的另一方面,那就是反应。

反应

碰撞反应指对象碰撞后发生的行为。在了解不同类型的碰撞反应以前,我们必须先知道碰撞发生的新位置点。有了Swept AABB函数,这并不难办。

float normalx, normaly;
float collisiontime = SweptAABB(box, block, out normalx, out normaly);
box.x += box.vx * collisiontime;
box.y += box.vy * collisiontime;

float remainingtime = 1.0f – collisiontime;

current pos 5(from gamedev.net)

current pos 5(from gamedev.net)

1.0f – collisiontime显示的是在这框架中的剩余时间(还是0到1)。这会正确地执行碰撞,且可能有些用处。但如果你试图对角地移动方框到对象(“贴墙”),那么你会发现你不能移动了。移动中的方框将停下来。这时候,不同的反应就派上用场了。

Deflect

游戏中最经常出现的碰撞反应就是对象像乒乓球一样弹开。

current pos 6(from gamedev.net)

current pos 6(from gamedev.net)

你会注意到当对象发生碰撞时,移动中的对象仍然有速度。对象将以剩余速度朝相反方向移动,从而造成一种反弹(deflect)的效果。

// deflect
box.vx *= remainingtime;
box.vy *= remainingtime;
if (abs(normalx) > 0.0001f)
box.vx = -box.vx;
if (abs(normaly) > 0.0001f)
box.vy = -box.vy;

首先我们按剩余时间减少速度。最终取消发生碰撞的所有轴上的速度。相当简单。

Push

Push更接近传统的“贴墙”概念,也就是,当对象的一边碰到墙体,它将沿着墙继续滑动。

current pos 7(from gamedev.net)

current pos 7(from gamedev.net)

// push
float magnitude = sqrt((box.vx * box.vx + box.vy * box.vy)) * remainingtime;
float dotprod = box.vx * normaly + box.vy * normalx;
if (dotprod > 0.0f)
dotprod = 1.0f;
else if (dotprod < 0.0f)
dotprod = -1.0f;
NewBox.vx = dotprod * normaly * magnitude;
NewBox.vy = dotprod * normalx * magnitude;

它再次使用剩余速度,在与碰撞边缘相同的方向上移动。第一步是计算速度的大小(magnitude)(游戏邦注:这是程序员版本的毕达哥拉斯定律)。下一步是用速度和碰撞面的法向来计算点积(dotprod)。我们必须标准化这个点积(因为我们还要设置我们自己的距离),最后一步是标准化后的点积、转换后的法向(normal)和速度的大小三者相乘得到新的方框速度。

或者,你可以在计算完值后再标准化速度,这样你就不必标准化点积了。

Slide

Push技术的问题在于,对象的移动速度可能比设想中的更快。更实际一些的做法是Slide。

current pos 8(from gamedev.net)

current pos 8(from gamedev.net)

滑动使用向量投影来寻找边缘的等效位置。它比Push更简单。

// slide
float dotprod = (box.vx * normaly + box.vy * normalx) * remainingtime;
NewBox.vx = dotprod * normaly;
NewBox.vy = dotprod * normalx;

你要记住的第一件事是,我们正在交换法向(交换x和y值)。我们计算点积时,是把它乘以magnitude,最后乘以交换后的法向值。现在我们就得了投射速度。

Broad-Phasing

Swept AABB算法运行得非常快,但随着越来越多对象添加进来,运行速度也随之迅速下降。解决方法就是broad-phase。你可以用它来快速决定是否发生碰撞,虽然准确度没那么高。执行的技术有若干种(如循环距离),但因为我们的对象是轴对齐方框,所以再次使用方框是合理的。

defect(from gamedev.net)

defect(from gamedev.net)

外部的黑色框显示的是broad-phase区域。用这个方框,我们可以执行简单的AABB测试来确定是否有碰撞发生。看上图,可以说如果对象没有在这个broad-phase区域内,它就不会与对象发生碰撞。但如果它在broad-phase区域内,也未必表示存在碰撞。如果在broad-phase区域内有碰撞,那么我们就知道应该执行Swept AABB来得到更精确的答案。

Box GetSweptBroadphaseBox(Box b)
{
Box broadphasebox;
broadphasebox.x = b.vx > 0 ? b.x : b.x + b.vx;
broadphasebox.y = b.vy > 0 ? b.y : b.y + b.vy;
broadphasebox.w = b.vx > 0 ? b.vx + b.w : b.w – b.vx;
broadphasebox.h = b.vy > 0 ? b.vy + b.h : b.h – b.vy;

return broadphasebox;
}

第一步是计算broad-phase区域。也就是给边缘添加速度(取决于速度的方向)。现在我们要做的就是执行一般的AABB测试。

bool AABBCheck(Box b1, Box b2)
{
return !(b1.x + b1.w < b2.x || b1.x > b2.x + b2.w || b1.y + b1.h < b2.y || b1.y > b2.y + b2.h);
}

这是一个大大简化的函数,当碰撞发生时,返回的结果为真。

现在我们可以把所有片段放在一起了:

// box is the moving box
// block is the static box

Box broadphasebox = GetSweptBroadphaseBox(box);
if (AABBCheck(broadphasebox, block))
{
float normalx, normaly;
float collisiontime = SweptAABB(box, block, out normalx, out normaly);
box.x += box.vx * collisiontime;
box.y += box.vy * collisiontime;

if (collisiontime < 1.0f)
{
// perform response here
}
}

局限性

以上执行法有几点局限性,你可以已经知道了。那就是:

1、没有考虑重新调整大小(即,如果方框在框架中改变大小)。

2、只允许线性移动。如果移动中的方框作环形移动,它就不能确定在哪里超出曲线。

3、只允许一个方框移动(即,如果两个方框朝彼此方向移动然后发生碰撞)。这是我有意回避的问题,因为涉及许多物理学概念如质量和力。

4、它仍然只支持正方形!甚至不允许旋转!显然,算法的名称已经告诉你了。但如果你已经征服了Swept AABB,那么你应该可以进入下一阶段(学习SAT或GJK)了。

5、只适用于2D。幸运的是,很容易把代码转换成3D。只要你理解这个概念,你就不会遇到太多麻烦。我之所以只做2D的,是为了尽量保持简单。

代码

本文中出现的所有C/C++代码都可以下载。我还用C#执行了代码。但案例代码只是作为示范,只表现相关的函数。

defect(from gamedev.net)

defect(from gamedev.net)

本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转载,如需转载请联系:游戏邦

Swept AABB Collision Detection and Response

By BrendanL.K

Collision detection is an area of game development that scares most into using third party physics APIs due to its seemingly vertically-steep learning curve. Most programmers understand the axis-aligned bounding box (AABB) algorithm but have trouble transitioning to the more difficult algorithms such as SAT and GJK. Swept AABB is the middle player that will show a lot of the problems that can occur with normal AABB and help understand core concepts used in more advanced collision techniques.

Note:  This article assumes you understand the AABB algorithm. There is also a bit of vector math, but it won’t get overly complicated. Examples are done in C/C++ but can be easily converted to other languages. At the end, I have given source files for C/C++ and C#.

What is Swept?

AABB has a major fundamental problem that may not be visible at first. Take these 3 examples:

Example 1: A normal AABB collision. The blue box is where the box is at the beginning of the frame. The green box is where the box is expected to be by the end of the frame. The aqua box shows where AABB will place the box after collision. The gray box is a static (unmovable) block that is tested for collision. This shows a normal collision. The box is moved to the nearest point that is not a collision. This is fine and is the expected result of AABB.

Example 2 shows a similar collision where the destination is further on the opposite side. As you can see, AABB has placed the response box on the opposite side of the block. Logically, this makes no sense as it has magically passed through the object.

Example 3 shows a destination that doesn’t collide with the object. AABB will assume that there was no collision and the moving box will move through it like there was no collision at all.

So when do these problems occur?

These problems usually appear when objects are moving fast and/or the program is running at a low frame rate. To avoid this, we need to somehow predict where the box travelled between each frame. This concept is called swept.

Implementing Swept AABB

In this implementation, we will assume that a box is defined by a position at the top-left corner of the box and a width and height. Now that we are taking swept into consideration, we also need to remember the velocity.

Note:  The velocity of an object is how far the object will move per second. If we multiply the velocity by the delta time, you will have the displacement that the object must move in this frame.

So we will define our box like so:

// describes an axis-aligned rectangle with a velocity
struct Box
{
// position of top-left corner
float x, y;

// dimensions
float w, h;

// velocity
float vx, vy;
};

vx and vy refer to the velocities, w and h are the box dimensions.

The function that will perform the test will look like this:

float SweptAABB(Box b1, Box b2, float& normalx, float& normaly)

The first parameter is the box that is moving. The second is the static box that will be tested against. The last two parameters make up the normal of the collided surface. This will be used later on when we want to respond to the collision.

Note:  A normal is the direction that an edge of an object is facing. Think of a perpendicular arrow pointing away from face at 90 degrees.

The return value is a number between 0 and 1 that indicates when the collision occurred. A value of 0 indicates the start of the movement and 1 indicates the end. If we get a value of 1, we can assume that there was no collision. A value of 0.5 means that the collision occurred halfway through the frame. This will also be used later to respond to the collision.

Now, to first start the algorithm, we need to find the distance and time that it takes to reach a collision on each axis.

float xInvEntry, yInvEntry;
float xInvExit, yInvExit;

// find the distance between the objects on the near and far sides for both x and y
if (b1.vx > 0.0f)
{
xInvEntry = b2.x – (b1.x + b1.w);
xInvExit = (b2.x + b2.w) – b1.x;
}
else
{
xInvEntry = (b2.x + b2.w) – b1.x;
xInvExit = b2.x – (b1.x + b1.w);
}

if (b1.vy > 0.0f)
{
yInvEntry = b2.y – (b1.y + b1.h);
yInvExit = (b2.y + b2.h) – b1.y;
}
else
{
yInvEntry = (b2.y + b2.h) – b1.y;
yInvExit = b2.y – (b1.y + b1.h);
}

xInvEntry and yInvEntry both specify how far away the closest edges of the objects are from each other. xInvExit and yInvExit is the distance to the far side of the object. You can think of this is a being like shooting through an object; the entry point is where the bullet goes through, and the exit point is where it exits from the other side. These values are the inverse time until it hits the other object on the axis. We will now use these values to take the velocity into account.

// find time of collision and time of leaving for each axis (if statement is to prevent divide by zero)
float xEntry, yEntry;
float xExit, yExit;

if (b1.vx == 0.0f)
{
xEntry = -std::numeric_limits<float>::infinity();
xExit = std::numeric_limits<float>::infinity();
}
else
{
xEntry = xInvEntry / b1.vx;
xExit = xInvExit / b1.vx;
}

if (b1.vy == 0.0f)
{
yEntry = -std::numeric_limits<float>::infinity();
yExit = std::numeric_limits<float>::infinity();
}
else
{
yEntry = yInvEntry / b1.vy;
yExit = yInvExit / b1.vy;
}

What we are doing here is dividing the xEntry, yEntry, xExit and yExit by the object’s velocity. Of course, if the velocity is zero on any axis, it will cause a divide-by-zero error. These new variables will give us our value between 0 and 1 of when each collision occurred on each axis. The next step is to find which axis collided first.

// find the earliest/latest times of collision
float entryTime = std::max(xEntry, yEntry);
float exitTime = std::min(xExit, yExit);

Time will tell use when the collision first occurred and exitTime will tell us when it exited the object from the other side. This can be useful for certain effects, but at the moment, we just need it to calculate if a collision occurred at all.

// if there was no collision
if (entryTime > exitTime || xEntry < 0.0f && yEntry < 0.0f || xEntry > 1.0f || yEntry > 1.0f)
{
normalx = 0.0f;
normaly = 0.0f;
return 1.0f;
}

The if statement checks to see if there was a collision or not. If the collision time was not within 0 and 1, then obviously there was no collision during this frame. Also, the time when the collision first entered should never be after when it exited out the other side. This is checked, and if it failed, then we assume that there was no collision. We specify 1 to indicate that there was no collision.

If there was a collision, our last step is to calculate the normal of the edge that was collided with.

else // if there was a collision
{
// calculate normal of collided surface
if (xEntry > yEntry)
{
if (xInvEntry < 0.0f)
{
normalx = 1.0f;
normaly = 0.0f;
}
else
{
normalx = -1.0f;
normaly = 0.0f;
}
}
else
{
if (yInvEntry < 0.0f)
{
normalx = 0.0f;
normaly = 1.0f;
}
else
{
normalx = 0.0f;
normaly = -1.0f;
}
}

// return the time of collision
return entryTime;
}

Since all of our boxes are axis-aligned, we can assume that there are only 4 possible normals (one for each edge of the box). This simple test will figure that out and then return the collision entry time.

This is all of the code we will use for swept AABB but it won’t work correctly in certain cases! That is because we need to implement broadphase (we will cover this soon). But, for now, there is a whole other step in a collision, and that is the response.

Responses

A collision response is how we want the object to behave after a collision. Before going into some of the different types of responses, we need to figure out the new point where the collision occurred. This should be easy now that we have our swept AABB function.

float normalx, normaly;
float collisiontime = SweptAABB(box, block, out normalx, out normaly);
box.x += box.vx * collisiontime;
box.y += box.vy * collisiontime;

float remainingtime = 1.0f – collisiontime;

Doing 1.0f – collisiontime will give us the remaining time left in this frame (0 to 1 value again). This will perform the collision correctly and might be enough for some uses. But if you try to move the box diagonally into the object (“hugging the wall”) then you’ll find that you can’t move. The moving box will not move at all. This is where the different responses can help.

Deflecting

This is most common in games like pong where there is a ball that bounces off objects.

You will notice that when the objects collide, the moving object still has some velocity left in it. What will happen is that the remaining velocity will be reused to move it in the opposite direction, creating a bounce-like effect.

// deflect
box.vx *= remainingtime;
box.vy *= remainingtime;
if (abs(normalx) > 0.0001f)
box.vx = -box.vx;
if (abs(normaly) > 0.0001f)
box.vy = -box.vy;

First we are reducing the velocity by our remaining time. Then we negate the velocity on whichever axis there was a collision. Pretty simple.

Push

Pushing is more of the traditional “wall hugging” concept where if you run towards a wall on an angle, you will slide along the wall.

// push
float magnitude = sqrt((box.vx * box.vx + box.vy * box.vy)) * remainingtime;
float dotprod = box.vx * normaly + box.vy * normalx;
if (dotprod > 0.0f)
dotprod = 1.0f;
else if (dotprod < 0.0f)
dotprod = -1.0f;
NewBox.vx = dotprod * normaly * magnitude;
NewBox.vy = dotprod * normalx * magnitude;

It reuses the remaining velocity and pushes it in the direction that is parallel to the collided edge. The first step is to calculate the magnitude of the velocity (this is a programmer version of the Pythagorean Theorem). The next step is performing the dot product with the velocity and the normal of the collided face. We must then normalize this scalar (because we are going to set our own distance). The final step is to multiply the normalized dot product, the switched normal and the magnitude.

Alternatively, you could normalize the velocity after calculating the magnitude, so then you don’t have to normalize dotprod.

Slide

The problem with the push technique is that it may push the object along faster than expected. A more realistic approach is to do sliding.

This uses vector projection to find the equivalent position on the edge. This is a simpler approach than the push method.

// slide
float dotprod = (box.vx * normaly + box.vy * normalx) * remainingtime;
NewBox.vx = dotprod * normaly;
NewBox.vy = dotprod * normalx;

The first thing to remember is that we are swapping the normals around (swap x value with y value). We calculate the dot product, multiply it by the magnitude, and finally multiply it by the swapped normal value. And now we should have our projected velocity.

Broad-Phasing

The swept AABB algorithm runs pretty fast, but as more objects come into play, the performance will drop rapidly. A way to combat this is called broad-phasing. This is where you can do a faster, less accurate test to quickly determine if there isn’t a collision. There are a few techniques to do this (such as circular distance) but, because our objects are all axis-aligned boxes, it makes sense to use a box again.

The black box around the outside shows us the broad-phase area. This is a box that we can perform a simple AABB test to check if there is a collision or not. Looking at the image, it is safe to say that if an object is not in this broad-phase area, it will not collide with the object. But just because it is within the broad-phase area, does not indicate that there is a collision. If there is a collision with the broad-phase area, we know that we should perform the swept AABB check to get a more precise answer.

Box GetSweptBroadphaseBox(Box b)
{
Box broadphasebox;
broadphasebox.x = b.vx > 0 ? b.x : b.x + b.vx;
broadphasebox.y = b.vy > 0 ? b.y : b.y + b.vy;
broadphasebox.w = b.vx > 0 ? b.vx + b.w : b.w – b.vx;
broadphasebox.h = b.vy > 0 ? b.vy + b.h : b.h – b.vy;

return broadphasebox;
}

This first step is to calculate the broad-phase area. As bad as this looks, all it is doing is adding the velocity to the edge (depending on the direction of the velocity). Now all we have to do is a generic AABB test.

bool AABBCheck(Box b1, Box b2)
{
return !(b1.x + b1.w < b2.x || b1.x > b2.x + b2.w || b1.y + b1.h < b2.y || b1.y > b2.y + b2.h);
}

This is a rather simplified function that returns true if a collision occurred.

Now we should be able to put all of the pieces together like this:

// box is the moving box
// block is the static box

Box broadphasebox = GetSweptBroadphaseBox(box);
if (AABBCheck(broadphasebox, block))
{
float normalx, normaly;
float collisiontime = SweptAABB(box, block, out normalx, out normaly);
box.x += box.vx * collisiontime;
box.y += box.vy * collisiontime;

if (collisiontime < 1.0f)
{
// perform response here
}
}

Limitations

The implementation described here has some limitations that you may have figured out already. These include:

Doesn’t take resizing into consideration (i.e. if a box resizes throughout the frame).

Only allows linear movement. If your moving box is moving in a circular fashion, it will not check where it was extended out on the curve.

Only allows one box to be moving (i.e. if two boxes move towards each other and collide). This is something I intentionally left out as it starts to involve many of the physics concepts like mass and force.

It is still only square shapes! You can’t even rotate them! This is obvious because the name of the algorithm sort of says that already. But if you have conquered swept AABB, then you might be ready to move onto the next level (like SAT or GJK).

It is made for 2D only. Luckily, it is quite easy to convert this code to 3D. So long as you understand the concept well, you shouldn’t have much trouble with it. I kept it as 2D to keep things as simple as possible.

Code

All of the C/C++ code specified in this article is available for download here. I have also implemented it in C#. This example code will not run a demonstration; it shows only the functions involved.

And, just for the hell of it, here’s a picture of everything in action:(source:gamedev)


上一篇:

下一篇: