Простой вопрос эффективности C ++ (распределение памяти) .. и, возможно, поможет какое-то обнаружение столкновений?

Question

Я пишу небольшую аркадную игру на C ++ (многонаправленный 2-мерный космический шутер) и заканчиваю процесс обнаружения столкновений.

Вот как я это организовал (я просто придумал, чтобы это была дерьмовая система):

Каждый корабль состоит из круговых компонентов - количество компонентов на каждом корабле является произвольным (больше компонентов, больше циклов ЦП). У меня есть расстояние maxComponent, которое я вычисляю при создании корабля, которое является в основном самой длинной линией, которую я могу провести от центра корабля до края самого дальнего компонента. Я слежу за вещами на экране и использую maxComponentDistance, чтобы увидеть, достаточно ли они близки для столкновения.

Если они находятся в непосредственной близости, я начинаю проверять, пересекаются ли компоненты разных кораблей. Здесь мой вопрос эффективности.

У меня есть (x, y) расположение компонента относительно центра корабля, но это не учитывает, как корабль вращается в данный момент. Я держу их относительными, потому что не хочу пересчитывать компоненты каждый раз, когда корабль движется. Итак, у меня есть небольшая формула для расчета вращения, и я возвращаю 2d-вектор, соответствующий положению, важному для вращения, относительно центра корабля.

Обнаружение столкновения находится в GameEngine и использует 2d-вектор. Мой вопрос о типах возврата. Должен ли я просто создавать и возвращать 2d-векторный объект каждый раз, когда вызывается функция или же я должен дать этому компонентному объекту дополнительную частную переменную 2d-вектора, отредактировать частную переменную при вызове функции и вернуть указатель на этот объект?

Я не уверен в эффективности распределения памяти по сравнению с наличием постоянной, редактируемой, закрытой переменной. Я знаю, что память также должна была бы быть выделена для закрытой переменной, но не каждый раз, когда она проверялась на наличие коллизий, только при создании нового компонента. Компоненты не являются постоянными в моей среде, так как они удаляются при разрушении корабля.

Это моя главная дилемма. Я также был бы признателен за любые советы по разработке моей реальной системы обнаружения столкновений. Это мой первый раз, когда я взломал его (возможно, следовало немного прочитать)

Заранее спасибо.

Answer 1

Вы должны абсолютно постараться избежать выделения памяти для вашего компонента-вектора при каждом вызове функции-получателя. Вместо этого делайте распределение как можно реже. Например, вы можете сделать это, когда состав компонентов корабля изменяется или даже реже (перераспределением).

Конечно, вы также можете исследовать пулы памяти, где вы предварительно выделяете много таких компонентов и помещаете в пул, чтобы вы могли выделить новый компонент за постоянное время.

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

Answer 2

Если ваш 2D вектор просто:

 class Vector2D { double x, y; };

Тогда непременно верните его! Например:

  Vector2D function( ... );

Или передать по ссылке:

  void function( Vector2D * theReturnedVector2D, ... );

Избегайте любой ценой:

 vector<double> function(...);

Постоянное выделение / освобождение кучи, присущее классу Vector, является ошибкой!

---

Копирование вашего собственного класса Vector2D очень дешево с точки зрения вычислений. В отличие от Vector <>, ваш собственный класс Vector2D может включать любые методы, которые вам нравятся.

В прошлом я использовал эту функцию для включения таких методов, как distanceToOtherPointSquared (), scanfFromCommandLineArguments (), printfNicelyFormatted () и operator [] (int).

---

или я должен дать этому компонентному объекту дополнительную приватную переменную 2d-вектора, отредактировать приватную переменную при вызове функции и вернуть указатель на этот объект?

Остерегайтесь множественных вызовов функций, делающих недействительными предыдущие данные. Это рецепт катастрофы!

Answer 3

Существует большая разница между распределением памяти в куче и в стеке. Выделение в куче, например, с использованием new / delete или malloc / free выполняется очень медленно. Распределение в стеке действительно довольно быстро. Со стеком обычно медленная часть копирует ваш объект. Так что следите за вектором и тому подобным, но возвращение простых структур, вероятно, нормально.

Answer 4

Не используйте 2D вектор. Скорее используйте vector из point с. Аналогично для вашего обнаружения столкновений. Использование двумерного вектора - это просто неправильная структура данных.

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

vector<int> f(int baz) {
    vector<int> ret;
    if (baz == 42)
        ret.push_back(42);
    return ret;
}

vector<int> g(int baz) {
    if (baz == 42)
        return vector<int>(1, 42);
    else
        return vector<int>();
}

Компилятор может выполнять NRVO для вызовов на f, но не на g.

Answer 5

1. Вы можете начать с простого возврата вектора и оценки его производительности. Кто знает, это может быть достаточно быстро. С помощью профилировщика вы даже можете увидеть, какая часть занимает время выполнения.
2. Вы можете использовать Пул памяти для повторного использования векторов и уменьшения количества копий
3. Вы можете попробовать шаблон Flyweight для координат, чтобы уменьшить копирование и распределение, если они повторяются по всему движку.
4. Хранение данных в компоненте является хорошим способом сокращения выделений, но вводит некоторые ошибки в ваш дизайн, например, тот, кто использует вектор, зависит от жизненного цикла компонента. Пул памяти, вероятно, лучше.