Path Planning Technical Information

From HEWIKI
Jump to: navigation, search


Contents

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:

Figure 1 : Master Control configuration path

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

Figure 2 : The status page of the PathMaker process in Master Control, showing the status of navigation mesh generation.

In Master Control you can limit the amount of CPU given up by the Physics Server to provide pathfinding services:

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


DefaultNavMesh.ini

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:

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
(Figure 3 : The Path Planning Panel in HeroBlade

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.

See also

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox