2
\$\begingroup\$

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:

enter image description here

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

\$\endgroup\$
  • \$\begingroup\$ Could you describe a bit more what you're trying to do? Are you generating a bunch of boxes that intersect each other, start a physics simulation and wait until they no longer intersect? \$\endgroup\$ – Alexandre Vaillancourt Aug 18 '16 at 12:13
  • \$\begingroup\$ Yes, I've generated a number of box bodies of random dimensions (rounded to the nearest multiple of the tilesize) and random position inside a circle of radius 5*tilesize. It is intended that they intersect each other initially. The simulation is run until the bodies no longer intersect. \$\endgroup\$ – Itolet Aug 18 '16 at 12:18
  • \$\begingroup\$ That's interesting. I'm not familiar with box2d; I would have suggested to increase the restitution and the timestep, a lot! You might want to consider the number of iterations (steps) as well as the time it takes. \$\endgroup\$ – Alexandre Vaillancourt Aug 18 '16 at 12:35
  • \$\begingroup\$ I've tried tweaking the restitution, linear damping and density of bodies, timesteps, interations per step, and all other parameters. I can't seem to come up with any combination of values that will solve the problem of the middle bodies being pressed-in. \$\endgroup\$ – Itolet Aug 18 '16 at 15:08
  • \$\begingroup\$ Maybe box2d is not what you need for this job. Perhaps if you rolled your own it would be faster as you'd use much less parameters? \$\endgroup\$ – Alexandre Vaillancourt Aug 18 '16 at 17:28
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. The simulation does seem to complete somewhat faster, but is still taking around 50+ seconds for me. I am starting to suspect the problem being the physical size of my objects. My box objects are about 32*5 x 32*5 pixels in dimensions on average. Maybe they would resolve faster if I used bodies 1/4th the length and width? May I ask what size your objects were? May I also ask how long one time step was in your simulation? \$\endgroup\$ – Itolet Aug 18 '16 at 19:40
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I see what you're saying, but my problem is with the accumulation of physics bodies being physically "heavy" so to speak, and thus hard to move around rather than the simulation being computationally slow (though I'm sure it could be). This does give me the idea to sub-divide each body into four parts, though... Hmmm... \$\endgroup\$ – Itolet Aug 18 '16 at 19:47

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.