The Recast Resource

A* pathfinding on automatically-generated navmeshes using the Recast/Detour library. Finally: stable, easy pathfinding for Torque!

Overview

This resource provides source code to integrate the excellent Recast/Detour library with T3D 1.1 final as described in this blog. I have received word that the resource works under 1.2 as well.

Recast automatically generates navigation meshes from arbitrary source geometry. This resource allows you to define a region using a NavMesh object that will be parsed and turned into a navmesh. You have access to all Recast's navmesh generation parameters to tweak our navmesh to suit different geometry and character types.

Detour finds paths across a navmesh. The NavPath class allows you to find a path between two specified points. The path can be looping or one-way, and optionally allows you to specify a set of waypoints to visit between your source and destination.

This resource uses code from Lethal Concepts' great Recast meshloader resource to parse Torque's geometry into a format Recast will accept. Kudos to them for writing the code and allowing me to share it and my modifications!


Pathfinding through an invisible Station mesh.

Installation

1. Download the source code from HNGames' public Torque file system.
2. If you're looking for the beta release, you can find it here or here.
3. Rename the folder called Project in RecastResource_T3D1.1F/My Projects to the name of the project you wish to install the resource into. (There really aren't many changes on this side of things - just some editor icons and a new mission - so this step is optional.)
4. Copy the contents of the RecastResource_T3D1.1F folder into your Torque 3D install folder (i.e., C:/Torque/Torque 3D Pro 1.1). When prompted, allow the folders to be merged. All of the files in this resource are new, so you shouldn't have to worry about overwriting anything.
5. Add the new files in the Engine/source/T3D/nav directory to your ProjectName DLL Visual Studio project. All of them. Even the ones in the nav/recast directory, which are the Recast/Detour source files.
6. Make the three code and script changes below:

In Engine/source/gfx/primBuilder.cpp, we need to allow the vertex buffer to grow beyond our original input size. This is because Recast's duDebugDraw interface class mimics an OpenGL-like drawing interface, and might input an indefinite number of vertices at a time.

Replace the header block at the top of primBuilder.cpp with this:

//*****************************************************************************
// Primitive Builder
//*****************************************************************************
namespace PrimBuild
{
Vector<GFXVertexPCT> mTempVertBuff;
GFXVertexBufferHandle<GFXVertexPCT> mVertBuff;
GFXPrimitiveType  mType;
U32               mCurVertIndex;
ColorI            mCurColor( 255, 255, 255 );
Point2F           mCurTexCoord;
const ColorI      _colWhite( 255, 255, 255, 255 );

U32 mMaxVerts;

static void CheckVertexBounds()
{
   // Grow vertex buffer
   if(mCurVertIndex == mMaxVerts)
   {
      mMaxVerts *= 2;
      mTempVertBuff.setSize(mMaxVerts);
   }
}

#ifdef TORQUE_DEBUG

#define INIT_VERTEX_SIZE(x) mMaxVerts = x;
//#define VERTEX_BOUNDS_CHECK() AssertFatal( mCurVertIndex < mMaxVerts, "PrimBuilder encountered an out of bounds vertex! Break and debug!" );
#define VERTEX_BOUNDS_CHECK() CheckVertexBounds()

// This next check shouldn't really be used a lot unless you are tracking down
// a specific bug. -pw
#define VERTEX_SIZE_CHECK() AssertFatal( mCurVertIndex <= mMaxVerts, "PrimBuilder allocated more verts than you used! Break and debug or rendering artifacts could occur." );

#else

#define INIT_VERTEX_SIZE(x) mMaxVerts = x;
#define VERTEX_BOUNDS_CHECK() CheckVertexBounds()
#define VERTEX_SIZE_CHECK()

#endif

In Engine/source/T3D/convexShape.cpp, we need to modify the buildPolyList method to return triangles. At the moment, it seems to return some odd six-vertex face that messes up the geometry-parsing step of generating a NavMesh. This change is actually optional; however, if you don't make it, ConvexShape objects will not contribute any geometry to NavMesh generation.

Replace the ConvexShape::buildPolyList method with this:

bool ConvexShape::buildPolyList( PolyListContext context, AbstractPolyList *plist, const Box3F &box, const SphereF &sphere )
{
   if ( mGeometry.points.empty() )	
      return false;

   // If we're exporting deal with that first.
   if ( context == PLC_Export )
   {
      AssertFatal( dynamic_cast<OptimizedPolyList*>( plist ), "ConvexShape::buildPolyList - Bad polylist for export!" );
      _export( (OptimizedPolyList*)plist, box, sphere );
      return true;
   }

   plist->setTransform( &mObjToWorld, mObjScale );
   plist->setObject( this );


   // Add points...

   const Vector< Point3F > pointList = mGeometry.points;

   S32 base = plist->addPoint( pointList[0] );

   for ( S32 i = 1; i < pointList.size(); i++ )	
      plist->addPoint( pointList[i] );


   // Add Surfaces...

   const Vector< ConvexShape::Face > faceList = mGeometry.faces;

   for ( S32 i = 0; i < faceList.size(); i++ )
   {
      const ConvexShape::Face &face = faceList[i];		

      S32 s = face.triangles.size();
      for ( S32 j = 0; j < s; j++ )
      {
         plist->begin( 0, s*i + j );

         plist->plane( PlaneF( face.centroid, face.normal ) );

         plist->vertex( base + face.points[ face.triangles[j].p0 ] );
         plist->vertex( base + face.points[ face.triangles[j].p1 ] );
         plist->vertex( base + face.points[ face.triangles[j].p2 ] );

         plist->end();
      }      
   }

   return true;
}

In My Projects/Project/game/tools/worldEditor/scripts/editors/creator.ed.cs, we need to add a few small hooks to make our new AI classes show up in the editor.

Have a look for this block of code:

%this.beginGroup( "System" );
   
      %this.registerMissionObject( "SimGroup" );
      
   %this.endGroup();

Before it, add:

%this.beginGroup("Navigation");

      %this.registerMissionObject("NavMesh", "Navigation mesh");
      %this.registerMissionObject("NavPath", "Path");

   %this.endGroup();

That's it for the installation! You should now be able to recompile and start navigating.

Use

This video gives a good overview of how to use the NavMesh class. However, there have been some additions to the code since it was published:

1. You can now build the NavMesh from within the editor! Click on the 'build' checkbox under the 'NavMesh Build' section of the object inspector pane to build the mesh with its currently-selected settings.
2. If you tick the 'buildThreaded' box, the NavMesh will build in a separate thread, leaving you to continue editing. The NavMesh will render in red while this process is ongoing.
3. NavMesh objects with a fileName specified will automatically save themselves to this file name when the level is saved, and load from it when a level is loaded. It's always a good idea to use this function! (Unless you expect the geometry inside the NavMesh to change, or you're generating it on-the-fly.)
4. Advanced options are presented beneath the build options.

The NavPath class was not shown off in the video. Here is a brief run-down of its use:

1. You can create a NavPath object from the editor in the same way as a NavMesh.
2. A NavPath must be assigned a NavMesh object to operate on. SImply type the name of the NavMesh object in the NavPath's 'mesh' field.
3. Once given a 'from' location and a 'to' location, a NavPath will automatically plan, and the result should be visible as a pink line in the editor.
4. If you're creating a NavPath in scripts, you might need to call %path.plan() to create the path.
5. You can optionally specify a regular Path object whose objects will be visited by the path between its 'from' and 'to' points. There is an example set up for you in navtest.mis.
6. NavPaths automatically replan when their associated NavMesh is modified. Give it a go!
7. You can access the points in a NavPath with the same scripting interface used with the regular Path class. This means NavPath objects can be plugged right into existing script functions like AIPlayer::spawnOnPath.
8. The member 'isSliced' will allow the NavPath to operate over a short length of time. The amount of planning that is done each tick is controlled by the 'maxIterations' member.

Here is a brief scripted example of constructing a NavPath:

%path = new NavPath() {
   from = "0 1 1";
   to = "10 1 1";
   mesh = TheNavMesh;
};
// The path now contains all the points to navigate between from and to.

// Let's change the destination:
%path.to = %obj.getPosition();
%path.plan();
// Now the updated path points to the location of %obj

Known issues

• Paths on large navmeshes will fail due to the maximum path length setting. You can modify this value, at the top of navPath.h (static const U32 MaxPathLen = 1024;).
• In navMesh.cpp, you'll need to remove the line #include "coverPoint.h"
• Steve Acaster has all the fun. Save some for us!

Happy trails!