Thursday, March 13, 2014

Self-Regenerating Destructible Objects

Destructible objects and terrain are pretty much awesome, so I figured I'd try implementing it myself (being able to program is fantastic). One thing I really wanted to focus on was making objects regenerate themselves once they had been destroyed. The main problem with destructible assets in games is that at some point everything is destroyed and one of the coolest features is eliminated; by having the assets gradually regenerate themselves this problem is avoided.

After looking into it a bit I decided that a voxel system would be the best way to accomplish this. A voxel is basically a particle with volume. By packing them together you can form a whole object or terrain whose individual voxels can be manipulated separately allowing for sections of it to be, for example, destroyed. Above is an example from my final product. The whole object is a box, but because it is made up of voxels, the upper right section can be easily removed independently.

The basic implementation was not even all that difficult. The first step for me was to set up some of the basic structures I would need. The two main ones were the Voxel which would hold information about itself and the VoxelUnit which would store and manage all the voxels contained in it. The VoxelUnit basically acts as a box that fills itself up with voxels and then makes decisions about activating and destroying each one; having this structure allows for there to be separate voxel objects that can be manipulated independently.

For this tech demo I used OpenGL and my own Vector3 class which holds three floats (x, y, z) and has basic vector math functionality.

You can view my code here.

Because the VoxelUnit handles the collision and display of each of its voxels, the Voxel itself is pretty simple.

struct Voxel
    Depth depth;
    float regenTimer;

The regenTimer is pretty obvious. To avoid instantaneous regeneration, each Voxel keeps track of how long it has been waiting to regenerate so that they can be regenerated gradually after a set amount of time.
The depth variable is a little more complex. This is used as a kind of depth identity; it is an integer defined by the following Depth enum.


EMPTY indicates a voxel that is not displayed or interacted with and will never regenerate; this allows for shapes other than a cube. In this system every VoxelUnit is made up of a box full of voxels, but by making some empty, different voxel shapes can be achieved.
DESTROYED voxels are like empty voxels, but they can be regenerated and border voxels are destroyed voxels that are adjacent to surface voxels; the VoxelUnit increments the regenTimer of these.
SURFACE and CENTER voxels are filled, but only surface voxels are rendered. Separating them also makes it convenient if you were to check surface collisions later.
EMPTY is set to -3 so that SURFACE is 0. By setting it up this way and putting the Depth values in order, you can easily check if the voxel is active by checking if its depth is greater than or equal to zero.

The VoxelUnit is basically just a Voxel manager:

class VoxelUnit
    ///// variables
    Vector3 Position;
    Vector3 Color;
    Vector3 Dimensions;
    Vector3 VoxelDimensions;
      //dimensions in number of voxels
    float VoxelSize;
      //the size of each side of each voxel
    Voxel*** Voxels
      //3D array to store the voxels

    ///// functions
    void update();
    void draw();

    void reassignDepth();
      //checks/resets the depth value for every Voxel
    Voxel* getAdjacent(Vector3 index);
      //returns an array of voxels adjacent to the one at index
    bool checkCollision(Vector3 c, float r);
      //check collision with a sphere at center c and radius r

I'll describe what each of these functions is responsible for later on, but first we need to populate our voxel array.
The first thing you need to do is determine is the voxel dimensions based on the desired dimensions of the box and the desired voxel size.



It's important to make sure that the voxel dimensions are integers -- you don't want partial voxels.
To populate the array, you simply loop through and assign the voxels at the desired depth value.


Voxels=new Voxel**[(int)VoxelDimensions.x];
for(int x=0;x<VoxelDimensions.x;x++)
    Voxels[x]=new Voxel*[(int)VoxelDimensions.y];
    for(int y=0;y<VoxelDimensions.y;y++)
        Voxels[x][y]=new Voxel[(int)VoxelDimensions.z];
        for(int z=0;z<VoxelDimensions.z;z++)
            //for generating a different shape:
            //if(i>10 && i<VoxelDimensions.x-11
            //    && j>10 && j<VoxelDimensions.y-11)
            //    Voxels[x][y][z].depth=EMPTY;

Assigning all the depth values to CENTER will result in a completely filled in box; you can get creative with generating interesting shapes though by setting the depth value of certain voxels to EMPTY (they will remain empty). Including the commented section in the code above will result in a box with a tunnel through the center of it, for example.

Throughout most of these functions, most of the actual logic will happen inside the inner-most loop of the nested loop structure because it allows access to each individual voxel.

The next key element of the VoxelUnit class is the reassignDepth function. This function is used to go through and make sure every voxel has the correct depth value after there is any change to the VoxelUnit. An optimal system might disperse this function and handle reassignment more locally depending on specific situations, but for the sake of getting things working, going through and reassigning the depth after any change ensures that reassignment will always be consistent and you can avoid a lot of edge cases. The depth of each voxel is mostly determined by the depths of the voxels surrounding it; this is where our getAdjacent function is primarily utilized as well.

