I created a new demo application to test the HPF algorithm (it's the pathfindingtest app). In this application, there is a player controled actor (Cally), which can be moved around by the arrow keys. The map used in this demo is the Castle map, from CrystalSpace.
Here is a list of hotkeys for this application:
Once a navigation structure is either built or loaded, the mouse can be used to create paths. A left click will create a path between the actor's current position and the clicked position.
For the path following code, I used the pcmove.mover property, modified so the curves are sharp and precise instead of smooth. If the old smooth behaviour was used, there would be no guarantee that the actor would not walk out of the navigation meshes. The new behavior can be activated in any application that uses pcmove.mover, all that has to be done is set iPcMover::SetSmoothMovement() to false (the old behaviour is the default one).
I made a video of the actor moving around, being controled by the mouse, you can check it clicking here or in the image below (unfortunately, I was unnable to embed the video).
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.
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:
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.
* - 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.
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):
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.
|<< <||Current||> >>|