Nowadays, many applications are using virtual worlds. Those virtual worlds are generally populated with autonomous virtual characters which bring those environments to life. The autonomy of these virtual characters rely on their ability to navigate within a considered virtual environments. This navigation capability is essential as it will allow the character to discover its surrounding environment and to augment its potential activities within this environment. The virtual characters navigation is a well-known problem in many application fields using virtual environments. On the one hand, when dealing with interactive applications such as video games, the focus is set on the computation time in order to have a fast result. On the other hand, in the context of production methods, such as the animation movies, the final rendering will be produced offline but fast preview methods are generally used to obtain a first idea of the final result while avoiding heavy computation costs. In this thesis we proposed a new path planning solution for dynamic environments. The dynamic environments we consider have evolving configuration over time. This evolution is not known a priori which makes the navigation problem even harder. In order to address this problem, we first introduced a new representation of the objects which defines explicitly interactions between this object and a considered character, regarding its navigation capabilities. We have proposed an innovative solution by considering these dynamic objects both as obstacles and as a navigable element that a character can use during its navigation task. We then proposed a representation structure to catch entirely the topology of the global environment. We add to this representation temporal information concerning detected accessibilities and obstructions in the environment. We thus obtain , with no a priori knowledge, an anytime representation of the global topology which allows to deduce temporal properties of the environment. Finally, we present a path planning algorithm using all the temporal information available to compute a navigation solution for the virtual character in the dynamic environment. During this thesis, we designed a global method that allows a virtual character to autonomously identify a path within a dynamic environment populated of navigable elements disconnected both in space and time. Moreover, according to our computation time constraints, our method is efficient and compatible with interactive applications.
Path Planning and posture adaptation in Dynamic Environments