Box2D Forums

Hi,

I thought I'd ask about this before trying to implement anything, since trying to implement it is maybe quite a lot of work, and I don't know if the results will be efficient enough to be workable anyway... So the responses to this question are likely to influence how my game design comes together.

I want destructable/deformable terrain in my game. The simplest (but least fun and flexible) interpretation of this would be certain static bodies which are flagged with properties in such a way that certain things in the game can destroy them (either by shattering them into smaller bodies or removing them entirely), and certain dynamic bodies could become permanent static fixtures in the level under some circumstances. The more advanced (and perhaps preferable in terms of gameplay) option would be to try to implement a fully deformable environment along the lines of Worms or Lemmings, where pretty much anything can be destroyed or rebuilt on a per-pixel basis, except for certain parts that are flagged as indestructable.

If I were to go about a per-pixel (or per-some-suitably-small-voxel) deformable environment, I guess I'd track it using a texture in the alpha channel of a texture representing the level: Stuff which destroys the environment writes 0 into voxels in the alpha channel of a texture, and stuff which creates bits of environment writes 1. The deformation/creation effects could be implemented quite easily, and the rendering would be pretty straightforward too. I'm not sure how it would translate into collision geometry which Box2D could use, though. Turning each voxel into the texture into a correspondingly-sized static square body would work, but would be pretty inefficient. I guess my approach would be that every time a change was made to the environment, I'd recalculate some kind of quadtree in order to destroy and remake sections of the static geometry to match the texture in such a way that hopefully minimises the number of bodies needed to represent the world.

Does the Lemmings/Worms style deformable terrain sound feasible in Box2D? Is the Quadtree the best approach? As well as the static level geometry, I'm hoping to be able to throw around a reasonable number of dynamic objects as well, so efficient use of the engine is pretty important to me (this is the C++ version, incidentally). Or am I best going back to the drawing board and having most of the environment indestructable, with only specific bodies which can be destroyed?

My naive approach would be to tessellate the ground-body where an explosion took place into large chunks, find the specific large-chunk that got hit, explode that into tiny bodies, and then perhaps recombine the large remaining bodies. I have no idea how expensive that might be to do on a regular basis...but it doesn't sound too bad.. unless you have many collisions every frame.

I don't know how you might combine a pixel-based model with Box2D...the only thing I can think of is to trace (roughly) along the border of the pixels, and turn that into a single large Box2D body... and then when an explosion takes place, remove some pixels, and retrace. That sounds very expensive though...you're better off writing your own physics for that I think. I did a few years back....wasn't too bad.

Anyway..that's my 1 cent (I'm not sure it's worth 2).

I really don't think box2d is meant to handle hundreds of tiny shapes in a body. Even if it would work (which it should) it would be highly ineffcient. You might try something based on convex decomposition (there are many topics on these boards about it), which I think is more realistic because it makes smooth surfaces rather than pixelated ones. No guarantees on how well this would work though. But I'm writing a game which will be a space shooter that has dynamic terrain in the form of free-floating asteroids and something that you could call "conservation of mass/area" in which breakages generate sub-shapes that "fit" (small ones naturally become particles and/or effects, and large pieces are free to be re-broken). I've got the code working, so it's not impossible. I wouldn't attempt such a thing in something like AS3 though (too slow).

I would also advise convex decomposition. There is a lot of evidence of this forum that it is very feasible for destructible terrain, and somewhere there was a very good C++ convex decomposer. This approach also makes very nice bits for explosion purposes, and can do the calculations for what shatters on an explosion in a more physically interesting way (rather than leaving a perfect circle of destruction, e.g.)

I don't think pixel type stuff is impossible, just that you would have to work at getting it right, and it's not clear how fast/good the final result would be. I would not attempt to represent it using a collection of Box2D shapes, even with a quadtree, as it's gonna be a lotta shapes no matter how you cut it.
Instead, I'd implement a custom shape type, and then report to Box2D collisions between the terrain and each shape using your own code (using a quadtree here, preferably). Remember that most of the games you've seen with pixel destructible terrain fake collision with it, as they are just platformers. That faking could work for you, too.

I've had a hunt around the forums and found a few things that look interesting...

dc443's sandbox (http://www.box2d.org/forum/viewtopic.php?f=6&t=975) which is very cool but (unless I'm mistaken) was just a test for dc443's game, so doesn't come with source. I do like the way it lets you draw shapes and then break them though.

Nimodo's testbed sample (viewtopic.php?f=3&t=836) which does the breakable thing with joints and has a constrained Delaunay Triangulator, which is something I'm very rusty on the details of but believe it to be quite a nifty way of breaking up shapes into usable polygons. The breakable joints look like they might be a bit flimsy for the purposes of simulation something that looks like solid but destructable terrain, but perhaps that could be tweaked.

ewjordan's thing here (viewtopic.php?f=4&t=83), which I'll admit had me completely confused in the thread but looks like it might perform some kind of preprocessing step to generate usable geometry, which could presumably then be made to be breakable at runtime.

I'm not sure which (if any) of these were the kind of thing you're talking about, but I kinda understand from looking at them the kind of thing you mean by convex decomposition, and what it can do - although I haven't looked up how the algorithms actually work in any great depth.

So, what I'm currently thinking about is constructing a level where the static geometry is formed from a number of relatively large polygon shapes, and when something happens that could damage the terrain, find out which shapes would be affected, and perhaps carve them up into a number of smaller ones, some of which can be made dynamic (i.e the debris chunks which are blown out of the terrain - possibly these would just be used for cool visual effects and could be removed from the simulation entirely after a short time), and some of which might remain static so that the visual effect isn't one of a big triangular hole. Am I thinking along the right lines now, or am I still way out?

Sounds good.

BTW I think nimodo's work is deliberately flimsy, to be deformable. It could be potentially pretty rigid, though not as much as a single shape.

the entirety of my convex decomposition code is available on my sourceforge project, but it's really not that clean and could take a decent amount of work to port it.

That's what I was suggesting :p Except leaving in a few small pieces is a good idea... didn't think of that. Long as the other dynamic pieces don't get stuck on em.

This is exactly what I am using right now with the exception that my breakable bodies are not static bodies. it's very doable. c++ code for it is rather nasty. But it's definitely doable.

I also am working on a game with deformable terrain. I looked at the contrained tessellator but it couldn't do what I needed. Holes where possible but not that intersected with the edge, ie removing just a chuck. I was going for a worms style deformable terrain.

My solution was to use the GLU tessellator. Here is what I did.

-query box2d for shapes in the blast radius
-feed shapes into tessellator with positive winding.
-delete the shapes.
-feed the blast as a negative outline.
-throw away degenerate triangles ( the GLU tessellator may return a triangle where all points are on a line )
-merge points that are too close to each other.
-merge triangles into convex polygons (this is tricky i'll explain if there is interest).
-throw away polygons that are too narrow ( p^2/a < 25. p is perimeter, a is area. 25 is the number i found that catches really long narrow triangles, you'll have to tune that by hand for your particular case.)
-add new shapes for these polygons.

This also works for adding a shape to terrain( AKA scorched earth dirt bomb ). Just feed in the blast shape with positive winding.

You can also configure GLU to give you the difference. A tessellation of the terrain about to be removed. Breaking those triangles into meaningful pieces is really hard. X-Men 2, the glass Magneto shatters in his escape. The cracks were predetermined by an artist. They tried to do it procedurally but it never looked natural. It might be easier to fudge.