In a recently released game, characters navigate (poorly) around a 2d martian surface performing tasks. Just for fun, I am trying to come up with a better algorithm.
The problem: Given a set of non-intersecting lines and two points, start and finish, find the shortest route which does not intersect any of the lines.
It's clear to me that the final path will consist of segments that either connect two points among the ends of the walls + start/finish, or run the entirety of a segment. So the search space isn't infinite -- there's only $O(n^2)$ segments to search and A* would be reasonably effective. If you need to check viability of segments naively, there's $O(n)$ work for $n^2$ segments, the algorithm would be $O(n^3)$. Is there a more efficient way to enumerate which points are "reachable" with a straight shot from some other point on the graph?
Just to be clear, this isn't a homework problem, it's just a thought experiment I was wondering about. There's some related problems discussed here, but nothing that matches precisely.
This problem is called "Any angle path planning". The short answer is there are ways of generating a visibility graph in $O(n^2 log n)$ time (and maybe better), but since visibility graphs may have up to $n^2$ edges, algorithms using generating a VG will always have worst case performance slower than $n^2$.
VG algorithm: Ch 13 of Computational Geometry: Algorithms and Applications by de Berg
Most modern techniques avoid generating VGs and instead sacrifice correctness for asymptotically faster results. Some resources for the motivated: