# Late Line-of-Sight Check and Prioritized Trees for Path Planning
## 6 Experiment
### Benchmark Test  
The pathfinding benchmark maps have different sizes, and the units of the grid maps are pixels. The size of game maps varies from 22 \(\times\) 28-1260 \(\times\) 1104. Maze maps (with a size of 512 \(\times\) 512) contain different corridor widths of mazes, and random maps (with a size of 512 \(\times\) 512) are covered by randomly-blocked cells with varying percentages. Street maps are the thumbnails of the real streets in different cities, and their sizes range from 256 \(\times\) 256-1024 \(\times\) 1024. We implemented these algorithms on the basis of Weighted A* with \(f(n)=(1-\lambda)*g(n)+\lambda*h(n),\lambda\in[0,1]\). In the experiment, there were over ten thousand tests done on each kind of map, and we set three different values for \(\lambda\). Figure 6 shows the extension processes of A*, Theta*, Lazy Theta*, and LLA* on a street map. In this example, LLA* was the fastest among the four algorithms, and it also generated the shortest path. Of course, this is just a particular case, and a general evaluation is given in the benchmark tests. Figure 5: Extension processes of LLA* on four different kinds of benchmark maps: game map (**a**), maze map (**b**), random map (**c**), and street map (**d**). Orange lines represent the final paths, and the blue lines are new edges after LoS-Check. Figure 7 shows the planning results against different values of \(\lambda\) in the benchmark tests. The average path length and execution time of the four algorithms on every map is shown in Table 1. When the factor \(\lambda\) equaled 0.5, these algorithms were all based on the original A*, and we can see that the path length of LLA* was shorter than that of Lazy Theta* or A*. Moreover, the execution time of LLA* was the least among the four algorithms. Meanwhile, we can also find that the paths of LoS-Check-based planners (Theta*, Lazy Theta*, and LLA*) were not shortened very much after LoSS smoothing, but the path of A* was shortened obviously. Therefore, post-smoothing with LoS-Check was also effective in generating shorter paths for the planners that did not use LoS-Check. However, the effects of post-processing were not as good as those of online LoS-Check. Figure 6: Extension processes of A* (**a**), Theta* (**b**), Lazy Theta* (**c**), and LLA* (**d**) on a street map. Orange lines are initial paths, and red lines are smoothed paths after the LoSS smoothing (one time of backward-LoSS and one time of forward-LoSS). (**a**) A*: initial length is 336.68, smoothed length is 320.35; (**b**) Theta*: initial length is 322.51, smoothed length is 317.79; (**c**) Lazy Theta*: initial length is 320.95, smoothed length is 316.31; (**d**) LLA*: initial length is 319.92, smoothed length is 316.31. In this example, LLA* has the least execution time and path length, which is a particular case, and the general evaluation is shown in the benchmark tests. From both Figure 7 and Table 1, we can see that when the factor \(\lambda>0.5\), the path length of Lazy Theta* and LLA* was similar, which was slightly longer than that of Theta*, but LLA* was still the fastest. Meanwhile, the gap of the execution time between LLA* and the other algorithms was not as big as the gap when \(\lambda=0.5\). Moreover, when the factor \(\lambda<0.5\), the path length of LLA* kept being shorter than that of Lazy Theta* or A*, and LLA* kept being the fastest among the four algorithms. At the same time, the gap of the execution time between LLA* and Theta* was bigger than the gap when \(\lambda=0.5\). We can see that LLA* always kept being the fastest and usually resulted in a shorter path than Lazy Theta* (just slightly longer than Theta*) no matter what the factor \(\lambda\) would be.