Jump to content

  • Log In with Google      Sign In   
  • Create Account


Trouble with Recast/Detour


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 Magusware   Members   -  Reputation: 109

Like
0Likes
Like

Posted 21 April 2012 - 07:09 AM

[Solved]

I recoded my Build Nav Mesh function with the help of andrew from the recast navigation google code group.
If anyone has the problem of nneis being zero on a search they know will have polys there, or subsequently the polycount in the findNearestPoly() is zero. Hell, even if its just not building your mesh, you might be able to solve your problem by looking at my code now that it works.

bool NavMeshBuilder::CreateNavMesh(int vertex_count, float* verts, int index_count, int* indices)
{
rcContext* ctx = new rcContext();
rcHeightfield*  hf  = rcAllocHeightfield();
rcCompactHeightfield* chf  = rcAllocCompactHeightfield();
rcContourSet*  cset  = rcAllocContourSet();
rcPolyMesh*  polyMesh = rcAllocPolyMesh();
rcPolyMeshDetail* detailPolyMesh = rcAllocPolyMeshDetail();
do
{
  //2
  rcConfig config;
  config.tileSize = 1;
  config.ch = 0.1;
  config.cs = 0.1;
  config.walkableClimb = 0.9;
  config.walkableRadius = 0.2;
  config.walkableHeight = 1.8;
  config.walkableSlopeAngle = 45;
  config.minRegionArea = 8;
  config.mergeRegionArea = 20;
  config.borderSize = 1;
  config.maxEdgeLen = 12;
  config.maxSimplificationError = 1.3;
  config.maxVertsPerPoly = 6;
  config.detailSampleDist = 6;
  config.detailSampleMaxError = 1;
  config.bmax[0] = verts[0];
  config.bmax[1] = verts[1];
  config.bmax[2] = verts[2];
  config.bmin[0] = verts[0];
  config.bmin[1] = verts[1];
  config.bmin[2] = verts[2];
  //3 determine tile boundingbox;
  for(int i = 0; i < vertex_count / 3; i++)
  {
   if (verts[i*3] > config.bmax[0])
    config.bmax[0] = verts[i*3];
   if (verts[i*3+1] > config.bmax[1])
    config.bmax[1] = verts[i*3+1];
   if (verts[i*3+2] > config.bmax[2])
    config.bmax[2] = verts[i*3+2];
   if (verts[i*3] < config.bmin[0])
    config.bmin[0] = verts[i*3];
   if (verts[i*3+1] < config.bmin[1])
    config.bmin[1] = verts[i*3+1];
   if (verts[i*3+2] < config.bmin[2])
    config.bmin[2] = verts[i*3+2];
  }
  //config.width = 370;
  //config.height = 250;
  rcCalcGridSize(config.bmin, config.bmax, config.cs, &config.width, &config.height);
  //4
  if (!rcCreateHeightfield(ctx, *hf, config.width, config.height, config.bmin, config.bmax, config.cs, config.ch))
   break;
  //5
  unsigned char* areas = new unsigned char[index_count/3];
  rcMarkWalkableTriangles(ctx, config.walkableSlopeAngle, verts, vertex_count, indices, index_count / 3, areas);
  //6
  hf->freelist = 0;
  rcRasterizeTriangles(ctx, verts, areas, index_count / 3, *hf);
  //7
  rcFilterLowHangingWalkableObstacles(ctx, config.walkableClimb, *hf);
  //8
  rcFilterLedgeSpans(ctx, config.walkableHeight, config.walkableClimb, *hf);
  //9
  rcFilterWalkableLowHeightSpans(ctx, config.walkableHeight, *hf);
  //10
  if(!rcBuildCompactHeightfield(ctx, config.walkableHeight, config.walkableClimb, *hf, *chf))
   break;
  //11
  if(!rcErodeWalkableArea(ctx, config.walkableRadius, *chf))
   break;
  //12
  chf->dist = 0;
  if(!rcBuildDistanceField(ctx, *chf))
   break;
  //13
  if(!rcBuildRegions(ctx, *chf, config.borderSize, config.minRegionArea, config.mergeRegionArea))
   break;
  //14
  if(!rcBuildContours(ctx, *chf, config.maxSimplificationError, config.maxEdgeLen, *cset))
   break;
  //15
  if(!rcBuildPolyMesh(ctx, *cset, config.maxVertsPerPoly, *polyMesh))
   break;
  this->BuildDebugRender(*polyMesh);
  //16
  if(!rcBuildPolyMeshDetail(ctx, *polyMesh, *chf, config.detailSampleDist, config.detailSampleMaxError, *detailPolyMesh))
   break;
  for (int i = 0; i < polyMesh->npolys; ++i)
  {
   if (polyMesh->areas[i] == RC_WALKABLE_AREA)
    polyMesh->areas[i] = SAMPLE_POLYAREA_GROUND;
   if (polyMesh->areas[i] == SAMPLE_POLYAREA_GROUND ||
    polyMesh->areas[i] == SAMPLE_POLYAREA_GRASS ||
    polyMesh->areas[i] == SAMPLE_POLYAREA_ROAD)
   {
    polyMesh->flags[i] = SAMPLE_POLYFLAGS_WALK;
   }
   else if (polyMesh->areas[i] == SAMPLE_POLYAREA_WATER)
   {
    polyMesh->flags[i] = SAMPLE_POLYFLAGS_SWIM;
   }
   else if (polyMesh->areas[i] == SAMPLE_POLYAREA_DOOR)
   {
    polyMesh->flags[i] = SAMPLE_POLYFLAGS_WALK | SAMPLE_POLYFLAGS_DOOR;
   }
  }
  //17
  dtNavMeshCreateParams params;
  memset(&params, 0, sizeof(params));
  params.verts  = polyMesh->verts;
  params.vertCount = polyMesh->nverts;
  params.polys  = polyMesh->polys;
  params.polyFlags = polyMesh->flags;
  params.polyAreas = polyMesh->areas;
  params.polyCount = polyMesh->npolys;
  params.nvp  = polyMesh->nvp;
  rcVcopy(params.bmin, polyMesh->bmin);
  rcVcopy(params.bmax, polyMesh->bmax);
  params.detailMeshes = detailPolyMesh->meshes;
  params.detailVerts = detailPolyMesh->verts;
  params.detailVertsCount = detailPolyMesh->nverts;
  params.detailTris = detailPolyMesh->tris;
  params.detailTriCount = detailPolyMesh->ntris;
  params.walkableClimb = config.walkableClimb;
  params.walkableHeight = config.walkableHeight;
  params.walkableRadius = config.walkableRadius;
  params.tileLayer = 0;
  params.tileX  = 0;
  params.tileY  = 0;
  params.offMeshConAreas = 0;
  params.offMeshConCount = 0;
  params.offMeshConDir = 0;
  params.offMeshConFlags = 0;
  params.offMeshConRad = 0;
  params.offMeshConUserID = 0;
  params.offMeshConVerts = 0;
  params.ch = config.ch;
  params.cs = config.cs;
  params.buildBvTree = true;
  if(!dtCreateNavMeshData(&params, &m_navMeshData, &m_navMeshDataSize))
   break;
}
while ( 0 != 0 );
delete ctx;
rcFreeHeightField(hf);
rcFreeCompactHeightfield(chf);
rcFreeContourSet(cset);
rcFreePolyMesh(polyMesh);
rcFreePolyMeshDetail(detailPolyMesh);

if (m_navMeshData != NULL && m_navMeshDataSize != 0)
{
  return LoadNavMesh();
}
return false;
}





