3D Destructible Terrain via Voxels

From YoYoGames Wiki

Introduction

As mentioned in my last article, the most sensible method for performing destructible terrain in Game Maker is by using a so-called Voxel engine where each volumetric pixel is represented by a small cuboid. Data structures give us a method for doing this effectively for the first time in version 6 and above and so, in order to fully understand this article, you will need to be well-versed in the data structure techniques of Game Maker. The main concept for this engine is that every solid space in the world is defined by a series of cuboids with any given length, width or height. When an explosion occurs, the cuboid is split into 6 other, smaller, cuboids which mimic the old cuboid minus the new hole. This may seem rather complex, but in reality it's nothing more than creating a framework and working within it. There are still many speed, accuracy and practical issues to be contended with and this article will discuss the major problems and their potential solutions. This is not a tutorial on 3D and will not cover more than is necessary in terms of 3D techniques.

Initial Framework

To accomplish such a grandiose task as to make a 3D terrain engine in itself is a daunting prospect. In order to efficiently be able to search our world for points of collision (the main function of terrain), we must consider two methods. One, a 3 dimensional grid (simulated in Game Maker by grids representing two axises within a grid representing the remaining axis) that records whether each and every space in the world is taken up or free - and the other, a grid that records the location of each and every individual block, given X, Y, Z, width, height, depth. It should be fairly clear from the off that the second method is far, far more effective for what we need. A large block in the first method would take up a large amount of room in the data structure and the drawing routine would have to draw every single individual block. Collision checking is admittedly faster, but we can compensate for this later. The framework that needs to be made must be able to easily add blocks of any size and take away blocks of any size and preferably store their textures for rendering later. As a programmer, you must be able to create a block by using one command only as it enhances the ease at which your code can be modified.

Deleting blocks

In this type 2 framework, a type I call a "General Block Grid" or GBG, each block has an ID dependant on which order it was created in. This presents a problem for deletion - If I have a block list of 64 blocks and I decide to delete number 23, do I leave a gap in the matrix or do I shuffle all the blocks "above" number 23 down? The question is more to do with practicality than it is to do with programming simplicity, believe it or not. The amount of searching required for a collision at a point is directly proportional to the size of the grid - note the emphasis on size. If one does not shuffle all the blocks down when deleting, the grid does not get any smaller but blocks are removed. This may not be a problem if one or two blocks are deleted, but larger numbers will cause problems. This is particularily noticeable when creating destructible terrain as large amounts of blocks will be removed. Shuffling down may require more computing time at that moment, but in the long run, it is more effecient.

Modifying blocks

The Holy Grail, so to speak, is the modifying of blocks, a fact that little can dispute. In order to do so, the other block's dimensions must be recording into a temporary set of variables and 6 more created around the hole that should be there (whether all 6 blocks still remain after the operation is another matter altogether). Each of these new cuboids should be, as mentioned above, able to be created via one script so that you may more easily debug the code should any problems occur. The 6 blocks represent the two realms of each axis, so that's positive and negative on the X axis, positive and negative on the Y axis and positive and negative on the Z axis or rather "left, right, front, back, top, bottom" in rather inaccurate but handy terminology. I will give you the example of the "top" block to demonstrate how to achieve the process. In psuedo-code:

• ox = original block x location
• oy = original block y location
• oz = original block z location
• ow = original block width dimension
• oh = original block height dimension
• od = original block depth dimension

• hx = hole x location
• hy = hole y location
• hz = hole z location
• hw = hole width dimension
• hh = hole height dimension
• hd = hole depth dimension

• nx = new block (top) x location
• ny = new block (top) x location
• nz = new block (top) x location
• nw = new block (top) width dimension
• nh = new block (top) height dimension
• nd = new block (top) depth dimension

• nx = hx
• ny = hy
• nz = hz+hd
• nw = minimum(ox+ow-hx,hw)
• nh = minimum(oy+oh-hy,hh)
• nd = oz+od-hz-hd

Try drawing a diagram of what I have described using mathematics. Repeat this process for the 5 other blocks, check if they have a width or height or depth of less than 1 and you've made your very own 3D DT engine via GBG Voxels. If you're looking for an example, one will be made available soon.

Conclusion

I hope you've understood what I have written here. It's taken Game Maker users a long while to realise their dreams of fully 3 dimensional terrain that can be deformed at will, but I feel we are coming extremely close to the final product. The only main areas left untouched are the implentation, adapting AI to the world or sending information over the internet, simplification, we can avoid some nasty collision-checking slowdowns at the expense of memory space, and GBG rendering conglomeration, turning all visible faces into planes to help the rendering engine. I would love to hear all suggestions and contributions at the Destructible terrain topic on the GMC or over messaging.