## 3 Algorithm Design: Hybrid Voronoi-A* Framework and Pseudocode  
After the above research, a combined Voronoi-A* algorithm is designed to meet the route planning needs of drones in complex mountainous environments. The main steps of the proposed algorithm are as follows: (1) By utilizing the obstacle density information from the DEM layer, the drone's primary flight level and a higher backup obstacle avoidance layer are adaptively selected, producing a three-dimensional trajectory. (2) The Voronoi method is applied to process the flight level, and the Voronoi vertex set of that level is obtained, serving as a point set for fast path search space. (3) Based on weight designs, the weight of each Voronoi vertex is calculated, and after sorting, the highest-weighted point is added to the path. (4) If no additional Voronoi vertex can be connected at the current flight level, then the algorithm attempts to switch to a higher level to query Voronoi vertices, continuing the fast connection. If it fails, then A* is activated at the flight level to expand the route. Then, steps (3) and (4) are repeated until the destination is added to the route points. (5) To address redundant sparse path points and excessive turning angles, interpolation and optimization are performed on the route. (6) The optimized route is then output as the primary flight route for drones in mountainous terrain. Due to the use of a combined layered obstacle avoidance and A* expansion strategy, this path can quickly generate flyable routes while avoiding obstacles in complex mountainous environments, and the algorithm exhibits a high degree of safety and robustness. The pseudocode and flowchart for the hybrid Voronoi-A* algorithm are presented in Algorithm 1 and Figure 6, respectively. ```
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60



## 4 Implementation and Results

The algorithm's simulation environment is configured on a laptop equipped with an Intel Core i9-10900K CPU and 64 GB of memory, using Windows 10 as the operating system and MATLAB R2023a as the programming environment for simulation experiments. To evaluate the performance of the newly proposed Voronoi-A* fusion algorithm, we carry out a comparison with the following algorithms in simulation tests across several complex mountainous environments: APF, traditional A*, and RRT. The three real elevation map scenarios include mountainous, hilly, and canyon terrain, which represent typical complex mountainous features. In each of the three terrains, a drone uses different algorithms to plan the flight path from the same starting point to the same destination. The comparison is based on factors such as the success of path planning, the number of waypoints, path length, and planning time, evaluating the performance of each algorithm in different terrains and obstacle environments. All DEM data employed in the experiments were obtained through Global Mapper v19.1. To ensure experimental design fairness, we conducted 20 repeated trials for each comparative method under the same scenario and statistically analyzed the key performance metrics, including the success rate of the flight path's generation, the planned path length, the number of critical waypoints, and the required computational time. For a consistent comparison, all algorithms (A*, RRT, APF, etc.) were simplified to 2D trajectory planning by adopting the same flight altitude level as the proposed method. The computational time measurement started after DEM-based layered 2D flight-level map generation (a preprocessing step that can be performed offline) and ended upon the completion of the planning process. ### Scene 1: Mountainous Terrain

The same starting and ending points are set with a map scale of 1:0.2. In the simulation, the position of the UAV is represented by discrete coordinates.