Path Planning Technical Information
|
Overview
The HeroPath pathing system for HeroEngine, new in version 1.21, is implemented via server plugin components, and integrated as part of the Physics Server process. A NavMesh is created for each area, automatically updated when changes are made to the area. This HeroPath NavMesh then provides a server-side representation of the walkable area geometry, which can be used when other parts of HeroEngine request pathing data from one point to another.
Background
The major difference for this pathing system as compared to pre v1.21, is that it is entirely automated, and produces valid navigation data for the entire area; not just heightmaps.
This is accomplished by implementation of the algorithm published in AI Game Programming Wisdom 4, Automatic Generation of Navigation Meshes by John W. Ratcliff and published by Charles River Media.
The pathing system is implemented in the PhysicsServer.exe server process. This process is launched in two different modes:
- The Physics Server process, by default, connects to area server processes and provides collision detection and real-time pathing services.
- When the Physics Server process is launched in PathMaker mode, it acts as a dedicated service that will continuously build and maintain valid navigation meshes for all areas which have been edited.
Physics Server
The physics server process loads pre-computed navigation meshes (created by the PathMaker service) for any area needed. HSL script calls made on the area server are transmitted as pathing requests to the Physics Server to be processed. All pathing requests are asynchronous. When pathing results are available, they are transmitted back to the area server and then returned to the HSL script which made the original request. As many as 60 areas can all share a single Physics Server process. The Physics Server timeslices all pathing requests and can efficiently handle thousands of search requests per second.
The path search implementation uses an extremely high speed Astar implementation that is leveraged against a highly efficient navigation mesh. Searches can easily span vast distances without consuming an excessive amount of memory or CPU. Additionally, paths returned can be optimized using ‘string pulling’ which produces more direct path solutions and avoids zig-zag results.
Configuration parameters
In Master Control you can limit the amount of CPU given up by the Physics Server to provide pathfinding services:
- MAX_SOLVER_CPU, under ‘Default Parameters’, controls approximately what percentage of the CPU is used to respond to path finding requests. The default value is 25, for 25% of the CPU. This parameter can be adjusted on a per server basis. (See figure 1)
- MAX_PATH_BUILD_CPU, controls what percentage of the CPU can be used to rebuild pathing data as needed.
PathMaker
The PathMaker server process is dedicated to rebuilding the HeroPath navigation meshes as editing changes occur, and maintaining the queue of areas waiting to be rebuilt. Rebuilding a navigation mesh for a single area can be a time-consuming process, even if you assign 100% of the CPU available. Since we usually don’t want to use up all of the CPU on a single server, the PathMaker system will generally get a fraction of the total computing power available; thereby taking even longer to rebuild. For small areas, the navigation mesh can be rebuilt on the order of a few minutes. Extremely large areas could take hours to be recomputed.
Every single time an edit is performed on an area, the PathMaker server process notices the change to the Repository, and adds that area to a queue to have its NavMesh rebuilt. The PathMaker server process handles all such requests for a World (collection of areas) and can simultaneously rebuild pathing data for as many as five areas at a time, up to the amount of budgeted memory available (PATHMAKER_MAX_MEMORY).
Note: Since rebuilding navigation data can take a substantial amount of time, the server-side representation of the area geometry may occasionally be out of synch with the live area. The Physics Server will always load the most recently available version of the navigation mesh to use.
To see which areas are in the queue to be processed, view the status page of the PathMaker server in Master Control. This also displays the state of the rebuild phase for each one. (See figure 2)
The PathMaker server produces two additional data assets which accompany the ‘area.dat’ file. The first is ‘area.pth’. This file simply indicates the current version number of the navigation data, and consists of three lines of text:
[SETTINGS] /world/areas/102377190275/area.ai=2 build_version=106
The file ‘area.pth’ is in the format of a standard .INI file:
- The first line indicates the ‘settings’ section.
- The next line records the version number of the area.dat file that the navigation mesh was built against. Each time the version number of an area.dat file changes, then the corresponding navigation mesh must be rebuilt to match.
- The next line ‘build_version’ indicates the master version number (i.e. format) of the navigation mesh. Occasionally the format of the navigation mesh data may change and, if it does, this master version number will be bumped. When this occurs, all outstanding navigation mesh data will be rebuilt to match the new format.
The second file is the actual navigation mesh data itself. This is a binary file which contains all of the nodes and connections describing how to navigate the space of an area. The file will always be called ‘area.ai’ and will be in the same location in the repository as the corresponding ‘area.dat’ file.
When the PathMaker server rebuilds a navigation mesh, it does so based on a set of rules which are defined in a master INI file called ‘DefaultNavMesh.ini’. This file is located in the root folder of your Repository. The first time a PathMaker server is ever spun up, if this file does not exist, then it will create a default one to use.
This file describes the rules which are applied when a navigation mesh is built. Great caution must be taken before making changes to this file, as it is easy to configure it in ways that would produce explosively large navigation mesh files. It has been pre-configured and tuned to work with the default character controller in HeroEngine.
With the 1.22 release of HeroEngine, there is only a single navigation mesh file available for any given area.
Currently you can edit the default settings, but it is strongly advised to do so with great caution and consultation before making the change.
The settings in the ‘DefaultNavMesh.ini’ file are as follows:
- build_version : This is the master version number of all pathing data. If you make a change to any of these rules which would invalidate your old navigation mesh data, then you should bump this version number up by one. This will force each navigation mesh to get rebuilt using the new set of rules.
- terrain : true/false. This indicates whether or not navigation mesh data should be generated on heightmaps. It is doubtful you would ever set this to be false unless, for some reason, no pathing on terrain would ever be necessary.
- non-terrain : true/false. Non terrain is anything in the area which is not terrain, water, or underwater. Generally speaking this corresponds to mesh objects in your world. In most cases you would want this to be true unless, in the context of your game design, you never want pathing to occur on anything other than heightmaps.
- water : true/false. This option indicates whether or not navigation mesh nodes should be generated on the surface of water. Additional work on the character controller would be necessary to take full advantage of this feature.
- underwater : true/false. Indicates whether or not navigation mesh nodes should be generated on surfaces which are below water. These nodes would be used for creatures which are capable of walking underwater, as opposed to swimming only on the surface. Additional work on the character controller would be necessary to take full advantage of this feature.
- dive_down : true/false. Indicates whether or not connections should be generated between water surface nodes and underwater nodes. This would allow path searches to consider diving down to the bottom of the underwater surface when producing solutions. Additional work on the character controller would be necessary to take full advantage of this feature.
- swim_up : true/false. Indicates whether or not connections should be generated from underwater nodes up to nodes on the surface of water. This would allow path searches to consider swimming up from the bottom as part of the solution. Additional work on the character controller would be necessary to take full advantage of this feature.
- avoid1-4 : true/false. Indicates whether not navigation mesh nodes should be generated on objects marked as ‘avoid1’ through ‘avoid4’. Generally speaking this option would never be set to false, as the ‘avoid1’ flag is used primarily to steer pathing requests.
- prefer1-4 : true/false. Indicates whether not navigation mesh nodes should be generated on objects marked as ‘prefer1’ through ‘prefer4’. Generally speaking this option would never be set to false, as the ‘prefer1’ flag is used primarily to steer pathing requests.
- character_capsule : true/false. Indicates whether or not the character controller is to be modeled as a capsule or a box. The default character controller settings in HeroEngine are modeled as a capsule.
- character_width : Indicates the width of the character controller. The default value of 0.03 matches that used by the default character controller in HeroEngine. If you have modified the character controller width in your game, you would want to match the size change here.
- character_height : Indicates the height of the character controller. The default value of 0.19 matches that used by the default character controller in HeroEngine. If you have modified the character controller height in your game, you would want to match the size change here.
- character_step_height : Indicates the step height of the character controller. The default value of 0.04 matches that used by the default character controller in HeroEngine. The character_step_height defines how high a character controller can ‘step onto’ a higher surface (example walking up stairs). If you have modified the character controller step height in your game, you would want to match the size change here.
- node_granularity : Describes the detail level of the navigation mesh nodes. Note that the default value of 0.03 matches the character width. This is a value which should be tuned extremely carefully! If you were to make it just a tiny bit smaller it could easily produce a navigation mesh that is far too detailed and could take forever to build and consume a massive amount of memory. However, it is generally safe to make it larger. In general you want the granularity to be as large as possible while still producing navigation mesh nodes in the tightest spaces a character could walk. Matching it to your character width is generally a safe bet.
- node_min : The minimum size of a valid navigation mesh node. The default value is 3 which indicates 3 times the node_granularity value. Making this number smaller would be dangerous as it would explode the number of navigation mesh nodes produced. It is always safe to make it larger. As you can see the node_granularity and the node_min value work together to define the smallest space that will be represented by the navigation mesh.
- node_max : This value defines the maximum size a single navigation mesh node should be. This number cannot be greater than 63. The actual maximum size is equal to node_max*node_granularity. In general you want this number to be large, as it reduces the density of the navigation mesh substantially and represents large open spaces more efficiently. However, very large nodes can limit the detail of the search space to some extent.
- connection_search_distance : This describes the distance to search for neighboring nodes when building connections. If you change your node granularity and node maximum sizes, you might want to adjust the search distance accordingly, though the default value should work fine in most cases.
- connection_search_count : This defines how many neighboring nodes will be considered for building connections. The default is 20 and probably more than sufficient in all cases. These parameters probably do not need to be tuned in most cases.
- connection_max : This is the maximum number of connections to keep between any one navigation mesh node and another.
Plugin components
HBPathSystem
HBPathSystem is the central plugin-component that manages path building and path solving requests. The pathing system plugin was designed so that different pathing solutions could be supported. Currently only a single implementation is integrated, though plans to support AISEEK and possibly other SDKs is still an option for the future.
The public interface specification for HBPathSystem is located in. .\he_plugins\include\HBPathSystem\HBPathSystem.h The implementation of the HBPathSystem plugin is located in .\he_plugins\src\HBPathSystem
HBPathSystem_AIWISDOM
The specific implementation of the pathing system which uses the algorithm presented in AIWisdom4 is provided.
The implementation can be found in:
.\he_plugins\src\HBPathSystem_AIWISDOM
AIPathFind.h and AIPathFind.cpp contains the source code that manages path solution and queries against a previously built navigation mesh.
AIPathMaker.cpp and AIPathMaker.h contains the source code that builds and handles edits to navigation meshes.
StringPull.cpp and StringPull.h contains the source that produces straight-line paths whenever possible and remembers those results to speed up future queries.
HBPathSystem_AIWISDOM.cpp contains the implementation of the HBPathSystem pure virtual interface.
PathMaker plugin
This plugin manages the process of rebuilding navigation mesh data in correspondence with all outstanding area editing changes.
The public interface specification is located in:
.\he_plugins\include\PathMaker\PathMaker.h
The implementation is located in:
.\he_plugins\src\PathMaker\PathMaker.cpp
Path Planning panel
- Main page: Path Planning panel
The Path Planning panel allows developers to visualize the navigation mesh data and edit the ‘DefaultNavMesh.ini’ file as well as test pathing solutions.
