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, with millisecond runtimes even on 6000 x 6000 maps. On large maps, with the use of pre-processing, these algorithms are at least an order of magnitude faster than existing algorithms like Visibility Graphs, Anya and Theta*.

A common way to represent dynamic 2D open spaces in robotics and video games for any-angle path planning is through the use of a grid with blocked and unblocked cells. The Basic Theta* algorithm is an existing algorithm that produces near-optimal solutions with a running time close to A* on 8-directional grids. However, a disadvantage is that it often finds non-taut paths that make unnecessary turns. In this paper, we demonstrate that by restricting the search space of Theta* to taut paths, the algorithm will, in most cases, find much shorter paths than the original. We describe two novel variants of the Theta* algorithm, which are simple to implement and use, yet produce a remarkable improvement over Theta* in terms of path length, with a very small running time trade-off. Another side benefit is that almost all paths found will be taut, which makes more convincing paths.