65.9K
CodeProject 正在变化。 阅读更多。
Home

我的第一个碰撞算法

Vasily Tserekh
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.98/5 (38投票s)

2013年8月24日

CPOL

7分钟阅读

viewsIcon

50003

downloadIcon

1783

碰撞算法并非火箭科学，本文将证明这一点。

引言

当我开始 3D 编程时，我很快意识到，我在玩过的所有游戏中理所当然的许多事情，实际上并非如此。例如，在 3D 世界中，只有纹理和三角形需要绘制。碰撞和许多类似的东西必须自己创建。这意味着，如果你希望摄像机不穿过墙壁，你必须创建墙壁的内部几何表示并自己管理逻辑。我想指出，处理碰撞有许多方法。我只展示我的方法，我认为一切都应该从简单到复杂。我见过很多人试图进入 3D 编程世界，但大多数人都退缩了，因为许多教程要求具备很多领域的先备知识，这通常会让人不知所措。关于本文使用的数学，我在 12 岁左右时在学校学的，所以我想你不需要扎实的背景知识就能理解这一点，它也不会是火箭科学。我再说一遍，这个算法只是我的方法，我认为网络上还有很多更好的方法，但这个方法相当简单，而且能让你走上正轨。

背景

首先，我假设我处理的是 2D 碰撞。我身处 3D 环境，但地板是一个平面。这就像从上方看迷宫，墙壁可以看作线段，摄像机可以看作一个点。如果我将这些线段绘制到坐标轴上，我就可以利用解析几何来进行一些碰撞计算。所以，例如，如果我不想让我的摄像机靠近墙壁（在这种情况下，墙壁是一条线段）超过 1 个单位；那么每次我移动我的摄像机时，我都会检查到所有线段的距离，如果一个距离小于 1 个单位，那么就发生了碰撞，摄像机就不会朝那个方向移动。当然，在移动摄像机之前，必须检查新位置。

这张图给你展示了我方法的概览

这有一个缺点。你必须自己创建线段。这意味着，如果你有一个房间，你就必须创建 4 条线段。这又带来了一个复杂性，因为你无法知道点的坐标。由于这个演示仅用于教育目的，我在场景中创建了一段代码，在屏幕的左上角显示了摄像机的当前位置。你走到一个角落，记下坐标，然后走到墙壁的另一个角落，记下另一个坐标。这样，你就有了创建线段所需的 2 个点。我知道要为一个简单的场景创建所有碰撞需要做很多工作，但这有助于理解。稍后，如果你想简化，你可以为 3D 对象创建虚拟点，然后在代码中解释它们。

确定碰撞的步骤

本次演示的主要目标是找出点（摄像机）与线段（墙壁）之间的距离。以下是具体步骤。

Y = MX + N，其中 M 是方程的斜率，N 是它与 Y 轴的交点。第一步是找出该方程。M 可以使用线段的 2 个点找到，其方程为 M = (Y1 – Y2)/(X1 - X2)；为了避免除以零，如果 (X1 - X2) 导致零，我会添加一个非常小的数字。

  1. 线段由 2 个点定义，并包含在形如

M1X + N1 = M2X + N2
X = (N2 – N1)/ (M1 – M2)

通过将 X 代入两个方程之一来找到 Y。

  1. 稍后，你尝试找出垂直于该方程的直线方程。为此，你知道该方程的斜率是 M2 = - 1/M1。


     
  2. 然后你使两个函数相等，以找到交点。
  3. 找到交点时，有三种选择

    1. 交点包含在线段上。

    2. 交点不包含在线段上，并且靠近线段的一个端点。
    3. 交点不包含在线段上，并且靠近线段的另一个端点。

这正是我计算交点与两个端点之间距离的主要原因，然后实际距离是三者中最小的。距离是通过欧几里得方法计算的，如果你不知道，可以试试这个链接。它很简单。

请注意，在这个例子中，交点不包含在线段上。

Using the Code

在这个演示中，我使用了一个我开发的简化引擎来处理纹理加载、绘制和其他方面的工作。这里简要介绍一下它包含的类。

House.cs

此类包含绘制演示中看到的房子的方法。这是我创建所有碰撞的代码。

