Category: Hierarchical Pathfinding

2010-08-01

Saving and loading navigation structures

Permalink 07:21:22 pm, Categories: Navigation Meshes, Hierarchical Pathfinding  

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.

2010-07-26

Hierarchical pathfinding

Permalink 01:55:38 am, Categories: Hierarchical Pathfinding  

The basics of hierarchical pathfinding were already discussed in the post about the API (link). In this post, I'm going to talk a little about the implementation of HPF.

First of all, in order to build the high level graph that connects all portals, we needed a way to find a point that represents a portal. In the current implementation, the central point of the portal polygon was chosen. While this heuristic will give good results most of the time, it won't result in optimal paths. The difference in length to the shortest path possible will be more noticeable in a map that has very large portals. One alternative to reduce the effects of this problem is to create a number of points per portal proportional to it's size, relative to the agent size. However, while using more points per portal will result in more accurate paths, it will also cause a decrease in performance, so the number of points has to be chosen with care.

To find a path in the high level graph, we first need to add both the source and destination points to it, and then connect them to other nodes that share their sectors. We then calculate the path using A*. After the path is calculated, we remove the source and destination nodes from the graph, as well as any edges connected to them.

With the high level path calculated, it's time to refine it. For each two consecutive nodes in the high level path, we calculate a low level path segment using the Detour pathfinding. This step is done on demand: each time a user asks for the next node, either a new low level path segment is calculated or the next position of the current low level path is returned (if there is one).

In case the destination point is not reachable, the path to it's closest point in the navigation structure will be calculated.

2010-07-16

Changes to the graph plugin

Permalink 01:29:58 am, Categories: Hierarchical Pathfinding, Graph  

In order to implement the hierarchical pathfinding algorithm (hpf), I needed to create a graph representing the portals in a map, and then find shortest paths between pairs of points in this graph. Since CEL already has a graph implementation that meets these requirements, I decided to use it. However, I did find a few points where some changes had to be made to the code, as well as some bugs. Here is a list of all the changes (besides bugfixes):

  • Added a weight element to iCelEdge - Since the graph implementation was used for navigation, it was safe to assume the weight (or cost) between two nodes would always be the euclidean distance between then. This is not the case for hpf, however.
    The weight can be set using the edge's setter method, or using the new overloaded version of iCelNode::AddSuccessor(), which takes the weight as a parameter. The old version will still consider the weight to be the euclidean distance between the nodes.
  • Added a way to remove edges and nodes from the graph - Nodes can be removed using iCelGraph::RemoveNode(), while edges can be removed by either using iCelGraph::RemoveEdge() or iCelNode::RemoveEdge(). The methods used to create nodes and
    edges were also changed to return the index of the added element.
  • Added a way to create a new node for the graph - Nodes in a graph can now be created using the method iCelGraph::CreateEmptyNode().

Besides those changes, I also made an alternative implementation of the A* algorithm, since the one found in iCelGraph::ShortestPath() looked unfamiliar to me (meaning I don't belive its correct, but I'm not sure). It's possible the differences are due to some optimization I don't know about, but hpf already had a lot of issues to check, so I decided to be on the safe side. This new version of A* was based on this article and wikipedia. I believe it is the most general version of the algorithm, and it should present no problems. For now, I left this new implementation of the A* algorithm in iCelGraph::ShortestPath2(), as an alternative to the old one.

One important difference about the old A* implementation and the new one is that the path returned by the former doesn't contain the starting (current) position, while the later contains both the starting and ending position. I decided this was important, since the path could be inverted, in which case the destination could be missing.

Do note that none of these changes will break existing code that uses the graph plugin.

2010-06-12

The API

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.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.

October 2014
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

Search

Archives

Misc

XML Feeds

What is this?

powered by
b2evolution