3
\$\begingroup\$

I am working at dynamic voxel engine in Unity (something like Space Engineers) where player can create object from voxels, push them, damage and split in to other object.

I store all data in 3D array, 1 mean voxel, 0 mean empty node.

So I looking for solution to break object (array). For example when I remove enough voxels object should split in to two.

00000000            00000    0000
01110110   ====>    01110    0110
01110110            01110    0110
00000000            00000    0000

In 2D example it should split like that.

I try to use BFS search but it not fast enough ;(. It works fine for small grids like 5x5x5, when I creat 5x5x50 grid it works few seconds before break arrays.

My algorithm: 1) First find empty node 2) When you find empty node start BFS from that node, collect all not empty nodes, when you cant find not empty node finish.

If break exist it will collect only one part of array so it find break, if there is no break it will return whole array.

The problem is speed of it ;/ How to make it faster?

\$\endgroup\$
3
\$\begingroup\$

When you remove a node, take any solid nodes attached to it and do a connectivity test between each pair. If any of the solid nodes that were once connected to the solid node you just removed are no longer connected, then removing that node has just created two separate objects.

This algorithm isn't affected by the size of the grid, but rather the size of the objects. There are additional optimizations you can do for connectivity for large objects. (See this answer for some optimizations you can implement there). However, most of your searches are going to be very quick, because objects will still be connected with short paths.

I'll use a 2D example here for simplicity:

enter image description here

  1. Our single object
  2. We remove the red node and do connectivity checks between every green node with every other green node. We find they're all still connected.
  3. We remove the red node and do connectivity checks between every green node with every other green node. We find that these nodes are no longer connected.
  4. We have two separate objects. You can define these objects by taking the green nodes that were not connected and doing a BFS on each to determine the bounds of each completed object.
\$\endgroup\$
  • \$\begingroup\$ Great idea for finding breaks, but still when object split in to two object which contains for example 2000 voxels each, using BFS still will be to slow. \$\endgroup\$ – Kacper Kleczewski Feb 6 '15 at 11:50
  • \$\begingroup\$ BFS for connectivity would be a bad idea, use something like A*. \$\endgroup\$ – MichaelHouse Feb 6 '15 at 12:47
  • \$\begingroup\$ What if it splits in 3 parts? What if it splits into 6 parts? The code to do all this seems complex. \$\endgroup\$ – Aaron Franke Sep 13 '17 at 17:10
  • \$\begingroup\$ @AaronFranke The first line says to run the operation on each node that was attached to the removed node. That means each of the 6 parts would have the same operation performed and be defined as distinct parts. \$\endgroup\$ – MichaelHouse Sep 13 '17 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.