Simple C ++ efficiency question (memory allocation) .. and maybe help for finding conflicts?
I am writing a small arcade game in C ++ (multi-directional 2D space shooter) and I am finishing up the collision detection part.
This is how I organized it (I just did it to make it a crappy system):
Each ship is made up of circular components - the number of components on each ship is arbitrary (more components, more CPU cycles). I have a maxComponent distance that I calculate when I create the ship, which is basically the longest line I can draw from the center of the ship to the edge of the farthest component. I keep track of the material on screen and use this maxComponentDistance to make sure they are even close enough to collide.
If they are in close proximity, I start checking if the components of different ships overlap. This is where my efficiency question comes in.
I have the (x, y) position of the component relative to the center of the ship, but it doesn't account for how the ship is currently spinning. I consider them relative because I don't want to recalculate the components every time the ship moves. So I have a little formula for calculating rotation and I return a 2d vector corresponding to the rotational position relative to the center of the ships.
The collision detection is in GameEngine and uses a 2d vector. My question is about return types. Should I just create and return a 2d-vector object every time this function is called or should I provide this component object with 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 and has a persistent, editable, private variable. I know that memory should also be allocated for the private variable, but not every time it was checked for collisions, only when a new component was created. The components are not permanent in my environment as they are removed when the ship is destroyed.
This is my main dilemma. I would also appreciate any pointers with the design of my actual collision detection system. This is my first time giving hack it (maybe should have read a little)
Thanks in advance.
source to share
You should absolutely try to avoid allocating memory for your vector component every time you call the getter function. Instead, distribute it as sparingly as possible. For example, you could do this when the composition of a ship component changes, or even less frequently (by over-highlighting).
You can, of course, also explore memory pools where you pre-allocate a lot of such components and put in a pool so that you can allocate a new component at a constant time.
As a general (and apologetic if it's too obvious), when you do this collision detection: the square of the distances, not the calculation of square roots. :)
source to share
If your 2D vector is fair:
class Vector2D { double x, y; };
Then, by all means, return it! For example:
Vector2D function( ... );
Or follow the link:
void function( Vector2D * theReturnedVector2D, ... );
Avoid at all costs:
vector<double> function(...);
The constant heap allocation / deallocation inherent in the Vector class is a bug!
Copying your own Vector2D class is computationally very cheap. Unlike Vector <, your own Vector2D class can include whatever methods you like.
I've used this feature in the past to include methods such as distanceToOtherPointSquared (), scanfFromCommandLineArguments (), printfNicelyFormatted (), and operator [] (int).
or should I provide this component object with an additional private variable of the 2d vector, edit the private variable when the function is called, and return a pointer to that object?
Make sure that multiple functions call invalid previous data. This is a recipe for disaster!
source to share
- You can start by simply returning a vector and compare it. Who knows, it might be fast enough. With a profiler, you can even see how much the runtime is taking.
- You can use Memory Pool to reuse vectors and reduce copying
- You can try Flyweight pattern for coordinates to reduce copying and distribution if they are repeated throughout the engine.
- Storing the data in a component is a good way to reduce the selection, but it introduces some finishing touches to your design, for example whoever uses the vector depends on the component's lifecycle. Perhaps the memory pool is better.
source to share
Don't use a 2D vector. Rather, use vector
of point
s. Likewise for 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 an NRVO (i.e. named return value optimization ), which means that in the optimal case, returning a vector has no overhead, i.e. it is 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 keep track of the execution paths within the function and see that the same object is returned for each return path. 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 on calls f
, but not on g
.
source to share
There is a big difference between memory allocation on the heap and on the stack. Heap allocations, such as using new / delete or malloc / free, are very slow. Allocation on the stack is pretty fast. With a stack, usually the slower part is copying your object. So watch out for the vector and so on, but returning simple structures is probably ok.
source to share