Adding NavMesh, Agents and Animation in Cocos2d-x
What is a NavMesh? It is short for Navigation Mesh and is the underlying data structure for path queries. Wikipedia defines it better,
A navigation mesh is a collection of two-dimensional convex polygons (a polygon mesh) that define which areas of an environment are traversable by agents. In other words, a character in a game could freely walk around within these areas unobstructed by trees, lava, or other barriers that are part of the environment. Adjacent polygons are connected in a graph. Path-finding within one of these polygons can be done trivially in a straight line because the polygon is convex and traversable. Path-finding between polygons in the mesh can be done with one of the large numbers of graph search algorithms, such as A*. Agents on a navmesh can thus avoid computationally expensive collision detection checks with obstacles that are part of the environment.
Many game engines support this for AI path-finding and to accomplish point-and-click movements in a strategy game. It naturally supports the idea of obstacles and non-traversable or differently traversable areas. We can construct the NavMesh by parsing the terrain geometry guided by parameters. Agents navigate the NavMesh constrained by their own set of parameters like velocity, acceleration, etc.
Cocos2d-x supports NavMesh and Agents, but I couldn't find and easy-to-follow documentation for beginners. The source code has samples that show a use case of these objects. The NavMesh class encapsules the Detour objects and expects a baked NavMesh in binary format along with a geometry file. Cocos2d-x lists recastnavigation as an external dependency accompanied by Detour for path-finding. We can see the expected header definition for the binary input in the mesh construction methods. Now, I just had to mimic/find the serialization in recast.
Luckily, Recast has a demo sample built on SDL, which offers a friendly GUI for Mesh construction and visualization. The Rasterization parameter influences the size of generated tiles as it influences the generation of voxels used to build the NavMesh. Agent Radius controls the boundary of the mesh, and Max Slope limits steep geometry. Users can also control the number of output tiles. 'Temp Obstacles' generates multiple tiled meshes and writes out the cocos-compatible all_tiles_tilecache.bin file on saving. Pressing the '9' key writes out the geometry file as %meshname%.gset. The file contains Off-Mesh links, which connect two disjoint NavMesh polygons or shortens an otherwise longer path. We use Off-Mesh links for a variety of effects, such as jumping and swimming. Configuring agents with a specific type can filter some entities while allowing others via the link. For example, only after learning the swimming skill, the player can cross the river and explore other islands.
The current workflow only supports non-dynamic meshes. We can make it dynamic with recast objects for a much larger open-world project like Gothic or Skyrim. Another strategy could be to use a TileManger object with a limited number of tiles around the player node, and as we move, we swap in new tiles for old ones and activate-deactivate AI agents. I will use this to build a basic RPG, a portfolio item focusing more on character design and mechanics. NavMesh optimization is not the focus area(at least for now).
The mesh can then be inserted into the game using a few lines of code. Scene object stores an internal pointer for the NavMesh, and the game loop is rigged to support locomotion. NavMeshAgent class wraps a dtCrowdAgent as a Component that can be added to a Node. It is parameterized to move with a certain velocity and acceleration and have an avoidance radius. If the acceleration value is low in some proportion to the velocity parameter with the custom implementation, the agent exhibits damped oscillations.
The RPG is mobile-based with the basic idea of a company of characters around a player unit. Characters are typical RPG with different stats and leveling up schemes. The player's level determines the size of its company. Touch inputs move the company around in search of enemy companies to conquer and level up.
To support the primary player interaction, one has to figure out the 3D coordinates of the screen-space point. Unprojecting the homogenized coordinate and casting a ray from the camera's position to the unprojected point gives us the required coordinate on terrain geometry. I used the physics engine for raycasting, and the hit-result is used to navigate a solo agent.
I got some rigged models from @Quaternius