Dynamic Allocation in Game Programming

Container Classes

For example, std::vector.

Obviously this is limited by available process memory, but on most PCs that will be a LOT of data.

Common approach would be to use a std::vector of pointers to your entities. You need to delete them when you are done though:



You might like to look into boost::ptr_vector instead.

Oh wow, that was actually not as difficult as I was thinking it would be. Having just used vectors, it especially makes sense to me. Thanks you guys for the info.... and the brain fodder ;]

std::vector is nice enough for simple uses, but be aware that it's not a silver bullet. Specific problems you might encounter include the possibility that it will need to reallocate the entire array (and it is a bog standard array underneath) and the fact that doing such a reallocation will invalidate all other references you may have elsewhere in your code to both the vector and to objects contained in the vector.

Reference: http://www.cplusplus.com/reference/stl/vector/push_back/

It's important that you are aware of these before you use it, otherwise you may experience strange behaviour in your program without knowing where it's coming from.

Quote:

Specific problems you might encounter include the possibility that it will need to reallocate the entire array (and it is a bog standard array underneath) and the fact that doing such a reallocation will invalidate all other references you may have elsewhere in your code to both the vector and to objects contained in the vector.

A reallocation will never invalidate references to the vector itself, but pointers or references to the objects contained and iterators will be invalidated. In the case the vector stores pointers, then only pointer-to-pointer or reference-to-pointers will be invalidated, not pointers to the objects themselves (the vector will not and cannot move the pointed-to objects).

While it is good advice to keep in mind, I'd hardly say that this disqualifies vector from non "simple uses". It practically is a silver bullet, once you understand how to use it correctly. A great number of bugs and performance issues are solved by using a Standard C++ Library container rather than some hand rolled alternative.

Quote:

It's important that you are aware of these before you use it, otherwise you may experience strange behaviour in your program without knowing where it's coming from.

Good advice: read the documentation before doing non-trivial things. Somewhere beginners frequently mess up is modifying the vector structurally while iterating over it. Naive loops to remove elements are often written in a way that will cause iterators to become invalid, as well as running in O(n²). Research the remove/erase idiom for the right way to do this.

@OP You might find these videos on the Standard C++ Library helpful:

• Part 1
  


• Part 2
  


• Part 3
  

(if you don't want to install silverlight there is a button to download it in a normal video format towards the bottom right).

If your game needs to store a number of units that are routinely being killed off and respawned, and you need to maintain pointers/references to these objects, then std::list is your best bet. Pointers/references to objects in a list are only invalidated when the object itself is erased. And objects can be removed from and inserted into the list in O(1). Lists are only preferable in certain cases though. They lack random access, have a per-element space overhead and require dynamic allocation on every operation, which can be a serious bottleneck in a tight loop. Unless there are specific reasons not to, use vector as your general container of choice.

Thank you all very much for your posts and help. I will definitely be writing some code and experimenting with vectors and lists once I've finished this chapter on pointers and completed all of the exercise problems. I understand that, using vectors, you can create a virtually endless number of spawned beings with the push_back function. Of course, there are a million things I want to try out, and chances are high that I won't have a solid grasp on any of them until I actually sit down and code through all of them and learn from my mistakes. :] And I will definitely learn more about the Standard Library.... that's another couple of chapters in this book, as well as the subject of a couple of other books I have. Thanks again for all your guys' help.... hopefully soon I'll actually have some code samples and experiments to show and need some help for :p

Another alternative I like, and this is Windows only but I'm certain there are equivalents on other platforms, is to use VirtualAlloc to reserve a chunk of memory that's "big enough", commit memory from that chunk as required, and cast it as a (type **) of whichever type I'm interested in. You can nicely wrap this in a class that does all the heavy lifting for you, and the beauty is that if it needs to expand it can do so in the same consecutive memory region without having to move other references around. Remember I said "big enough" - how big is that? It depends on how many of each object type you want it to store. 1 MB can hold 256k pointers (assuming 32-bit) so I work around that.

I also keep a "scratch buffer" of about 1 MB handy for any time I need to quickly build a list of things and use it immediately. A very very useful thing to have.

Quote:

