Box2D: How can I speed up a physics simulation with many, many overlapping box bodies?

Question

I'm new to physics libraries and am trying to use Box2D to help implement the procedure described in this article: http://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php

(Edit for clarification:) The algorithm involves rectangular bodies of random dimensions being created in a random point in a circle. They are meant to intersect initially and have those intersections resolved by the simulation, so as to evenly distribute the bodies.

I've managed to get the algorithm working but it runs extremely slowly. Even with only sixty bodies to distribute, it takes over thirty seconds for all intersections to be solved and the bodies to return to sleep. For 120 bodies, it takes well over three minutes, which is horrendously slow.

The simulation progresses quickly when many bodies are overlapping, but slows down dramatically as the area becomes increasingly crowded with bodies. I suppose each body must have more work to do, in an abstract sense, to push an increasingly large number of bodies and interlocking rows of bodies out of the way.

I've tried making each body 0.00001f units in density (therefore lowering mass?), I've tried increasing the restitution value of each body and lowering the friction and linear damping values, but the simulation runs at about the same speed. Even multiplying the number of time steps, position iterations, and velocity iterations by ten doesn't seem to do anything.

So my question is, how can I tweak the simulation or each body's parameters as to greatly increase the speed at which every intersection will be solved? Accuracy of the simulation is no issue; I am subverting it anyway by rounding the coordinates to the nearest 32 px in the end.

Description of my physics bodies and fixtures:

b2BodyDef roomGenBody;
b2PolygonShape roomGenPolygonShape;
b2FixtureDef roomGenFixture;

roomGenBody.type = b2_dynamicBody;
roomGenBody.fixedRotation = true;
roomGenBody.linearDamping = 0.001f; // Seems to have no effect.
roomGenBody.allowSleep = true;

roomGenFixture.density = 0.00001;
roomGenFixture.restitution = 60.0f; // As far as I understand, more bouncy objects repel each other with greater force?
roomGenFixture.friction = 0.0f;

Concerning the world and running the simulation:

b2Vec2 physicsGravity(0.0f, 0.0f); // No gravity and at no angle.

float32 timeStep = 1.0f / 60.0f;  // Increasing timestep doesn't seem to have a very noticible effect.
int32 velocityIterations = 10; 
int32 positionIterations = 8;

physics->Step(timeStep, velocityIterations, positionIterations);

Attached is an image describing my problem- Orange lines are the boundaries of my boxes, labelled 1-160:

Please let me know if any necessary information is missing. Thanks!

Answer 1

I was able to come up with a quick solution for you. I tested the algorithm and came across your problem. I found that by increasing the position iterations in the world.step() function and reducing the velocity iterations, the collisions resolve much faster. For 140 rooms it took about 5 or 6 seconds to set all of the rooms to sleep. I set "1" for the velocity iterations and "10" for the position iterations. I also set the fixtures restitution to 0. I hope this helps.

Answer 2

Ok, this may not be a bonafied answer, but its some food for thought.

Have you considered using quad trees? In a nutshell, a quad tree is all your data in a container, that gets smart by breaking itself into smaller containers as needed.

How could this be usefull? Well, it sounds like initiall, all your rectangles are colliding, and pushing themselfs out from the center, and repeating over and over. All your rectangling are "testing" each other every time. We can reduce the numbers of tests by breaking your circle into four parts, and every rectangle test every other rectangle in that part of the circle. It saves your machine from doing tons of extra work.

Hope my "answer" helps.