[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 == RC_WALKABLE_AREA)
polyMesh->areas = SAMPLE_POLYAREA_GROUND;
if (polyMesh->areas == SAMPLE_POLYAREA_GROUND ||
polyMesh->areas == SAMPLE_POLYAREA_GRASS ||
polyMesh->areas == SAMPLE_POLYAREA_ROAD)
{
polyMesh->flags = SAMPLE_POLYFLAGS_WALK;
}
else if (polyMesh->areas == SAMPLE_POLYAREA_WATER)
{
polyMesh->flags = SAMPLE_POLYFLAGS_SWIM;
}
else if (polyMesh->areas == SAMPLE_POLYAREA_DOOR)
{
polyMesh->flags = 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.
[/quote]

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

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

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

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.

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.

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.

Bump,
Anyone got any thoughts?

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