# Pathfinding in 3d voxel: waypoints?

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:

1. Each waypoint has a set of connected waypoints; the straight line path between any two connected waypoints is unobstructed.

2. 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.

3. 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.

## 2 Answers

Take a look at hierarchical A* (aka HPA*); its basically what you're looking for. However, keep in mind that adding pre-processing can add so much overhead that it might not be worth it. You will want to profile your existing planner first to make sure there aren't any obvious bottlenecks.

Another thing you can try is to create a sparse probabalistic road map by randomly sampling grid cells and trying to connect them with A* to their nearest nieghbors, then caching the result. Once the PRM is generated, modifying it is quite fast -- but you're not garunteed to find paths in more complicated environments.

• Ah, the PRM might be exactly what I'm looking for. I'm actually using this for robot path planning in an industrial application. I asked here because it seemed similar to the kinds of problems that come up in games. – Dan Bryant Apr 28 '15 at 16:17
• in this case you will want to use A* as the "local planner" in the PRM, and only rebuild the edges affected by a change in voxel occupancy. – mklingen Apr 28 '15 at 17:58
• Preliminary experiments with a PRM-ish solution are looking promising. – Dan Bryant Apr 28 '15 at 22:33

A hard but probably better way: if you walk on surfaces you would use navigation mesh based on triangles that share edges. In 3D space you could use tetrahedrons that share faces. Tetrahedrons should be able to fill your space reasonably and running A* on the graph of tetrahedra should be much faster, as you would probably not need so many of them. As in NavMesh, the added benefit is that once you have the path built of tetrahedrons, you can effectively cut corners and create really pretty paths.

But how would you generate the tetrahedral partition of your space? If you are in for a tough read and lots of fun in implementation - this paper seems to have an answer http://www.cs.berkeley.edu/~jrs/papers/cdtbasic.pdf

Disclaimer: I have never implemented even remotely similar algorithm. It might be difficult and the generation time may be pretty long.

An easier but probably workable way:

1. Generate a point at a random position in the empty space.
2. Find the largest radius so that a sphere centered at the new point with the radius does not intersect any colliding vector. This is your new waypoint
3. Repeat, until sufficient coverage is achieved.

Afterwards you prune the useless waypoints (like spheres completely/almost completely contained in others, spheres that are too small ...) and connect waypoints with each other wherever possible.

This is in principle very similar to the probabilistic road maps hinted in @mklingen's answer.

• That paper from Berkeley is very interesting, but definitely a bit intimidating. I've done stuff with Delauney triangulation before, but tetrahedralization looks to be considerably more complex. – Dan Bryant Apr 28 '15 at 16:36