Research On Global Path Planning For Virtual Human

With the in-depth development of virtual reality technology and the increasing requirement for it, the researches on virtual human technology have attracted more and more attention. The research on the path planning is one of the important tasks in the study of virtual human, gradually forming a new hot research field.Path planning in a virtual environment requires a model or representation of the environment known as environment map. The methods about how to generate the environment map and the path planning algorithms are the two most important aspects of path planning technology, which are systemically and deeply studied in this thesis. The main work and contributions are summarized as follows:Firstly, common methods on modeling of virtual environment and searching strategy are reviewed. In the review, the advantages and disadvantages of those methods are listed. Grid method is chosen to generate the environment map, and hierarchical bounding box technology is introduced to reduce the complication of the environment map generation process.Then, this thesis presents a simple technique to speed up optimal path planning on Euclidean-cost grids and lattices, which is called RGN method. Grids and the shortest paths in the grids have their respective characteristic, which can be exploited to improve the efficiency of planning on grids. So RGN method is proposed and proved, which can be used to any path planning algorithm based on grid map. And the use areas of RGN method can be explored to high dimension grid as well. This paper also gives out the corresponding math models.Thirdly, a path planning algorithm for the special case of navigation on a 2D grid is proposed in the thesis, which is called as RBPPA. It combines the RGN method to reduce the number of neighboring nodes considered during a node expansion step. The analysis about how to use the RBPPA algorithm on the path planning for virtual human is also presented in the paper.Finally, a simulation system is set up, which is developed to run these path planning algorithms. Comparing the simulation results of RBPPA and others shows that the RBPPA is feasible and more efficient.