A Focal Any-Angle Path-finding Algorithm Based on A* on Visibility Graphs
This work addresses path-finding problems in domains like robotics or gaming, but it is incremental as it builds on existing A* and visibility graph methods.
The researchers tackled path-finding by developing a new algorithm that combines a pruned visibility graph with a novel visibility check technique, resulting in improved efficiency and performance compared to traditional methods like A* on grids, Theta*, and A* on visibility graphs, as measured by path length, nodes evaluated, and computational time.
In this research, we investigate the subject of path-finding. A pruned version of visibility graph based on Candidate Vertices is formulated, followed by a new visibility check technique. Such combination enables us to quickly identify the useful vertices and thus find the optimal path more efficiently. The algorithm proposed is demonstrated on various path-finding cases. The performance of the new technique on visibility graphs is compared to the traditional A* on Grids, Theta* and A* on Visibility Graphs in terms of path length, number of nodes evaluated, as well as computational time. The key algorithmic contribution is that the new approach combines the merits of grid-based method and visibility graph-based method and thus yields better overall performance.