[Original topic]

Greetings once again GameDev.

I'm having trouble getting recast and detour to work properly. I can get it to generate a navmesh from my world mesh but when I call my pathfinding function it fails to get the nearest poly to the start position and end position. I have clearly overlooked something, what a certain setting does or even missed out a step entirely during the generation.

My NavMesh generation is based on a post by a guy on a forum who gave the correct call order to build the navmesh.

1 - Get geometry for the area you want to mesh from your parser
2 - Create rcConfig structure with your config values
3 - Determine bounding box for the tile you want to create
4 - Call rcCreateHeightField, passing in the geometry from the parser
5 - Call rcMarkWalkableTriangles
6 - Call rcRasterizeTriangles
7 - Call rcFilterLowHangingWalkableObstacles
8 - Call rcFilterLedgeSpans
9 - Call rcFilterWalkableLowHeightSpans
10 - Call rcBuildCompactHeightField
11 - Call rcErodeArea
12 - Call rcBuildDistanceField
13 - Call rcBuildRegions
14 - Call rcBuildContours
15 - Call rcBuildPolyMesh
16 - Call rcBuildPolyMeshDetail
17 - Call dtCreateNavMeshData. This will give you the structure to save to the disk. This will be the mesh for the tile you've just created. Later you can load these files and use dtAddTile (or something similarly named) to load the tiles for use in pathfinding.


