11
\$\begingroup\$

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.

| improve this question | |
\$\endgroup\$
  • \$\begingroup\$ In your example would a valid path from a3 to c3 be the following : c3->c2->b2->a2->a3 ? \$\endgroup\$ – user27340 Mar 12 '13 at 16:04
  • \$\begingroup\$ that is correct \$\endgroup\$ – Bram Vaessen Mar 12 '13 at 22:09
12
\$\begingroup\$

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.

enter image description here

For some optimizations, check out my answer here.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ looks like it really shoots forward until it hits that wall then it kind of creeps \$\endgroup\$ – GameDev-er Mar 12 '13 at 17:17
  • 1
    \$\begingroup\$ @GameDev-er Yes, that's because of the heuristic. If there was no obstacle it would be a very fast search, nearly a straight line. \$\endgroup\$ – MichaelHouse♦ Mar 12 '13 at 17:43
  • \$\begingroup\$ With better sorting of the nodes, this would expand the path closest to the final node first. If you have a fast data structure for ordering the nodes, sort them by distance to the target for the most direct path. \$\endgroup\$ – MichaelHouse♦ Mar 12 '13 at 22:37
9
\$\begingroup\$

If you're prepared to do some pre-processing and eat the storage cost, then partitioning voxels into connected groups at build time gives an obvious answer to 'is there a path at all'. There is a path between two voxels if they're in the same group. The problem with that obviously is that you have to store group information somewhere, and that depends on your data layout. If you're storing a simple list, you can just break that into multiple lists, one for each spatially connected group. If you're organising in some kind of BVH, then you could probably get some reasonably good efficiencies if you can say "all voxels in this node and below belong to group X".

Alternatively, you could do some spatial pre-partioning and store some smaller set of 'hub' voxels for each connected group. Then you can path-find from your source and target voxels to their nearest hub voxel, which should be a much shorter / cheaper to calculate path. If you can find a path from a voxel to a hub voxel, then the voxel is part of the hub voxel's group. With smart selection of those hub voxels, you can minimise the number of path traversals. E.g. a sphere might have just one hub voxel in its centre, but a long thin group might have a hub voxel every X voxels along its length. If your source and target voxels are at either end of the length, they only have to go at most X voxels to find a hub, and even though there might be a huge number of voxels between the start and end of the length, the pathfinding involved would be relatively short.

It all depends on just how pathological your voxel groups are: if you expect a huge number of smallish disconnected groups, the increase in storage cost is going to massively outweigh the performance hit of just pathfinding. If you expect relatively few connected groups but of odd topologies, then naive pathfinding might be hugely expensive and the storage cost and minimal pathfinding is a much cheaper option.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This is the right answer, but to implement it efficiently, it should not be stored as a list. Add a pointer to each voxel that points to its "representative voxel", which you set using the union-find algorithm. This is constant storage cost per voxel, and basically linear in the number of edges for computational cost. \$\endgroup\$ – Neil G Mar 12 '13 at 21:15
  • \$\begingroup\$ Interesting ideas, but there are two things that might complicate the situation. The first is that the content of the voxel grid is not known in advance, so in order to make hub voxels, I'd also need an algorithm that can determine which voxels should be hubs. \$\endgroup\$ – Bram Vaessen Mar 12 '13 at 22:04
  • 1
    \$\begingroup\$ Second problem is that the algorithm is needed right after removal of one voxel, to determine if the group it was part is broken into smaller groups due to the removal of that voxel. \$\endgroup\$ – Bram Vaessen Mar 12 '13 at 22:11
  • \$\begingroup\$ @BramVaessen If you're looking for all pairwise interconnectivity relations - and in particular, whether groups 'break up' - then that's a somewhat different matter than simply reachability (though reachability is the easiest way of going about it); I'd encourage adding more details on specifically what you're after to the original question, as it may allow for better answers to the 'problem behind the question'. \$\endgroup\$ – Steven Stadnicki Mar 12 '13 at 23:08
  • \$\begingroup\$ To keep it clean, I have asked my initial problem in a different question here gamedev.stackexchange.com/questions/50953/… \$\endgroup\$ – Bram Vaessen Mar 13 '13 at 12:18
4
\$\begingroup\$

I'm not very familiar with voxels, but I would imagine that you could get quite good performance from using a best-first search algorithm such as A*. The problem with using A* in this instance is that the heuristic one would normally use is designed to prioritise finding the shortest path and not just 'any path' as quickly as possible.

You may have some luck using an alternate heuristic which expands fewer nodes such as

f(p) = g(p) + w(p) * h(p)

where w >= 1. you decrease the value of 'w' the closer you get to the goal, thereby giving a higher priority to the path cost 'g' the closer you get to the voxel you're looking for.

I hope this helps!

| improve this answer | |
\$\endgroup\$

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.