Game Development Community

dev|Pro Game Development Curriculum

The Recast Resource

by Daniel Buckmaster · 12/04/2011 (2:56 pm) · 202 comments


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

!! This resource is deprecated !!

The Torque3D steering committee has accepted a pull request containing an updated version of this resource. You can use it by checking out the development branch of Torque3D, or waiting until release 4.0.

Overview

This resource provides source code to integrate the excellent Recast/Detour library with T3D 1.1 final and T3D 1.2 as described in this blog.

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!

img440.imageshack.us/img440/3069/stationpath.png
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 &amp;amp;lt;= mMaxVerts, &amp;amp;quot;PrimBuilder allocated more verts than you used! Break and debug or rendering artifacts could occur.&amp;amp;quot; );

#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 &amp;amp;amp;amp;quot;coverPoint.h&amp;amp;amp;amp;quot;
  • Steve Acaster has all the fun. Save some for us!
Happy trails!

About the author

Studying mechatronic engineering and computer science at the University of Sydney. Game development is probably my most time-consuming hobby!

Page «Previous 1 2 3 4 5 6 7 Last »
#1
12/04/2011 (4:03 pm)
Excellent work Daniel. This is potentially one of the most important resources ever released.
#2
12/04/2011 (7:02 pm)
Hey Daniel, this is awesome.
Quote:NavPaths automatically replan when their associated NavMesh is modified. Give it a go!

I have some questions, you may have experience already with, otherwise, I'll have to wait and test it for myself :)

What kind of performance and times has a real-time NavMesh modification? Is it feasible?
And the same for NavPaths replans, is this acceptable in real time? Have you tested it with multiple agents?

Thanks for your great work!
#3
12/04/2011 (10:45 pm)
Quote:What kind of performance and times has a real-time NavMesh modification? Is it feasible?
Heh, that's the caveat I didn't mention. NavMesh build times aren't great. This feature was intended more for when you're using NavPaths as static paths (like the one set up in navtest.mis) and modify the NavMesh while editing the level.

Build times range from fractions of a second for the likes of navtest.mis to a couple of seconds on something like Burg, to a minute for a 300x300 metre test I did of Deathball Desert. It all, of course, depends on the geometry you input and the size of the navmesh. If I had it in me, I'd have done more detailed benchmarks to see where the bottleneck was at (parsing geometry or the Recast process itself).

Detour actually does support local modification of a navmesh, allowing you to rebuild just a small piece of the mesh, which would make the performance acceptable for real-time use. However, that's a fairly advanced feature that I've yet to wrap my head around :P.

Path planning is very quick - even the longest paths I've tested with have been generated pretty much instantly. Again, I've not stress-tested much, so I don't know how multi-agent performance will go. But I've written a fairly thin wrapper around Detour's path planning functionality, and it is a very performant library.

Detour does have the ability to do 'sliced' path planning - i.e., spread a plan out over multiple updates. However, as far as I know, you can't plan multiple paths on a single NavMesh concurrently, so I chose not to include those methods. To me, sliced planning is all about running lots of queries in parallel!
#4
12/05/2011 (5:02 am)
Heh, excellent summary Daniel, outstanding work, thanks very much!

#5
12/05/2011 (6:11 am)
Great stuff, Danny. :)

Now resource the "Make My Game Button". ;)
#6
12/05/2011 (7:14 am)
Silly billy that I am, I've managed to forget to implement the NavPath function that gets a point on the path. I'll fix this for the 'proper' release, but until then, replace NavPath::getNode in Engine/source/T3D/nav/navPath.cpp with this:
Point3F NavPath::getNode(S32 idx)
   {
      if(idx < getCount() && idx >= 0)
         return mPoints[idx];
      return Point3F(0,0,0);
   }

   DefineEngineMethod(NavPath, getNode, Point3F, (S32 idx),,
      "@brief Get a specified node along the path.")
   {
      return object->getNode(idx);
   }

@Steve I'm keeping that one under wraps for now...
#7
12/05/2011 (8:13 am)
Wow, that went in easy.
Epic work Daniel!
#8
12/05/2011 (8:28 am)
This is so cool! So this includes A* or is that a separate resource? I am so close to needing some decent path planning. For my current project I need to have plausible interaction of AI and this should help at least with movement.
#9
12/05/2011 (9:41 am)
This is just amazing work here. I'm sure I'll be messing around with this one for quite a while. :P
#10
12/05/2011 (1:14 pm)
Quote:So this includes A* or is that a separate resource?
Yes, this resource handles both generating navmeshes and pathfinding on them using A*.

