1

基本上我正在尝试在 XNA 2D 中制作一个磁贴引擎，我目前正在使用一个大的磁贴列表（我的类保存磁贴的所有数据）并选择我的视图范围内的那些，然后将它们显示在屏幕上。

显然，我遇到的问题是，我的 Tiles 整体列表越大，我在尝试挑选范围内的 Tiles 时遇到的延迟就越多。我目前在 for 循环中使用 Linq 来选择图块，如下所示：

//loop from the maximum view at the top of the screen to the maximum view at the bottom
for (int height = topView; height < bottomView; height++)
{
    //loop from the maximum view to the left of the screen to the maximum view of the right
    for (int width = leftView; width < rightView; width++)
    {
        //select the tile at this grid position
        Tile t = tileList.Where(x => x.GridPosition == new Vector2(width, height)).FirstOrDefault();
        if (t != null)
        {
            //calculate the screen position and add it to the list of local tiles within range
            t.ScreenPosition = new Vector2(screenWidth * 30, screenHeight * 30);
            localList.Add(t);
        }
        else
        {
            //the tile wasn't found, add a random blank one to fill the gap.
            Tile brokenTile = new Tile(game, new Vector2(width, height), 9001);
            brokenTile.ScreenPosition = new Vector2(screenWidth * 30, screenHeight * 30);
            localList.Add(brokenTile);
        }
        //increment the screen width used to calculate the screen position
        screenWidth++;
    }
    //increment the screen height used to calculate the screen position and reset the width
    screenHeight++;
    screenWidth = 1;
}

我想知道是否有一种方法可以更有效地做到这一点，理想情况下可以减少在增加“地图”的整体大小并选择范围内的这些图块时所经历的滞后。

我唯一能想到的是在加载地图时将总列表分成“块”的某种方法，并且只查看每个块以拉出瓷砖..但是我不太确定我会怎么做因为如果我需要从多个“块”中拉出节点可能会很麻烦但是任何关于这样做的好方法的帮助也会很棒！

非常感谢！:)

编辑：这里有一些截图：http ://i.imgur.com/RJmSYYF.png 与http://i.imgur.com/LgwB8CJ.png相比

4

2 回答 2

0

可以在 k 维空间中快速找到对象的集合是 KD-Tree。

请参阅Wikipedia 和Geometric Algorithms上的kd 树。

我将 KD-tree 的 Java 实现移植到 C#。请参阅RoboWiki 上的用户：Ojd/KD-Tree。你可以在那里下载代码。

KD 树的搜索时间为O(log n) 。

更新：

您的屏幕截图显示瓷砖放置在矩形网格中。为什么不直接使用二维数组来存储您的图块？

Tile[,] grid = new Tile[m,n];

现在选择图块变得非常自然，因为您可以从屏幕位置计算它们在网格中的位置。像这样，您可以通过它们的 xy 索引直接访问它们，而无需在 lagre 列表中搜索它们。单个图块的访问时间是O(1)，即与图块的总数无关。

于 2013-03-31T18:37:31.040 回答
0

我会考虑使用某种形式的空间分区，例如四叉树。

这意味着根据它们的位置将您的对象分配给常规大小的四边形。您将能够有效地确定哪些四边形是可见的，并且每个四边形将知道它包含哪些对象（尽管您需要在移动对象时对其进行管理）。

于 2013-03-31T18:47:15.343 回答