Navigation Mesh Dynamic Obstacle Splitting Technical Overview

Overview

High level overview

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

Build on-demand

Additionally once the polygon 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.

Implementation details

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 screen shots of this example path object disabled(unregistered), and then enabled(registered):
Note: In the screen shots 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()

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 static mesh, 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 unregister it and then register it again.

PreserveInternalPolys()

One last important part of path obstacles is the ability to dictate what type of Edge is added betweeen polygons inside the obstacle and outside (for obstacles preserving internal geometry only). Whenever a link (Edge) is going to be made between polygons inside an obstacle to polygons 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

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 of adding regular edges
• Implement Interface_NavMeshPathObject::CostFor() (see Path Object Documentation)

AddObstacleEdge()

/**
 * 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 splitter code will run around new polygons and try to link them to the world around them. When it finds a potential polygon 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 polygons.

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 polygons outside the obstacle linking to polygons inside. So most of the logic here is just determining if the order of the polygons is right, and if not swapping things around so the edge gets added in the right direction.