public void CreateCollisions()
{
 Collision.AddCollisionSegment(new Vector2F(-24.4f, -14.1f), new Vector2F(18.9f, -14.1f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-24.4f, -14.1f), new Vector2F(-24.4f, 13.2f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-20.2f, -0.1f), new Vector2F(-4.8f, -0.1f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-0.5f, 0.7f), new Vector2F(-0.5f, -8.7f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(19.4f, 14.4f), new Vector2F(-24.4f, 14.4f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(19.4f, 14.4f), new Vector2F(19.4f, -14.4f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-17.5f, 0.5f), new Vector2F(-17.5f, 11), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(13.4f, -0.15f), new Vector2F(18.74f, -0.15f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-0.43f, -9.1f), new Vector2F(12.4f, -9.1f), 0.5f);
 //Collision.GhostMode = true;   
}

请注意，第三个参数是碰撞有效的距离。我的意思是，如果摄像机到该线段的距离小于该参数，将触发碰撞事件。

Camera.cs

此类处理摄像机移动。如果你查看代码，你会看到碰撞是如何管理的。

if (pressedButton == 1) // forward button is pressed
{
    if (!Collision.CheckCollision(new Vector3(eyex - (float)i * 
            forwardSpeed, eyez - (float)k * forwardSpeed, 0)))
    {
       eyex -= (float)i * forwardSpeed;
       eyez -= (float)k * forwardSpeed;
    }   
}

请注意，只有在没有摄像机碰撞的情况下，才会更新当前的 X 和 Z 位置。另请注意，地板位于 XZ 平面上。

Collision.cs

这是处理碰撞的类；请注意检查碰撞的代码。

public static bool CheckCollision(Vector3 camaraPos)
{
    if (!ghostMode) //if collisions are not disabled
    {
       foreach (var item in colitionSegments)
       {
           if (item.segment.DistToSegment(camaraPos) < item.ColitionDistance)
           {
              return true; 
            }
       }               
     }
     return false; 
}

Segment 结构

此 `struct` 包含本文底部所述的所有计算。首先，它在构造函数中查找线段的线性方程，并具有计算点与线段之间距离的方法。

public float DistToSegment(Vector3 other)
{
    //calculate the two linear functions
    float n2 = other.Y - m2 * other.X;   //y = m2x + n   m2 = -1/m1

    //calculate the intersection point(i.p.)
    Vector3 intersectionPoint = new Vector3();
    intersectionPoint.X = (n2 - n1) / (m1 - m2);
    intersectionPoint.Y = m1 * intersectionPoint.X + n1;
    float d = Vector3.DistPointToPoint(intersectionPoint, other);

    float dist1 = Point3D.DistPointToPoint(other, first);
    float dist2 = Point3D.DistPointToPoint(other, second);


    //if the i.p. is contained in the rect segment, return d else 
    //the minimun value between dist1 and dist2
    if ((intersectionPoint.X < first.X && intersectionPoint.X > second.X) ||
        (intersectionPoint.X > first.X && intersectionPoint.X < second.X))
        return d;
    else
        return Math.Min(dist1, dist2);   
}

Controller.cs

这是控制器类；与本教程最相关部分是 `Draw` 方法。

public void DrawScene()
{    
   house.Draw();
   sky.Draw();  
   //DebugMode.WriteCamaraPos(200, 200);
   //Collision.DrawColissions();
}

`WriteCamaraPos` 函数将摄像机的当前坐标输出到屏幕；这就是我找出墙壁两个端点的坐标以将其定义为线段的方式。另一个被注释掉的函数在场景中绘制所有表示碰撞的线条。我就是这样看到一切是否正常工作的。有时，如果你想看到它们，你必须注释掉绘制房子到屏幕上的代码才能看到它们。

关注点

你会发现，演示中房子的所有碰撞都没有实现，只实现了一部分。如果你想学习我是如何做到的，不妨试试并尝试完成场景中的碰撞。这种方法将为你想学习 3D 编程的这一方面打下基础。我认为本文证明了在游戏中实现自己的碰撞不一定总是困难的。此外，它还证明了，如果你真的想学习 3D 编程，你必须自己做很多事情，而不是依赖复杂的引擎。这样，你就是自己的上帝，你的想象力将带你去任何地方。

历史

  • 2013 年 8 月 25 日：初次发布
  • 2013 年 8 月 30 日：修正了博客链接、图片顺序并更改了封面图片（现在有 Code Project 标志）
  • 2014 年 7 月 18 日：将源代码上传到 Code Project，而不是外部服务器
© . All rights reserved.