Navigation Mesh Dynamic Obstacle Splittery Technical Overview

Overview

In lots of situations it is useful to be able to affect the mesh (and the state of AI navigation) at runtime based on dynamically changing situations. This document outlines how this is done with the navigation mesh system.

High level overview

The basic idea is that Interface_navmeshpathobstacle provides the user with an interface for specifying shapes which the Navigation Mesh should be split around. Whenever a new obstacle enters the game world that the AI needs to navigate around, the user calls RegisterObstacleWithNavMesh() which will then determine which polygons in the existing mesh are affected by this obstacle, and split them around the shape provided if necessary.

Consider the image below:

In the image the default mesh consisting of four polygons is split around the shape of an obstacle taking the shape of a cube. Your obstacles can be more complex than this, and off axis even. The only restriction here is that the shape provided is convex.

Hierarchy: When the mesh is split around obstacles, what it's really doing is creating a new mesh in place of existing polygons. In this way it forms a sort of hierarchy which is consulted whenever AIs use affected polys. When pathfinding through a polygon which has an intermediate (or imposter) mesh, that sub-mesh will be consulted and pathed on rather than just pathing from that polygon's edges.

Build on-demand: When an AI requests to path through a polygon which has been tagged as affected by an obstacle, if the poly has not yet been split about that obstacle it will be split at that time. This is not done right after obstacle registration. This is to alleviate the cost of obstacle registration somewhat. For example if you had an obstacle which was being registered and unregistered with the system very frequently, the expensive part of dealing with this obstacle would only be done when an AI was in need of affected mesh data.

Additionally once the poly has been split there is no additional cost associated with pathing through that geometry. This means that registering obstacles only incurs a computational cost once. Also since the parent structure of the mesh is not being changed, when an obstacle is removed returning to the original makeup is virtually free.

The nitty gritty

For a very simple example of a path obstacle consider NavMeshObstacle (NavMeshObstacle.uc)

Here you will see some kismet logic for enabling/disabling the obstacle.. but the interesting part is this:

cpptext
{
   /**
    * this function should populate out_polyshape with a list of verts which describe this object's 
    * convex bounding shape
    * @param out_PolyShape - output array which holds the vertex buffer for this obstacle's bounding polyshape
    * @return TRUE if this object should block things right now (FALSE means this obstacle shouldn't affect the mesh)
    */
   virtual UBOOL GetBoundingShape(TArray<FVector>& out_PolyShape);

   virtual UBOOL PreserveInternalPolys() { return TRUE; }
}

This is a pretty basic path obstacle. Currently all this obstacle is going to do is split the mesh about its shape.
Consider these screenshots of this example path object disabled(unregistered), and then enabled(registered):
(Note: in the screenshots below PreserveInternalGeo() is ON, more on this shortly)
Here is an obstacle in the world which has not yet been registered with the mesh. The mesh consists of one large polygon with an obstacle placed inside it.

Here is the mesh after the obstacle has been registered and the mesh split (at runtime):

Let's walk through both of the functions this example object has defined.

GetBoundingShape:
Here is this object's implementation..

UBOOL ANavMeshObstacle::GetBoundingShape(TArray<FVector>& out_PolyShape)
{
   out_PolyShape.AddItem(Location + FRotationMatrix(Rotation).TransformFVector(FVector(200.f,200.f,0.f)));
   out_PolyShape.AddItem(Location + FRotationMatrix(Rotation).TransformFVector(FVector(-200.f,200.f,0.f)));
   out_PolyShape.AddItem(Location + FRotationMatrix(Rotation).TransformFVector(FVector(-200.f,-200.f,0.f)));
   out_PolyShape.AddItem(Location + FRotationMatrix(Rotation).TransformFVector(FVector(200.f,-200.f,0.f)));
   return TRUE;
}

