Title: Edge N-Level Sparse Visibility Graphs: Fast Optimal Any-Angle Pathfinding Using Hierarchical Taut Paths,
Abstract: In the Any-Angle Pathfinding problem, the goal is to find the shortest path
between a pair of vertices on a uniform square grid, that is not constrained to
any fixed number of possible directions over the grid. Visibility Graphs are a
known optimal algorithm for solving the problem with the use of pre-processing.
However, Visibility Graphs are known to perform poorly in terms of running
time, especially on large, complex maps. In this paper, we introduce two
improvements over the Visibility Graph Algorithm to compute optimal paths.
Sparse Visibility Graphs (SVGs) are constructed by pruning unnecessary edges
from the original Visibility Graph. Edge N-Level Sparse Visibility Graphs
(ENLSVGs) is a hierarchical SVG built by iteratively pruning non-taut paths. We
also introduce Line-of-Sight Scans, a faster algorithm for building Visibility
Graphs over a grid. SVGs run much faster than Visibility Graphs by reducing the
average vertex degree. ENLSVGs, a hierarchical algorithm, improves this
further, especially on larger maps. On large maps, with the use of
pre-processing, these algorithms are orders of magnitude faster than existing
algorithms like Visibility Graphs and Theta*.