I am developing a little Game with something like particles, where every particle is represented by a box2d Body.

To insert new particles I need to find a place in the b2World where no bodies reside. How can I obtain this?



Depending on the density of the particles this can be a pretty hard problem to solve.

If the density of particles is low you have a good chance that a (semi-random) position is free. And something like this would be viable. (pseudo code of course)

bool placed = false;
Vector2 position = (50,50); // rough indication of where we want to insert the particle
    // Slightly randomize the position so that we try a different position
    // near the intended position every iteration.
    float direction = A random number between 0 and 2*PI;
    float length = A random number between 0 and a chosen maximum displacement
    Vector2 displacement = (sin(direction), cos(direction)) * length;
    Vector2 tryPosition = position + displacement;

    // Iterate over all the bodies already in the simulation.
    // Note that you can get the bounds of a body using its shape list.
    if there are no bodies at tryPosition
        placed = true;
        Add the particle

But be wary, there are a few problems with this algorithm. There is a chance that it will take a long time (or maybe even forever) before a free position is found, and the chances of it taking a very long time increase with the density of particles.

A second solution is more work but is guaranteed to finish.

You divide the world in cells (this is called spatial partitioning). You select a cell where you want to place the new particle. In the image below the cell where we, at first, want to place the new particle is colored blue:

Initial state

As you can see the cell marked blue is occupied by an existing particle (the red circle). So we can't place a new particle here. We mark the cell as occupied and continue to spiral out:

The next step

We continue to spiral out (no randomness here, we just rotate clockwise around the already checked cells) until we find the solution: The solution

As you can see we will always find a place to put the new particle that is as close as possible to the intended space.

Note that since we know which places we have checked the algorithm can in the end even give up telling us there are no free places. So it has a guaranteed runtime of O(maxNumberOfParticles * numberOfCells) before it has placed a new particle or has given up.

Now you have to make a decision on the size of the cell. Too large and you might miss free spaces, too small and finding a solution will take a long time. Another decision you have to make is if you want to cache a list of occupied cells to use in further frames (you will have to update part of it whenever a particle moves) or that just doing this when you spawn a new particle is good enough (in that case you won't even need a list, it's implied that a cell is occupied by the algorithm continuing).

  • 1
    \$\begingroup\$ Just adding something to this solution, you should use AABB queries to get the particles in a specific region: box2d.org/manual.html#_Toc258082976. And also you should start with a large query, and then if something is found, subdivide and search again. \$\endgroup\$ – Rui Campos Sep 9 '12 at 9:52
  • \$\begingroup\$ +1, I didn't know that was built in. You're absolutely right and this should speed up the algorithm considerably. \$\endgroup\$ – Roy T. Sep 9 '12 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.