C# XNA : Optimizing Collision Detection?

Question

我正在开发一个简单的碰撞检测演示，其中仅包含一堆在窗口中弹跳的对象。 (目标是查看游戏一次可以处理多少个对象而不会丢帧。)

存在重力，所以物体要么移动要么与墙壁碰撞。

天真的解决方案是 O(n^2):

foreach Collidable c1:
      foreach Collidable c2:
             checkCollision(c1, c2);

这很糟糕。因此，我设置了 CollisionCell 对象，它维护有关屏幕一部分的信息。这个想法是每个 Collidable 只需要检查其单元格中的其他对象。对于 60 像素 x 60 像素的单元格，这产生了近 10 倍的改进，但我想进一步插入它。

分析器显示，代码将 50% 的时间花在每个单元格用来获取其内容的函数上。在这里:

    // all the objects in this cell
    public ICollection<GameObject> Containing
    {
        get
        {
            ICollection<GameObject> containing = new HashSet<GameObject>();

            foreach (GameObject obj in engine.GameObjects) {
                // 20% of processor time spent in this conditional
                if (obj.Position.X >= bounds.X &&
                    obj.Position.X < bounds.X + bounds.Width &&
                    obj.Position.Y >= bounds.Y &&
                    obj.Position.Y < bounds.Y + bounds.Height) {

                    containing.Add(obj);
                }
            }

            return containing;
        }
    }

程序的 20% 的时间花在了该条件语句上。

这里是调用上述函数的地方:

    // Get a list of lists of cell contents
        List<List<GameObject>> cellContentsSet = cellManager.getCellContents();

        // foreach item, only check items in the same cell
        foreach (List<GameObject> cellMembers in cellContentsSet) {
            foreach (GameObject item in cellMembers) {
                 // process collisions
            }
        }


//...

    // Gets a list of list of cell contents (each sub list = 1 cell)
    internal List<List<GameObject>> getCellContents() {
        List<List<GameObject>> result = new List<List<GameObject>>();
        foreach (CollisionCell cell in cellSet) {
            result.Add(new List<GameObject>(cell.Containing.ToArray()));
        }
        return result;
    }

现在，我必须遍历每个单元格 - 甚至是空单元格。也许这可以以某种方式改进，但我不确定如何在不以某种方式查看单元格的情况下验证单元格是否为空。 (也许我可以在一些物理引擎中实现类似于 sleep 对象的东西，如果一个对象将静止一段时间，它就会进入休眠状态，并且不会包含在每一帧的计算中。)

我可以做些什么来优化它？ (此外，我是 C# 的新手 - 还有其他明显的文体错误吗？)

当游戏开始滞后时，物体往往会挤得相当紧，因此不会有太多运动。也许我可以以某种方式利用这一点，编写一个函数来查看给定对象的当前速度，它是否可以在下一次调用 Update()

之前离开其当前单元格

UPDATE 1 我决定维护一个列表，列出上次更新时发现在单元格中的对象，并首先检查它们是否仍在单元格中。此外，我维护了 CollisionCell 变量的一个 area，当单元格被填满时我可以停止查看。这是我的实现，它使整个演示变慢了很多:

    // all the objects in this cell
    private ICollection<GameObject> prevContaining;
    private ICollection<GameObject> containing;
    internal ICollection<GameObject> Containing {
        get {
            return containing;
        }
    }

    /**
     * To ensure that `containing` and `prevContaining` are up to date, this MUST be called once per Update() loop in which it is used.
     * What is a good way to enforce this?
     */ 
    public void updateContaining()
    {
        ICollection<GameObject> result = new HashSet<GameObject>();
        uint area = checked((uint) bounds.Width * (uint) bounds.Height); // the area of this cell

        // first, try to fill up this cell with objects that were in it previously
        ICollection<GameObject>[] toSearch = new ICollection<GameObject>[] { prevContaining, engine.GameObjects };
        foreach (ICollection<GameObject> potentiallyContained in toSearch) {
            if (area > 0) { // redundant, but faster?
                foreach (GameObject obj in potentiallyContained) {
                    if (obj.Position.X >= bounds.X &&
                        obj.Position.X < bounds.X + bounds.Width &&
                        obj.Position.Y >= bounds.Y &&
                        obj.Position.Y < bounds.Y + bounds.Height) {

                        result.Add(obj);
                        area -= checked((uint) Math.Pow(obj.Radius, 2)); // assuming objects are square
                        if (area <= 0) {
                            break;
                        }
                    }
                }
            }
        }
        prevContaining = containing;
        containing = result;
   }

UPDATE 2 我放弃了最后一种方法。现在我正在尝试维护一个可碰撞对象池(孤儿)，并在找到包含它们的单元格时从中删除对象:

    internal List<List<GameObject>> getCellContents() {
        List<GameObject> orphans = new List<GameObject>(engine.GameObjects);
        List<List<GameObject>> result = new List<List<GameObject>>();
        foreach (CollisionCell cell in cellSet) {
            cell.updateContaining(ref orphans); // this call will alter orphans!
            result.Add(new List<GameObject>(cell.Containing)); 
            if (orphans.Count == 0) {
                break;
            }
        }
        return result;
    }

    // `orphans` is a list of GameObjects that do not yet have a cell
    public void updateContaining(ref List<GameObject> orphans) {
        ICollection<GameObject> result = new HashSet<GameObject>();

        for (int i = 0; i < orphans.Count; i++) {
            // 20% of processor time spent in this conditional
            if (orphans[i].Position.X >= bounds.X &&
                orphans[i].Position.X < bounds.X + bounds.Width &&
                orphans[i].Position.Y >= bounds.Y &&
                orphans[i].Position.Y < bounds.Y + bounds.Height) {

                result.Add(orphans[i]);
                orphans.RemoveAt(i);
            }
        }

        containing = result;
    }

这只会产生边际改善，而不是我正在寻找的 2 倍或 3 倍。

UPDATE 3 我再次放弃了上述方法，并决定让每个对象保持其当前单元格:

    private CollisionCell currCell;
    internal CollisionCell CurrCell {
        get {
            return currCell;
        }
        set {
            currCell = value;
        }
    }

这个值得到更新:

    // Run 1 cycle of this object
    public virtual void Run()
    {
        position += velocity;
        parent.CellManager.updateContainingCell(this);
    }

CellManager 代码:

private IDictionary<Vector2, CollisionCell> cellCoords = new Dictionary<Vector2, CollisionCell>();
    internal void updateContainingCell(GameObject gameObject) {
        CollisionCell currCell = findContainingCell(gameObject);
        gameObject.CurrCell = currCell;
        if (currCell != null) {
            currCell.Containing.Add(gameObject);
        }
    }

    // null if no such cell exists
    private CollisionCell findContainingCell(GameObject gameObject) {

        if (gameObject.Position.X > GameEngine.GameWidth
            || gameObject.Position.X < 0
            || gameObject.Position.Y > GameEngine.GameHeight
            || gameObject.Position.Y < 0) {
            return null;
        }

        // we'll need to be able to access these outside of the loops
        uint minWidth = 0;
        uint minHeight = 0;

        for (minWidth = 0; minWidth + cellWidth < gameObject.Position.X; minWidth += cellWidth) ;
        for (minHeight = 0; minHeight + cellHeight < gameObject.Position.Y; minHeight += cellHeight) ;

        CollisionCell currCell = cellCoords[new Vector2(minWidth, minHeight)];

        // Make sure `currCell` actually contains gameObject
        Debug.Assert(gameObject.Position.X >= currCell.Bounds.X && gameObject.Position.X <= currCell.Bounds.Width + currCell.Bounds.X,
            String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.X, currCell.Bounds.X, currCell.Bounds.X + currCell.Bounds.Width));
        Debug.Assert(gameObject.Position.Y >= currCell.Bounds.Y && gameObject.Position.Y <= currCell.Bounds.Height + currCell.Bounds.Y,
            String.Format("{0} should be between lower bound {1} and upper bound {2}", gameObject.Position.Y, currCell.Bounds.Y, currCell.Bounds.Y + currCell.Bounds.Height));

        return currCell;
    }

