I have an application where I have a 3d collision voxel space (passable or non-passable at each point) and I want to plot a short unobstructed path between two points. There are no gravity constraints, so the shortest unobstructed path is a straight line between two points.
I know that A* can be generalized to 3-space, but this is a bit slow for my purposes. In my particular application, the collision space changes infrequently and there is a finite number of permutations, so what I'd like to do is automatically pre-process the voxel and generate a set of 'waypoints' with the following properties:
Each waypoint has a set of connected waypoints; the straight line path between any two connected waypoints is unobstructed.
For every passable point in space, there is an unobstructed straight line path to at least one waypoint. I'll probably store a lookup table to make this easy to find.
Ideally, the waypoints are generated so that the paths are still reasonably close to optimal, but I don't need to find the absolute optimal path.
If it's relevant, my collision space mainly consists of a few large contiguous 'blobs'; all empty spaces should be accessible, but the 'blobs' do have concave areas and holes allowing passage. Also, since I'm precomputing this, I can live with relatively long running times (though I'd prefer an upper bound of minutes, rather than hours or days.)
Is there a well-known algorithm for doing this? My first thought is some sort of repeated A* for random point pairs and looking for 'choke points' (regions through which a lot of paths go), but I'm guessing this is a problem that has already been studied.