7

我正在开发一款游戏，其中一个对象可能存在于(x, y)wherex和yare的位置ints。例如，一个对象可能存在(0, 0)也可能不存在，但不可能同时存在多个对象。

我正在尝试决定使用哪个 STL 容器来解决手头的问题以及解决此问题的最佳方法。

基本上，我从一个对象及其(x, y)位置开始。目标是根据该对象的周围对象确定最高、最大的可能矩形。必须使用当前对象上方和下方的所有对象来创建矩形。也就是说，它必须是可能基于起始对象位置的最高点。

例如，假设以下代表我的对象网格，我从 location 的绿色对象开始(3, 4)：

在此处输入图像描述

然后，我正在寻找的矩形将由下面的粉红色方块表示：

在此处输入图像描述

因此，假设我从(3, 4)示例中所示的对象开始，我将需要检查对象是否也存在于(2, 4)、(4, 4)、(3, 3)和(3, 5)。如果对象存在于这些位置中的任何一个，我需要重复该过程以使对象找到最大可能的矩形。

这些物品相当稀有，游戏世界很大。new整个游戏世界只使用一个 2D 数组似乎并不实际，因为大多数元素都是空的。但是，我需要索引到任何位置以随时检查对象是否存在。

相反，我考虑过使用std::map这样的：

std::map< std::pair<int, int>, ObjectData> m_objects;

然后，当我检查周围的物体时，我可以map::find()在我的循环中使用，检查周围的物体是否存在：

if(m_objects.find(std::pair<3, 4>) != m_objects.end())
{
    //An object exists at (3, 4).
    //Add it to the list of surrounding objects.
}

如果我决定这样做，我可能会打很多电话map::find()，但地图占用的内存比newing 整个世界的 2D 数组要少得多。

有人对我可以用来查找所需内容的简单算法有任何建议吗？我应该继续使用 astd::map还是有更好的容器来解决此类问题？

4

4 回答 4

1

您需要在每个网格位置存储多少数据？如果您只是在寻找指示邻居的标志，那么您至少有两个“低技术”解决方案

a) 如果你的网格是稀疏的，每个方格保存一个邻居列表怎么样？所以每个方格都知道哪些相邻方格被占用。当广场被占用或腾出时，您将需要做一些工作来维护列表。但是邻居列表意味着您根本不需要网格图

b) 如果网格地图位置确实只是点，则每个网格位置使用 1 位。结果映射将比为每个网格点使用字节的映射小 8x8=64 倍。位操作正在快速减轻。10,000x10,000 的地图将占用 100,000,000 位或 12.5MB（大约）

于 2012-12-17T06:14:45.013 回答
0

您可能需要考虑空间数据结构。如您所说，如果数据是“稀疏”的，那么进行四叉树邻域搜索可能会为您节省大量处理能力。我个人会使用 R-tree，但这很可能是因为我有一个我编写的 R-tree 库并且可以轻松导入。

例如，假设您有一个1000x1000包含 10,000 个元素的网格。假设目前是均匀随机分布，我们将（基于密度）期望不超过，说。. . 在任一维度上接触的三到五个对象链（在此密度下，三个垂直方向的对象链将以 0.01% 的概率发生）。假设所考虑的对象位于(x,y)。一个窗口搜索，从 at(x-5,y-5)开始到(x+5,y+5)将给你一个最多包含 121 个元素的列表来执行线性搜索。如果您的 rect-picking 算法注意到有可能形成一个更高的矩形（即，如果正在考虑的 rect 触及这个11x11边界框的边缘），只需重复窗口搜索另一个5x5原稿的一个方向上的区域。根据需要重复。

当然，这仅在您拥有极其稀疏的数据时才有效。可能值得调整 R-tree 以使叶子成为关联。数据结构（即Int -> Int -> Object），但在这一点上，最好只找到一个适用于更密集数据的解决方案。

我可能想多了；在某个地方可能有一个更简单的解决方案。

关于 R-trees 的一些参考资料：

如果我有时间清理一下，我将使用指向我自己的 R-tree 实现（公共域）的链接对其进行编辑。

于 2012-12-16T22:34:53.630 回答
0

如果可能的话，一种改进是使用哈希图。这将允许您至少以 O(1) 的预期时间复杂度进行潜在的广泛搜索。

这里有一个线程（将两个整数映射到一个，以独特且确定的方式）详细介绍了如何将两个整数散列在一起。

如果你的编译器支持 C++11，你可以使用 std::unordered_map。如果没有，boost 基本相同： http: //www.boost.org/doc/libs/1_38_0/doc/html/boost/unordered_map.html

于 2012-12-16T19:50:56.103 回答
0

这听起来像是一个家庭作业问题（因为它有一个奇怪的条件“必须通过使用当前对象上方和下方的所有对象来创建矩形”，这使得解决方案变得微不足道）。但无论如何我都会试一试。为方便起见，我将使用“像素”一词而不是“对象”。

如果您的应用程序确实需要重量级的解决方案，您可以尝试将像素存储在四叉树中（其叶子包含每个只有几千像素的普通旧二维数组）。或者您可以将连续的像素组合成“形状”（例如，您的示例将仅包含一个“形状”，即使它包含 24 个单独的像素）。给定一个初始的非结构化像素坐标列表，很容易找到这些形状；谷歌“联合查找”。存储连续形状的具体好处是，当您寻找最大的矩形时，您只需要考虑与初始像素形状相同的那些像素。

存储连续形状的一个特定缺点是，如果您的像素对象四处移动（例如，如果它们代表 roguelike 游戏中的怪物），我不确定 union-find 数据结构是否支持增量更新。您可能必须在每个“帧”上运行 union-find，这将非常糟糕。

无论如何...假设您正在使用 a std::unordered_map<std::pair<int,int>, ObjectData*>，因为这对我来说听起来很合理。（您几乎肯定应该在映射中存储指针，而不是实际对象，因为复制所有这些对象会比复制指针慢很多。）

typedef std::pair<int, int> Pt;
typedef std::pair<Pt, Pt> Rectangle;
std::unordered_map<Pt, ObjectData *> myObjects;

/* This helper function checks a whole vertical stripe of pixels. */
static bool all_pixels_exist(int x, int min_y, int max_y)
{
    assert(min_y <= max_y);
    for (int y = min_y; y <= max_y; ++y) {
        if (myObjects.find(Pt(x, y)) == myObjects.end())
            return false;
    }
    return true;
}

Rectangle find_tallest_rectangle(int x, int y)
{
    assert(myObjects.find(Pt(x,y)) != myObjects.end());
    int top = y;
    int bottom = y;
    while (myObjects.find(Pt(x, top-1) != myObjects.end()) --top;
    while (myObjects.find(Pt(x, bottom+1) != myObjects.end()) ++bottom;
    // We've now identified the first vertical stripe of pixels.
    // The next step is to "paint-roller" that stripe to the left as far as possible...
    int left = x;
    while (all_pixels_exist(left-1, top, bottom)) --left;
    // ...and to the right.
    int right = x;
    while (all_pixels_exist(right+1, top, bottom)) ++right;
    return Rectangle(Pt(top, left), Pt(bottom, right));
}
于 2012-12-21T23:44:15.923 回答