Simple efficiency question C++ (memory allocation)..and maybe some collision detection help?

Question

I'm writing a little arcade-like game in C++ (a multidirectional 2d space shooter) and I'm finishing up the collision detection part.

Here's how I organized it (I just made it up so it might be a shitty system):

Every ship is composed of circular components - the amount of components in each ship is sort of arbitrary (more components, more CPU cycles). I have a maxComponent distance which I calculate upon creation of the ship which is basically the longest line I can draw from the center of the ship to the edge of the furthest component. I keep track of stuff onscreen and use this maxComponentDistance to see if they're even close enough to be colliding.

If they are in close proximity I start checking to see if the components of different ships intersect. Here is where my efficiency question comes in.

I have a (x,y) locations of the component relative to the ship's center, but it doesn't account for how the ship is currently rotated. I keep them relative because I don't want to have to recalculate components every single time the ship moves. So I have a little formula for the rotation calculation and I return a 2d-vector corresponding to rotation-considerate position relative to the ships center.

The collision detection is in the GameEngine and it uses the 2d-vector. My question is about the return types. Should I just create and return a 2d-vector object everytime that function is called or should I give that component object an additional private 2d-vector variable, edit the private variable when the function is called, and return a pointer to that object?

I'm not sure about the efficiency of memory allocation vs having a permanent, editable, private variable. I know that memory would also have to be allocated for the private variable, but not every time it was checked for collisions, only when a new component was created. Components are not constant in my environment as they are deleted when the ship is destroyed.

That's my main dilemma. I would also appreciate any pointers with the design of my actual collision detection system. It's my first time giving a hack at it (maybe should have read up a bit)

Thanks in advance.

Answer 1

You should absolutely try to avoid doing memory allocations for your component-vector on each call to the getter-function. Do the allocation as seldom as possible, instead. For instance, you could do it when the component composition of the ship changes, or even more seldom (by over-allocating).

You could of course also investigate memory pools, where you pre-allocate lots of such components and put in a pool, so you can allocate a new component in constant time.

As a general (and apologies if it's too obvious) point when doing this kind of collision-detection: square the distances, rather than computing the square roots. :)

Answer 2

1. You can start by just returning a vector, and benchmark it. Who knows, it could be fast enough. With a profiler you can even see what part takes the run time.
2. You can use a Memory Pool to reuse vectors and reduce copying
3. You can try the Flyweight pattern for the coordinates to reduce copying and allocating, if they repeat throughout the engine.
4. Keeping the data in the component is a good way to reduce allocations, but introduces some gotchas into your design, like that whoever uses the vector depends on the lifecycle of the component. A memory pool is probably better.

Answer 3

Do not use a 2D vector. Rather, use a vector of points. Likewise for your collision detection. Using a 2D vector here is just the wrong data structure.

Depending on the content of the function, the compiler will be able to perform NRVO (that is, named return value optimization) which means that in the optimal case, returning a vector has no overhead, i.e. it's never copied. However, this only happens when you use the return value of your function to initialize a new instance, and when the compiler is able to trace the execution paths inside the function and see that for each return path, the same object is returned. Consider the following two:

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>();
}

The compiler can perform NRVO for calls to f, but not for g.

Answer 4

If your 2D vector is just:

 class Vector2D { double x, y; };

Then by all means return it! E.g:

  Vector2D function( ... );

Or pass by reference:

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

Avoid at all costs:

 vector<double> function(...);

The constant heap allocation/deallocation inherent to the Vector class is a mistake!

---

Copying your own Vector2D class is very cheap, computationally speaking. Unlike Vector<>, your own Vector2D class can incorporate whatever methods you like.

I've used this feature in the past to incorporate methods such as distanceToOtherPointSquared(), scanfFromCommandLineArguments(), printfNicelyFormatted(), and operator[](int).

---

or should I give that component object an additional private 2d-vector variable, edit the private variable when the function is called, and return a pointer to that object?

Watch out for multiple function calls invalidating previous data. That's a recipe for disaster!

Answer 5

There's a big difference between allocating memory on the heap and on the stack. Allocating on the heap, e.g., using new/delete or malloc/free is very slow. Allocating on the stack is really quite fast. With the stack, usually the slow part is copying your object. So watch out for vector and such, but returning simple structures is probably OK.