我认为这会让它变得更好——现在我只需要遍历可碰撞对象，而不是所有可碰撞对象 * 单元格。取而代之的是，游戏现在慢得可怕，使用我的上述方法只能提供其性能的 1/10。

探查器表明现在主要的热点是一种不同的方法，并且为对象获取邻居的时间非常短。该方法与以前相比没有变化，所以我可能比以前更常调用它...

Answer 1

它在该函数上花费了 50% 的时间，因为您经常调用该函数。优化一个功能只会对性能产生增量改进。

或者，只需少调用函数!

您已经通过设置空间分区方案开始了这条道路(查找 Quadtrees 以查看您的技术的更高级形式)。

第二种方法是将 N*N 循环分解为增量形式并使用CPU 预算。

您可以为每个需要在帧时间内(更新期间)执行操作的模块分配 CPU 预算。碰撞是这些模块之一，人工智能可能是另一个。

假设您希望以 60 fps 的速度运行游戏。这意味着您有大约 1/60 s = 0.0167 s 的 CPU 时间在帧之间刻录。不，我们可以在我们的模块之间拆分那些 0.0167 秒。让我们给碰撞 30% 的预算:0.005 秒。

现在您的碰撞算法知道它只能花费 0.005 秒的时间工作。因此，如果它用完了时间，它将需要推迟一些任务以备后用——您将使算法增量。实现这一点的代码可以很简单:

const double CollisionBudget = 0.005;

Collision[] _allPossibleCollisions;
int _lastCheckedCollision;

void HandleCollisions() {

    var startTime = HighPerformanceCounter.Now;

    if (_allPossibleCollisions == null || 
        _lastCheckedCollision >= _allPossibleCollisions.Length) {

        // Start a new series
        _allPossibleCollisions = GenerateAllPossibleCollisions();
        _lastCheckedCollision = 0;
    }

    for (var i=_lastCheckedCollision; i<_allPossibleCollisions.Length; i++) {
        // Don't go over the budget
        if (HighPerformanceCount.Now - startTime > CollisionBudget) {
            break;
        }
        _lastCheckedCollision = i;

        if (CheckCollision(_allPossibleCollisions[i])) {
            HandleCollision(_allPossibleCollisions[i]);
        }
    }
}

现在不管碰撞代码有多快，它都会尽可能快地完成，不会影响用户的感知性能。

好处包括:

• 该算法旨在用完时间，它会在下一帧恢复，因此您不必担心这种特殊的边缘情况。
• 随着高级/耗时算法数量的增加，CPU 预算变得越来越重要。想想人工智能。因此，尽早实现此类系统是个好主意。
• 人类响应时间小于 30 赫兹，您的帧循环以 60 赫兹运行。这给了算法 30 帧来完成它的工作，所以它没有完成它的工作是可以的。
• 这样做可以提供稳定、数据独立的帧速率。
• 它仍然受益于碰撞算法本身的性能优化。
• 碰撞算法旨在追踪发生碰撞的“子帧”。也就是说，您永远不会幸运地 catch 碰撞，恰好发生碰撞 - 认为您这样做是在自欺欺人。