Leonardo RD's blog

In order to showcase the updating capabilities of the navigation structure, I have added a large stone block to the initial sector of the path finding demo application. This block moves linearly back and forth between two points near the stairs, and it is taken into account when building the navigation structure.

Stone block and the hole left behind when the navigation structure was built.

I also added some new hotkeys to this application, here is a description:

• '4' - Toggle stone block rendering.
• 'u' - Update the area of the navigation structure where the stone block is.
• 'y' - Toggle auto-updating for the area where the stone block is. When this is turned on, the navigation structure will be updated every frame.

Although building navigation structures only take a couple of seconds (at least for the maps in CrystalSpace), it's important to be able to save and load them to/from files.

Since the navigation structures are composed of one navigation mesh for each sector and some extra information (like the name of the sectors contained in the navstruct and the high level graph), I decided the best way to save them was creating a zip file, containing one file for each navmesh and one file with some general information. These files are all serialized to XML.

To save each navmesh, the iCelNavMesh::SaveToFile() method is used. It receives as a parameter a iFile, which is where it will save the data to. To save navigation structures, iCelHNavStruct::SaveToFile() is used. This is the method that will probably be called by the user. It receives a pointer to the virtual file system and a char array as parameters, and will save the zip file in the current directory of the VFS, with the name described by the char array.

To load navigation structures, iCelHNavStrucBuilder::LoadHNavStruct() is used. It receives a pointer to the VFS and a file name, just like the SaveToFile method, and expects the file to be on the current directory of the iVFS received. It will open the zip file, read the main file and then call iCelNavMeshBuilder::LoadNavMesh() for each navigation mesh. It's important to notice that the load methods are in the builder classes, so the only way to create (either new or load) both navigation meshes and structures is from the builder classes.

In the demo application, loading the navigation mesh for the castle map is significantly faster then building it.

In order to build a navigation mesh, all Recast needs are the triangles that form the meshes that compose the map. So, to build the navmesh for terrain meshes, I had to triangulate the terrain. This was done using the iTerrainSystem mesh interface. Meshes of this type have a collection of cells (iTerrainCell objects), which are further divided into a finer grid. These cells have a method for querying the height of the grid at a specific point (iTerrainCell::GetHeight()).

Once I had the grid size and a way to query the height, triangulating the terrain was trivial. The only thing that may cause some confusion are the triangle indices, since the terrain cells don't use the default coordinate system.

Here are a few screenshots of the navigation meshes built for the terrainf map, from CrystalSpace:

Navigation mesh for the terrainf map

Navigation mesh for the terrainf map

