#### Archived

This topic is now archived and is closed to further replies.

# Breakable objects

This topic is 5093 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I''m working on an algorithm for breakable two dimensional rocks. I''m putting it in here, in math and physics, because I don''t really care about code right now, just the mathematics. Once I have the mathematics, I''ll be able to code it on my own. Now, I have an idea for a simple game, similar to asteroids, but with a slight modification. There is only one asteroid, it is really large, and it has minerals and metals spread throughout it (think like the ol'' plum pudding model of an atom). The player will blast away little chunks of the asteroid in order to get at the valuable stuff. Now, one could piece together the asteroid out of little blocks, and then the game becomes a cross between asteroids and arkanoid (weird...), and that is a consideration, but I would rather not do it quite that way, as it''s not the graphical image I had in mind. What I would rather do is represent the asteroids via vertices, adding new vertices as the asteroid is shot up. In example one, the original asteroid was only a pentagon, 5 vertices. After it was hit, a triangle shape was blown off of it, adding three new vertices, making 8 vertices total. In example two, the ship is firing at a non-normal angle. As a consequence, the "force" of the blast is not as direct, leaving only a smaller whole. Example three is my work so far. Each shot has a "blast triangle". The blast triangle "points" in the direction that the shot is travelling. One vertex of the triangle goes IN the polygon, one connects to the edge of the polygon, and the last is left to outside the polygon (unless the shot came in at a normal angle, in which case there are two vertices on the edge of the polygon). Any suggestions, thoughts, anything?

##### Share on other sites
I actually wrote out a model for this a long, long time ago...

Basically, with the first few hits, the object would crack, not break. It would crack where it was weakest (with a map of the strength of random points in the asteroid). The force would be subtracted from the point that was hit, and a weaker force would be subtracted from each point it hits (according to the distance form the hit point) as it passes through the asteroid. At 0, the point would turn into a crack, connected to the nearest point (within reasonable distance) with a strength of 0. When a strength drops below 0, more points can be spawned and cracked, OR a small fragment can break off.

If two cracks connect, the piece can be broken off and become another asteroid.

That's basically the design I had... it might not immitate real physics, but it's a good approximation without getting into nasty math.

EDIT : The force would be subtracted and projected into the polygon like a triangle.

EDIT : DIAGRAM CLICKY

[edited by - Axiom on February 8, 2004 3:44:03 PM]

##### Share on other sites
capn: ah, but what if you hit a corner?

just a thought, but couldn''t you represent the asteroid as a texture (in system memory, not graphics)? Then, when you fire a shot, you can do some simple 2d pixels tests to find the first point of intersection, and then delete all of the pixels around the blast point. you could then upload the texture to the graphics card (this wouldn''t be too expensive as it only needs to be done on a successful hit).

you could also check to see if all the sounding pixels for the objects inside have been killed. if so, free the objects.

no, i don''t have any maths for you. google "2d bitmap intersection" for some very dandy links.

##### Share on other sites
that looks fine for a simple triangle edge, but what would happen if you started using this algo with an already pretty fragmented asteroid. I''m not sure this would work.

Another solution, tesselate the original asteroid shape, with small perturbation (for each triangle edge, get roughly the midpoint, and interconnect the midpoints, that will split the parent triangle into 4 smaller chunks, and do that recursively). Once you have a decent enough level of detail, stop, and when you fire a shot, do a radius check with the point of collision of the shot and the triangles on the asteroid. detach all triangles included into the blast radius from the main asteroid.

You can also use the tesselation properties (basically, it''s a recursive subdivision), to quickly determine the triangular areas inside a radius. Furthermore, if a large chunk is detached, all you have to do is, in the triangle tree, detach a branch of the tree all together. You can further split the detached chunk the same way.

##### Share on other sites
using the verlet stuff and stiff constraints, you can do something like Axiom said. When a crack appear, remove a segment constraint, and part of the asteroid will come loose, all by itself. Also, the asteroid will react to shots you fire at it. It will start to spin, and move about after it gets hit.

##### Share on other sites

I like the tesselation idea. It is still the "arcanoid" idea, however, it is with a different shape of block.

so, each mini-triangle would be a node in a sort of binary tree? hmm, I think I can see it.

