-
Notifications
You must be signed in to change notification settings - Fork 20
Home
This is just draft of documentation. More will come soon.
Nav consists of 3 elements: navmesh, navigator, and explorer. Navmesh is responsible for building, modifying and storing navigation data. User can implement its own navmesh class based on this one to automatically feed data to the system. Navigator is responsible for pathing. User sets all movement parameters through this class. Each navigator is connected to single navmesh, allowing multiple agents to share the same exploration data. Explorer is responsible for automatic navmesh traversal. There is sample explorer built-in already with fast and pretty much human-like exploration algorithm. Explorer is optional, but when provided must be connected with navmesh and navigator. Navigation data consists of grid cells and cells. A single cell is just axis aligned cuboid placed in 3D. Grid cells are a form of spatial partitioning grouping cells which are inside its AABB.
The first step to using Nav is creating an instance of proper navmesh class and navigator.
Nav.Navmesh navmesh = new Nav.Navmesh();
Nav.NavigationEngine navigator = new Nav.NavigationEngine(navmesh);
Nav.ExplorationEngine explorer = new Nav.ExploreEngine.Nearest(navmesh, navigator);
By navigation data, I mean set of grid cells, each with cells belonging to it. Currently, new cells can be added with grid cells granularity with an assumption that no new cells will be added to a grid cell once it has been added to navmesh. Grid cells removal from navmesh is not implemented yet. Currently, cells must be associated with grid cells by data supplier. Automatic grid generation is not implemented yet as well. Of course, all cells can be as well placed in one huge grid cell for sake of simplicity. There are 3 ways of supplying navigation data.
A file consists of multiple lines where grid cells and cells belonging to them are defined. After each grid cell definition, there should be defined all cells belonging to it. Regions can be defined anywhere.
g 0 0 0 200 200 0
;g means its a grid cell following 6 values defines its AABB: min_x min_y min_z max_x max_y max_z
n 0 0 0 100 200 0
;n means its a cell following 6 values defines its AABB: min_x min_y min_z max_x max_y max_z
n 100 0 0 200 200 0
g 200 0 0 400 200 0
n 300 0 0 350 200 0
r 75 75 0 100 100 0 3
;r means its a region following 7 values defines its AABB and movement cost multiplier: min_x min_y min_z max_x max_y max_z move_cost_mult
Whole navigation state can be saved to file and loaded later (usually for debugging purposes).To serialize navmesh, navigator and explorer state call navmesh Serialize. The state can be restored using Deserialize.
A supplier should generate grid cell, fill it with cells overlapping its AABB and add it to navmesh using Add.
All updates and calculations are performed on separate threads, so there is no need for calling any kind of update function. Navigator needs actual agent position to properly track movement along an internally calculated path.
Navigator is responsible for getting an agent to the desired location. If a destination is outside navmesh, then path leads to the closest position on navmesh. User must update navigator with current agent position and destination. In return, he gets a go-to position.
There are 6 different destination types, however, only two of them can be explicitly set by user. Each destination has priority. Starting from most important those are:
- runaway (automatically set a destination to closest navigation-wise safe spot on navmesh)
- backtrack (automatically set when backtrack is enabled)
- user (set through Destination)
- custom (just like user but not cleared automatically when reached, set through SetCustomDestination)
- grid (automatically set when there is grid cell with ID matching one of those defined in DestinationGridsId available and reachable)
- waypoint (automatically set when there is waypoints path specified in Waypoints)
- explore (automatically set when exploration is enabled)
Thanks to priorities, there may be multiple systems setting destination, but navigator will lead agent to the most important one. Any destination except for custom is automatically cleared when agent is within given distance from it. For all destination types except explore and grid this distance is defined by Precision. In case explore and grid it is defined by ExploreDestPrecision and GridDestPrecision respectively. When destination is reached all registered navigation observers are notified. To register one user needs to implement inferface NavigationObserver and register instance of an object using AddObserver. When destination is reached and agent registered himself as an NavigationObserver callback OnDestinationReached will be called with destination position and destination type just reached. Similarly when destination cannot be reached OnDestinationReachFailed will be invoked for each observer.
Its best to refresh current position as frequent as possible (like each frame) for smooth navigation.
navigator.CurrentPos = new Nav.Vec3(agent_pos_X, agent_pos_Y, agent_pos_Z);
User can keep setting the same value as there is internal check whenever destination has actually changed. This destination overrides most of internal destinations (including exploration). When You just want to explore You do not need to set any destination. It will be set automatically.
navigator.Destination = new Nav.Vec3(dest_X, dest_Y, dest_Z);
Navigator automatically tracks agent progression on the path to current destination. This is the position that agent should move towards.
navigator.GoToPosition;
User can provide list of waypoints. Navigator will start from nearest waypoint on the list and continue through the list until all waypoionts has been visited.
Navigator automatically stores rough destinations history to allow backtrack. When backtrack is enabled navigator will follow path through those locations.
If any exploration engine is supplied during navmesh creation, exploration data in form of explore cells will be generated automatically. Explore cells, each with constant dimensions, will cover whole navmesh creating some kind of simplified navmesh. Exploration is nothing more than graph traversal. Keep in mind that this graph is changing with each new grid cells added to navmesh.
To alter exploration, user can specify so called hint position. Explorator will try to visit explore cells nearest to hint location first. This is useful when agent wants to get to given location, but navigation required to do so is not yet streamed in. Simple navigation may fail in some cases, as navigator is searching for best path given only present navigation data.
public class TestBot : IDisposable, NavigationObserver
{
public TestBot(Nav.Navmesh navmesh, NavigationEngine navigator, ExplorationEngine explorer, Vec3 pos, Vec3 dest, bool explore = false, int dest_grid_id = -1, List<Vec3> waypoints = null)
{
m_Navmesh = navmesh;
m_Navigator = new NavigationEngine(navmesh);
m_Navigator.AddObserver(this);
m_Navigator.CurrentPos = pos;
m_Navigator.Precision = 2;
if (dest_grid_id != -1)
m_Navigator.DestinationGridsId = new List<int>(new int[] { dest_grid_id });
if (waypoints != null)
m_Navigator.Waypoints = waypoints;
if (explore)
m_Explorer = new Nav.ExploreEngine.Nearest(m_Navmesh, m_Navigator);
Destination = dest;
}
public void Dispose()
{
m_Navigator.Dispose();
m_Explorer.Dispose();
}
public void Update(float dt)
{
if (!m_Destination.IsEmpty)
m_Navigator.Destination = m_Destination;
Vec3 dir = m_Navigator.GoToPosition - m_Navigator.CurrentPos;
float dist = dir.Length();
dir.Normalize();
//do whatever is necessary for a bot to move towards m_Navigator.GoToPosition
//in this example I just simulate movement by changing current position of bot
m_Navigator.CurrentPos = m_Navigator.CurrentPos + dir * Math.Min(SPEED * dt, dist);
}
public void OnDestinationReached(DestType type, Vec3 dest)
{
if (dest.Equals(m_Destination))
m_Destination = Vec3.Empty;
}
public void OnDestinationReachFailed(DestType type, Vec3 dest)
{
}
public void OnHugeCurrentPosChange()
{
}
public bool BackTrace
{
get { return m_Navigator.BackTrackEnabled; }
set { m_Navigator.BackTrackEnabled = value; }
}
public static float SPEED = 60;
private Nav.Navmesh m_Navmesh = null;
private Nav.NavigationEngine m_Navigator = null;
private Nav.ExplorationEngine m_Explorer = null;
private Vec3 m_Destination = Vec3.Empty;
}