Вложенная итерация в одной мультикарте - PullRequest
Новая
       17

Вложенная итерация в одной мультикарте

0 голосов
/ 27 декабря 2011

Я пытаюсь выполнить проверку столкновения на моих игровых объектах.У меня есть мультикарта, которая содержит объекты одного типа в каждом ключе.Ключ представляет тип объекта.Тем не менее, все типы происходят из одного и того же класса.Мне нужно было разделить их, чтобы объекты знали, что делать, когда объект одного типа касается другого объекта другого типа.Но похоже, что мой способ проверки столкновения очень медленный, потому что я заметил, что чем больше объектов я добавляю, тем медленнее они движутся.Может кто-нибудь мне помочь?: (

Вот точный код: 

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 - это просто shared_ptr Actor;

Ответы [ 2 ]

1 голос
/ 27 декабря 2011

Обнаружение столкновений сводится к минимизации количества проверок, которые вы должны сделать.Например, вы должны , а не проверять каждого актера против остальных, если у вас мало актеров.Это алгоритм O (N ^ 2), который не очень хорошо масштабируется при добавлении актеров (удвоение числа занимает в четыре раза больше времени).Возможно, вы знаете размер каждого актера?Тогда вы можете попробовать столкновение с актерами, которые находятся в этом диапазоне.Есть библиотека под названием ANN , с помощью которой можно очень быстро найти ближайших соседей.

Удачи!

0 голосов
/ 27 декабря 2011

Ваш алгоритм в основном квадратичен по количеству объектов, поэтому неудивительно, что с увеличением числа объектов он замедляется.

Я бы применил некоторую сегментацию: вы разделяете объекты на разные списки в зависимости от их местоположения, так что только объекты из тех же или смежных списков могут сталкиваться. Таким образом, количество сравнений будет меньше.

Другой популярной оптимизацией будет проверка только тех объектов, которые были перемещены с момента последней проверки, это может (или не может) исключать множество статических объектов.

...