Insomniac Games GDC Presentation: AI and Navigation Meshes

Insomniac Games GDC Presentation: AI and Navigation Meshes

    In class, we had a video presentation from Insomniac games and there AI and Navigation Meshes which they use within there games, like Resistance and Ratchet & Clank.  He talked about how adding in navmeshes allows to solve problems in constantly evolving worlds, and adds more life-like AI for NPC's.

    He starts off by talking about how the implemented navmeshes in Ratchet & Clank: Deadlocked for the PS2.  These nodes were made by the designer, and then were used as nodes for the A* algorithm.  He then talked about navmeshes and their use in Resistance: Fall of Man, which was a PS3 launch title.  These navmeshes were also designer laid, in maya.  They then had tools which built a convex poly mesh for runtime.  The volumes were again, used as nodes which were navigated through by the A* algorithm.

    He then moved on to how they corrected cornering, for a smooth continuous motion.  They implemented a Bezier curve for modified smoothing around corners.  Curve Tangents were ensured within the NPC mesh, so they applied the bezier algorithm within the pathfinding.  They NPC would then follow along this corrected path, allowing for a much seamless and realistic movement around corners.  This helped avoid the look that a character would be on "rails" and making rigid course correction.

    Then, the topic moved onto custom links, which detailed jumping, ladders, and other environmental objects which the AI could use to navigate through the level.  Originally, this was done with point-to-point links, however, the problem with this was that it was unfriendly to changes, does not fit nicely with the A* algorithm or smoothing and causes issues with dynamic objects near the links.  How Insomniac tackled this was by creating custom-clue-boxes, which would denote an action that can be taken, and outfitted with custom-clue-edges.  These edges could be represented within A* as nodes.  This would then allow an NPC to approach an area, then receive information through these custom-clue-boxes on what action can be taken here, and follow through with said action.

    Finally, he went into how they generated their nav meshes.  The first thing they would do would generate world geometry into a voxel grid.  Then, they would build navigable voxels, filter and smooth them and then erode the resulting navigable voxels.  In their third step, they would build watershed partitioning.  This is done to indicate region boundaries.  They would build the distance transforms, making each catchment basin a mesh chunk.  In the fourth stage, they would trace the catchment basin's contours, forming the nav mesh chunk's boundary edges.  In the last stage, they would triangulate/tesselate to create the nav mesh.  The issues they ran into however, were undesired nav-meshes.  To fix this, they created custom override polygons, which would negate the undesired nav-meshes.

    In conclusion, I found the fact that they continue to evolve navigation meshes from what it is today fascinating.  I'm very interested in the advancement of AI, both in games and in other applications, and look forward to what they will be implementing in the next gen.