The Recast and Detour toolset has a lot of parameters to set. In CEL's implementation, those parameters can be found on the iCelNavMeshParams class. But what values should be used for them? This post contains a very brief description of the parameters and a compilation of tips found either on the documentation for Recast and Detour or at Mikko's blog (http://digestingduck.blogspot.com, for some reason I can't link it here). Also, for more information, be sure to check the Recast and Detour discussion group.

• AgentHeight and AgentRadius: These values represent the bounding cylinder of an agent. For example, if we wanted to represent a human (using meters as unit), we could use AgentHeight=2.0 and AgentRadius=0.4.
• AgentMaxClimb: The height of the tallest step an agent can walk over. Following the previous example, we could use an approximate value of AgentMaxClimb=0.6 for a human.
• AgentMaxSlopeAngle: The maximum surface inclination where the agent can walk, in degrees. In our example, a value of 45.0 would be appropriate.
• CellSize: The size of the voxelization cell*. Smaller values give higher navigation mesh accuracy, at the expense of higher computation time. Good values generally range from AgentRadius/3 to AgentRadius/2.
• CellHeight: The height of the voxelization cell*. Smaller values give higher navigation mesh accuracy, at the expense of higher computation time. Generally, a good value is CellSize/2.
• MaxSimplificationError: When the rasterized areas are converted back to vectorized representation the MaxSimplificationError parameter describes how loosely the simplification is done (the simplification is Douglas-Peucker, so this value describes the max deviation in voxels). Good values are between 1.1-1.5 (1.3 usually yield good results). If the value is less, some strair-casing starts to appear at the edges and if it is more than that, the simplification starts to cut some corners.
• DetailSampleDist and DetailSampleMaxError: These parameters define how the navigation mesh is tesselated**. Sample points are generated inside the polygon. If the difference of height between one of those points and the height of the navmesh at that location is greater then DetailSampleDist, that point gets added to the mesh. DetailSampleMaxError controls the maximum allowed error when the mesh or poly outline is simplified. If both parameters are zero, the mesh won't be tessellated. For more details, look for the posts about "Navmesh Height Accuracy" on Mikko's blog.
• MaxEdgeLength: Maximum edge length for the navmesh polygons. A good value is something around eight times the agent radius in voxels (8 * (AgentRadius / CellSize)).
• MinRegionSize: Minimum isolated region size that is still kept after watershed partitioning***. A region is removed if the regionVoxelCount < minRegionSize * minRegionSize. The default value used in the SetSuggestedValues method is 20.
• MergeRegionSize: Maximum region size. The regions derived from watershed partitioning*** are merged. If regionVoxelCount > mergeRegionSize * mergeRegionSize, the region is not allowed to be merged with another region anymore. The default value used in the SetSuggestedValues method is 50.
• MaxVertsPerPoly: Maximum number of vertices per polygon of the navigation mesh.
• TileSize: Tile size****.
• BorderSize: Border size***** for the navigation mesh, in voxels. A good value is the agent radius in voxels, plus some padding ((agentRadius / cellSize) + 3).
• PolygonSearchBox: Before creating a path, Detour finds the closest polygons in the navigation mesh to the origin and destination points. This parameter determines the dimensions of the bounding box where Detour will look for the closest polygons. The bounding box is represented by two vertices: (center + polygonSearchBox) and (center - polygonSearchBox), where center is the point one wants to find the closest polygon to.
  This parameter is also used to determine if a low level path that was calculated by Detour reaches it's intended destination (Detour always returns a path, either to the destination or the closest possible point). If the distance between the two points, in each of the coordinates, is less then this parameter, then they are considered to be close enough for this purpose.

* - Recast calculates the walkable area of a map by voxelizing the triangles of the meshes that compose it.
** - At some point, the navigation mesh is tessellated in order to get more accurate values for the height.
*** - Watershed partitioning is used to group the walkable voxels and form the navmesh polygons.
**** - The navigation mesh is divided in tiles that can be rebuild, loaded or saved independently. We can, for example, update a navmesh to account for a dynamic object by changing only the tiles this object is into.
***** - Recast leaves a border about the size of the agent radius out of the navigation mesh, so it can guarantee any straight path cast inside the navmesh is valid, and the agent won't go through a wall when walking on it.

In order to help getting some initial results, the iCelNavMeshParams class has a method called SetSuggestedValues. This method receives as arguments the AgentHeight, AgentRadius and AgentMaxSlopeAngle, and either derives from that some initial values for the other parameters or gives them a default value. Using the values from this method may not generate a perfect navigation mesh, but will at least give a base to work on.

One of the most annoying problems that comes from building one navigation mesh for each sector is that a gap is formed between two navmeshes, near a portal. In a nutshell, this problem occurs because Recast subtracts a border from each navmesh (for more details, see the post before this one).

In order to solve this problem, I created a "fake corridor" of triangles for each portal, going out of the map in the direction of the portal's normal. This corridor is like an extrusion of the portal's polygon, going in the direction of it's normal. This way, the border is subtracted from this fake corridor instead of the walkable map.

The portal's polygon is a planar convex polygon. For each of it's vertices v, another vertex was created at the position v + n * b, where n is the portal's normal and b is the navmesh's border size. Triangles were then created to connect these new vertices to the old ones (two triangles for each of the polygon's edges). The triangles were defined clockwise for an observer inside the corridor formed.

This approach successfully closed the gap between navmeshes from adjacent sectors, as can be seen below:

Door between two sectors, before and after applying the fix.

One important thing to notice is that some parts of the navigation mesh are not visible. In the current state of the test application, only the navmesh of the sector the camera is on is visible. This happens because of the way portals are handled in some maps (including the castle map used for this application): when a portal is visible, the sector it connects to is first rendered to a texture, which is then applied to a portal mesh. Since there is no connection between the navmeshes and the sector, the later are not rendered to this texture. So, in order to take this screenshot, I positioned the camera right between the two sectors, causing both sectors to be rendered directly.

At first sight, there is no simple way to make all meshes visible without altering the rendering engine. So, for now, I'll probably leave this problem as it is. On my project proposal, I allocated the last week to polishing the demo application, so maybe that would be a good time to try and fix this.

Since I am now able to produce some nice looking screenshots, I think this is the right time to talk about the current state of the project.

I'm using the castle map for the example application, since each of it's rooms is a different sector. I have tweaked the colors from the default debug rendering code used in the Recast & Detour demo application, so it would look different and a little more visible in the map used. Here are a few screenshots: (light yellow edges for tile borders, dark yellow for other polygon edges).

Navigation Mesh for the reception

Navigation Mesh for the throne room

Navigation Mesh for the basement dining area

Although it can't be seen from the examples above, even though I'm rendering all the navigation meshes at every frame, I cannot see navigation meshes through a portal. I don't know why that is happening, specially since the navmeshes are rendered directly with opengl, but I'm not worrying too much about it now.

There is still one problem related to building the navmesh. In order to make sure that a unit can walk in any straight path cast inside the navmesh, Recast removes a border proportional to the unit's radius from the navmesh (so the unit won't go inside a wall, for example). Since the navmeshes are being built independently for each sector, this generates a gap between two sectors where the unit can't move to.

The picture below is the bottom part of a door, which is a portal between two sectors. Notice that there is an area that should be walkable, but has no navmesh over it:

Gap between two sectors

Recast uses the triangles from the collision detection data to build the navigation meshes. In order to fix the gap, I plan to feed Recast with some "fake" triangles, normal to the portal. This way, the border will be subtracted from these "fake" triangles instead of the walkable area.

Path-finding

In order to be able to see a path in the example application, you have to first set a source point (shift + left click) and a destination point (left click). The points are graphically represented by a cylinder, which has the same height and radius of the unit used to build the navmesh. Right now, the path is only calculated correctly when both points are on the same sector. Here are a few screenshots: (blue cylinder is source, green is destination)

Path example 1

Path example 2

In this post I'll talk a little about the division between the navigation mesh API and the hierarchical navigation structure API (fancy names, what do those mean?).

The main objective of this project is to use Recast to build navigation meshes for Crystal Space maps. In Crystal Space, we have Sectors, which define an area in space where we can put geometry. Generally, a map is composed of a collection of sectors. These sectors are then connected by Portals.

In order to build a navigation mesh for an area using Recast, we need all the triangle locations from the collision detection meshes that are inside that area. However, in Crystal Space two or more sectors can share world coordinates, so we cannot use Recast directly to build the navmesh for an area formed by more then one sector.

That is where the Hierarchical Navigation Structure comes into place. The idea is that we build independent navmeshes for each sector, and have a higher level structure connecting these navmeshes. In our case, this structure will be a graph, where each node represents a portal. In this graph, edges exist between two nodes if the portals can be connected by a path, and the edge weights represent the smallest possible length for such paths.

Finding a path in this structure takes two steps:

• Find out which portals we will have to cross to reach our destination. This is done using the A* algorithm in our high level graph. With this information, we also know which sectors the path will go through.
• For each sector our path goes through, we find the part of our path that is inside that sector.

Here area a couple of examples of how to use navigation mesh API. It's important to keep in mind that one probably won't use these interfaces directly, but will rather use the hierarchical version (unless one's map only has a single sector).

Creating a navmesh:

csRef<iCelNavMeshBuilder> navMeshBuilder = csQueryRegistry<iCelNavMeshBuilder>(object_reg);
csRef<iCelNavMeshParams> params;
params.AttachNew(navMeshBuilder->GetNavMeshParams()->Clone());
params->SetSuggestedValues(1.0f, 0.2f, 45.0f);
navMeshBuilder->SetNavMeshParams(params);
// iSector* sector;
navMeshBuilder->SetSector(sector);
csRef<iCelNavMesh> navMesh;
navMesh.AttachNew(navMeshBuilder->BuildNavMesh());


Finding a path:

csRef<iCelNavMeshPath> path;
// csVector3 origin, destination;
path.AttachNew(navMesh->ShortestPath(origin, destination));


The hierarchical navigation API is very similar to the navigation mesh one. Here are the equivalent examples from the two above:

Creating a navmesh:

csRef<iCelHNavStructBuilder> navStructBuilder = csQueryRegistry<iCelHNavStructBuilder>(object_reg);
csRef<iCelNavMeshParams> params;
params.AttachNew(navStructBuilder ->GetNavMeshParams()->Clone());
params->SetSuggestedValues(1.0f, 0.2f, 45.0f);
navStructBuilder ->SetNavMeshParams(params);
// csList<iSector*> sectorList;
navStructBuilder ->SetSectors(sectorList);
csRef<iCelHNavStruct> navStruct;
navStruct.AttachNew(navStructBuilder->BuildHNavStruct());


Finding a path:

csRef<iCelPath> path;
// csVector3 origin, destination;
// iSector* originSector; iSector* destinationSector;
path.AttachNew(navStruct->ShortestPath(origin, originSector, destination, destinationSector));


The complete APIs can be seen here: Navigation Mesh API and Hierarchical Navigation Structure API.

I'll talk more about the iCelNavMeshParams structure and how to find the values for it's parameters in a later post.