As you can see it's just providing a simple square. All this function is doing is providing a polygon that describes the boundary of the obstacle. If your obstacle was a staticmesh, you might use the mesh's bounds to do something similar to the above.

One important thing to remember is that this function is called only once when the mesh is first being split around the obstacle after it was registered. Once the obstacle is registered and the mesh is split around it, the obstacle won't be re-considered unless you unreisger it and then register it again.

The next function overidden here is very simple. PreserveInternalPolys:
All this guy does is tell the splitting process whether geometry inside the obstacle should be kept in place. As you can see from the above screenshots Geometry inside the obstacle has been kept, and linked in with the rest of the mesh.

Here is another image illustrating this:

One last important part of pathobstacles is the ability to dictate what type of Edge is added betweeen polys inside the obstacle and outside (for obstacles preserving internal geometry only). Whenever a link (Edge) is going to be made betweeen polygons inside an obstacle to polys outside, that obstacle's AddObstacleEdge function will be called to do this.

This allows you the user to override the behavior and add whatever edge type is appropriate for your obstacle. The default behavior will simply add a normal Edge telling all AI they can move between the interior and the exterior of the path obstacle. There are many cases where you might need custom behavior when entering or exiting a path obstacle though, and in those cases you probably want to implement inteface_navmeshpathobject as well.

Use in conjunction with Interface_NavMeshPathObject

One very common case for overriding AddObstacleEdge is to add edges which link to a Path Object. For example you can create an obstacle which implements both interface_navmeshpathobstacle and interface_navmeshpathobject.

To illustrate why this is useful consider the case of a puddle of oil sprayed on the ground sometime after the level has started.

For our oil puddle we want the following:

• We need the static navigation mesh to be split around the shape of the puddle to give us the granularity we need for getting AIs around the puddle
• We need a way to supply additional cost of entering the oil puddle so AIs avoid it if they can

So in this case, we would implement Interface_NavMeshPathObstacle as outlined above in order to register the obstacle's shape with the mesh, and then we would also implement Interface_NavMeshPathObject in order to allow an interface for edges linking the inside of the puddle with the outside to modify the cost of traversing those edges.

So our list from above really turns into the following:

• implement Interface_NavMeshPathObstacle::GetBoundingShape()
• register the obstacle at the proper time
• override AddObstacleEdge to add PathObject edges linked to the oil puddle instead fo adding regular edges
• Implement Interface_NavMeshPathObject::CostFor() (see Path Object Documentation)

AddObstacleEdge

The only thing we haven't talked about in detail already is AddObstacleEdge, so let's examine the function in more detail, Shall we? Yes! Let's! yay!

   /**
    * This function is called when an edge is going to be added connecting a polygon internal to this obstacle to another polygon which is not
    * Default behavior just a normal edge, override to add special costs or behavior (e.g. link a pathobject to the obstacle)
    * @param Status - current status of edges (e.g. what still needs adding)    
    * @param inV1 - vertex location of first vert in the edge
    * @param inV2 - vertex location of second vert in the edge
    * @param ConnectedPolys - the polys this edge links
    * @param bEdgesNeedToBeDynamic - whether or not added edges need to be dynamic (e.g. we're adding edges between meshes)
    * @param PolyAssocatedWithThisPO - the index into the connected polys array parmaeter which tells us which poly from that array is associated with this path object
    * @return returns an enum describing what just happened (what actions did we take) - used to determien what accompanying actions need to be taken 
    *         by other obstacles and calling code
    */
   virtual EEdgeHandlingStatus AddObstacleEdge( EEdgeHandlingStatus Status, const FVector& inV1, const FVector& inV2, TArray<FNavMeshPolyBase*>& ConnectedPolys, UBOOL bEdgesNeedToBeDynamic, INT PolyAssocatedWithThisPO);
   

After the mesh has been split and the Dynamic Splittery code will run around new polys and try to link them to the world around them. When it finds a potential poly to link to, it will call this function with the proposed edge, and let the pathobstacle then determine the proper course of action.

