周围物体算法

我正在开发一款游戏，该位置可能只存在一个对象(x, y) where x and y are ints。例如，一个对象可能存在于(0, 0)也可能不存在，但不可能同时存在多个对象。

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

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

例如，假设以下内容代表我的对象网格，并且我从位置处的绿色对象开始(3, 4):

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

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

这些物品相当罕见，而游戏世界却很大。仅仅看起来不切实际new整个游戏世界的二维数组，因为大多数元素都是空的。但是，我需要索引到任何位置以检查对象是否随时存在。

相反，我考虑使用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()如果我决定这样做，但地图占用的内存比new整个世界的二维数组。

有人对我可以用来查找我要查找的内容的简单算法有任何建议吗？我应该继续使用std::map或者有更好的容器来解决这样的问题吗？

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

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

b) 如果网格地图位置确实只是点，则每个网格位置使用 1 位。结果图将比每个网格点使用字节的结果图小 8x8=64 倍。位运算快如闪电。 10,000x10,000 的地图将需要 100,000,000 位或 12.5MB（大约）