Nagivation Mesh Construction and Path-Finding for Architecture Environment

Abstract

With the fast development of computer science technology, path finding is kept a hot topic in research area; especially it plays an important role in game industry, video and film industry, and large model simulation. However, these approaches and underlying data structure construction are not suitable for all the situations.

In this thesis, we present an approach to semi-automatically construct an underlying structure (Navigation Mesh) in the pre-computing phase, and use a two-level path-finding algorithm during the real searching time for an architecture environment. There are many path-finding algorithm approaches with their underlying data structure which represents the real walkable world for game, video and film. However, the problem arises in architecture environment is very different with these situations. In a large hospital, hotel or airports, we need to more concentrate on those small obstacles as tables, chairs, or beds, rather than the un-smooth walkable surface in games or videos. The number of these obstacles is enormous in architecture environment so that we must be careful to choose the underlying data structure construction and also the relative path-finding.

In our approach, we construct a navigation mesh data structure for the underlying walkable surface with only relatively large obstacles and leave enormous number of small obstacles in the two-level path-finding phase. We will show that the real searching time will be faster in two-level path-finding approach instead of normal path-finding approach but with bigger number of navigation meshes as we must sub-divide large navigation mesh into lots of small pieces with the enormous number of small obstacles.