Efficient path finding in 3D games by using visibility tests with the A* algorithm

In this paper, we propose an efficient method of path finding in 3D games where the terrain is represented by navigation meshes. Our method uses the visibility tests with the A* algorithm. When the A* algorithm is applied to elaborated polygonal meshes for detailed terrain representation, the path finding can be very inefficient because there are too many states (polygons) to be searched. In our method, we reduce the search space by using visibility tests so that the search can be fast even on the detailed terrain with large number of polygons. First we find the visible vertices of the obstacles, and define the heuristic function of A* as the distance to the goal through those vertices. By doing that, the number of states that the A* search visits can be substantially reduced compared to the plane search with straight-line distance heuristic.