A framework of a fast any-angle path finding algorithm on visibility graphs based on A∗ for plumbing design

摘要

In this research, we investigate the issue of compact design that involves finding the shortest connecting plumbing path between hydraulic components. An improved version of visibility graph called visibility graph of candidate is proposed followed by a new line-of-sight technique called visible-neighbors which is straightforward to expand to 3D applications. A new data structure associated with the techniques developed are proposed in order to address the inefficiency issue coming with A∗ algorithm on visibility graphs. The performance of the new technique on visibility graphs is compared to the traditional A∗ and Theta∗ algorithms on the aspect of path length, nodes explored as well as computational time.