From that I have coded up:
bool CreateNavMesh(Ogre::Entity* ent)
{
  /*
  1 - Get geometry for the area you want to mesh from your parser
  2 - Create rcConfig structure with your config values
  3 - Determine bounding box for the tile you want to create
  4 - Call rcCreateHeightField, passing in the geometry from the parser
  5 - Call rcMarkWalkableTriangles
  6 - Call rcRasterizeTriangles
  7 - Call rcFilterLowHangingWalkableObstacles
  8 - Call rcFilterLedgeSpans
  9 - Call rcFilterWalkableLowHeightSpans
  10 - Call rcBuildCompactHeightField
  11 - Call rcErodeArea
  12 - Call rcBuildDistanceField
  13 - Call rcBuildRegions
  14 - Call rcBuildContours
  15 - Call rcBuildPolyMesh
  16 - Call rcBuildPolyMeshDetail
  17 - Call dtCreateNavMeshData. This will give you the structure to save to the disk. This will be the mesh for the tile you've just created. Later you can load these files and use dtAddTile (or something similarly named) to load the tiles for use in pathfinding.
  */
  //1.
  size_t vertex_count;
  float* verts;
  size_t index_count;
  int* indices;
  ::_getMeshInformation(ent, vertex_count, verts, index_count, indices);

  return CreateNavMesh(vertex_count, verts, index_count, indices);
}
bool CreateNavMesh(int vertex_count, float* verts, int index_count, int* indices)
{
  rcContext* ctx = new rcContext();
  //2
  rcConfig config;
  config.width = 370;
  config.height = 250;
  config.tileSize = 1;
  config.ch = 0.1;
  config.cs = 0.1;
  config.walkableClimb = 0.9;
  config.walkableRadius = 0.2;
  config.walkableHeight = 1.8;
  config.walkableSlopeAngle = 45;
  config.minRegionArea = 8;
  config.mergeRegionArea = 20;
  config.borderSize = 1;
  config.maxEdgeLen = 12;
  config.maxSimplificationError = 1.3;
  config.maxVertsPerPoly = 6;
  config.detailSampleDist = 6;
  config.detailSampleMaxError = 1;
  config.bmax[0] = verts[0];
  config.bmax[1] = verts[1];
  config.bmax[2] = verts[2];
  config.bmin[0] = verts[0];
  config.bmin[1] = verts[1];
  config.bmin[2] = verts[2];
  //3 determine tile boundingbox;
  for(int i = 0; i < vertex_count / 3; i++)
  {
   if (verts[i*3] > config.bmax[0])
	config.bmax[0] = verts[i*3];
   if (verts[i*3+1] > config.bmax[1])
	config.bmax[1] = verts[i*3+1];
   if (verts[i*3+2] > config.bmax[2])
	config.bmax[2] = verts[i*3+2];
   if (verts[i*3] < config.bmin[0])
	config.bmin[0] = verts[i*3];
   if (verts[i*3+1] < config.bmin[1])
	config.bmin[1] = verts[i*3+1];
   if (verts[i*3+2] < config.bmin[2])
	config.bmin[2] = verts[i*3+2];
  }
  /*
  Not sure if this is needed, got from looking at Recast Demo source
  */
  {
   config.bmax[0] += config.borderSize * config.cs;
   config.bmax[1] += config.borderSize * config.cs;
   config.bmax[2] += config.borderSize * config.cs;
   config.bmin[0] -= config.borderSize * config.cs;
   config.bmin[1] -= config.borderSize * config.cs;
   config.bmin[2] -= config.borderSize * config.cs;
  }
  //
  //4 create heightfield
  rcHeightfield hf;
  if (!rcCreateHeightfield(ctx, hf, config.width, config.height, config.bmin, config.bmax, config.cs, config.ch))
   return false;
  //5 mark walkable triangles
  unsigned char* areas = new unsigned char[index_count/3];
  rcMarkWalkableTriangles(ctx, config.walkableSlopeAngle, verts, vertex_count, indices, index_count / 3, areas);
  //6 rastarize tris
  hf.freelist = 0;
  rcRasterizeTriangles(ctx, verts, areas, index_count / 3, hf);
  //7 filter low hanging walkable objs
  rcFilterLowHangingWalkableObstacles(ctx, config.walkableClimb, hf);
  //8 filter ledge spans
  rcFilterLedgeSpans(ctx, config.walkableHeight, config.walkableClimb, hf);
  //9
  rcFilterWalkableLowHeightSpans(ctx, config.walkableHeight, hf);
  //10
  rcCompactHeightfield chf;
  rcBuildCompactHeightfield(ctx, config.walkableHeight, config.walkableClimb, hf, chf);
  //11
  rcErodeWalkableArea(ctx, config.walkableRadius, chf);
  //12
  chf.dist = 0;
  rcBuildDistanceField(ctx, chf);
  //13
  rcBuildRegions(ctx, chf, config.borderSize, config.minRegionArea, config.mergeRegionArea);
  //14
  rcContourSet cset;
  rcBuildContours(ctx, chf, config.maxSimplificationError, config.maxEdgeLen, cset);
  //15
  rcPolyMesh* polyMesh = rcAllocPolyMesh();
  rcBuildPolyMesh(ctx, cset, config.maxVertsPerPoly, *polyMesh);
  //16
  rcPolyMeshDetail* detailPolyMesh = rcAllocPolyMeshDetail();
  rcBuildPolyMeshDetail(ctx, *polyMesh, chf, config.detailSampleDist, config.detailSampleMaxError, *detailPolyMesh);
  //17
  dtNavMeshCreateParams params;
  params.verts  = polyMesh->verts;
  params.vertCount = polyMesh->nverts;
  params.polys  = polyMesh->polys;
  params.polyFlags = polyMesh->flags;
  params.polyAreas = polyMesh->areas;
  params.polyCount = polyMesh->npolys;
  params.nvp   = polyMesh->nvp;
  params.detailMeshes  = detailPolyMesh->meshes;
  params.detailVerts  = detailPolyMesh->verts;
  params.detailVertsCount = detailPolyMesh->nverts;
  params.detailTris  = detailPolyMesh->tris;
  params.detailTriCount = detailPolyMesh->ntris;
  if(!dtCreateNavMeshData(&params, &m_navMeshData, &m_navMeshDataSize))
   return false;
  delete ctx;
  if (m_navMeshData != NULL && m_navMeshDataSize != 0)
  {
   return LoadNavMesh();
  }
  return false;
}
bool LoadNavMesh()
{
  m_pNavMesh = new dtNavMesh();
  if(m_pNavMesh->init(m_navMeshData, m_navMeshDataSize, 0) != DT_SUCCESS)
  {
   delete m_pNavMesh;
   return false;
  }
  return true;
}