The trickiest part of this function is that there is this pesky Status parameter being passed around which tells you whether there has been an edge added in the other direction yet. This is needed because in some cases you only want edges going in one direction. For example you might want edges that allow AIs to leave a path obstacle but not go back in.

Consequently when you add edges you need to return what you just did, so that the calling code knows whether it needs to add a default edge in the other direction. Also it's possible to have two pathobstacles adjacent to each other which both want to add custom edges.

So if you look at the default implementation:

EEdgeHandlingStatus IInterface_NavMeshPathObstacle::AddObstacleEdge( EEdgeHandlingStatus Status, const FVector& inV1, const FVector& inV2, TArray<FNavMeshPolyBase*>& ConnectedPolys, UBOOL bEdgesNeedToBeDynamic, INT PolyAssocatedWithThisPO)
{
   return EHS_AddedNone;
}

You can see it's indicating that it hasn't done anything, so the calling code knows to then add default edges between Polys.

Now we'll look at an example of a path obstacle adding path object edges linked to itself.

EEdgeHandlingStatus UAIAvoidanceCylinderComponent::AddObstacleEdge( EEdgeHandlingStatus Status, const FVector& inV1, const FVector& inV2, TArray<FNavMeshPolyBase*>& ConnectedPolys, UBOOL bEdgesNeedToBeDynamic, INT PolyAssocatedWithThisPO)
{
   // if an edge has already been added in the direction we want to add an edge then there is probably a conflicting pathobstacle (e.g. we're butted
   // up against another obstacle which has already added an edge.. so just bail)
   if(Status == EHS_AddedBothDirs)
   {
      return Status;
   }

   // if there is already an edge point back into this PO from the other poly, bail
   if( (PolyAssocatedWithThisPO == 0 && Status == EHS_Added1to0) || 
      (PolyAssocatedWithThisPO == 1 && Status == EHS_Added0to1) )
   {
      return Status;
   }

   TArray<FNavMeshPolyBase*> ReversedConnectedPolys=ConnectedPolys;

   // so we want to add an edge back into the poly associated with this PO, so swap the order if we need to
   if(PolyAssocatedWithThisPO == 0)
   {
      ReversedConnectedPolys.SwapItems(0,1);
   }

   UNavigationMeshBase* Mesh = ReversedConnectedPolys(0)->NavMesh;

   if( Mesh == NULL )
   {
      return Status;
   }

   // Add the edge to the mesh
   TArray<FNavMeshPathObjectEdge*> CreatedEdges;
   Mesh->AddDynamicCrossPylonEdge<FNavMeshPathObjectEdge>(inV1,inV2,ReversedConnectedPolys,TRUE, &CreatedEdges);

   // grab a reference to the edge, and bind it to this pathobject
   FNavMeshPathObjectEdge* NewEdge = (CreatedEdges.Num() > 0) ? CreatedEdges(0) : NULL;
   checkSlowish(CreatedEdges.Num() <2);

   if(NewEdge == NULL)
   {
      return Status;
   }
   
   // bind new edge to this avoidance vol
   if(NewEdge != NULL)
   {
      NewEdge->PathObject = GetOwner();
      NewEdge->InternalPathObjectID = 0;
   }

   // indicate that we added an edge from dest poly to src poly
   if(Status == EHS_AddedNone)
   {
      if(PolyAssocatedWithThisPO == 0)
      {
         return EHS_Added1to0;
      }
      else
      {
         return EHS_Added0to1;
      }
   }
   else
   {
      // if we get here that means someone should have already added an edge in the opposite direction
      return EHS_AddedBothDirs;
   }
   
}

In this case the obstacle wants to add a PathObject edge linked to itself instead of a normal edge, but ONLY from polys outside the obstacle linking to polys inside. So most of the logic here is just determining if the order of the polys is right, and if not swapping things around so the edge gets added in the right direction.