A framework for navigation of autonomous characters in complex virtual environments

In order to create autonomous characters it is necessary to solve the problem of moving agents between two locations, at both the global and local navigation levels. Global navigation has two main components: the path finding algorithms being used and the space representation needed to abstract away the complexity of the static geometry. Once a path is found in a virtual environment, a local movement algorithm is applied to guide the agent through the free space representation from one way point to the next. This PhD dissertation therefore explores two areas: (1) new algorithms to automatically compute navigation meshes from complex virtual environments that can improve the global navigation; and (2) new methods to enrich the quality of the local movement given a general navigation mesh. The main goal of this thesis has been the development of a unified framework for the movement of autonomous characters in complex virtual environments, specifically aimed at those challenging applications that require a real-time response. In order to accomplish this goal, we first focused the research on developing a fully automatic system capable of generating a navigation mesh (a special space partition used for navigation) for any 3D scene represented as a polygon soup. Our system, entitled NEOGEN (from NEar-Optimal GEnerator of Navigation meshes) produces a navigation mesh that satisfies two very important requirements: it provides a near-optimal space subdivision and a tight adjustment to the input geometry. The first requirement is very important in order to minimize the computational cost of path finding, while the second is important for local movement. Realistic local movement requires an accurate representation of the walkable space that allows the algorithm to make a more realistic use of the environment by letting the characters move within the whole navigable space. We call our algorithm near-optimal since it almost always yields a solution in the lower fourth of the optimality interval. As presented in this dissertation, the autonomous navigation mesh generator has been built in several phases: (1) first we present a novel solution to compute a near-optimal partition for a 2D polygon with holes (NEOGEN-2D); (2) then we introduce a novel method to flatten the geometry given by a 3D polygon soup to obtain the 2D simple polygon with holes needed for the previous step; (3) next we present a method entitled NEOGEN-ML (the ML is for Multi-Layered geometry), to classify any 3D geometry into layers through a GPU based voxelization process, and then flatten each individual 3D floor. NEOGEN-ML provides 2.5D navigation mesh as it can handle multiple layers with a tight adjustment in 2D (X and Z axis) but not in Y; Finally (4), with the knowledge acquired at this stage of the PhD and being aware of the limitations of the voxelization phase, we present a final method, entitled NEOGEN-3D, which is a novel algorithm that can handle any 3D geometry and extract a navigation mesh that adjusts to the input geometry in its three dimensions. Taken together, our contributions are a powerful tool to ease the process of creating the navigation meshes needed to move characters in complex virtual environments. The final contribution is a real-time technique to compute paths with any desired amount of clearance that is independent of the underlying navigation mesh being used. Clearance values are used for both global navigation (discarding unreachable nodes due to the character's size) and local movement by strategically steering the characters. Attractor points for characters are set based on clearance, position and trajectory, thus guaranteeing that agents in a crowd will have different attractor points assigned. This reduces considerably the number of collisions between agents or against the static geometry, as well as obtaining a better usage of all the available space for navigation.Per tal de crear personatges autònoms, és necessari abordar el problema de fer que un agent es pugui moure entre dues localitzacions tant a nivell global com a nivell local. La navegació global té dos components principals: l’algorisme de cerca de camins i la representació de l’espai virtual que s’utilitza per abstreure la complexitat de la geometria estàtica. Una vegada hem trobat un camí dins l’entorn virtual, s’aplica un algorisme de moviment local que guia a l’agent a través de la representació de l’espai assignant diferents punts atractors (way points). Per tant, en aquesta tesi s’exploren dues àrees: (1) nous algorismes per calcular malles navegacionals de forma automàtica per entorns virtuals complexos; i (2) nous mètodes per millorar la qualitat del moviment local donat una malla navegacional general. L’objectiu principal d’aquesta tesi ha sigut el desenvolupament d’un framework unificat pel moviment dels personatges autònoms en entorns virtuals complexes. Primer ens hem centrat en desenvolupar un sistema automàtic capaç de generar una malla navegacional (un tipus de partició de l’espai emprat per navegació virtual) per qualsevol escena 3D representada com un conjunt de polígons. El nostre sistema, que té per nom NEOGEN (de NEar-Optimal GEnerator of Navigation meshes) produeix una malla navegacional que satisfà dos requisits molt importants: produeix una subdivisió quasi-òptima de l’espai i s’ajusta de forma precisa a la geometria original. El primer requisit és molt important per tal de minimitzar el cost computacional de la cerca de camins, mentre que el segon és important de cara al moviment local. Per aconseguir un moviment local realista, es necessita una representació acurada de l’espai que permeti als personatges utilitzar tot l’espai navegable disponible. Considerem que el nostre algorisme és quasi-òptim perquè gairebé sempre produeix una solució en el quart inferior de l’interval òptim. El generador de malles navegacionals s’ha construït en vàries fases: (1) primer presentem una nova solució per calcular una partició quasi-òptima per polígons 2D amb forats (NEOGEN-2D); (2) després introduïm un nou mètode per aplanar una geometria 3D representada com un conjunt de polígons, i obtenir el polígon 2D amb forats que necessita l’algorisme anterior; (3) a continuació es presenta un mètode anomenat NEOGEN-ML (ML és l’abreviació en anglès de Multi-Layered geometry) que classifica qualsevol geometria 3D en diferents capes, utilitzant una voxelització en GPU, i aplanant cada capa 3D de forma individual. NEOGEN-ML produeix malles navegacionals 2.5D ja que té un bon ajustament en 2D (X i Z), però no en Y; (4) finalment, amb el coneixement acumulat fins a aquest punt i essent conscient de les limitacions de la fase de voxelització, hem desenvolupat un nou mètode, anomenat NEOGEN-3D, que permet manegar qualsevol tipus de geometria 3D i extraure una malla navegacional que s’ajusta perfectament a la geometria original en les tres dimensions. En conjunt, les nostres contribucions són una potent eina per tal de facilitar el procés de creació de malles navegacionals, necessari pel moviment de personatges autònoms en entorns virtuals complexos. La contribució final és un mètode en temps real per calcular camins amb qualsevol quantitat clearance (distància mínima amb la geometria estàtica). El nostre algorisme és independent de la malla navegacional emprada. Els valors de clearance s’utilitzen tant a nivell global (descartant nodes inaccessibles degut al tamany del personatge) com a nivell local, calculant estratègicament la posició dels punts atractors. A més del clearance, el generador de punts atractors també té en compte la posició i trajectòria actuals del personatges, garantint que dos personatges tindran punts atractors diferents assignats. Això redueix el nombre de col·lisions entre agents i també amb la geometria estàtica, obtenint d’aquesta forma un millor ús de l’espai disponible per la navegació.Postprint (published version