Instead of writing out the nested loop to access each element, assume the following code is surrounded by such a loop and x, y, and z are the index values of the voxel for each array as it was above.


////// void reassignDepth() //////
//for each Voxel in Voxels:

Vector3 index(x,y,z);
 //get an array of adjacent voxels
Voxel* adj=getAdjacent(index);

 //first we handle the voxels that are active (surface or center)
      //check to see if any of the adjacent voxels are inactive or "outside"
    bool outsidePresent=false;
    for(int i=0;i<6;i++)
        if(adj[i].depth<0) //values less than 0 are inactive
    if(outsidePresent)    //if next to an inactive voxel
    else                  //if all surrounding voxels are active

 //next we handle inactive voxels (border or destroyed)
else if(Voxels[x][y][z].depth!=EMPTY)
     //check to see if any of the adjacent voxels are active
    bool objectPresent=false;
    for(int i=0;i<6;i++)
        if(adj[i].depth>=0) //values 0 and higher are active
    if(objectPresent)    //if next to an active voxel
    else                 //if all surrounding voxels are inactive

All that getAdjacent(Vector3 index) does is return an array of the six voxels with one greater and one less index value for each dimension. To ensure that even edge voxels (index value of 0) have six adjacent voxels, I first populated the array with voxels that had a depth of EMPTY and reassigned them if the voxel actually existed.
Calling reassignDepth() after instantiating a new voxel array will sort out what is a surface, center, border, etc voxel so that you don't have to worry about that while instantiating.

The update() function is really pretty simple. It is mostly responsible for incrementing the border voxels' regenTimer and restoring the voxels that have waited the necessary time to regenerate.


////// void update() //////
//for each Voxel in Voxels:

    Voxels[x][y][z].regenTimer+=DeltaTime; //add the time passed to the Voxel's timer
    { //if the timer has reached the required wait time, fill the voxel
        shouldReassign=true; //a boolean to keep track of if anything changes

//if shouldReassign=true after each voxel is checked, call reassignDepth()

The next step is to draw the VoxelUnit. The most important thing involved with this is calculating each SURFACE voxel's position because the Voxel in my system does not hold its own position. Maybe it should, but it's easy enough to calculate, so I'm just going to stick with that.


////// void draw() //////
//for each Voxel in Voxels:

if(mVoxels[x][y][z].depth==SURFACE) //only draw surface voxels
     //find the position of the specific voxel
    Vector3 pos=Position-(VoxelDimensions*VoxelSize/2);
    Vector3 index(x,y,z);

     //the following is for the fun rainbow coloration in my examples, based on a root Color
    Vector3 color=(Vector3(1,1,1)-Color);

    //Draw your voxel cube at pos with color

All of this gives you a VoxelUnit that draws and regenerates itself, now all that's left to do is make it destructible. In my tech demo I only handle destructive sphere collision, but it would not be difficult to check collisions with other shapes as well. Basically you first determine if your destructive area collides with the bounding box of the VoxelUnit at all. If it does, loop through each of the voxels and, if the voxel is active (voxel.depth>=0), check to see if it collides with the destructive area. The depth of each voxel that collides should be set to DESTROYED and, unless no voxels were destroyed, reassignDepth() should be called.

The end result should be a destructible voxel object that regenerates itself over time, like so:

Or, if the VoxelUnit is not a solid box:

As you may have noticed in that clip, I set it so that you could change the destruction radius and the regeneration speed. It's also fun to play around with VoxelSize. The VoxelUnit in the video above has 90,000 voxels (as determined by a decreased VoxelSize), but you can get some pretty cool result with much fewer as well. Obviously, though, more voxels yields much smoother results; unfortunately this leads to massive frame rate hits as well.

720 voxels:

720,000 voxels:

Another cool thing I was able to accomplish with minimal additional effort in this system was the ability to place objects in the space without the VoxelUnit regrowing through it. This seemed like a good thing to implement on the premise of increased user immersion; if the player wanted to build on or place an object within a destroyed area, the voxel object or environment should not hinder that because of its regrowing.

By placing permanent spheres and applying destructive sphere collision every frame, the VoxelUnit will regenerate around the object, but will not regrow through it.

I added the ability to remove all of the permanent spheres, and it worked beautifully:

The next step for me in this project would be to get non-destructive collision working, so that these objects could be used as terrain or interacted with in ways other than being destroyed. Another feature I would love to add to this demo would be the ability to load in and "voxelize" custom models so that any object could be turned into a self-regenerating, destructible object. I'll post an update here when I accomplish these things!

Update: I can now voxelize models!