But when I run the search on it with 2 points I know exist, it fails to find the nearest poly's, the code for this search is based on the CapekNav pathfinder by Michael Cutler

bool GetPath(Vector3 start, Vector3 end, std::list<Vector3>& path)
{
  float spos[3] = { start.x, start.y, start.z };
  float epos[3] = { end.x, end.y, end.z };
  dtQueryFilter filter;
  filter.setIncludeFlags(0xffffff);
  filter.setExcludeFlags(0);
  float extents[3] = { 0, 0, 0 };
  dtPolyRef startRef;
  dtPolyRef endRef;
  float nfs[3] = { 0, 0, 0 };
  float nfe[3] = { 0, 0, 0 };
  m_pQuery->findNearestPoly(spos, extents, &filter, &startRef, nfs);
  m_pQuery->findNearestPoly(epos, extents, &filter, &endRef, nfe);
  if (!startRef || !endRef)
   return false;
  dtPolyRef  polys[MAX_POLYS];
  int	nbPolys = 0;
  float   strPath[MAX_POLYS*3];
  int	nbStrPath = 0;
  unsigned char strPathFlags[MAX_POLYS];
  dtPolyRef  strPathPolys[MAX_POLYS];

  m_pQuery->findPath(startRef, endRef, spos, epos, &filter, polys, &nbPolys, MAX_PATH);
  if(nbPolys)
  {
   m_pQuery->findStraightPath(spos, epos, polys, nbPolys, strPath, strPathFlags, strPathPolys, &nbStrPath, MAX_PATH);
   for( int i = 0; i < nbStrPath/3; i++)
   {
	Vector3 point(strPath[i*3+0], strPath[i*3+1], strPath[i*3+2]);
	path.push_back(point);
   }
   path.back().x = end.x;
   path.back().y = end.y;
   path.back().z = end.z;
  }
  return true;
}

