Permalink 12:15:46 am, Categories: Navigation Meshes, Hierarchical Pathfinding  

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->SetSuggestedValues(1.0f, 0.2f, 45.0f);
// iSector* sector;
csRef<iCelNavMesh> navMesh;

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;

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.

Trackback address for this post:

This is a captcha-picture. It is used to prevent mass-access by robots.
Please enter the characters from the image above. (case insensitive)

Comments, Trackbacks, Pingbacks:

No Comments/Trackbacks/Pingbacks for this post yet...

This post has 8 feedbacks awaiting moderation...

Comments are not allowed from anonymous visitors.

January 2017
Sun Mon Tue Wed Thu Fri Sat
 << <   > >>
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

Leonardo RD's blog




XML Feeds

What is this?

powered by