So, today is the last day of this year's Google Summmer of Code (although the date on the post will say it's August 17, it's still August 16 where I am =]). Time surely has flown by! I was really worried at the beginning of the program, there was a lot of code I had to get used to, and I still didn't know exactly how some things had to be done. But in the end, everything worked out, and I believe this project was a great success.
I was able to finish all the tasks that were on the original proposal, with minimal adaptations. I also documented everything as well as I could, both with comments in the code and posting the details in this blog. There are two demo applications as well, to show how the API should be used.
I would like to thank everyone from CrystalSpace for the opportunity, specially my mentor Andrew. People have been very helpful and friendly since our first contacts, during the GSoC applications period. I hope the code produced during this program can be put to good use.
Please feel free to contact me at anytime by mail. I will also stick around the IRC channel.
This last week I have made a few changes to the code, and I thought it would be good to make one post to talk a little about them.
First and most important, I found a problem with the demo application (not exactly a bug, more of a map misbehavior). If you plot a path going from the stairs in the basement01 sector to the basement03 sector, near the basement-dungeon sector, the path is likely to go below the stairs and through a wall. After careful examination, I realized this was actually caused by some parts of navigation meshes that were created below the stairs, due to the level geometry. Since Detour searches for the polygon nearest to the path's starting point, one of the polygons in this disconnected piece of mesh was being chosen, which caused the problem. In order to fix this, I altered the portal's polygon position for the portals that connect basement01 and basement03 in the world xml file, moving them up a little (the portal polygons were going below the stair level).
Here is the modified world file: link.
Second, I changed the DebugRender methods to return a list of csSimpleRenderMesh instead of drawing the structures directly using OpenGL. Notice that now you don't have to (read you shouldn't) call those methods every frame, only when the structure being drawn changes (you have to ask the iGraphics3D plugin to draw the meshes every frame, however).
Finally, I added another hotkey to the pathfindingtest application. Upon pressing 't', a path will be calculated between two predetermined points. This path will then be compared to a path previously calculated, and an error message will be displayed if they differ. If the paths are equal, nothing will happen.
I have added a new parameter to the iCelNavMeshParams class, polygonSearchBox. Here is a detailed description (copied from the parameter values post):
"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."
One simple way to understand this parameter using the demo application is clicking on a point that is not exactly on the navigation mesh. For example, consider clicking on the walls: the greater the y coordinate of the polygonSearchBox, the higher you can click on the wall and still have the path traced.
If some object changes position in a map, instead of rebuilding the whole navigation structure, one can update it using the iCelHNavStruct::Update() method. This method takes a bounding box and a pointer to a sector as parameters (although the sector is optional): the bounding box describes the area of the navigation mesh that one wishes to update, and the sector determines which sector should be updated. If no sector is specified, then the bounding box will be collided with each of the sectors navigation meshes' bounding boxes to determine what sectors have to be updated.
Note that this should probably not be used for objects that are on constant movement (npcs for example), since it's not very fast. This can be seen on the apppathfindingtest application by pressing 'y' (check last modifications to the demo application on this post).
Although updating a navigation structure takes some time, it is still way faster then rebuilding it.
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.
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.
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:
- b: Build the navigation structure.
- l: Load a previously built navigation structure.
- s: Save the current navigation structure.
- c: Clear the navigation structure, as well as the current path, if there is one.
- 1: Toggle navigation structures debug rendering.
- 2: Toggle destination point debug rendering.
- 3: Toggle path debug rendering.
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.
- 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.