Search code examples
c++stlparticle-system

What kind of container is appropriate for a "The Powder Toy" style sandbox?

Basically I am making a game similar to The Powder Toy. The world can have a maximum of 256,000 particles in one given frame. In my old Javascript implementation, I looped through every pixel and it caused severe lag because 256,000 is a lot to go through even when you only have around 20,000 particles active. I decided to have a container full of all the currently active particles instead, but then ran into the problem that querying a container for particles at a specific coordinate is also processor intensive. Therefore I came up at the simple solution that I should keep all particles in a lookup table (2-dimensional array) and also have a heap (array of active particles), and iterate through the heap while using the lookup table as a reference. Anything done to the heap is done to the lookup table, and vice versa. This worked very well in Javascript but now as I need to port my program to C++ I am having trouble with finding a good container to hold the heap. Vectors are very slow to add and remove and I cannot remove easily an object by reference from a vector.

Which container should I use, and if there is a better way to handle particles like those in The Powder Toy, what is it? Thanks in advance, and here is a picture for those not familiar with The Powder Toy.

enter image description here

Notice how each pixel there is a particle, and similar builds run extremely fast on my computer. I wonder how they do it...

Solution

  • Vectors are fine for this kind of problem. They provide contiguous storage, so they allow better usage of cache.

    Try to allocate a proper vector capacity beforehand, either via constructor or using std::vector::reserve(). Without this, automatic reallocation of the allocated storage space will be triggered every time your vector's size exceeds the current capacity.

    You can also try removing elements from a vector using std::swap() and then std::vector::pop_back(), like this: 

    std::swap(vect.back(), vect[1]);
vect.pop_back();

    instead of: 

    std::vector::erase()

    The complexity of both std::vector::pop_back() and std::swap() is constant, and the complexity of std::vector::erase() is linear.

    However if you need to preserve the order of elements, the swap - pop method is of no use.