# Late Line-of-Sight Check and Prioritized Trees for Path Planning
### Any-Angle Path Planning  
It is popular to use the A*[7] algorithm for pathfinding on grids or navigation meshes. A* can usually find the optimal solution along with grid edges, but it is not the real shortest path because the paths are constrained to grid edges [2]. To relax this kind of constraint and obtain a more ideal and shorter path, many types of research attempts have been made. Related methods are called any-angle path planning, meaning that the path will not be constrained to grid edges. Line-of-Sight Check (LoS-Check) is an efficient method to relax the constraint of grid edges via checking whether there is a straight line between two non-adjacent vertices. If the straight path does not traverse the obstacles, the updated path will be shorter according to the triangle inequality. LoS-Check can be efficiently implemented by the line-drawing algorithm [29].  
Any-angle path planning can be divided into three main categories: post-processing, online-processing, and preprocessing.  
Post-processing is a method that obtains the grid-optimal path firstly and then uses the shortcut to replace the old path between those points, which satisfies the line-of-sight condition [30]. Although this kind of LoS-Check can smooth the planned path, actually it can hardly result in the real shortest solution.  
More and more any-angle path planning algorithms are concentrating on online-processing. Field D*[31] uses linear interpolation on grid edges to relax the edge constraint, but it is not optimal. Theta*[2] performs LoS-Check between the parent of the current vertex and every successor of the current vertex, showing that the planned path is close to the shortest. Lazy Theta*[32] is a variant of Theta*, which adopts the lazy evaluation strategy to reduce the amount of LoS-Check, and it shows good performance in a 3D environment. Lazy Theta* has been used in the path planning of a multirotor UAV [33]. There is also an optimal any-angle pathfinding algorithm called Anya [34], which can always return an optimal path without any preprocessing or memory overheads. Anya is an optimal and online any-angle path planning algorithm, but it will cost more time on the \"interval\" search. Meanwhile, [PERSON] and [PERSON] [35] showed that Anya is slower than A* and Theta* on average.  
Preprocessing is often used to accelerate the planning speed, which usually needs some computation before the main planning, aiming to collect more informed information about the given environment. Block A*[36] employs a preprocessed database, which contains the distances between local points. Subgoal graphs [37] are preprocessed from grids by placing subgoals at the corners of obstacles and adding edges between the necessary ones. PolyAnya [4] is a variant of Anya based on the navigation mesh, but it may cost more time on constructing the navigation meshes. These methods can speed up any-angle path planning.  
Sometimes, there is no need to get the strictly shortest path for Real-Time strategy (RTS) games, and the most important goal is to get a relatively short path as quickly as possible. Considering that  
Figure 1: Moving a piano from one corner to another corner using the LLA* algorithm (top view). The left figure shows the start place and the goal place of the piano (from the left corner to the right corner). The right figure shows the composite moving trajectory of the piano without touching the tables and chairs.  
the environment of a game may change frequently, the online-processing any-angle path planning algorithm is a better choice. Therefore, we design our algorithms on the basis of A* and use less LoS-Check to optimize the path, aiming to get a shorter path with less time simultaneously.