Can anyone see what I've missed?

Thanks in advance,
-MaGuSware

Edited by Magusware, 29 April 2012 - 06:55 AM.


Sponsor:

#2 Steadtler   Members   -  Reputation: 220

Like
0Likes
Like

Posted 21 April 2012 - 11:08 AM

Do you have debug display to show the resulting mesh ? Tools are important.

#3 Magusware   Members   -  Reputation: 109

Like
0Likes
Like

Posted 22 April 2012 - 09:14 AM

It appears to generate the mesh nicely... I think.
Posted Image

#4 Steadtler   Members   -  Reputation: 220

Like
0Likes
Like

Posted 22 April 2012 - 01:44 PM

Then you're down to good old debugging :) Make a simple map with only a flat square surface. Then step in the method and see while it fails.

#5 Magusware   Members   -  Reputation: 109

Like
0Likes
Like

Posted 22 April 2012 - 04:12 PM

Then you're down to good old debugging Posted Image Make a simple map with only a flat square surface. Then step in the method and see while it fails.


That's what I was doing before I posted on here. I stepped so far into the code I no longer knew what it was doing. The only thing that I managed to find was an uninitialized variable called called qfac in "dtNavMeshQuery::queryPolygonsInTile", that gets set by "tile->header->bvQuantFactor" which is the first time ive seen that.

#6 Magusware   Members   -  Reputation: 109

Like
0Likes
Like

Posted 25 April 2012 - 01:40 PM

Bump,
Anyone got any thoughts?

#7 FLeBlanc   Crossbones+   -  Reputation: 3101

Like
0Likes
Like

Posted 25 April 2012 - 04:55 PM

You might have better luck asking Mikko directly about the internals of R&D. He's pretty friendly and helpful most of the time.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS