DEVBLOG #1 : Building Destruction
Tags: lua, roblox, gamedev
Published: 2021-08-03 15:13:00

*PRELIMINARY: I decided to start a devblog. Hopefully I remember to actually make these posts. They will describe any projects I'm working on. If it's been a while since I've made one please bug me on twitter @ preacher_online*

**DEVBLOG #1: BUILDING DESTRUCTION**

For the past few weeks, I've been working on building destruction. There are many ways to approach this but I prefer to take a procedural approach instead of making premade chunks of a building like what battlefield does. Obviously the first thing that should come to anybody's mind is minecraft, and that's absolutely what I tried to do last year for a different project (https://twitter.com/preacher_online/status/1238651653680771078?s=20). It uses pre-defined "grounded" voxels that voxels will path to to figure out if they're connected to the ground or not. If the building takes damage and afterwards voxels are not connected, then they get destroyed. It turned out quite well, but they were 4x4x4 cubes and for this project I need more detail. The old project also used a global grid, so every part had to be globally axis aligned. I rewrote it to use 2x2x2 voxels, as well as let each building have its own local grid. The parts inside the buildings had to be locally axis aligned but allowed me to rotate the buildings around globally. It turned out really well but was too slow since its 4x more voxels, and scaled horribly. ![building picture](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dgrocg7rpa37xgpzu9o9.png)
 
And now I thought, why do I even need a 3d grid like minecraft? Sure, it helps find neighbors of voxels (if you don't know if they have any), and let's you add and remove voxels easily. You might think you'd want to use a 3D table to store 3D voxel data, and maybe octrees. But lua tables are slow at indexing and even worse with memory. So I did one big 1D table and just hashed the vector3s into it since its integers. (hash is just pos.z + pos.y * gridSizeZ + pos.x * gridSizeZ * gridSizeY, dont ask why its zyx, also it starts at 0) This allows me to only have to index the table once instead of three times, at the cost of some very simple math. But I soon realized that 3d voxels scale poorly if I want many large buildings, since most buildings are pretty hollow, which means they are basically sparse 3d arrays and would waste alot of memory using my solution. So I thought of instead of using a grid, why not just use a big tree?

So that's what I did. I pre-cache each part's neighbor using EgoMoose's rotated Region3 that uses GJK (https://devforum.roblox.com/t/rotated-region-3-module/334068). It would be a little faster (1.4-1.6x) if all the parts inside of the building are axis aligned and I just used Roblox Region3, however that would limit the visual fidelity of the buildings if I can't rotate the parts. I used the same grounded labeled voxels. When damage takes place, I destroy the parts that get damaged. The neighbors of the destroyed parts that are still alive get their references to the destroyed parts nil'ed (nilled?). I use a depth-first search and loop through neighbors recursively until one of them has the grounded label. It works really well and is a lot faster, since a part can span multiple voxels. The best part is that they don't have to be aligned in any way, and they can be any size. The one optimization that I need to do is have a biased order for the neighbors. Most buildings should have a biased search downwards since its looking for the ground. So neighbors that are below a part should be in the beginning of the neighbor table. Here's a gif of it first checking upwards then resorting downwards: https://i.gyazo.com/31c2971e3b016b536327d589f7cfd2e4.mp4

Overall I'm happy with this solution so far, it allows the most creative freedom and the least computation. It'll be interesting the different ways I can do destruction with this since it won't have to be grid aligned. I'll have to look into some more graph theory and search algorithms since that's exactly what this system is, a big visual graph. Directed acyclic graphs caught my eye but I don't think it'd work well for parts dangling only from their top edge.