I first heard about navmeshes in class when professor Hogue showed us a video of Resistance 2, created by Insomniac games, and how the developers used navmeshses in the game. So what is a navigation mesh or navmesh? A navmesh is a path that is defined as a series of nodes. The path is used for characters and objects to travel through without running into problems or obstacles. Here is an example. Say the game you are building takes place in a forest. You want the AI to intercept the player somewhere in the level. So the AI's destination is the player. If it is told to just walk from point A to B it will clip through obstacles and look unrealistic. It would pretty much look like the AI is a ghost walking through walls directly to reach the player. A navmesh can be used for the AI to walk intelligently throughout the forest and still reach its destination (the player). This can be achieved by placing nodes throughout the level that the AI can go to. Another interesting way to look at it is through tiling on the ground. Treat each tile as a node that you can travel to. If there is something on top of the tile you clearly can't step onto it.
In the picture above, you can see two path. They both start and end at the same point. In the green line you can see that AI unrealistically clips through the wall, its trying to find a short path so it cuts corner. The yellow line depicts the AI following the path more realistically using the nodes from the navmesh. The AI object also travels the shortest distance to get to the end node and doesn't take unintelligent routes.
Insomniac Games have created many popular AAA games. Resistance: Fall of Man, Resistance 2, Ratchet and Clank, and even some of the Spyro games. After doing some research, I was able to find some of the ways they used navmeshes through these games, how they worked, and some of the problems they faced.
Ratchet and Clank
Lets start with their work in Ratchet and Clank. The navmeshes were very basic at first and were hand made by the designers of the game. They would create the mesh and set the nodes for a specific destination they wanted the AI to travel on. They used the A* algorithm to make them travel from point A to point B. Using a handmade navmesh helped the game by making less run-time calcualtions because they didn't use the geometry from the level, they just set specific nodes.
Resistance
For Resistance, Insomoniac decided to keep the same method. They created the navmeshes again by themselves in Maya and used that data to build a convex poly mesh at run-time. They wanted to again use A* path finding but they ran into some problems. Only 8 objects could run on the mesh at any given time. The cause of this was because of bottle necking on the physics processing unit.
Resistance 2
In Resistance 2, Insomniac had to improve on their bottle necking problems on the PPU. They didn't just fix the problem though, they revolutionized the way they use their navmeshes. they created multiple navmeshes in the level. They placed them in clusters and in different heights of the level. They accounted for the size of particular enemy AI units (some were big, some were small) and were also parametrized to account for the characters jumping to higher and lower places on the map. How they did all of this was by using a
3-sided poly mesh instead of a 8-sided poly mesh. This prevented any
overlapping within the polygons of the mesh to not cause any problems with
the A* navigation used. They then combined path caching with A* to improve their path finding.
In conclusion, navigation meshes create immerse experiences for players by adding intelligent and fun non playable characters in the games they play. Insomniac has done a great job of showing how they incorporate such great methods of path finding in their games and they keep on improving how they do it.
No comments:
Post a Comment