Thanks, everyone, for the kind words!
#11
12/05/2011 (7:31 pm)
So, it generates the nav mesh every time the mission loads? Is there a way to short-circuit that so that you can save out the mesh and load it back in at mission load or would it make that much of a difference?
#12
12/05/2011 (8:36 pm)
This...this...this is so pretty...
#13
12/05/2011 (11:43 pm)
Quote:So, it generates the nav mesh every time the mission loads?
Quote: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!
The only time you shouldn't use this ability is when you have dynamically-created content inside the navmesh that will be different each time you load the mission. Then, you may need to let it regenerate every time.
#14
12/06/2011 (2:25 am)
Daniel sincerely when time ago I saw you pick up T3D I was thinking "Oh good! Cannot wait to see what resources he will come up with for T3D!"

Ehehe I was really right! :-)

(by the way cannot wait also to see something more about your procedural goodies :D ... )
#15
12/06/2011 (7:18 am)
Ah - sorry - case of TL/DR... lol
#16
12/06/2011 (8:00 am)
Quote:Ah - sorry - case of TL/DR
I know, I did bury quite a bit of information in that wall of text ;P.
Quote:(by the way cannot wait also to see something more about your procedural goodies :D ... )
Me neither :P. Not done much more on that, but I'll get back to it eventually!
#17
12/06/2011 (11:01 am)
Great resource Daniel, recast and detour are great libraries. For updating meshes in real time you need recast to be using the tilemesh and not the more simple static mesh that this implements.

The navMesh is then built up of a bunch of seperate tiles that are built one by one, allowing just a single tile to be rebuilt. I was playing around with the physX stuff in torque and having it update the meshes in real time as I knocked some items about.

Thing to watch is the tile size though -- too big and it causes lag rebuilding that tile and make them too small then there are too many tiles and pathfinding is slow.

Superb work :)
#18
12/06/2011 (2:36 pm)
Cheers, Andy... your early blogs on navmeshes were probably my first exposure to them, now that I think about it! I'm still jealous of the editor integration you had... no idea how to even start to go about creating something like that ;P.

Recast/Detour has a bunch of exciting extra features, and I've got no idea what to implement first... I guess the shortlist is:

  • Tiled meshes
  • Off-mesh connections (jumping, teleporting, etc.)
  • Crowd simulation/per-agent steering
  • Query filters (i.e., exclude certain types of poly)
  • Temporary obstacles (slightly different to dynamic obstacles)
And that's not even considering extra features outside what RC/DT provides, like automated cover annotation.

EDIT: I've just discovered that Detour actually doesn't modify the NavMesh when performing searches, so it's possible to run multiple path queries at the same time. Sliced queries, here we come!

EDIT: More debug drawing than you could shake a stick at!

img94.imageshack.us/img94/2772/debugdraw.png

The blue lines there are actually the closed list tree of the search you can just see going over the bridge. Not sure why that was necessary, but Detour supports it!
#19
12/07/2011 (11:54 am)
Thanks Daniel, as much recast automates generating the mesh its never quite perfect and you find some oddities that need tweaking which is where the editor came in so handy.

I've been meaning to write a T3D version of the editor - sadly it is a rewrite for most parts not a port as the editors in T3D are way too different and I've learnt a lot since the hacked together version I wrote for TGEA.

I started looking at it a few months back and on the plus side T3D editors architecture is much nicer as they went with a plugin approach rather than making you hack the core files and scripts in TGEA, plus some of the more complex features of dragging and moving points must be in the engine now as tools like the river editor, road editor have that functionality.

Wondering whether now is a good time to kick start that again or team up with someone to put out a great pathfinding resource with editors and all. If you fancy that let me know.
#20
12/07/2011 (12:50 pm)
I haven't looked in detail, but yeah, the T3D editor scripts do seem far cleaner. I was quite impressed when even the small change of adding the AI classes was four lines of script. And I didn't need to do anything to have the class icons work properly!

I'll get back to you on that offer... it's seriously tempting, but at this point I kind of want to start focusing on the precise needs of my game, so I can move on to creating some actual AI ;P.
Page «Previous 1 2 3 4 5 6 7 Last »