I have a voxel game, where in 3d space, voxels can be added or removed.

Because these voxels can be moved as a whole, I keep connected voxels in an assembly structure.

My issue comes when I delete a voxel, essentially splitting an assembly into two separate assemblies.

I need a way to determine if any of the adjacent voxels to the one deleted, are still in the same assembly, or if a new assembly needs to be created.

I am using only 6 directions, forward, back, left, right, up, down.

This is the original assembly, the voxel highlighted in red is the one I plan to delete

Once the voxel is removed, the void is surrounded by 3 voxels that could potentially be a new assembly, A B and C

Logically we can see that voxel A and B will still be part of the original assembly, but voxel C, and the ones connected to it, will need to be part of a new assembly.

At first I thought of making a list of new assembly contenders (A,B and C) then doing a 3d flood fill starting with A, and checking to see if that flood fill would eventually land on the spot of B or C, if it did, remove it from the list of contenders for a new assembly, then repeat for all remaining voxels on the list of contenders.

Then, I though… maybe there is a faster way, by instead using a path finding algorithm, to see if there is a valid path between the points of A, B and C, sort of like the flood fill method, I get a list of contenders, and starting with the first in the list A, try to find a path to B, then C, if any path is found, remove that voxel from the list.

So… I ask, which method would be less expensive, as I would like to do this in real time, with rather large assemblies.

and where would I even find good algorithms to do this.

I tried to look up 3d flood fill, but didn't really find any good results.

I also looked up some path finding algorithms, but again, they all seem to be for 2D implementations, and not really any luck finding things for 3d.

Thanks in advance for any help.

I'd recommend to use a disjoint set data structure to cluster adjacent voxels into distinct connected sets. You would initialize the set (an array) to contain one entry for each voxel, with each voxel having itself as its parent index (i.e. not connected to anything else). Then, iterate over all adjacent pairs of voxels, and merge together their sets (pick one of the two to merge the other into). This is done by determining the root index for each voxel in a pair (follow the indices to find the voxel that has itself as the set index), and then picking one to assign the other voxel to. Whichever set index is chosen is assigned as the parent of all voxels (i.e. if merging set B into set A, you assign the root voxel of the B to have A as its parent, to make everything in B a child of A). At the end, you should have for every voxel the index of the parent voxel which it is associated with, which defines an implicit tree, with the root of each tree representing a distinct cluster. For each voxel, determine the root voxel index to get a unique identifier for the cluster. There will be one cluster index for each disjoint set of voxels.

I am still trying to work through what Aressera said, if I am able to get it working, I will post my solution here.

Find the voxels around the deleted voxel. For each pair of “around” voxels try to find a path between them without crossing an assembly boundary. If that works both ends are in the same assembly, otherwise they are not.

In this way you get groups of “around” voxels that can reach each other. Each group belongs to one assembly.

Seems like a recursive fill pattern cycle in paint, but in 3d. If parts of the voxels are not being ,,recolored'' then you can disconnect those.