检查矩形列表和单个矩形之间交集的最快方法

Question

我想检查一个 Rectangle(A Player) 是否与列表 (List) 中的一个矩形相交。

我目前正在使用 for 循环，这使它变慢并且性能不佳。

for (int i = 0; i < gameObjects.objectList.Count; i++)
{
   if (gameObjects.objectList[i].IntersectsWith(gameObjects.player))
   {
        gameObjects.objectList.RemoveAt(i); // if the player collided with an object, remove that object
    }
}

我怎样才能让它更有效率/有没有其他方法可以让它更快？

Answer 1

您可以尝试在名为 k-d-tree.

的结构中组织您的矩形

在大型矩形数组 (> 100) 中，它的复杂度最高为 O(log N)。

F.e。制作固定长度的二叉树，比如 2。将 space 分成左右两半，然后将每一半分成上下四分之一（依此类推）。

在叶节点内部创建一个矩形列表。如果一个矩形落在左半边和上四分之一处，则在该四分之一的列表中找到它。

一个矩形可能同时位于几个列表中（f.e。如果它落在左右两半）。

要检查交叉点，您应该在响应的一半和四分之一处测试矩形。

或者，您删除了太多矩形，在您自己的代码中将剩余的矩形复制到新列表中会更快。

小例子。

public enum CheckBy
{
    Horizontal,

    Vertical
}

public class Node
{
    public Node First { get; set; }

    public Node Second { get; set; }

    public int Coordinate { get; set; }

    public CheckBy CheckBy { get; set; }

    public List<Rectangle> Rectangles { get; set; }
}

public bool IsRectangleInFist(Node node, Rectangle rectangle)
{
    if (node.CheckBy == CheckBy.Horizontal)
        return rectangle.Left <= node.Coordinate;

    return rectangle.Top <= node.Coordinate;
}

public bool IsRectangelInSecond(Node node, Rectangle rectangle)
{
    if (node.CheckBy == CheckBy.Horizontal)
        return rectangle.Right >= node.Coordinate;

    return rectangle.Bottom >= node.Coordinate;
}

public void AddRectangleInSuitableNode(Node node, Rectangle rectangle)
{
    if (InRectangleInFirst(node, rectangle))
        AddRectangleInSuitableNode(node.First, rectangle);

    if (InRectangleInSecond(node, rectangle))
        AddRectangleInSuitableNode(node.Second, rectangle);
}

public void SearchIntersectedRectangles(Node node, Rectangle rectangle, List<Rectangles> result)
{
    // If not-leaf node
    if (node.Rectangles == null && node.First != null && node.Second != null)
    {
        if (IsRectangleInFirst(node, rectangle))
            SearchIntersecatedRectangles(node.First, rectangle, result);

        if (IsRectangleInSecond(node, rectangle))
            SearchIntersecatedRectangles(node.Second, rectangle, result);

        return;
    }

    result.AddRangle(Rectangles.Where(r => r.IsIntersect(rectangle)));
}

这些所有的线构成了简单的二维树。首先，制作树：

// Say, all rectangles would be inside this "space"
const int leftest = -1000;
const int rightest = 1000;
const int bottomest = -1000;
const int toppest = 1000;

// Tree with depth == 2
var tree = new Node
{
    CheckBy = CheckBy.Hozirontal,
    Coordinate = (leftest + rightest)/2,
    First = new Node
    {
        CheckBy = CheckBy.Vertical,
        Coordintate = (toppest + bottomest)/2,
        Rectangles = new List<Rectangle>(),
    },
    Second = new Node
    {
        CheckBy = CheckBy.Vertical,
        Coordintate = (toppest + bottomest)/2,
        Rectangles = new List<Rectangle>(),
    },
}

然后，对这棵树中的所有矩形进行排序：

foreach (var rectangle in rectangles)
    AddRectangleInSuitableNode(tree, rectangle);

现在你可以快速得到相交的矩形：

var intersecting = new List<Rectangles>();
SearchIntersecatedRectangles(tree, targetRectangle, intersecting);
// Here you can remove intersecting rectangles...

Answer 2

基本上，您每次都需要停止检查所有矩形。您需要以某种方式找出哪些矩形位于玩家附近。

您可以使用某种空间网格来存储您的矩形，这样您就可以快速找到要检查碰撞的相邻矩形。例如，请参阅本教程：N Tutorial B - Broad-Phase Collision。

Answer 3

我怀疑它会更快，但你总是可以在一个班轮中与 Ling 一起完成：

gameObjects.objectList = gameObjects.objectList
                         .Select(go => go)
                         .Where(go => !go.IntersectsWith(gameObjects.player))
                         .ToList();

这实质上将列表设置为一个列表，其中删除了与 player 冲突的任何 gameObject。

另请注意，首先处理排序列表通常更快，因此这样做：

gameObjects.objectList = gameObjects.objectList
                         .OrderBy(go => go.X)
                         .ThenBy(go => go.Y)
                         .ToList();

可能有助于加快处理速度。虽然对每一帧进行这种排序会很慢，但值得在对象添加到列表时对其进行排序。

检查矩形列表和单个矩形之间交集的最快方法

Fastest way to check intersection between a Rectangle List and a single Rectangle

c#

iteration

game-engine