I'm looking for a good algorithms for the following problem: Given a 3D grid of voxels (which may be either empty or filled), if I pick two non-adjacent voxels, I want to know if they are connected to each other by other voxels.
For example (to illustrate the situation in 2D), where # is a filled square:
1 2 3
a # # #
b # #
c # # #
If I pick a3 and c3, I want to determine as quickly as possible if they they are connected; if there is a path between a3 and c3 through filled pixels. (The real situation is in a 3D voxel grid, of course.)
I've looked at floodfill algorithms and path finding algorithms, but I'm not sure which to choose. Both do unneccesary work: Flood fill tries to fill all voxels, but this is not needed. Path-finding algorithms are usually concerned with finding the shortest path, which is also not necessary. I only need to know if there is a path.
What algorithm should I be using?
Edit: based on the comments, I think should add the following: the content of the voxels are not known in advance, and also, the algorithm is needed to detect if removal (emptying) of a voxel would cause the group of voxels to break into two or more smaller groups.
c3->c2->b2->a2->a3
? \$\endgroup\$ – user27340 Mar 12 '13 at 16:04