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.
Answer
A* would work just fine. Path finding is what you want, finding the shortest path is just as fast (or faster) than finding any path at all. In this situation A* is likely the most suitable given you have a start and end point. this means you have the added heuristic to speed up the search.
With A* typically the first path you find is the shortest, so it's not doing extra work after it's already found a path.
For some optimizations, check out my answer here.
No comments:
Post a Comment