Help needed: "Floating block" detection algorithm

Hi all,

I'm coding game that allows players to build structures from 1x1x1 blocks and others are able to destroy them. Each cube is now own gameobject. I'm trying to figure out fast and good way to detect when destoyed block causes other blocks to have no support from the ground. So i want that no "floating islands" of blocks is possible. If blocks dont have "route to the ground" via other neighborg block, it should fall down.

I'm not interested about suggestions, that "u should use chunks" or "having invidual blocks as own gameobjects is not the way to go, its not efficient enough.." etc. I have that part covered allready. And i'm not trying to find the most efficient way of rendering blocks. I'm purely trying to find routine, logic, simple way or algorithm to efficiently figure out if block is hanging in air or not.

It's easy to check if block has neighbors, but checking if those blocks have neighbors aswell and so on.. and is there ground connection or not.. iterations yes, but what method is quickest, easiest and most efficient??

Also this leads to same kind of problem with ledges. I would want that people are able to build ledges but with only into certain point. Like 3 blocks out from supporting wall would be ok, but 4th block is too much and would be not allowed, because ledge structure comes too weak to support it's own weight.

I know that this is pretty common scenario for people who build "Minecraft style" block games, but i couldnt find any info/tutorials about this feature. Floating blocks or block stucture integrity..

All help is welcome and appreciated! I think i'm not the only one strugling with this problem..

-Jehvi-

 

You could add a structuralStability variable to each block. each time you add or remove a block, check all it's neighbours and update their integrity, then have them update their neighbours and so on.

for example, I have a block on the ground, since the bottom neighbour is the ground, I give it an integrity of 100%.
I put another block on top, the bottom neighbour is unaffected, and should tell its top neighbour that it's integrity is the same, so 100%
then you add a block to the left of that top block. You could determine side neighbours get -20% integrity, so it's neighbour tells it it gets it's own (100%) minus 20% for being on the side (80%).
Then if you add another side neighbour, it's gonna be at 60% and so on. If integrity is 0, the block falls.

In the same way if you remove the very first block, it updates the upper block, telling it hey, you now have 0 integrity, which will tell the same to it's neighbours and so on, and all will fall.

 

Hmm... i think i'm getting some results now. \o/

I'm currently doing some testing with raycasts and each block calculates stability % from neighbouring blocks.
First time when block is placed and after one update round they continue checking with little different logic. It seems to work pretty nice. Structures are getting stronger when i add ground supports and weaker when going further away from supported wall. Underhanging structrures also weakens blocks on top of them.

Needs some testing that it covers all possible building scenarios properly and then find more efficient way for testing rather than using raycasts..

I will record some videos to show it when i have cleaned and optimised the code.

Fun little problem to solve. especially when you start seeing some results.