同一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

碰撞检测就是要尽量减少检查的次数。例如，您应该而不是对照其他角色检查每个角色，除非您的角色非常少。这是一个O(N^2)的算法，当你添加角色时，它的伸缩性不是很好(数量翻倍需要4倍的时间)。也许你知道每个演员的身高?然后你可以尝试碰撞在这个范围内的演员。有一个叫做ANN的库，可以用来快速找到最近的邻居。

祝你好运!

Answer 2

你的算法基本上是对象数量的二次，所以难怪随着对象数量的增加它会变慢。

我会应用某种分割:你将对象根据它们的位置分成不同的列表，这样只有相同或相邻列表的对象才能碰撞。这样你的比较次数会更少。

另一个流行的优化是只检查自上次检查以来移动的对象，这可能(也可能不)排除许多静态对象。