[R + D] Problem with finding path

[pladi]

Hello all.

So i've been working on a navmesh system for my bot, and think i've gotten pretty far. However, i'm having a problem with finding a path: FindNearestPoly fails everytime. Been searching around, but can't seem to find a solution. I'm currently using Namreeb's data for creating a navmesh, and the result fits perfectly:

However, when i use my findPath code on it, it can't find the nearest poly. (findPath succeeds everytime i load a navmesh generated through the demo, though).
Was hoping someone could shed some light on what the problem might be.
(Here's the code, which i use for generating my navmeshes)

unsigned char* buildTileMesh(const int tx, const int ty, const float* bmin, const float* bmax, int& dataSize)
{
	
	m_tileMemUsage = 0;
	m_tileBuildTime = 0;
	
	const float* verts = m_Loader->getVerts();
	const int nverts = m_Loader->getVertCount();
	const int ntris = m_Loader->getTriCount();
	const rcChunkyTriMesh* chunkyMesh = m_chunkyMesh;
		
	// Init build configuration from GUI
	memset(&m_cfg, 0, sizeof(m_cfg));
	m_cfg.cs = CellSize;
	m_cfg.ch = CellHeight;
	m_cfg.walkableSlopeAngle = WalkableSlopeAngle;
	m_cfg.walkableHeight = (int)ceilf(WorldUnitWalkableHeight / m_cfg.ch);
	m_cfg.walkableClimb = (int)floorf(WorldUnitWalkableClimb / m_cfg.ch);
	m_cfg.walkableRadius = (int)ceilf(WorldUnitWalkableRadius / m_cfg.cs);
	m_cfg.maxEdgeLen = 8;(int)MaxEdgeLen;
	m_cfg.maxSimplificationError = MaxSimplificationError;
	m_cfg.minRegionArea = (int)rcSqr(MinRegionSize);		// Note: area = size*size
	m_cfg.mergeRegionArea = (int)rcSqr(MergeRegionSize);	// Note: area = size*size
	m_cfg.maxVertsPerPoly = 6;
	m_cfg.tileSize = (int)TileSize;
	m_cfg.borderSize = m_cfg.walkableRadius + 3; // Reserve enough padding.
	m_cfg.width = m_cfg.tileSize;// + m_cfg.borderSize*2;
	m_cfg.height = m_cfg.tileSize;// + m_cfg.borderSize*2;
	m_cfg.detailSampleDist = DetailSampleDist;
	m_cfg.detailSampleMaxError = DetailSampleMaxError;
	
	rcVcopy(m_cfg.bmin, bmin);
	rcVcopy(m_cfg.bmax, bmax);
	m_cfg.bmin[0] -= m_cfg.borderSize*m_cfg.cs;
	m_cfg.bmin[2] -= m_cfg.borderSize*m_cfg.cs;
	m_cfg.bmax[0] += m_cfg.borderSize*m_cfg.cs;
	m_cfg.bmax[2] += m_cfg.borderSize*m_cfg.cs;
	
	std::cout << "Building navigation:" << std::endl;
	std::cout << m_cfg.width << " x " << m_cfg.height << std::endl;
	std::cout << nverts/1000.0f << "K verts, " << ntris/1000.0f << "K tris" << std::endl;
	
	// Allocate voxel heightfield where we rasterize our input data to.
	m_solid = rcAllocHeightfield();
	if (!m_solid)
	{
		std::cout << "Out of memory solid." << std::endl;
		return 0;
	}
	if (!rcCreateHeightfield(m_ctx, *m_solid, m_cfg.width, m_cfg.height, m_cfg.bmin, m_cfg.bmax, m_cfg.cs, m_cfg.ch))
	{
		std::cout << "Could not create solid heightfield." << std::endl;
		return 0;
	}
	
	// Allocate array that can hold triangle flags.
	// If you have multiple meshes you need to process, allocate
	// and array which can hold the max number of triangles you need to process.
	m_triareas = new unsigned char[chunkyMesh->maxTrisPerChunk];
	if (!m_triareas)
	{
		std::cout << "Out of memory m_triareas." << std::endl;
		return 0;
	}
	
	float tbmin[2], tbmax[2];
	tbmin[0] = m_cfg.bmin[0];
	tbmin[1] = m_cfg.bmin[2];
	tbmax[0] = m_cfg.bmax[0];
	tbmax[1] = m_cfg.bmax[2];
	int cid[512];// TODO: Make grow when returning too many items.
	const int ncid = rcGetChunksOverlappingRect(chunkyMesh, tbmin, tbmax, cid, 512);
	if (!ncid)
		return 0;
	
	m_tileTriCount = 0;
	
	for (int i = 0; i < ncid; ++i)
	{
		const rcChunkyTriMeshNode& node = chunkyMesh->nodes[cid[i]];
		const int* ctris = &chunkyMesh->tris[node.i*3];
		const int nctris = node.n;
		
		m_tileTriCount += nctris;
		
		memset(m_triareas, 0, nctris*sizeof(unsigned char));
		rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle,
								verts, nverts, ctris, nctris, m_triareas);
		
		rcRasterizeTriangles(m_ctx, verts, nverts, ctris, m_triareas, nctris, *m_solid, m_cfg.walkableClimb);
	}
	
	if (!m_keepInterResults)
	{
		delete [] m_triareas;
		m_triareas = 0;
	}
	
	// Once all geometry is rasterized, we do initial pass of filtering to
	// remove unwanted overhangs caused by the conservative rasterization
	// as well as filter spans where the character cannot possibly stand.
	rcFilterLowHangingWalkableObstacles(m_ctx, m_cfg.walkableClimb, *m_solid);
	rcFilterLedgeSpans(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid);
	rcFilterWalkableLowHeightSpans(m_ctx, m_cfg.walkableHeight, *m_solid);
	
	// Compact the heightfield so that it is faster to handle from now on.
	// This will result more cache coherent data as well as the neighbours
	// between walkable cells will be calculated.
	m_chf = rcAllocCompactHeightfield();
	if (!m_chf)
	{
		std::cout << "Out of memory chf." << std::endl;
		return 0;
	}
	if (!rcBuildCompactHeightfield(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid, *m_chf))
	{
		std::cout << "Could not build compact data." << std::endl;
		return 0;
	}
	
	if (!m_keepInterResults)
	{
		rcFreeHeightField(m_solid);
		m_solid = 0;
	}

	// Erode the walkable area by agent radius.
	if (!rcErodeWalkableArea(m_ctx, m_cfg.walkableRadius, *m_chf))
	{
		std::cout << "Could not erode." << std::endl;
		return 0;
	}
	
	if (m_monotonePartitioning)
	{
		// Partition the walkable surface into simple regions without holes.
		if (!rcBuildRegionsMonotone(m_ctx, *m_chf, m_cfg.borderSize, m_cfg.minRegionArea, m_cfg.mergeRegionArea))
		{
			std::cout << "Could not build regions." << std::endl;
			return 0;
		}
	}
	else
	{
		// Prepare for region partitioning, by calculating distance field along the walkable surface.
		if (!rcBuildDistanceField(m_ctx, *m_chf))
		{
			std::cout << "Could not build distance field." << std::endl;
			return 0;
		}
		
		// Partition the walkable surface into simple regions without holes.
		if (!rcBuildRegions(m_ctx, *m_chf, m_cfg.borderSize, m_cfg.minRegionArea, m_cfg.mergeRegionArea))
		{
			std::cout << "Could not build regions." << std::endl;
			return 0;
		}
	}
 	
	// Create contours.
	m_cset = rcAllocContourSet();
	if (!m_cset)
	{
		std::cout << "Out of memory 'cset'." << std::endl;
		return 0;
	}
	if (!rcBuildContours(m_ctx, *m_chf, m_cfg.maxSimplificationError, m_cfg.maxEdgeLen, *m_cset))
	{
		std::cout << "Could not create contours." << std::endl;
		return 0;
	}
	
	if (m_cset->nconts == 0)
	{
		return 0;
	}
	
	// Build polygon navmesh from the contours.
	m_pmesh = rcAllocPolyMesh();
	if (!m_pmesh)
	{
		std::cout << "Out of memory 'pmesh'." << std::endl;
		return 0;
	}
	if (!rcBuildPolyMesh(m_ctx, *m_cset, m_cfg.maxVertsPerPoly, *m_pmesh))
	{
		std::cout << "Could not triangulate contours." << std::endl;
		return 0;
	}
	
	// Build detail mesh.
	m_dmesh = rcAllocPolyMeshDetail();
	if (!m_dmesh)
	{
		std::cout << "Out of memory 'dmesh'." << std::endl;
		return 0;
	}
	
	if (!rcBuildPolyMeshDetail(m_ctx, *m_pmesh, *m_chf,
							   m_cfg.detailSampleDist, m_cfg.detailSampleMaxError,
							   *m_dmesh))
	{
		std::cout << "Could not build polymesh detail" << std::endl;
		return 0;
	}
	
	if (!m_keepInterResults)
	{
		rcFreeCompactHeightfield(m_chf);
		m_chf = 0;
		rcFreeContourSet(m_cset);
		m_cset = 0;
	}
	
	unsigned char* navData = 0;
	int navDataSize = 0;
	if (m_cfg.maxVertsPerPoly <= DT_VERTS_PER_POLYGON)
	{
		if (m_pmesh->nverts >= 0xffff)
		{
			// The vertex indices are ushorts, and cannot point to more than 0xffff vertices.
			std::cout << "Too many vertices per tile!" << std::endl;
			return 0;
		}
		
		// Update poly flags from areas.
		for (int i = 0; i < m_pmesh->npolys; ++i)
		{
			if (m_pmesh->areas[i] == RC_WALKABLE_AREA)
				m_pmesh->areas[i] = SAMPLE_POLYAREA_GROUND;
			
			if (m_pmesh->areas[i] == SAMPLE_POLYAREA_GROUND ||
				m_pmesh->areas[i] == SAMPLE_POLYAREA_GRASS ||
				m_pmesh->areas[i] == SAMPLE_POLYAREA_ROAD)
			{
				m_pmesh->flags[i] = SAMPLE_POLYFLAGS_WALK;
			}
			else if (m_pmesh->areas[i] == SAMPLE_POLYAREA_WATER)
			{
				m_pmesh->flags[i] = SAMPLE_POLYFLAGS_SWIM;
			}
			else if (m_pmesh->areas[i] == SAMPLE_POLYAREA_DOOR)
			{
				m_pmesh->flags[i] = SAMPLE_POLYFLAGS_WALK | SAMPLE_POLYFLAGS_DOOR;
			}
		}
		
		dtNavMeshCreateParams params;
		memset(&params, 0, sizeof(params));
		params.verts = m_pmesh->verts;
		params.vertCount = m_pmesh->nverts;
		params.polys = m_pmesh->polys;
		params.polyAreas = m_pmesh->areas;
		params.polyFlags = m_pmesh->flags;
		params.polyCount = m_pmesh->npolys;
		params.nvp = m_pmesh->nvp;
		params.detailMeshes = m_dmesh->meshes;
		params.detailVerts = m_dmesh->verts;
		params.detailVertsCount = m_dmesh->nverts;
		params.detailTris = m_dmesh->tris;
		params.detailTriCount = m_dmesh->ntris;
		params.walkableHeight = WorldUnitWalkableHeight;
		params.walkableRadius = WorldUnitWalkableRadius;
		params.walkableClimb = WorldUnitWalkableClimb;
		params.tileX = tx;
		params.tileY = ty;
		params.tileLayer = 0;
		rcVcopy(params.bmin, m_pmesh->bmin);
		rcVcopy(params.bmax, m_pmesh->bmax);
		params.cs = m_cfg.cs;
		params.ch = m_cfg.ch;
		params.buildBvTree = true;
		
		if (!dtCreateNavMeshData(&params, &navData, &navDataSize))
		{
			std::cout << "Could not build detour navmesh" << std::endl;
			return 0;
		}		
	}
	m_tileMemUsage = navDataSize/1024.0f;
	std::cout << "Memory usage: " << m_tileMemUsage << std::endl;

	dataSize = navDataSize;
	return navData;
}

Thank you.

[Bananenbrot]

Don't mean to rip on you, but Recast's code in itself is not that easy to trace and pasting a 300 lines (approx, donno) doesn't make it better. You know google and sitewnedcore.com, don't you? because the first match from 'findNearestPoly' is 2 months old. It may help you finding your bug. http://www.ownedcore.com/forums/worl...oly-fails.html (Detour - findNearestPoly fails)
If you didn't already found that, you should use google more often and more efficiently to complement your programming skills.

[pladi]

Allready googled it, ofc and been reading pretty much every thread (inkluding the one you linked, in which his navmesh was generated outside of the actual mesh, which isn't my case - therefor the picture ). The reason for posting my code, was simply in case someone hadn't tried my problem, but would give a shot at helping anyway.

[guizmows]

are you sure of you meshes coordinates?
R&D demo use his own coordinate calculation, but how have you done that in your bot?