Managing many objects at once.

Question

Hi, I want to find a way to efficiently keep track of a lot of objects at once. One practical example I can think of would be a particle system. How are hundreds of particles kept track of? I think I'm on the right track, I found the term 'instancing' and I also learned about flyweights. Hopefully somebody can shed some light on this and share some techniques with me. Thanks.

Answer 1

How to keep track of the objects depends very much on what you want to do with them. Do you need to quickly access some particle known by index? Then use a vector. Are your particles somehow mapped by names? Then you can use a map. And so on, and so forth.

"Hundreds" of objects is certainly not something you should worry about with C++, unless you choose a particularly bad data structure. Why are you concerned? Do you think you'll waste too much memory? Or perhaps have a slow running time? In any case, you must describe exactly the objects involved and the operations required of them, and then select an appropriate data structure.

Answer 2

You can't process them without looping through them.

A container class may well have an issue with locality (cache performance). You might consider using a custom allocator, but of course there are other ways.

The fastest data structure to loop through is an array or vector with the data actually in the vector - not pointed to. Obviously this breaks down with in cases where flyweight is appropriate, where there's a lot of pointers in the container, but only a small number of pointed-to objects - but there must be unique characteristics along with the pointer to the shared characteristics anyway (no point having a thousand particles all at the same position and moving the same direction).

For updating the shared characteristics, you just iterate through that container instead.

One issue is efficient deleting from the middle of the vector of pointers and unique details. Swap or copy the top item into that space, then delete the top item, instead.

With the shared data, don't do that - first it means updating the references, second with enough shared data the copying is an excessive overhead, and third the cache is an issue whatever you do anyway since most accesses are random order (you iterate through the pointers in order, not the objects they point to). Just keep a free list, so you can find the gaps easily to put new items in them. You'll probably be using that link to list the valid items to, so you can iterate through them easily. You may even have an extra link or two so you can have lists that are limited to particular items - there's no reason why each item shouldn't appear in more than one list.

EDIT - I'm basically talking about intrusive linked lists here. Linked list code is very simple, but you could make use of the Boost intrusive container library.

Finally, you may find all this only really becomes necessary with tens of thousands of objects, depending on your performance constraints.

EDIT - on tiles.

The obvious approach to tiles is a big two-dimensional array. It's pretty easy to iterate over a clipped area of such an array row-by-row. However, with tile-based rendering, there's a good chance you want to draw all tiles of a particular type at once, then all of the next type, and so on, where the type determines the texture needed to render them.

I'd say use a draw list for each tile type. Rebuild your draw-lists from scratch on each update - that's only one scan of the tile map. Then it's easy to process/render the tiles one type at a time. You could do incremental updates of the draw-lists, but it's probably unnecessary. Again, you'll probably keep the draw lists in arrays rather than linked lists.

Answer 3

You can keep track of many objects the same way you would keep track of many anythings.

If you want to "track" them by a name or named property, use a hash table.

If you want to "track" them in order of some property, then use a sorted array or tree (binary or multi-way).

If you want to simply iterate through them, then use an array or linked list.

If you need to several of the above, then you can use multiple methods.

Answer 4

On the site GameProgrammingPatterns, take a look at the Object Pool pattern. It's extremely well written.

From the article:
Improve performance and memory use by reusing objects from a fixed pool instead of allocating and freeing them individually.