DEVBLOG #2: More Building Destruction
Tags: roblox, robloxdev, lua, gamedev
Published: 2021-08-19 05:44:40

In the last post I talked about making a tree-based destruction system instead of a voxel-based system. This will give me much more creative freedom and visual fidelity than the old system. I just finished a prototype, you can see it [here.](https://twitter.com/preacher_online/status/1428205991061954564)

It works quite well, is extremely flexible, and is faster than the old system. To negate I simply subdivide the part into multiple smaller parts. I also have a minimum axis size for the parts. This helps with annoyances of blasting a hole in a wall and having a slither of a part block the entrance, and also reduces the overall amount of parts created. I do a simple [depth-first search](https://en.wikipedia.org/wiki/Depth-first_search) through a part tree and search for any parts marked as "grounded", which to mark parts is as simple as just putting a folder in a part named "ground" and then caching those in the beginning. This system is very flexible, I simply inserted a few free models from the toolbox and then inserted a folder into the bottom part with the neighbor "ground", and that's all that's needed to set it up.

I decided to store each part's neighbors in an unordered dictionary instead of an ordered list. I did some benchmarking and lua is much faster at inserting and removing with dictionaries, as well as O(1) table indexing instead of having to search through the list for the neighbor I want (O(n)). This is very important for scalability where a part will have lets say 6+ neighbors. The downside to this is that I cannot order them. Originally I had it where neighbors positioned below a part will be at the the front of the ordered list, so we visit those first, since we want a downwards-biased search. This is obviously because buildings are usually in contact with the ground at the bottom. So while I gain some performance with using dictionaries, I also lose some since the search method is unbiased and searches the tree in a random matter, which means we could have a part near the bottom searching upwards for a while before reverting back down. The new system is better for smaller and more dense buildings, while the older system is better for very large buildings with lots of spaced out parts. To counter this I can just keep this in the back of my head while I make the buildings. I could always implement an A* algorithm or check the positions and sort them into a table when we check the neighbors, but I'm sure these will be slower than just the current naive search.

I had another issue where when you put a hole in a part marked as grounded, the subdivided parts wouldn't be labeled as grounded and the whole building would fall apart. I get the bottom y value of the global [AABB](https://en.wikipedia.org/wiki/Minimum_bounding_box) of the part. I used the lowest AABB y of the original part being negated, and compared that to the lowest reach of the new subdivided parts, and if they were about the same (fuzzy equals to take into account floating point inaccuracies) then the new subdivided parts were considered grounded. This is so that if you have a big lamp post and you cut it in half, the top part wouldn't be considered grounded since its bottom is way above the bottom of the original lamp post. I guess I could've just explained it in layman's terms using that analogy instead of this whole paragraph though, haha.

The next step is doing debris. In the twitter video I simply unanchored the parts that are no longer connected to the tree, but I plan on making a cool debris system to make it look a lot better.