Skip to main content
Game Development

Return to Question

added 269 characters in body
Source Link
Bram Vaessen
Bram Vaessen
  • 195
  • 1
  • 6

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.

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?

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.

Tweeted twitter.com/#!/StackGameDev/status/311471459082043392
Condensed. Fixed grammar. Clarified wording.
Source Link
Anko
Anko
  • 13.5k
  • 10
  • 56
  • 82

I'm looking for possiblea good algorithms for the following problem:

given Given a 3d3D grid of voxels (which canmay be either empty or filled), if I pick two non-adjacent voxels (which are not adjacent), I needwant to know if they are interconnectedconnected to each other by other voxels. 

For example, if I (to illustrate the situation in 2d with 3x3 pixels2D), where # is a pixel which is filled, square:

  1 2 3
a # # #
b # #
c # # #

ifIf I pick a3 and c3, I want to determine as fastquickly as possible if they they are connected, in other words,connected; if there is a path between a3 and c3 going troughthrough filled pixels.    (but theThe real situation is in a 3d3D voxel grid, of course.)

I'm lookingI've looked at floodfill algorithms and path finding algorithms, but I'm not sure which would be the best way to gochoose. I feel like both try toBoth do some unneccesary work.: Flood fill tries to fill all voxels, but this is not needed, and path finding. Path-finding algorithms are usually concerned with finding the shortest path, which is also not neccesary,necessary. I only need to know if there ISis a path.

Anyway have some suggestions for algorithmsWhat algorithm should I be using?

Thank you very much!

I'm looking for possible algorithms for the following problem:

given a 3d grid of voxels (which can be either empty or filled), if I pick two voxels (which are not adjacent), I need to know if they are interconnected. For example, if I illustrate the situation in 2d with 3x3 pixels, where # is a pixel which is filled,

  1 2 3
a # # #
b # #
c # # #

if I pick a3 and c3, I want to determine as fast as possible if they they are connected, in other words, if there is a path between a3 and c3 going trough filled pixels.  (but the real situation is in a 3d voxel grid)

I'm looking at floodfill algorithms and path finding algorithms, but I'm not sure which would be the best way to go. I feel like both try to do some unneccesary work. Flood fill tries to fill all voxels, but this is not needed, and path finding algorithms are usually concerned with finding the shortest path, which is also not neccesary, I only need to know if there IS a path.

Anyway have some suggestions for algorithms?

Thank you very much!

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?

Source Link
Bram Vaessen
Bram Vaessen
  • 195
  • 1
  • 6

Algorithm to see if two voxels are interconnected

I'm looking for possible algorithms for the following problem:

given a 3d grid of voxels (which can be either empty or filled), if I pick two voxels (which are not adjacent), I need to know if they are interconnected. For example, if I illustrate the situation in 2d with 3x3 pixels, where # is a pixel which is filled,

  1 2 3
a # # #
b # #
c # # #

if I pick a3 and c3, I want to determine as fast as possible if they they are connected, in other words, if there is a path between a3 and c3 going trough filled pixels. (but the real situation is in a 3d voxel grid)

I'm looking at floodfill algorithms and path finding algorithms, but I'm not sure which would be the best way to go. I feel like both try to do some unneccesary work. Flood fill tries to fill all voxels, but this is not needed, and path finding algorithms are usually concerned with finding the shortest path, which is also not neccesary, I only need to know if there IS a path.

Anyway have some suggestions for algorithms?

Thank you very much!