XNA如何写好碰撞算法？

Question

我目前正在使用 XNA 开发一款新游戏，我只是在设置一些基本的东西，比如 sprites/animations、输入、游戏对象等

与此同时，我正在尝试想出一种检测所有游戏对象碰撞的好方法，但我真的想不出一个快速的算法，它将游戏限制在很少的对象上。这是我在上一个学校作业项目中所做的

    public static void UpdateCollisions()
{
    //Empty the list
    AllCollisions.Clear();

    //Find all intersections between collision rectangles in the game
    for (int a = 0; a < AllGameObjectsWithCollision.Count; a++)
    {
        GameObject obja = AllGameObjectsWithCollision[a];
        for (int b = a; b < AllGameObjectsWithCollision.Count; b++)
        {
            GameObject objb = AllGameObjectsWithCollision[b];

            if (obja.Mask != null & objb.Mask!= null && obja != objb && !Exclude(new Collision(obja, objb)))
            {
                if (obja.Mask.CollisionRectangle.Intersects(objb.Mask.CollisionRectangle))
                    AllCollisions.Add(new Collision(obja, objb));
            }
        }
    }
}

所以它会检查所有对象之间的所有碰撞，但不包括添加我认为不必要的碰撞。

为了通知我的对象它们正在碰撞，我使用了一个虚拟方法 OnCollision，我这样调用

//Look for collisions for this entity and if a collision is found, call the OnCollision method in this entity
        var entityCol = FindCollision(entity);

        if (entityCol != null)
        {
            if (entityCol.Other == entity)
                entityCol = new Collision(entity, entityCol.Obj1);
            entity.OnCollision(entityCol);
        }

Collision FindCollision(GameObject obj)
{
    Collision collision = AllCollisions.Find(delegate (Collision col) { return (GameObject)col.Obj1 == obj || (GameObject)col.Other == obj; });
    return collision;
}

当游戏对象数量增加时，这使我的游戏运行变慢得相当快。

我脑海中浮现的第一件事就是创建新线程，这是个好主意吗？我该如何以好的方式做到这一点？

我学习了一点算法，所以我知道基本概念和 ordo 的工作原理。

我对 C# 和整体编程还很陌生，所以不要在没有解释的情况下过于深入。不过我学得很快。

Answer 1

您可以做很多事情：

嵌套的 for 循环产生二次运行时间，随着对象数量的增加，它增长得相当快。相反，您可以使用一些加速数据结构（例如网格、kd 树、BVH）。这些允许您将相交检查减少到仅可能相交的实体。

如果您可以对实体进行排序，则只需检查实体对即可将碰撞检查减少一半，其中第二个比第一个 "greater"（就顺序而言）。 IE。如果您已经检查了 a-b，则不需要检查 b-a。

这部分可能会很慢：

!Exclude(new Collision(obja, objb)))

如果Collision是class，那么这将始终在堆上分配新内存并最终回收它。因此，将 Collision 设为 struct（如果还没有）或将 obja 和 objb 直接传递给 Exclude() 可能会更好。这也适用于 Collision 的其他用途。您还没有显示 Exclude() 的实现，但如果它是一个简单的线性搜索，则可以改进（例如，如果您在包含每个对象条目的列表中进行线性搜索，您已经有一个立方体运行只是循环的时间）。

FindCollision() 的实现很可能是线性搜索（取决于 AllCollisions 是什么），它可能会变得很慢。你为什么要存储碰撞？不能一发现碰撞就直接调用OnCollision()吗？如果您想检查碰撞是否有效地与特定实体相关联，则不同的数据结构（例如哈希映射）会更合适。

最后，并行化无疑是一个可行的选择。然而，这有点复杂，我建议首先关注基础知识。如果操作正确，您可以将立方运行时间减少到 n log n 甚至 n。

XNA如何写好碰撞算法？

XNA how to write a good collision algorithm?

c#

algorithm

xna

collision-detection

monogame