So, if a bullet hit #9, it would destroy #9 and sever #8's and #15's connections, leaving them to float free.

edit1: Hmm, I grew that from the top down, 1 through 16, when I think it would be better to grow it from the center out, creating a hexagon. Then, each triangle would look up its linkages to find out where it is supposed to move, with the #1 node being the root/master.

edit2: I think hexagons would be better than triangles, as then I won't have to worry about which way is "up" or "down" for the triangle.

[edited by - capn_midnight on February 8, 2004 4:03:24 PM]

[edited by - capn_midnight on February 8, 2004 4:05:27 PM]

##### Share on other sites
actually yeah, you can tesselate each polygon any way you want, use quads instead of triangles, as long as the shape retain a nice aspect ratio (don''t squish them to much, as the subdivision will make it even worse). The advantage is, you can keep the LODs in a tree structure, and remove whole parts of the asteroid by simply removing a branch in the tree. If you use quads, You can remove a quarter of the tree by removing one of the root subdivisions all together, and attach it as a root to another asteroid. For collision detection, it''s also beneficial, as you just have to trasverse the tree from lowest LOD to finest LOD.

##### Share on other sites
quote:
Original post by oliii
actually yeah, you can tesselate each polygon any way you want, use quads instead of triangles, as long as the shape retain a nice aspect ratio (don''t squish them to much, as the subdivision will make it even worse). The advantage is, you can keep the LODs in a tree structure, and remove whole parts of the asteroid by simply removing a branch in the tree. If you use quads, You can remove a quarter of the tree by removing one of the root subdivisions all together, and attach it as a root to another asteroid. For collision detection, it''s also beneficial, as you just have to trasverse the tree from lowest LOD to finest LOD.

...yeah... I think that''s the ticket... wild stuff, thanks guys. We''ll see how this goes.

##### Share on other sites
Haven''t read all through, may have been suggested... have blocks but not regular shapes. Have predetermined ''fault-lines'' which allow bits to break off in a seemingly random way. The details are up to you but it seems reasonable, what do you think?

##### Share on other sites
Anyone seen any articles on the Red Faction terrain engine?

##### Share on other sites

was looking for Stan Melax''s vox demo, but can''t find it anywhere, so here is a guy who made an equivalent. Vox demo

There are also BSP trees, and doing CSG operations, of course

##### Share on other sites
okay, I didn''t want to search for a hex tessalation fractal algo, I wanted to come up with one on my own. Here is what I have:

#include <cmath>//define constants, extreme precision unnecessary#define PIo3 1.04719#define sqrt3 1.73205void hex(float r, float a, float x, float y){   if(r>5){      float tr = r/sqrt3;      hex(tr, a + PIo3, x, y);      for(int n=0; n<6; ++n){         float ta, tx, ty;         ta = a + n*PIo3;         tx = x + r*cos(ta);         ty = y + r*sin(ta);         hex(tr, ta, tx, ty);      }   }   else{      //pseudocode      pushPolyStack(createHexPoly(r, a, x, y));   }      }

##### Share on other sites
who knows, by the time I''m done with this, I might have an article in the making.

##### Share on other sites
Check out James O''brien''s paper on Brittle Fracture.

http://www.cs.berkeley.edu/~job/Papers/

It really is exactly what you want to do. His work is true 3D but 2D is much easier. Start with your base shape and then tesselate it into finite elements using something like constrained Delaunay triangulation. Then use a strain formula to calculate the strain forces at each of the connecting nodes. If the strain exceeds some threshold you set, a fracture has occurred.

It ends up being sort of a mass and spring mesh system where the stretch is the strain on the element. Since everyone here is so into the rod-constraint stuff, a simple 2D tinkertoy demo using the Jakobsen style contraints could be made to work in this way very easy.

Then you can either do it the fast and easy way or the hard and more accurate way. Fast is just allow the object to split along the tesselated edges of your object. The crack will follow the path but if you tesselate enough and in a sort of non-regular way, it will be fine.

The "right" thing to do is calculate how the crack would go through the object and then remesh. The paper covers that in detail.

I also did a talk with James on these issues at GDC last year so can go into more particulars if you find the papers confusing.