Sorry for the double post, but I think I understand what happened. Apparently, when running the app, PolyVox threw an exception for not finding a path from the start point (0,0,0) to the end point (63,63,63). So I tried to make things easier for the algorithm and made the start point (63,63,0) and the end point (63,63,63). I expected the algorithm to calculate the path with no problem.

Was that an error on my part for not understanding the way the algorithm works? From what I understand of PolyVox, the point at coordinates (0,0,0) was a solid block. Does the AStarPathfinder require an empty block for the beginning and end points or can it calculate a path through blocks also?

Thank you for the help.

EDIT: Apparently, if I compile the code with a starting point that has 2 null coordinates and the third having a value lower or equal to 25 (i.e. 25,0,0 or 0,14,0) the app crashes. For any other combination, it appears to work fine, as long the start point isn't too close to the origin of the volume (0,0,0). I don't understand ...

Ok, I know what is going on here. Basically one of the AStarPathfinderParams members is called 'uMaxNoOfNodes' and this basically controls the maximum number of cells that the algorithm will explore (I think this was to stop it getting stuck in a never ending loop). It defaults to 10000, and changing it to 300000 does seem to let the algorithm find the path between the two corners of your cube.



However, it is extremely slow. I took somewhere between 5 minutes and 1 hour to process on my laptop (not sure exactly as I went off for dinner). In other words you can't really use it in it's current state.

I'm sure there are a lot of optimization opportunities but this is something I'll be looking into myself as I'm not using pathfinding at the moment. Alternatively you can try running the pathfinding on a smaller version of you volume.

I'm not actually sure what the expected performance of A* is. In terms of the number of elements a 64x64x64 volume is the same as a 512x512 image, but I don't know whether A* would normally work on an image that size as I'm not an AI guy. But even with the same number of nodes, the volume case is harder because it needs to explore in three dimensions instead of two.

So there's probably some slow code in there, but it probably a tough problem as well.

The problem here is, that you have open space and want the shortest route inside that space...
you have nearly no constraints...
if you start adding constraints, it will become much much faster as most paths it is testing will be dropped due to failing to be in the constraints.

think of it this way... testing all possible paths inside a labyrinth(not many possible ones... every fork adds 1-2 new paths) is easier than testing all possible paths in a completely empty room(there's 2-3 new paths to go per voxel if you just think about the 2d case... in 3d it's even more)

Yes, this is very true. Actually the only time I've actually used the AStarPathfinder was in a prototype where the user could click on the landscape and their vehicle would drive there. In this case I knew the vehicle had to stay one the ground, and so a position was only considered valid if it had a solid voxel under it. This cut down the number of voxels to be processed.

Ok, I understand. Does the AStarPathfinder contain any built-in functions to add constraints? As an example, for my cube, if I want to get from the centre of the top face to the centre of the bottom face, through the cube, in a vertical line, but avoiding different materials inside the volume?

Let's say I have a cube made of dirt, but that dirt cube has voxels assigned to be stone or obsidian (it's best to visualize a chunk from Minecraft, I think), how can I make a NPC dig through the dirt but avoid the stone and obsidian? Is this where the connectivity member function comes into play?

Thank you all for the helpful info.

The AStarPathfinderParams has a mamber called 'isVoxelValidForPath'. This is actually a callback function which specifies whether any given voxel can form part of the path. By default this callback function points to 'aStarDefaultVoxelValidator', and this function considers a voxel to be valid if the material is zero (i.e. empty space). You can provide your own function, attach it to 'isVoxelValidForPath', and then the pathfinder will use that function instead. You should do this by passing your function as a parameter to the AStarPathfinderParams constructor.

Connectivity is different - it basically determines which voxels are considered to be the neighbours of a given voxel. You might consider a voxel to have 6 neighbours (sharing a face) 18 neighbours (sharing a face or an edge) or 26 neighbours (sharing a face, edge, or corner).

Ok, I think I've got the hang of this ... Hopefully, I will make a demo in the future to showcase a project of mine. Don't expect this to soon, because I don't have a lot of time on my hand, but I am sure I'll use PolyVox. Thank you all for all your help.