c++ - 同一 multimap 中的嵌套迭代

Question

我正在尝试对我的游戏对象进行碰撞检查。我有一个 multimap，它在每个键中包含相同类型的对象。键代表对象的类型。但是，所有类型都派生自同一个类。我需要将它们分开，以便当一种类型的对象接触到另一种类型的另一个对象时，这些对象知道该怎么做。但是我检查碰撞的方法似乎很慢，因为我注意到我添加的对象越多，它们移动的越慢。谁能帮我？ :(

具体代码如下:

void CheckCollisions()
{
    if (!Actors.empty())
    {
        std::multimap<std::string, boost::shared_ptr<std::vector<PActor>>>::const_iterator it;
        it = Actors.begin();
        while (it != Actors.end())
        {
            for (int i = 0; i < static_cast<int>(it->second->size()); i++)
            {
                std::multimap<std::string, boost::shared_ptr<std::vector<PActor>>>::const_iterator it2;
                it2 = Actors.begin();
                while(it2 != Actors.end())
                {
                    for (int j = 0; j < static_cast<int>(it2->second->size()); j++)
                    {
                        if (i != j)
                        {
                            if (Touch(it->second->at(i), it2->second->at(j)))
                            {
                                it->second->at(i)->Touch(it2->first, it2->second->at(j));
                                it2->second->at(j)->Touch(it->first, it->second->at(i));
                            }
                        }
                    }
                    it2++;
                }
            }
            it++;
        }
    }
}

注意: PActor 只是 Actor 的一个 shared_ptr；

Answer 1

碰撞检测就是要最大限度地减少您必须执行的检查次数。例如，你不应该不检查每个 Actor 与其他 Actor ，除非你的 Actor 很少。这是一个 O(N^2) 算法，在添加 Actor 时不能很好地扩展(双倍的数字需要四倍的时间)。也许你知道每个 Actor 的身材？然后你可以尝试与这个范围内的 Actor 碰撞。有一个图书馆叫ANN可用于快速找到最近的邻居。

祝你好运!