Fast visibility graph solver?

Question

I am trying to program a pathfinder on the worlds oceans. I have used an A* algorithm on a cell mesh containing land and water cells previously. But I think that a better solution will be to have continents and islands and polygons; calculate a visibility mesh for the space in between (just once); then include origin and destination in the visibility graph; then solve A* on the resulting graph. Looking around, I have found a book called computational geometry that describes an algorithm for computing the visibility graph. However, before trying to implement it in C++ - does that sound like a good idea?

As far as I know, a lot of different algorithms have been proposed for computing visibility graphs, with differing numerical complexity. It also seems to me that this is an active field, not something that's been solved for good. So this seems to me to be a genuine question. If you think otherwise, please let me know why!

Edit: I have now implemented an algorithm that first computes the visibility graph, on a world map comprising of polygons, with about 5,000 vertices. In a second step, A* runs on the visibility graph. There is probably a limit, in terms of running time and memory, to how detailed the map can be. Currently, the visibility graph takes about 10 minutes to compute on my laptop (I believe that the algorithm is quite efficient; but I also believe that my code is not very efficient and could be speeded up significantly). Once the visibility graph is calculated, the A* is very quick. Many thanks again for the answers and comments given!

Answer 1

Planning on a graph rather than a cell decomposition is a fantastic way to improve the performance of path and motion planning algorithms. However, many algorithms that deal with computational geometry are fraught with challenges (particularly when you can't afford to make mistakes), and it's often best to rely on reliable computational geometry libraries developed by experts in the field.

Rather than overcomplicating your solution, it's probably worth flagging that much of the research in path planning over the last 15 years has been focused on Probabilistic Motion Planning techniques. The two best known examples of these techniques are Rapidly-exploring Random Trees (RRTs) and Probabilistic Roadmaps (PRMs). These algorithms are easy to implement, there are plenty of examples available, and require little in depth knowledge of geometry to get started.

• Chapter 5 - Sampling Algorithms from "Planning Algorithms" by LaValle covers most of what you'll need to know to get started with Probabilistic Motion Planning
• Chapter 6 - Combinatorial Algorithms from the same goes over most of the classic visibility like decompositions, and is prefaced with the warning "Warning: Some methods are impractical. Be careful not to make the wrong assumptions when studying the algorithms of this chapter. A few of them are efficient and easy to implement, but many might be neither"

Answer 2

I had this exact same use case and ended up implementing Lee's visibility graph algorithm which runs in O(n^2 log n) time. I made it into a Python package if anyone has similar use: https://github.com/TaipanRex/pyvisgraph/

I also wrote some blog posts that explain the algorithm:

https://taipanrex.github.io/2016/09/17/Distance-Tables-Part-1-Defining-the-Problem.html

https://taipanrex.github.io/2016/10/19/Distance-Tables-Part-2-Lees-Visibility-Graph-Algorithm.html

To play with visibility graphs interactively, I made: https://github.com/TaipanRex/visgraph_simulator