Original post by mhagain Another alternative I like, and this is Windows only but I'm certain there are equivalents on other platforms, is to use VirtualAlloc to reserve a chunk of memory that's "big enough", commit memory from that chunk as required, and cast it as a (type **) of whichever type I'm interested in. You can nicely wrap this in a class that does all the heavy lifting for you, and the beauty is that if it needs to expand it can do so in the same consecutive memory region without having to move other references around. Remember I said "big enough" - how big is that? It depends on how many of each object type you want it to store. 1 MB can hold 256k pointers (assuming 32-bit) so I work around that. I also keep a "scratch buffer" of about 1 MB handy for any time I need to quickly build a list of things and use it immediately. A very very useful thing to have.

Don't forget vector::reserve() and resize(), boost::pool, and so on. (I just mention these because it sounds like you're doing some things manually and without type safety that could maybe be automated and/or made portable and type-safe. Not saying these solutions would be better necessarily, but just mentioning them as an option.)

Quote:

Original post by mhagain Another alternative I like, and this is Windows only but I'm certain there are equivalents on other platforms, is to use VirtualAlloc to reserve a chunk of memory that's "big enough", commit memory from that chunk as required, and cast it as a (type **) of whichever type I'm interested in. You can nicely wrap this in a class that does all the heavy lifting for you, and the beauty is that if it needs to expand it can do so in the same consecutive memory region without having to move other references around. Remember I said "big enough" - how big is that? It depends on how many of each object type you want it to store. 1 MB can hold 256k pointers (assuming 32-bit) so I work around that. I also keep a "scratch buffer" of about 1 MB handy for any time I need to quickly build a list of things and use it immediately. A very very useful thing to have.

In addition to jyk's comment, bear in mind that an implementation of the standard library written for a computer running Windows is likely using the API memory allocation functions (or whatever functions the API calls) to allocate and release memory.

You are probably reinventing a wheel that is less round than the one you already have. [smile]

Quote:

Original post by jyk Quote: Original post by mhagain Another alternative I like, and this is Windows only but I'm certain there are equivalents on other platforms, is to use VirtualAlloc to reserve a chunk of memory that's "big enough", commit memory from that chunk as required, and cast it as a (type **) of whichever type I'm interested in. You can nicely wrap this in a class that does all the heavy lifting for you, and the beauty is that if it needs to expand it can do so in the same consecutive memory region without having to move other references around. Remember I said "big enough" - how big is that? It depends on how many of each object type you want it to store. 1 MB can hold 256k pointers (assuming 32-bit) so I work around that. I also keep a "scratch buffer" of about 1 MB handy for any time I need to quickly build a list of things and use it immediately. A very very useful thing to have. Don't forget vector::reserve() and resize(), boost::pool, and so on. (I just mention these because it sounds like you're doing some things manually and without type safety that could maybe be automated and/or made portable and type-safe. Not saying these solutions would be better necessarily, but just mentioning them as an option.)

All viable alternatives. :)

Sometimes the more hands-on stuff is needed if you're using plain C, other times you may want a degree of finer control, but that's up to your own needs, and if the stl or boost stuff is good enough for what you're doing, then it's good enough.

Quote:

Original post by Aardvajk Common approach would be to use a std::vector of pointers to your entities. You need to delete them when you are done though: *** Source Snippet Removed *** You might like to look into boost::ptr_vector instead.

I would definitely not recommend anything boost related given the OP's apparent experience with C++.

Quote:

Original post by AardvajkIn addition to jyk's comment, bear in mind that an implementation of the standard library written for a computer running Windows is likely using the API memory allocation functions (or whatever functions the API calls) to allocate and release memory. You are probably reinventing a wheel that is less round than the one you already have. [smile]

Depends. The API HeapCreate/HeapAlloc/etc, for example, (which underlies malloc on Windows), lets you create and destroy multiple independent heaps on the fly and as you require. Need a chunk of unbounded memory for your particles, and need to be able to destory everything in that chunk at any arbitrary point and without affecting any other allocation? HeapCreate/HeapAlloc/HeapDestroy are your friends. If you need that kind of functionality then there's no harm in using them (and certainly less harm than in wrapping malloc or another allocator with the same kind of functionality). Also very handy if you're using C and don't have access to STL.