周围物体算法

Question

我工作的一个游戏,只有一个对象可以在位置存在(x, y)哪里x以及y是ints.例如,对象可能存在于(0, 0)或不存在,但是不可能同时存在多个对象.

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

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

例如,假设以下代表我的对象网格,并且我从位置处的绿色对象开始(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()如果我决定这样做,我可能会做很多调用,但是地图占用的内存比new整个世界的2D数组少得多.

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

Answer 1

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

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

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