Like said in the title, in this article we will focus on something various games use as a side or core gameplay mechanism, destructible terrain. As a matter of fact, it is not difficult to implement, depending of course of your environment structure and in-game environment storage. Some games that have Polygon based terrains might want some parts to be destructible by let's say bombs or bullets. We will focus on this type of terrains, based on Polygon shapes in the box2d/libgdx context.
The algorithm, and implementation.
The algorithm we will be using is described in the article "Efficient Clipping of Arbitrary Polygons" by Günther Greiner and Kai Hormann.
(full article available here). I recommend reading it to understand the full detail ;).
Before implementing this solution on my own, I checked if there wasn't one available on Github, and stubled upon the implementation of Helder Correia
(Great thanks to him ! You can find his latests news on his website http://heldercorreia.com/).
You can find his implementation here.
In general, I prefer creating my own implementation, but this one was very well done, and way cleaner that the one I could have done with the time I had.
Here is a link to the class we will be needing for our polygon clipping mechanism Polygon.java
You can even just include it in your project, as its dependence free.
In order to use it in a box2d/libgdx environment, we need to wrap it into a class to links the general implentation to environment specific polygons.
Here is the class I'm talking about.
import java.util.ArrayList;
import java.util.List;
import com.badlogic.gdx.math.Vector2;
import com.badlogic.gdx.physics.box2d.ChainShape;
import com.badlogic.gdx.physics.box2d.PolygonShape;
import com.badlogic.gdx.physics.box2d.Shape;
import com.quailsHillStudio.Utils.CollisionGeometry;
public class PolygonBox2DShape extends Polygon{
Vector2 circPos = new Vector2();
float circRadius = 0;
public PolygonBox2DShape(float[] verts) {
for (int i = 0; i < verts.length; i+=0) {
add(new Vertex(verts[i++], verts[i++]));
}
}
public PolygonBox2DShape(Shape shape){
if(shape instanceof ChainShape) this.ConstPolygonBox2DShape((ChainShape)shape);
else if (shape instanceof PolygonShape) this.ConstPolygonBox2DShape((PolygonShape) shape);
}
public void ConstPolygonBox2DShape(ChainShape shape){
float[] verts = null;
if(shape.isLooped()){
verts = new float[shape.getVertexCount()*2 - 2];
for(int i = 0, j = 0; i < shape.getVertexCount() - 1; i++){
Vector2 vect = new Vector2();
shape.getVertex(i, vect);
verts[j++] = vect.x;
verts[j++] = vect.y;
}
}else{
verts = new float[shape.getVertexCount()*2];
for(int i = 0, j = 0; i < shape.getVertexCount(); i++){
Vector2 vect = new Vector2();
shape.getVertex(i, vect);
verts[j++] = vect.x;
verts[j++] = vect.y;
}
}
if((verts.length%2) == 1){
for (int i = 0; i < verts.length; i+=0) {
add(new Vertex(verts[i++], verts[i++]));
}
}
public void ConstPolygonBox2DShape(PolygonShape shape){
float[] verts = new float[shape.getVertexCount()*2];
for(int i = 0, j = 0; i < shape.getVertexCount(); i++){
Vector2 vect = new Vector2();
shape.getVertex(i, vect);
verts[j++] = vect.x;
verts[j++] = vect.y;
}
for (int i = 0; i < verts.length; i+=0) {
super.add(new Vertex(verts[i++], verts[i++]));
}
}
public PolygonBox2DShape(float[][] points) {
super(points);
}
/** Return a simple array with the vertices*/
public float[] vertices(){
float[] verts = new float[vertices*2];
Vertex v = first;
for (int i = 0, j = 0; i < vertices; i++) {
verts[j++] = v.x;
verts[j++] = v.y;
v = v.next;
}
return verts;
}
/** Return a simple array with the vertices*/
public float[] verticesToLoop(){
//float[] verts = new float[vertices*2 - 1];
int NbIn = 0;
List<Float> verts = new ArrayList<Float>();
Vertex v = first;
for (int i = 0, j = 0; i < vertices - 1; i++) {
// Here escape the verts that have a square distance > 0.005f * 0.005f to avoid the b2DistanceSquared(v1,v2) > 0.005f * 0.005f expression
if(v.equals(first) || (b2SquaredDistance(verts.get(j-2), verts.get(j-1), v.x, v.y) > (0.25f))){
verts.add(v.x);
j++;
verts.add(v.y);
j++;
}
if(circRadius != 0 && CollisionGeometry.isInCircle(circPos.x, circPos.y, circRadius, v.x, v.y)){NbIn ++;}
v = v.next;
}
float[] vertsTab = null;
if((NbIn == 0 || circRadius == 0) || (NbIn != (vertices -1))){
vertsTab = new float[verts.size()];
for(int i = 0; i < verts.size(); i ++){
vertsTab[i] = verts.get(i).floatValue();
}
}else{
vertsTab = new float[0];
}
return vertsTab;
}
public List<PolygonBox2DShape> unionCS(Polygon poly) {
return this.clipCS(poly, false, false);
}
public List<PolygonBox2DShape> intersectionCS(Polygon poly) {
return this.clipCS(poly, true, true);
}
public List<PolygonBox2DShape> differenceCS(Polygon poly) {
return this.clipCS(poly, false, true);
}
public List<PolygonBox2DShape> clipCS(Polygon poly, boolean b, boolean b2){
List<Polygon> rs = super.clip(poly, b, b2);
List<PolygonBox2DShape> rsCS = new ArrayList<PolygonBox2DShape>();
for(int i = 0; i < rs.size(); i++){
rsCS.add(new PolygonBox2DShape(rs.get(i).points()));
}
return rsCS;
}
public void circleContact(Vector2 vec, float radius){
this.circPos = vec;
this.circRadius = radius;
}
private float b2SquaredDistance(float x1,float y1,float x2,float y2){
Vector2 vec = new Vector2(x1, y1);
return vec.dst2(x2, y2);
}
}
Those two classes will now help us achieve what we want : destructible terrain !
But first, we need to set up the where and when it will get into action !
Life cycle of a game using this implementation.
In order to use this newly wrapped Polygon clipping algorithm, we will have some steps to add to our game.
The first will be to detect when to trigger polygon clipping in word collisions. To do so, we have to define types for our bodies, the one that can be clipped (or destructed) and the one clipping. This can be achieved by adding it to the UserData of a body. In this experiment, a UserData Object is just storing an integer, but remember you can do a lot more !
public class UserData {
public static final int GROUND = 0;
public static final int BOMB = 1;
public static final int BALL = 2;
public int type;
public boolean mustDestroy;
public boolean destroyed;
public UserData(int type) {
this.type = type;
}
public int getType() {
return type;
}
}
As you can see, in our small class, we are defining three constants and story the value in the type attribute for each instance. We added also destruction-related booleans (you have to remember that checking if a body is destroyed before destroying it in box2dworld is VERY important !)
Now that we can differenciate a destructor from a destructible body, we can handle the collision detection between those.
The first step is to create a class that inherits from ContactListener (com.badlogic.gdx.physics.box2d.ContactListener). It should also store a reference to the game screen or applicationListener, where we will need to store an array and a method to create the ground fixtures.
In the postSolve method that we override, we're adding this simple code :
@Override
public void postSolve(Contact contact, ContactImpulse impulse) {
Body a= contact.getFixtureA().getBody();
Body b= contact.getFixtureB().getBody();
UserData dataA = (UserData)a.getUserData();
UserData dataB = (UserData)b.getUserData();
if(dataA instanceof UserData && dataA.getType() == UserData.GROUND && dataB instanceof UserData && dataB.getType() == UserData.BOMB){
clippingGround(a, b, dataA);
}else if(dataB instanceof UserData && dataB.getType() == UserData.GROUND && dataA instanceof UserData && dataA.getType() == UserData.BOMB){
clippingGround(b, a, dataB);
}
}
You might have notice that we call a method called clippingGround()... Well played ! Here's the code of this method hosted in the same class ;)
private void clippingGround(Body a, Body b, UserData dataA) {
List<PolygonBox2DShape> totalRS = new ArrayList<PolygonBox2DShape>();
float[] circVerts = CollisionGeometry.approxCircle(b.getPosition().x, b.getPosition().y, circRadius, segments );
ChainShape shape = new ChainShape();
shape.createLoop(circVerts);
PolygonBox2DShape circlePoly = new PolygonBox2DShape(shape);
Body body = a;
Array<Fixture> fixtureList = body.getFixtureList();
int fixCount = fixtureList.size;
for(int i = 0; i < fixCount; i++){
PolygonBox2DShape polyClip = null;
if(fixtureList.get(i).getShape() instanceof PolygonShape){
polyClip = new PolygonBox2DShape((PolygonShape)fixtureList.get(i).getShape());
}
else if(fixtureList.get(i).getShape() instanceof ChainShape){
polyClip = new PolygonBox2DShape((ChainShape)fixtureList.get(i).getShape());
}
List<PolygonBox2DShape> rs = polyClip.differenceCS(circlePoly);
for(int y = 0; y < rs.size(); y++){
rs.get(y).circleContact(b.getPosition(), circRadius);
totalRS.add(rs.get(y));
}
}
game.switchGround(totalRS);
((UserData)body.getUserData()).mustDestroy = true;
}
You see now why we needed a reference to the game screen (called here game). It host the creation / deletion of ground logic.
Therefore, we will now focus on the elements we need in our game screen, to make destructible terrain work.
As we are in a box2d environment, each body can possess a UserData which could be anything really, as it can store a Java Object.
In addition, we want the ground to be created from multiple arrays of verts. To do so, I decided to encapsulate those arrays in a class called GroundFixture in my code, that stores those arrays in an array, to be able to store in one place all the vertices needed for one body. The operation of creating instances of these groundFixtures and setting the mustCreate boolean attribute is performed in the switchGround method.
public void switchGround(List<PolygonBox2DShape> rs) {
mustCreate = true;
List<float[]> verts = new ArrayList<float[]>();
for (int i = 0; i < rs.size(); i++) {
verts.add(rs.get(i).verticesToLoop());
}
GroundFixture grFix = new GroundFixture(verts);
polyVerts.add(grFix);
}
Setting this boolean to true triggers then two events in the render or act method of our game screen : first, the destruction of ALL the terrain, and then, the creation of a new terrain body using the new vertices we just stored.
Here is the code related to those two operations in the render/act method :
for (int i = 0; i < world.getBodyCount(); i++) {
Array bodies = new Array();
world.getBodies(bodies );
UserData data = ((UserData) bodies.get(i).getUserData());
if (data != null && data.getType() == UserData.GROUND) {
if ((data.mustDestroy || mustCreate) && !data.destroyed) {
world.destroyBody(bodies.get(i));
bodies.removeIndex(i);
}
}
}
if(mustCreate)
createGround();
We are almost there ! We only need to define the last, but not least creatGround method.
Basically what it does, is that it iterate over the array containing vertices the algorithm gave us after clipping, and creating a body and it's fixtures based on them. If you already used box2d, it will be pretty much straight forward operation ;)
protected void createGround() {
BodyDef groundDef = new BodyDef();
groundDef.type = BodyDef.BodyType.StaticBody;
groundDef.position.set(0, 0);
for (int i = 0; i < polyVerts.size(); i++) {
Body nground = world.createBody(groundDef);
UserData usrData = new UserData(UserData.GROUND);
nground.setUserData(usrData);
List<Fixture> fixtures = new ArrayList<Fixture>();
for (int y = 0; y < this.polyVerts.get(i).getVerts().size(); y++) {
if (this.polyVerts.get(i).getVerts().get(y).length >= 6) {
ChainShape shape = new ChainShape();
shape.createLoop(this.polyVerts.get(i).getVerts()
.get(y));
FixtureDef fixtureDef = new FixtureDef();
fixtureDef.shape = shape;
fixtureDef.density = 1;
fixtureDef.friction = .8f;
fixtures.add(nground.createFixture(fixtureDef));
}
}
polyVerts.get(i).setFixtures(fixtures);
}
this.mustCreate = false;
polyVerts.clear();
}
and here we go, a destructible terrain, of any shape, and destructible by any shape ! Isn't that great ? :)
Make it your own, or improve it !
That's about it. We have a destructible terrain. Although it works, it is far from perfect. You might have noticed that I exclusively use ChainShape to create the terrain. This type of shape isn't well fitted for mobile games, as it increases the computational time for box2d. You might want to triangulate it, but as it is an experiment, I didn't want to add that part and optimization. Adding to that, we do not handle a possible use case, that two points of a Polygon would be too close (or roughly in some parts). Be careful at the size of polygons you are clipping !
I am currently using this mechanism to achieve a destructible terrain myself, so stay tuned, maybe you'll see a possible use of this experiment !
Here is a link to the experiment in our github : https://github.com/QuailsHillStudio/libGDX-Box2D-Destructible-Terrain Feedback, as always is very much appreciated, and of course improvements, other ideas, or even other ways to do it !