G.E.D. blog#3 - Navigation of A.I.

The use of A.I. is to give the illusion of human behaviour in game, and most of the time developers achieve this by using if statements and state-machine design. However, this still cannot cover everything and it would result in bad A.I.
http://www.youtube.com/watch?v=mgWhF1WkBJk

The above clip shows the some of the poor performances of A.I.. The characters reacts to the situation, but they are not sensing the player nor dynamic enough to make decisions. So today lecture we talked more about A.I. behaviour and watched the presentation from Reddy Sambavaram who participated in the game project of Deadlocked, Resistance: Fall of Man, etc.

Nav-Mesh
Reddy suggested the idea of using nav-mesh to help navigating the NPCs move around map in more flexible and dynamic manner. A nav-mesh is basically an abstract data structure to help finding path in large space, filter out the obstacle, and reduce the effort of calculation.

A.I. basically uses the path generated from nav-mesh and follow it rather than doing all the collision detection as it moves. One of the benefits of using nav-mesh is to make A* algorithm's job easier by giving its data to generate path faster. The mesh will provide node data to A* as the picture below. Reddy's development team removed the hierarchical  path-finding to attempt to remove some of its issues. However, they put it back at the end because nav-mesh would able to make it more efficient.

Although nav-mesh reduces the effort for path finding, there is still difficulty for A.I. to turn around corners. The red line in the below image illusrates a faster path to cross the map, but there is a sudden change of direction as it passes through a corner or it stays really close to the boundary of the mesh. This might cause flickering animation as the path has conflict with the collision detection system.

In order to solve this problem, Reddy introduces his solution by using Bezier curve. It simply takes the point of the direction the character is facing and the point locates in the opposite side from the turning path. It would allow character to have more space before making the turn. After using Reddy's solution, the character will have more room to make turns as illustrated in the following where green line is the controls of the bezier curve and orange line is the new path.

Through the use of nav-mesh, A.I. is able to select multiple paths and perform different behaviours depends on the situation. In the example Reddy used, meshes are located at different level. By using a custom link  that is set in between levels, it becomes one of the options for character to cross river.

As shown in his slide, when multiple characters collide together, they are able to figure out an alternative path through the use of pre-determined custom links between meshes at different level (Slide 34 http://www.insomniacgames.com/assets/extras/flash/Navigation.swf).

Another advantage of using nav-mesh is that it is convenient when it comes to level design. Designing level becomes more efficient as designer can change the nav-mesh easily according to the level. In the example Reddy provided, the designer decides to remove the wall while the nav-mesh is already defined, however, he/she is able to alter the nav-mesh easily to match the new design in Maya.

A designed level and nav-mesh

Wall is deleted and nav-mesh is hidden

The new layout of the level with the old version of nav-mesh

Nav-mesh covers the empty area with a few easy clicks

Overall, I learned about the implementation and the experience of using nav-mesh through Reddy's presentation. With the use of navigation mesh, dynamic A.I. becomes more possible and changing the implementation of nav-meshes opens up a variety of possibility for specific scenario.