Path finding for human motion in virtual environments

This paper presents an efficient and robust technique for generating global motion paths for a human model in virtual environments. Initially, a scene is discretized using raster hardware to generate an environment map. An obstacle-free cell path sub-optimal according to Manhattan metric is generated between any two cells. Unlike 2D techniques present in literature, the proposed algorithm works for complex 3D environments suitable for video games and architectural walk-throughs. For obstacle avoidance, the algorithm considers both physical dimensions of the human and actions such as jumping, bending, etc. Path smoothening is carried out to keep the cell path as closely as possible to Euclidean straight-line paths