Weight-Based Framed-Quadtree Path Planning in Three-Dimensional Terrains

The path planning problem in three dimensional terrains is discussed. A new approach, namely the weight based frame quadtree path planning is presented. It improves the traditional method based on regular grids. Using this method, the number of nodes in search is decreased, so that the running speed is increased. By adding weight values to each leaf in the quadtree, time optimal path can be obtained. Furthermore, the method is suitable for different applications in three dimensional environment provided that different functions to each factor corresponding to a specific application are set.