DoomRTX/neo/engine/tools/compilers/recast/RecastNavigation.cpp

/*
===========================================================================

IceTech GPL Source Code
Copyright (C) 2026 Justin Marshall

===========================================================================
*/

#include "precompiled.h"
#pragma hdrstop

#include "RecastNavigation.h"

#include "Recast.h"
#include "DetourAlloc.h"
#include "DetourCommon.h"
#include "DetourNavMesh.h"
#include "DetourNavMeshBuilder.h"
#include "DetourNavMeshQuery.h"
#include "DetourCrowd.h"

static const int RECAST_NAVMESH_VERSION = 1;
static const int RECAST_NAVMESH_MAGIC = ( 'R' << 24 ) | ( 'N' << 16 ) | ( 'A' << 8 ) | 'V';
static const unsigned short RECAST_POLYFLAGS_WALK = 0x01;
static const int MAX_RECAST_PATH_POLYS = 256;
static const float RECAST_AREA_BLOCKER_MATCH_EXPAND = 128.0f;
static const float RECAST_BUILD_CELL_SIZE = 4.0f;
static const float RECAST_BUILD_CELL_HEIGHT = 2.0f;

struct recastBoundsBlocker_t {
	idBounds				bounds;
	int						areaContents;
	bool					active;
};

class idRecastNavMeshLocal {
public:
							idRecastNavMeshLocal( void );
							~idRecastNavMeshLocal( void );

	void					Shutdown( void );
	bool					InitForAAS( const idStr &aasName, const idAASSettings &settings, unsigned int mapFileCRC );
	bool					Load( const idStr &fileName, unsigned int mapFileCRC );
	bool					BuildAndSave( const idMapFile *mapFile, const idStr &fileName, unsigned int mapFileCRC, const idAASSettings &settings );
	void					DebugDraw( idRenderWorld *renderWorld, int drawMode, int lifetime ) const;

	bool					IsLoaded( void ) const { return navMesh != NULL && navQuery != NULL; }
	const idStr &			GetName( void ) const { return name; }
	int						NumPolys( void ) const { return polyRefs.Num(); }
	const idAASSettings *	GetSettings( void ) const { return IsLoaded() ? &settings : NULL; }
	void					Stats( void ) const;

	int						PointAreaNum( const idVec3 &origin ) const;
	int						PointReachableAreaNum( const idVec3 &origin, const idBounds &searchBounds, const int areaFlags ) const;
	int						BoundsReachableAreaNum( const idBounds &bounds, const int areaFlags ) const;
	void					PushPointIntoAreaNum( int areaNum, idVec3 &origin ) const;
	idVec3					AreaCenter( int areaNum ) const;
	int						AreaFlags( int areaNum ) const;
	int						AreaTravelFlags( int areaNum ) const;
	bool					Trace( aasTrace_t &trace, const idVec3 &start, const idVec3 &end ) const;

	bool					SetAreaState( const idBounds &bounds, const int areaContents, bool disabled );
	recastObstacleHandle_t	AddObstacle( const idBounds &bounds );
	void					RemoveObstacle( const recastObstacleHandle_t handle );
	void					RemoveAllObstacles( void );

	int						TravelTimeToGoalArea( int areaNum, const idVec3 &origin, int goalAreaNum, int travelFlags ) const;
	bool					RouteToGoalArea( int areaNum, const idVec3 origin, int goalAreaNum, int travelFlags, recastPath_t &route ) const;
	bool					PathToGoal( recastPath_t &path, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags ) const;
	bool					PathValid( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, idVec3 &endPos, int &endAreaNum ) const;
	bool					PathAreaList( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, int *areas, int &numAreas, int maxAreas ) const;

	static bool				BuildMapFile( const idStr &mapName, const idStr &aasType );
	static idStr			NavFileNameForAASName( const idStr &aasName );

private:
	static void				ToDetour( const idVec3 &in, float out[3] );
	static idVec3			FromDetour( const float in[3] );
	bool					FindNearestPoly( const idVec3 &origin, const idBounds &searchBounds, dtPolyRef &ref, idVec3 *nearest ) const;
	int						AreaForRef( dtPolyRef ref ) const;
	dtPolyRef				RefForArea( int areaNum ) const;
	bool					FindPathRefs( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, dtPolyRef *pathRefs, int &numPathRefs, const int maxPathRefs ) const;
	bool					LineHitsBlocker( const idVec3 &start, const idVec3 &end ) const;
	bool					PointInsideBlocker( const idVec3 &origin ) const;

private:
	idStr					name;
	unsigned int			crc;
	idAASSettings			settings;
	dtNavMesh *				navMesh;
	dtNavMeshQuery *		navQuery;
	dtCrowd *				crowd;
	mutable idList<dtPolyRef> polyRefs;
	idList<recastBoundsBlocker_t> obstacles;
	idList<recastBoundsBlocker_t> areaBlockers;
};

class idDoomRecastContext : public rcContext {
public:
	idDoomRecastContext( void ) : rcContext( true ) {}

protected:
	virtual void doLog( const rcLogCategory category, const char *msg, const int len ) {
		idStr text( msg );
		if ( len >= 0 && len < text.Length() ) {
			text.CapLength( len );
		}
		if ( category == RC_LOG_ERROR ) {
			common->Warning( "Recast: %s", text.c_str() );
		} else if ( category == RC_LOG_WARNING ) {
			common->DWarning( "Recast: %s", text.c_str() );
		} else {
			common->Printf( "Recast: %s\n", text.c_str() );
		}
	}
};

struct recastBuildGeometry_t {
	idList<float>	verts;
	idList<int>		tris;
	idBounds		bounds;

	void Clear( void ) {
		verts.Clear();
		tris.Clear();
		bounds.Clear();
	}
};

static bool RecastMaterialIsSolid( const char *materialName ) {
	const idMaterial *mat = declManager->FindMaterial( materialName );
	if ( !mat ) {
		return false;
	}
	const int contents = mat->GetContentFlags();
	return ( contents & ( CONTENTS_SOLID | CONTENTS_AAS_SOLID | CONTENTS_MONSTERCLIP ) ) != 0;
}

static bool RecastEntityIsBakeGeometry( const idMapEntity *mapEnt, int entityNum ) {
	const char *classname = mapEnt->epairs.GetString( "classname" );

	if ( entityNum == 0 ) {
		return true;
	}

	if ( idStr::Icmp( classname, "func_static" ) == 0 ||
		 idStr::Icmp( classname, "func_clipmodel" ) == 0 ) {
		return true;
	}

	return false;
}

static void RecastAppendVertex( recastBuildGeometry_t &geom, const idVec3 &v ) {
	geom.verts.Append( v.x );
	geom.verts.Append( v.z );
	geom.verts.Append( v.y );
	geom.bounds.AddPoint( v );
}

static void RecastAppendTriangle( recastBuildGeometry_t &geom, const idVec3 &a, const idVec3 &b, const idVec3 &c ) {
	if ( idWinding::TriangleArea( a, b, c ) < 0.1f ) {
		return;
	}
	const int base = geom.verts.Num() / 3;
	RecastAppendVertex( geom, a );
	RecastAppendVertex( geom, b );
	RecastAppendVertex( geom, c );
	geom.tris.Append( base + 0 );
	geom.tris.Append( base + 1 );
	geom.tris.Append( base + 2 );
}

static void RecastAddWinding( recastBuildGeometry_t &geom, const idWinding &winding, const idVec3 &origin, const idMat3 &axis ) {
	const int numPoints = winding.GetNumPoints();
	if ( numPoints < 3 ) {
		return;
	}

	const idVec3 v0 = winding[0].ToVec3() * axis + origin;
	for ( int i = 1; i < numPoints - 1; i++ ) {
		const idVec3 v1 = winding[i].ToVec3() * axis + origin;
		const idVec3 v2 = winding[i + 1].ToVec3() * axis + origin;
		RecastAppendTriangle( geom, v0, v1, v2 );
	}
}

static void RecastAddBrushGeometry( recastBuildGeometry_t &geom, const idMapBrush *brush, const idVec3 &origin, const idMat3 &axis ) {
	for ( int i = 0; i < brush->GetNumSides(); i++ ) {
		const idMapBrushSide *side = brush->GetSide( i );
		if ( !RecastMaterialIsSolid( side->GetMaterial() ) ) {
			continue;
		}

		idFixedWinding winding( side->GetPlane() );
		bool clipped = true;
		for ( int j = 0; j < brush->GetNumSides(); j++ ) {
			if ( j == i ) {
				continue;
			}
			if ( !winding.ClipInPlace( -brush->GetSide( j )->GetPlane(), ON_EPSILON, true ) ) {
				clipped = false;
				break;
			}
		}
		if ( clipped && !winding.IsTiny() && !winding.IsHuge() ) {
			RecastAddWinding( geom, winding, origin, axis );
		}
	}
}

static void RecastAddPatchGeometry( recastBuildGeometry_t &geom, const idMapPatch *patch, const idVec3 &origin, const idMat3 &axis, const idAASSettings &settings ) {
	if ( !settings.usePatches || !RecastMaterialIsSolid( patch->GetMaterial() ) ) {
		return;
	}

	idSurface_Patch mesh( *patch );
	if ( patch->GetExplicitlySubdivided() ) {
		mesh.SubdivideExplicit( patch->GetHorzSubdivisions(), patch->GetVertSubdivisions(), false, true );
	} else {
		mesh.Subdivide( DEFAULT_CURVE_MAX_ERROR_CD, DEFAULT_CURVE_MAX_ERROR_CD, DEFAULT_CURVE_MAX_LENGTH_CD, false );
	}

	const idDrawVert *verts = mesh.GetVertices();
	const int *indexes = mesh.GetIndexes();
	for ( int i = 0; i + 2 < mesh.GetNumIndexes(); i += 3 ) {
		RecastAppendTriangle( geom,
			verts[indexes[i + 0]].xyz * axis + origin,
			verts[indexes[i + 1]].xyz * axis + origin,
			verts[indexes[i + 2]].xyz * axis + origin );
	}
}

static void RecastAddMapEntityGeometry( recastBuildGeometry_t &geom, const idMapEntity *mapEnt, const idAASSettings &settings ) {
	idVec3 origin;
	idMat3 axis;

	mapEnt->epairs.GetVector( "origin", "0 0 0", origin );
	if ( !mapEnt->epairs.GetMatrix( "rotation", "1 0 0 0 1 0 0 0 1", axis ) ) {
		const float angle = mapEnt->epairs.GetFloat( "angle" );
		if ( angle != 0.0f ) {
			axis = idAngles( 0.0f, angle, 0.0f ).ToMat3();
		} else {
			axis.Identity();
		}
	}

	for ( int i = 0; i < mapEnt->GetNumPrimitives(); i++ ) {
		idMapPrimitive *prim = mapEnt->GetPrimitive( i );
		if ( prim->GetType() == idMapPrimitive::TYPE_BRUSH ) {
			RecastAddBrushGeometry( geom, static_cast<const idMapBrush *>( prim ), origin, axis );
		} else if ( prim->GetType() == idMapPrimitive::TYPE_PATCH ) {
			RecastAddPatchGeometry( geom, static_cast<const idMapPatch *>( prim ), origin, axis, settings );
		}
	}
}

static bool RecastCollectMapGeometry( recastBuildGeometry_t &geom, const idMapFile *mapFile, const idAASSettings &settings ) {
	geom.Clear();

	int acceptedEntities = 0;
	int skippedEntities = 0;
	int skippedDynamicEntities = 0;
	int brushPrimitives = 0;
	int patchPrimitives = 0;

	common->Printf( "Recast: scanning %d map entities for build geometry\n", mapFile->GetNumEntities() );

	for ( int i = 0; i < mapFile->GetNumEntities(); i++ ) {
		const idMapEntity *mapEnt = mapFile->GetEntity( i );

		if ( !RecastEntityIsBakeGeometry( mapEnt, i ) ) {
			const char *classname = mapEnt->epairs.GetString( "classname" );
			if ( idStr::Icmp( classname, "func_aas_obstacle" ) == 0 ||
				 idStr::Icmp( classname, "func_aas_portal" ) == 0 ||
				 idStr::Icmp( classname, "func_door" ) == 0 ||
				 idStr::Icmp( classname, "func_mover" ) == 0 ) {
				skippedDynamicEntities++;
			}
			skippedEntities++;
			continue;
		}

		acceptedEntities++;
		for ( int j = 0; j < mapEnt->GetNumPrimitives(); j++ ) {
			idMapPrimitive *prim = mapEnt->GetPrimitive( j );
			if ( prim->GetType() == idMapPrimitive::TYPE_BRUSH ) {
				brushPrimitives++;
			} else if ( prim->GetType() == idMapPrimitive::TYPE_PATCH ) {
				patchPrimitives++;
			}
		}
		RecastAddMapEntityGeometry( geom, mapEnt, settings );
	}

	common->Printf( "Recast: accepted %d static entities, skipped %d entities (%d dynamic AAS/door/mover), saw %d brushes and %d patches\n",
		acceptedEntities, skippedEntities, skippedDynamicEntities, brushPrimitives, patchPrimitives );
	common->Printf( "Recast: collected %d verts and %d tris, bounds mins (%g %g %g), maxs (%g %g %g)\n",
		geom.verts.Num() / 3, geom.tris.Num() / 3,
		geom.bounds[0].x, geom.bounds[0].y, geom.bounds[0].z,
		geom.bounds[1].x, geom.bounds[1].y, geom.bounds[1].z );

	return geom.verts.Num() >= 9 && geom.tris.Num() >= 3;
}

idRecastNavMeshLocal::idRecastNavMeshLocal( void ) {
	crc = 0;
	navMesh = NULL;
	navQuery = NULL;
	crowd = NULL;
}

idRecastNavMeshLocal::~idRecastNavMeshLocal( void ) {
	Shutdown();
}

void idRecastNavMeshLocal::Shutdown( void ) {
	if ( crowd ) {
		dtFreeCrowd( crowd );
		crowd = NULL;
	}
	if ( navQuery ) {
		dtFreeNavMeshQuery( navQuery );
		navQuery = NULL;
	}
	if ( navMesh ) {
		dtFreeNavMesh( navMesh );
		navMesh = NULL;
	}
	name.Clear();
	crc = 0;
	polyRefs.Clear();
	obstacles.Clear();
	areaBlockers.Clear();
}

bool idRecastNavMeshLocal::InitForAAS( const idStr &aasName, const idAASSettings &aasSettings, unsigned int mapFileCRC ) {
	settings = aasSettings;
	crc = mapFileCRC;
	name = aasName;
	return true;
}

idStr idRecastNavMeshLocal::NavFileNameForAASName( const idStr &aasName ) {
	idStr navName = aasName;
	navName += ".navmesh";
	return navName;
}

void idRecastNavMeshLocal::DebugDraw( idRenderWorld *renderWorld, int drawMode, int lifetime ) const {
	if ( !renderWorld || !navMesh || drawMode <= 0 ) {
		return;
	}

	const idVec3 lift( 0.0f, 0.0f, 2.0f );

	for ( int tileNum = 0; tileNum < navMesh->getMaxTiles(); tileNum++ ) {
		const dtMeshTile *tile = navMesh->getTile( tileNum );
		if ( !tile || !tile->header ) {
			continue;
		}

		for ( int polyNum = 0; polyNum < tile->header->polyCount; polyNum++ ) {
			const dtPoly *poly = &tile->polys[polyNum];
			if ( poly->getType() != DT_POLYTYPE_GROUND || poly->vertCount < 3 ) {
				continue;
			}

			for ( int edgeNum = 0; edgeNum < poly->vertCount; edgeNum++ ) {
				const float *start = &tile->verts[poly->verts[edgeNum] * 3];
				const float *end = &tile->verts[poly->verts[( edgeNum + 1 ) % poly->vertCount] * 3];
				renderWorld->DebugLine( colorCyan, FromDetour( start ) + lift, FromDetour( end ) + lift, lifetime, false );
			}
		}
	}

	if ( drawMode < 2 ) {
		return;
	}

	for ( int i = 0; i < obstacles.Num(); i++ ) {
		if ( obstacles[i].active ) {
			renderWorld->DebugBounds( colorOrange, obstacles[i].bounds, vec3_origin, lifetime );
		}
	}
	for ( int i = 0; i < areaBlockers.Num(); i++ ) {
		if ( areaBlockers[i].active ) {
			renderWorld->DebugBounds( colorRed, areaBlockers[i].bounds, vec3_origin, lifetime );
		}
	}
}

bool idRecastNavMeshLocal::Load( const idStr &fileName, unsigned int mapFileCRC ) {
	Shutdown();

	idFile *file = fileSystem->OpenFileRead( fileName );
	if ( !file ) {
		return false;
	}

	int magic, version, dataSize;
	unsigned int fileCRC;
	file->ReadInt( magic );
	file->ReadInt( version );
	file->ReadUnsignedInt( fileCRC );
	file->ReadInt( dataSize );

	if ( magic != RECAST_NAVMESH_MAGIC || version != RECAST_NAVMESH_VERSION || fileCRC != mapFileCRC || dataSize <= 0 ) {
		fileSystem->CloseFile( file );
		return false;
	}

	unsigned char *navData = (unsigned char *)dtAlloc( dataSize, DT_ALLOC_PERM );
	if ( !navData ) {
		fileSystem->CloseFile( file );
		return false;
	}
	if ( file->Read( navData, dataSize ) != dataSize ) {
		dtFree( navData );
		fileSystem->CloseFile( file );
		return false;
	}
	fileSystem->CloseFile( file );

	navMesh = dtAllocNavMesh();
	if ( !navMesh ) {
		dtFree( navData );
		return false;
	}
	if ( dtStatusFailed( navMesh->init( navData, dataSize, DT_TILE_FREE_DATA ) ) ) {
		dtFree( navData );
		Shutdown();
		return false;
	}

	navQuery = dtAllocNavMeshQuery();
	if ( !navQuery || dtStatusFailed( navQuery->init( navMesh, 4096 ) ) ) {
		Shutdown();
		return false;
	}

	crowd = dtAllocCrowd();
	if ( crowd ) {
		const idBounds &bounds = settings.boundingBoxes[0];
		const float radius = max( idMath::Fabs( bounds[0].x ), idMath::Fabs( bounds[1].x ) );
		crowd->init( 128, radius, navMesh );
	}

	name = fileName;
	crc = mapFileCRC;
	return true;
}

bool idRecastNavMeshLocal::BuildAndSave( const idMapFile *mapFile, const idStr &fileName, unsigned int mapFileCRC, const idAASSettings &aasSettings ) {
	common->Printf( "Recast: building navmesh for %s -> %s\n", mapFile->GetName(), fileName.c_str() );
	common->Printf( "Recast: map geometry CRC %u\n", mapFileCRC );

	recastBuildGeometry_t geom;
	if ( !RecastCollectMapGeometry( geom, mapFile, aasSettings ) ) {
		common->Warning( "Recast: no solid map geometry found for %s", mapFile->GetName() );
		return false;
	}

	idDoomRecastContext ctx;
	rcConfig cfg;
	memset( &cfg, 0, sizeof( cfg ) );

	const idBounds &agentBounds = aasSettings.boundingBoxes[0];
	const float agentRadius = max( idMath::Fabs( agentBounds[0].x ), idMath::Fabs( agentBounds[1].x ) );
	const float agentHeight = agentBounds[1].z - agentBounds[0].z;

	common->Printf( "Recast: agent bbox mins (%g %g %g), maxs (%g %g %g)\n",
		agentBounds[0].x, agentBounds[0].y, agentBounds[0].z,
		agentBounds[1].x, agentBounds[1].y, agentBounds[1].z );
	common->Printf( "Recast: agent radius %g, height %g, max step %g, min floor cos %g\n",
		agentRadius, agentHeight, aasSettings.maxStepHeight, aasSettings.minFloorCos );

	cfg.cs = RECAST_BUILD_CELL_SIZE;
	cfg.ch = RECAST_BUILD_CELL_HEIGHT;
	cfg.walkableSlopeAngle = RAD2DEG( idMath::ACos( aasSettings.minFloorCos ) );
	cfg.walkableHeight = (int)ceilf( agentHeight / cfg.ch );
	cfg.walkableClimb = Max( 1, (int)ceilf( aasSettings.maxStepHeight / cfg.ch ) );
	cfg.walkableRadius = (int)ceilf( agentRadius / cfg.cs );
	cfg.maxEdgeLen = (int)( 12.0f * 64.0f / cfg.cs );
	cfg.maxSimplificationError = 1.3f;
	cfg.minRegionArea = rcSqr( 4 );
	cfg.mergeRegionArea = rcSqr( 12 );
	cfg.maxVertsPerPoly = 6;
	cfg.detailSampleDist = cfg.cs * 6.0f;
	cfg.detailSampleMaxError = cfg.ch;

	cfg.bmin[0] = geom.bounds[0].x;
	cfg.bmin[1] = geom.bounds[0].z;
	cfg.bmin[2] = geom.bounds[0].y;
	cfg.bmax[0] = geom.bounds[1].x;
	cfg.bmax[1] = geom.bounds[1].z;
	cfg.bmax[2] = geom.bounds[1].y;
	rcCalcGridSize( cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height );

	common->Printf( "Recast: config cellSize %g, cellHeight %g, grid %d x %d\n", cfg.cs, cfg.ch, cfg.width, cfg.height );
	common->Printf( "Recast: walkable height %d, climb %d, radius %d, slope %g degrees\n",
		cfg.walkableHeight, cfg.walkableClimb, cfg.walkableRadius, cfg.walkableSlopeAngle );
	common->Printf( "Recast: region min %d, merge %d, max edge len %d, max verts/poly %d\n",
		cfg.minRegionArea, cfg.mergeRegionArea, cfg.maxEdgeLen, cfg.maxVertsPerPoly );

	rcHeightfield *heightfield = rcAllocHeightfield();
	rcCompactHeightfield *compactHeightfield = NULL;
	rcContourSet *contourSet = NULL;
	rcPolyMesh *polyMesh = NULL;
	rcPolyMeshDetail *detailMesh = NULL;
	unsigned char *triAreas = NULL;
	unsigned char *navData = NULL;
	int navDataSize = 0;
	bool ok = false;

	const float *verts = geom.verts.Ptr();
	const int numVerts = geom.verts.Num() / 3;
	const int *tris = geom.tris.Ptr();
	const int numTris = geom.tris.Num() / 3;

	common->Printf( "Recast: allocating heightfield\n" );
	if ( heightfield &&
		 rcCreateHeightfield( &ctx, *heightfield, cfg.width, cfg.height, cfg.bmin, cfg.bmax, cfg.cs, cfg.ch ) ) {
		common->Printf( "Recast: heightfield created\n" );
		triAreas = new unsigned char[numTris];
		memset( triAreas, 0, numTris * sizeof( unsigned char ) );
		common->Printf( "Recast: marking walkable triangles\n" );
		rcMarkWalkableTriangles( &ctx, cfg.walkableSlopeAngle, verts, numVerts, tris, numTris, triAreas );
		common->Printf( "Recast: rasterizing %d triangles\n", numTris );
		if ( rcRasterizeTriangles( &ctx, verts, numVerts, tris, triAreas, numTris, *heightfield, cfg.walkableClimb ) ) {
			common->Printf( "Recast: filtering low-hanging obstacles, ledges, and low spans\n" );
			rcFilterLowHangingWalkableObstacles( &ctx, cfg.walkableClimb, *heightfield );
			rcFilterLedgeSpans( &ctx, cfg.walkableHeight, cfg.walkableClimb, *heightfield );
			rcFilterWalkableLowHeightSpans( &ctx, cfg.walkableHeight, *heightfield );

			common->Printf( "Recast: building compact heightfield\n" );
			compactHeightfield = rcAllocCompactHeightfield();
			if ( compactHeightfield &&
				 rcBuildCompactHeightfield( &ctx, cfg.walkableHeight, cfg.walkableClimb, *heightfield, *compactHeightfield ) &&
				 rcErodeWalkableArea( &ctx, cfg.walkableRadius, *compactHeightfield ) &&
				 rcBuildDistanceField( &ctx, *compactHeightfield ) &&
				 rcBuildRegions( &ctx, *compactHeightfield, 0, cfg.minRegionArea, cfg.mergeRegionArea ) ) {
				common->Printf( "Recast: compact heightfield built, walkable spans %d\n", compactHeightfield->spanCount );
				common->Printf( "Recast: building contours and poly mesh\n" );
				contourSet = rcAllocContourSet();
				polyMesh = rcAllocPolyMesh();
				detailMesh = rcAllocPolyMeshDetail();
				if ( contourSet && polyMesh && detailMesh &&
					 rcBuildContours( &ctx, *compactHeightfield, cfg.maxSimplificationError, cfg.maxEdgeLen, *contourSet ) &&
					 rcBuildPolyMesh( &ctx, *contourSet, cfg.maxVertsPerPoly, *polyMesh ) &&
					 rcBuildPolyMeshDetail( &ctx, *polyMesh, *compactHeightfield, cfg.detailSampleDist, cfg.detailSampleMaxError, *detailMesh ) ) {
					common->Printf( "Recast: contours %d, poly mesh %d verts / %d polys, detail %d verts / %d tris\n",
						contourSet->nconts, polyMesh->nverts, polyMesh->npolys, detailMesh->nverts, detailMesh->ntris );
					for ( int i = 0; i < polyMesh->npolys; i++ ) {
						if ( polyMesh->areas[i] == RC_WALKABLE_AREA ) {
							polyMesh->areas[i] = 0;
						}
						polyMesh->flags[i] = RECAST_POLYFLAGS_WALK;
					}

					dtNavMeshCreateParams params;
					memset( &params, 0, sizeof( params ) );
					params.verts = polyMesh->verts;
					params.vertCount = polyMesh->nverts;
					params.polys = polyMesh->polys;
					params.polyAreas = polyMesh->areas;
					params.polyFlags = polyMesh->flags;
					params.polyCount = polyMesh->npolys;
					params.nvp = polyMesh->nvp;
					params.detailMeshes = detailMesh->meshes;
					params.detailVerts = detailMesh->verts;
					params.detailVertsCount = detailMesh->nverts;
					params.detailTris = detailMesh->tris;
					params.detailTriCount = detailMesh->ntris;
					params.walkableHeight = agentHeight;
					params.walkableRadius = agentRadius;
					params.walkableClimb = aasSettings.maxStepHeight;
					rcVcopy( params.bmin, polyMesh->bmin );
					rcVcopy( params.bmax, polyMesh->bmax );
					params.cs = cfg.cs;
					params.ch = cfg.ch;
					params.buildBvTree = true;

					common->Printf( "Recast: creating Detour navmesh data\n" );
					ok = dtCreateNavMeshData( &params, &navData, &navDataSize );
					if ( ok ) {
						common->Printf( "Recast: Detour navmesh data created, %d bytes\n", navDataSize );
					} else {
						common->Warning( "Recast: dtCreateNavMeshData failed for %s", fileName.c_str() );
					}
				} else {
					common->Warning( "Recast: failed to build contours/poly mesh/detail mesh for %s", fileName.c_str() );
				}
			} else {
				common->Warning( "Recast: failed to build compact heightfield/regions for %s", fileName.c_str() );
			}
		} else {
			common->Warning( "Recast: failed to rasterize triangles for %s", fileName.c_str() );
		}
	} else {
		common->Warning( "Recast: failed to allocate/create heightfield for %s", fileName.c_str() );
	}

	if ( ok && navData && navDataSize > 0 ) {
		common->Printf( "Recast: writing navmesh file %s\n", fileName.c_str() );
		idFile *out = fileSystem->OpenFileWrite( fileName, "fs_devpath" );
		if ( out ) {
			out->WriteInt( RECAST_NAVMESH_MAGIC );
			out->WriteInt( RECAST_NAVMESH_VERSION );
			out->WriteUnsignedInt( mapFileCRC );
			out->WriteInt( navDataSize );
			out->Write( navData, navDataSize );
			fileSystem->CloseFile( out );
			common->Printf( "Wrote Recast navmesh %s (%d bytes, %d polys)\n", fileName.c_str(), navDataSize, polyMesh ? polyMesh->npolys : 0 );
		} else {
			common->Warning( "Recast: could not open %s for writing", fileName.c_str() );
			ok = false;
		}
	}

	if ( navData ) {
		dtFree( navData );
	}
	delete[] triAreas;
	if ( detailMesh ) {
		rcFreePolyMeshDetail( detailMesh );
	}
	if ( polyMesh ) {
		rcFreePolyMesh( polyMesh );
	}
	if ( contourSet ) {
		rcFreeContourSet( contourSet );
	}
	if ( compactHeightfield ) {
		rcFreeCompactHeightfield( compactHeightfield );
	}
	if ( heightfield ) {
		rcFreeHeightField( heightfield );
	}

	return ok;
}

bool idRecastNavMeshLocal::BuildMapFile( const idStr &mapName, const idStr &aasType ) {
	common->Printf( "Recast: requested build map '%s' type '%s'\n", mapName.c_str(), aasType.c_str() );

	idStr normalizedMapName = mapName;
	normalizedMapName.BackSlashesToSlashes();
	if ( normalizedMapName.Icmpn( "maps/", 5 ) != 0 ) {
		normalizedMapName = "maps/" + normalizedMapName;
	}
	normalizedMapName.SetFileExtension( ".map" );

	common->Printf( "Recast: normalized map path %s\n", normalizedMapName.c_str() );
	common->Printf( "Recast: parsing map file\n" );

	idMapFile mapFile;
	if ( !mapFile.Parse( normalizedMapName ) ) {
		common->Warning( "Recast: could not parse %s", normalizedMapName.c_str() );
		return false;
	}

	common->Printf( "Recast: parsed %s with %d entities, geometry CRC %u\n",
		mapFile.GetName(), mapFile.GetNumEntities(), mapFile.GetGeometryCRC() );

	common->Printf( "Recast: loading AAS settings entityDef '%s'\n", aasType.c_str() );
	const idDeclEntityDef *settingsDecl = static_cast<const idDeclEntityDef *>( declManager->FindType( DECL_ENTITYDEF, aasType, false ) );
	const idDict *settingsDict = settingsDecl ? &settingsDecl->dict : NULL;
	if ( !settingsDict ) {
		common->Warning( "Recast: unknown AAS/nav type '%s'", aasType.c_str() );
		return false;
	}

	idAASSettings settings;
	settings.FromDict( aasType, settingsDict );
	common->Printf( "Recast: settings loaded: extension %s, %d bbox(es), usePatches %s\n",
		settings.fileExtension.c_str(), settings.numBoundingBoxes, settings.usePatches ? "true" : "false" );

	idStr output = mapFile.GetName();
	output.SetFileExtension( aasType );
	output = NavFileNameForAASName( output );
	common->Printf( "Recast: output navmesh path %s\n", output.c_str() );

	idRecastNavMeshLocal builder;
	return builder.BuildAndSave( &mapFile, output, mapFile.GetGeometryCRC(), settings );
}

void idRecastNavMeshLocal::ToDetour( const idVec3 &in, float out[3] ) {
	out[0] = in.x;
	out[1] = in.z;
	out[2] = in.y;
}

idVec3 idRecastNavMeshLocal::FromDetour( const float in[3] ) {
	return idVec3( in[0], in[2], in[1] );
}

bool idRecastNavMeshLocal::FindNearestPoly( const idVec3 &origin, const idBounds &searchBounds, dtPolyRef &ref, idVec3 *nearest ) const {
	if ( !IsLoaded() || PointInsideBlocker( origin ) ) {
		ref = 0;
		return false;
	}

	float center[3], extents[3], nearestPoint[3];
	ToDetour( origin, center );
	extents[0] = max( idMath::Fabs( searchBounds[0].x ), idMath::Fabs( searchBounds[1].x ) );
	extents[1] = max( idMath::Fabs( searchBounds[0].z ), idMath::Fabs( searchBounds[1].z ) );
	extents[2] = max( idMath::Fabs( searchBounds[0].y ), idMath::Fabs( searchBounds[1].y ) );
	if ( extents[0] <= 0.0f ) {
		extents[0] = 64.0f;
	}
	if ( extents[1] <= 0.0f ) {
		extents[1] = 96.0f;
	}
	if ( extents[2] <= 0.0f ) {
		extents[2] = 64.0f;
	}

	dtQueryFilter filter;
	filter.setIncludeFlags( RECAST_POLYFLAGS_WALK );
	filter.setExcludeFlags( 0 );

	if ( dtStatusFailed( navQuery->findNearestPoly( center, extents, &filter, &ref, nearestPoint ) ) || ref == 0 ) {
		return false;
	}

	if ( nearest ) {
		*nearest = FromDetour( nearestPoint );
	}
	return true;
}

int idRecastNavMeshLocal::AreaForRef( dtPolyRef ref ) const {
	if ( ref == 0 ) {
		return 0;
	}
	for ( int i = 0; i < polyRefs.Num(); i++ ) {
		if ( polyRefs[i] == ref ) {
			return i + 1;
		}
	}
	return polyRefs.Append( ref ) + 1;
}

dtPolyRef idRecastNavMeshLocal::RefForArea( int areaNum ) const {
	if ( areaNum <= 0 || areaNum > polyRefs.Num() ) {
		return 0;
	}
	return polyRefs[areaNum - 1];
}

int idRecastNavMeshLocal::PointAreaNum( const idVec3 &origin ) const {
	dtPolyRef ref;
	if ( !FindNearestPoly( origin, settings.boundingBoxes[0], ref, NULL ) ) {
		return 0;
	}
	return AreaForRef( ref );
}

int idRecastNavMeshLocal::PointReachableAreaNum( const idVec3 &origin, const idBounds &searchBounds, const int areaFlags ) const {
	dtPolyRef ref;
	if ( !FindNearestPoly( origin, searchBounds, ref, NULL ) ) {
		return 0;
	}
	return AreaForRef( ref );
}

int idRecastNavMeshLocal::BoundsReachableAreaNum( const idBounds &bounds, const int areaFlags ) const {
	const idVec3 center = bounds.GetCenter();
	idBounds searchBounds;
	searchBounds[0] = bounds[0] - center;
	searchBounds[1] = bounds[1] - center;
	return PointReachableAreaNum( center, searchBounds, areaFlags );
}

void idRecastNavMeshLocal::PushPointIntoAreaNum( int areaNum, idVec3 &origin ) const {
	const dtPolyRef ref = RefForArea( areaNum );
	if ( ref == 0 || !IsLoaded() ) {
		return;
	}
	float pos[3], nearestPoint[3];
	ToDetour( origin, pos );
	if ( dtStatusSucceed( navQuery->closestPointOnPoly( ref, pos, nearestPoint, NULL ) ) ) {
		origin = FromDetour( nearestPoint );
	}
}

idVec3 idRecastNavMeshLocal::AreaCenter( int areaNum ) const {
	const dtPolyRef ref = RefForArea( areaNum );
	if ( ref == 0 || !navMesh ) {
		return vec3_origin;
	}

	const dtMeshTile *tile = NULL;
	const dtPoly *poly = NULL;
	if ( dtStatusFailed( navMesh->getTileAndPolyByRef( ref, &tile, &poly ) ) || !tile || !poly ) {
		return vec3_origin;
	}

	float center[3] = { 0.0f, 0.0f, 0.0f };
	for ( int i = 0; i < poly->vertCount; i++ ) {
		const float *v = &tile->verts[poly->verts[i] * 3];
		center[0] += v[0];
		center[1] += v[1];
		center[2] += v[2];
	}
	const float inv = 1.0f / poly->vertCount;
	center[0] *= inv;
	center[1] *= inv;
	center[2] *= inv;
	return FromDetour( center );
}

int idRecastNavMeshLocal::AreaFlags( int areaNum ) const {
	return AREA_REACHABLE_WALK;
}

int idRecastNavMeshLocal::AreaTravelFlags( int areaNum ) const {
	return TFL_WALK;
}

bool idRecastNavMeshLocal::Trace( aasTrace_t &trace, const idVec3 &start, const idVec3 &end ) const {
	idVec3 endPos;
	int endAreaNum;
	const int startArea = PointAreaNum( start );
	const bool valid = PathValid( startArea, start, 0, end, TFL_WALK, endPos, endAreaNum );
	trace.fraction = valid ? 1.0f : 0.0f;
	trace.endpos = endPos;
	trace.lastAreaNum = endAreaNum;
	trace.numAreas = endAreaNum > 0 ? 1 : 0;
	if ( trace.numAreas > 0 && trace.areas && trace.points && trace.maxAreas > 0 ) {
		trace.areas[0] = endAreaNum;
		trace.points[0] = endPos;
	}
	return !valid;
}

bool idRecastNavMeshLocal::SetAreaState( const idBounds &bounds, const int areaContents, bool disabled ) {
	if ( disabled ) {
		for ( int i = 0; i < areaBlockers.Num(); i++ ) {
			if ( areaBlockers[i].active &&
				 ( areaBlockers[i].areaContents & areaContents ) != 0 &&
				 areaBlockers[i].bounds.Expand( RECAST_AREA_BLOCKER_MATCH_EXPAND ).IntersectsBounds( bounds ) ) {
				areaBlockers[i].bounds = bounds;
				areaBlockers[i].areaContents = areaContents;
				return true;
			}
		}

		recastBoundsBlocker_t blocker;
		blocker.bounds = bounds;
		blocker.areaContents = areaContents;
		blocker.active = true;
		for ( int i = 0; i < areaBlockers.Num(); i++ ) {
			if ( !areaBlockers[i].active ) {
				areaBlockers[i] = blocker;
				return true;
			}
		}
		areaBlockers.Append( blocker );
	} else {
		for ( int i = 0; i < areaBlockers.Num(); i++ ) {
			if ( areaBlockers[i].active &&
				 ( areaBlockers[i].areaContents & areaContents ) != 0 &&
				 areaBlockers[i].bounds.Expand( RECAST_AREA_BLOCKER_MATCH_EXPAND ).IntersectsBounds( bounds ) ) {
				areaBlockers[i].active = false;
			}
		}
	}
	return true;
}

recastObstacleHandle_t idRecastNavMeshLocal::AddObstacle( const idBounds &bounds ) {
	recastBoundsBlocker_t blocker;
	blocker.bounds = bounds;
	blocker.areaContents = AREACONTENTS_OBSTACLE;
	blocker.active = true;

	for ( int i = 0; i < obstacles.Num(); i++ ) {
		if ( !obstacles[i].active ) {
			obstacles[i] = blocker;
			return i;
		}
	}
	return obstacles.Append( blocker );
}

void idRecastNavMeshLocal::RemoveObstacle( const recastObstacleHandle_t handle ) {
	if ( handle >= 0 && handle < obstacles.Num() ) {
		obstacles[handle].active = false;
	}
}

void idRecastNavMeshLocal::RemoveAllObstacles( void ) {
	obstacles.Clear();
	areaBlockers.Clear();
}

bool idRecastNavMeshLocal::LineHitsBlocker( const idVec3 &start, const idVec3 &end ) const {
	for ( int i = 0; i < obstacles.Num(); i++ ) {
		if ( obstacles[i].active && obstacles[i].bounds.LineIntersection( start, end ) ) {
			return true;
		}
	}
	for ( int i = 0; i < areaBlockers.Num(); i++ ) {
		if ( areaBlockers[i].active && areaBlockers[i].bounds.LineIntersection( start, end ) ) {
			return true;
		}
	}
	return false;
}

bool idRecastNavMeshLocal::PointInsideBlocker( const idVec3 &origin ) const {
	for ( int i = 0; i < obstacles.Num(); i++ ) {
		if ( obstacles[i].active && obstacles[i].bounds.ContainsPoint( origin ) ) {
			return true;
		}
	}
	for ( int i = 0; i < areaBlockers.Num(); i++ ) {
		if ( areaBlockers[i].active && areaBlockers[i].bounds.ContainsPoint( origin ) ) {
			return true;
		}
	}
	return false;
}

bool idRecastNavMeshLocal::FindPathRefs( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, dtPolyRef *pathRefs, int &numPathRefs, const int maxPathRefs ) const {
	numPathRefs = 0;
	if ( !IsLoaded() || PointInsideBlocker( origin ) || PointInsideBlocker( goalOrigin ) ) {
		return false;
	}

	dtPolyRef startRef = RefForArea( areaNum );
	dtPolyRef endRef = RefForArea( goalAreaNum );
	idVec3 nearest;
	if ( startRef == 0 ) {
		FindNearestPoly( origin, settings.boundingBoxes[0], startRef, &nearest );
	}
	if ( endRef == 0 ) {
		FindNearestPoly( goalOrigin, settings.boundingBoxes[0], endRef, &nearest );
	}
	if ( startRef == 0 || endRef == 0 ) {
		return false;
	}

	float start[3], end[3];
	ToDetour( origin, start );
	ToDetour( goalOrigin, end );

	dtQueryFilter filter;
	filter.setIncludeFlags( RECAST_POLYFLAGS_WALK );
	filter.setExcludeFlags( 0 );
	return dtStatusSucceed( navQuery->findPath( startRef, endRef, start, end, &filter, pathRefs, &numPathRefs, maxPathRefs ) ) && numPathRefs > 0;
}

int idRecastNavMeshLocal::TravelTimeToGoalArea( int areaNum, const idVec3 &origin, int goalAreaNum, int travelFlags ) const {
	dtPolyRef pathRefs[MAX_RECAST_PATH_POLYS];
	int numPathRefs;
	const idVec3 goalOrigin = AreaCenter( goalAreaNum );
	if ( !FindPathRefs( areaNum, origin, goalAreaNum, goalOrigin, travelFlags, pathRefs, numPathRefs, MAX_RECAST_PATH_POLYS ) ) {
		return 0;
	}
	const float dist = ( goalOrigin - origin ).Length();
	return idMath::Ftoi( dist * 100.0f / 300.0f );
}

bool idRecastNavMeshLocal::RouteToGoalArea( int areaNum, const idVec3 origin, int goalAreaNum, int travelFlags, recastPath_t &route ) const {
	recastPath_t path;
	const idVec3 goalOrigin = AreaCenter( goalAreaNum );
	if ( !PathToGoal( path, areaNum, origin, goalAreaNum, goalOrigin, travelFlags ) ) {
		route.travelTime = 0;
		route.moveAreaNum = 0;
		route.moveGoal = origin;
		route.secondaryGoal = origin;
		return false;
	}
	route = path;
	route.travelTime = idMath::Ftoi( ( path.moveGoal - origin ).Length() * 100.0f / 300.0f );
	return true;
}

bool idRecastNavMeshLocal::PathToGoal( recastPath_t &path, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags ) const {
	path.moveGoal = origin;
	path.moveAreaNum = areaNum;
	path.secondaryGoal = origin;
	path.travelTime = 0;

	dtPolyRef pathRefs[MAX_RECAST_PATH_POLYS];
	int numPathRefs;
	if ( !FindPathRefs( areaNum, origin, goalAreaNum, goalOrigin, travelFlags, pathRefs, numPathRefs, MAX_RECAST_PATH_POLYS ) ) {
		return false;
	}

	float start[3], end[3], straightPath[MAX_RECAST_PATH_POLYS * 3];
	unsigned char straightFlags[MAX_RECAST_PATH_POLYS];
	dtPolyRef straightRefs[MAX_RECAST_PATH_POLYS];
	int numStraight = 0;
	ToDetour( origin, start );
	ToDetour( goalOrigin, end );

	dtQueryFilter filter;
	filter.setIncludeFlags( RECAST_POLYFLAGS_WALK );
	filter.setExcludeFlags( 0 );

	if ( dtStatusFailed( navQuery->findStraightPath( start, end, pathRefs, numPathRefs, straightPath, straightFlags, straightRefs, &numStraight, MAX_RECAST_PATH_POLYS ) ) || numStraight <= 0 ) {
		return false;
	}

	const int steerIndex = numStraight > 1 ? 1 : 0;
	path.moveGoal = FromDetour( &straightPath[steerIndex * 3] );
	path.moveAreaNum = AreaForRef( straightRefs[steerIndex] ? straightRefs[steerIndex] : pathRefs[numPathRefs - 1] );
	path.secondaryGoal = goalOrigin;
	path.travelTime = idMath::Ftoi( ( path.moveGoal - origin ).Length() * 100.0f / 300.0f );
	if ( LineHitsBlocker( origin, path.moveGoal ) ) {
		return false;
	}
	return true;
}

bool idRecastNavMeshLocal::PathValid( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, idVec3 &endPos, int &endAreaNum ) const {
	if ( LineHitsBlocker( origin, goalOrigin ) ) {
		endPos = origin;
		endAreaNum = areaNum;
		return false;
	}

	dtPolyRef startRef = RefForArea( areaNum );
	idVec3 nearest;
	if ( startRef == 0 && !FindNearestPoly( origin, settings.boundingBoxes[0], startRef, &nearest ) ) {
		endPos = origin;
		endAreaNum = 0;
		return false;
	}

	float start[3], end[3], hitNormal[3];
	float t = 0.0f;
	ToDetour( origin, start );
	ToDetour( goalOrigin, end );

	dtQueryFilter filter;
	filter.setIncludeFlags( RECAST_POLYFLAGS_WALK );
	filter.setExcludeFlags( 0 );

	dtPolyRef visited[MAX_RECAST_PATH_POLYS];
	int numVisited = 0;
	if ( dtStatusFailed( navQuery->raycast( startRef, start, end, &filter, &t, hitNormal, visited, &numVisited, MAX_RECAST_PATH_POLYS ) ) ) {
		endPos = origin;
		endAreaNum = areaNum;
		return false;
	}

	if ( t > 1.0f ) {
		t = 1.0f;
	}
	endPos = origin + ( goalOrigin - origin ) * t;
	endAreaNum = numVisited > 0 ? AreaForRef( visited[numVisited - 1] ) : areaNum;
	return t >= 1.0f;
}

bool idRecastNavMeshLocal::PathAreaList( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, int *areas, int &numAreas, int maxAreas ) const {
	numAreas = 0;
	dtPolyRef pathRefs[MAX_RECAST_PATH_POLYS];
	int numPathRefs;
	if ( maxAreas <= 0 || !areas || !FindPathRefs( areaNum, origin, goalAreaNum, goalOrigin, travelFlags, pathRefs, numPathRefs, MAX_RECAST_PATH_POLYS ) ) {
		return false;
	}

	for ( int i = 0; i < numPathRefs && numAreas < maxAreas; i++ ) {
		areas[numAreas++] = AreaForRef( pathRefs[i] );
	}
	return numAreas > 0;
}

void idRecastNavMeshLocal::Stats( void ) const {
	int activeObstacles = 0;
	int activeBlockers = 0;

	for ( int i = 0; i < obstacles.Num(); i++ ) {
		if ( obstacles[i].active ) {
			activeObstacles++;
		}
	}
	for ( int i = 0; i < areaBlockers.Num(); i++ ) {
		if ( areaBlockers[i].active ) {
			activeBlockers++;
		}
	}

	common->Printf( "[%s]\n", name.c_str() );
	common->Printf( "Recast/Detour navmesh loaded: %d cached poly refs, %d active obstacles, %d active blockers\n", polyRefs.Num(), activeObstacles, activeBlockers );
	common->Printf( "DetourCrowd avoidance: %s\n", crowd ? "initialized" : "not available" );
}

class idRecastNavigationManagerLocal : public idRecastNavigationManager {
public:
	virtual					~idRecastNavigationManagerLocal( void );

	virtual recastNavHandle_t Alloc( void );
	virtual void			Free( recastNavHandle_t handle );

	virtual bool			Load( recastNavHandle_t handle, const char *aasName, const char *fileName, unsigned int mapFileCRC );
	virtual bool			BuildMapFile( const char *mapName, const char *aasType );
	virtual void			Stats( recastNavHandle_t handle ) const;
	virtual void			DebugDraw( recastNavHandle_t handle, idRenderWorld *renderWorld, int drawMode, int lifetime ) const;

	virtual bool			IsLoaded( recastNavHandle_t handle ) const;
	virtual const char *	GetName( recastNavHandle_t handle ) const;
	virtual int				NumPolys( recastNavHandle_t handle ) const;
	virtual const idAASSettings *GetSettings( recastNavHandle_t handle ) const;

	virtual int				PointAreaNum( recastNavHandle_t handle, const idVec3 &origin ) const;
	virtual int				PointReachableAreaNum( recastNavHandle_t handle, const idVec3 &origin, const idBounds &searchBounds, const int areaFlags ) const;
	virtual int				BoundsReachableAreaNum( recastNavHandle_t handle, const idBounds &bounds, const int areaFlags ) const;
	virtual void			PushPointIntoAreaNum( recastNavHandle_t handle, int areaNum, idVec3 &origin ) const;
	virtual idVec3			AreaCenter( recastNavHandle_t handle, int areaNum ) const;
	virtual int				AreaFlags( recastNavHandle_t handle, int areaNum ) const;
	virtual int				AreaTravelFlags( recastNavHandle_t handle, int areaNum ) const;
	virtual bool			Trace( recastNavHandle_t handle, aasTrace_t &trace, const idVec3 &start, const idVec3 &end ) const;

	virtual bool			SetAreaState( recastNavHandle_t handle, const idBounds &bounds, const int areaContents, bool disabled );
	virtual recastObstacleHandle_t AddObstacle( recastNavHandle_t handle, const idBounds &bounds );
	virtual void			RemoveObstacle( recastNavHandle_t handle, const recastObstacleHandle_t obstacleHandle );
	virtual void			RemoveAllObstacles( recastNavHandle_t handle );

	virtual int				TravelTimeToGoalArea( recastNavHandle_t handle, int areaNum, const idVec3 &origin, int goalAreaNum, int travelFlags ) const;
	virtual bool			RouteToGoalArea( recastNavHandle_t handle, int areaNum, const idVec3 origin, int goalAreaNum, int travelFlags, recastPath_t &route ) const;
	virtual bool			PathToGoal( recastNavHandle_t handle, recastPath_t &path, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags ) const;
	virtual bool			PathValid( recastNavHandle_t handle, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, idVec3 &endPos, int &endAreaNum ) const;
	virtual bool			PathAreaList( recastNavHandle_t handle, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, int *areas, int &numAreas, int maxAreas ) const;

private:
	idRecastNavMeshLocal *	Nav( recastNavHandle_t handle ) const;

	idList<idRecastNavMeshLocal *> navMeshes;
};

idRecastNavigationManagerLocal RecastNavigationManagerLocal;
idRecastNavigationManager *RecastNavigationManager = &RecastNavigationManagerLocal;

idRecastNavigationManagerLocal::~idRecastNavigationManagerLocal( void ) {
	for ( int i = 0; i < navMeshes.Num(); i++ ) {
		delete navMeshes[i];
	}
	navMeshes.Clear();
}

idRecastNavMeshLocal *idRecastNavigationManagerLocal::Nav( recastNavHandle_t handle ) const {
	if ( handle < 0 || handle >= navMeshes.Num() ) {
		return NULL;
	}
	return navMeshes[handle];
}

recastNavHandle_t idRecastNavigationManagerLocal::Alloc( void ) {
	for ( int i = 0; i < navMeshes.Num(); i++ ) {
		if ( navMeshes[i] == NULL ) {
			navMeshes[i] = new idRecastNavMeshLocal;
			return i;
		}
	}
	return navMeshes.Append( new idRecastNavMeshLocal );
}

void idRecastNavigationManagerLocal::Free( recastNavHandle_t handle ) {
	idRecastNavMeshLocal *nav = Nav( handle );
	if ( !nav ) {
		return;
	}
	delete nav;
	navMeshes[handle] = NULL;
}

bool idRecastNavigationManagerLocal::Load( recastNavHandle_t handle, const char *aasName, const char *fileName, unsigned int mapFileCRC ) {
	idRecastNavMeshLocal *nav = Nav( handle );
	if ( !nav ) {
		return false;
	}

	idStr aasType;
	idStr aasNameStr = aasName;
	aasNameStr.ExtractFileExtension( aasType );
	if ( aasType.IsEmpty() ) {
		return false;
	}

	const idDeclEntityDef *settingsDecl = static_cast<const idDeclEntityDef *>( declManager->FindType( DECL_ENTITYDEF, aasType, false ) );
	const idDict *settingsDict = settingsDecl ? &settingsDecl->dict : NULL;
	if ( !settingsDict ) {
		common->Warning( "Recast: unknown AAS/nav type '%s'", aasType.c_str() );
		return false;
	}

	idAASSettings settings;
	settings.FromDict( aasType, settingsDict );
	nav->InitForAAS( aasNameStr, settings, mapFileCRC );
	if ( !nav->Load( fileName, mapFileCRC ) ) {
		nav->Shutdown();
		return false;
	}
	return true;
}

bool idRecastNavigationManagerLocal::BuildMapFile( const char *mapName, const char *aasType ) {
	return idRecastNavMeshLocal::BuildMapFile( mapName, aasType );
}

void idRecastNavigationManagerLocal::Stats( recastNavHandle_t handle ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	if ( nav ) {
		nav->Stats();
	}
}

void idRecastNavigationManagerLocal::DebugDraw( recastNavHandle_t handle, idRenderWorld *renderWorld, int drawMode, int lifetime ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	if ( nav ) {
		nav->DebugDraw( renderWorld, drawMode, lifetime );
	}
}

bool idRecastNavigationManagerLocal::IsLoaded( recastNavHandle_t handle ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav && nav->IsLoaded();
}

const char *idRecastNavigationManagerLocal::GetName( recastNavHandle_t handle ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->GetName().c_str() : "";
}

int idRecastNavigationManagerLocal::NumPolys( recastNavHandle_t handle ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->NumPolys() : 0;
}

const idAASSettings *idRecastNavigationManagerLocal::GetSettings( recastNavHandle_t handle ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->GetSettings() : NULL;
}

int idRecastNavigationManagerLocal::PointAreaNum( recastNavHandle_t handle, const idVec3 &origin ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->PointAreaNum( origin ) : 0;
}

int idRecastNavigationManagerLocal::PointReachableAreaNum( recastNavHandle_t handle, const idVec3 &origin, const idBounds &searchBounds, const int areaFlags ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->PointReachableAreaNum( origin, searchBounds, areaFlags ) : 0;
}

int idRecastNavigationManagerLocal::BoundsReachableAreaNum( recastNavHandle_t handle, const idBounds &bounds, const int areaFlags ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->BoundsReachableAreaNum( bounds, areaFlags ) : 0;
}

void idRecastNavigationManagerLocal::PushPointIntoAreaNum( recastNavHandle_t handle, int areaNum, idVec3 &origin ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	if ( nav ) {
		nav->PushPointIntoAreaNum( areaNum, origin );
	}
}

idVec3 idRecastNavigationManagerLocal::AreaCenter( recastNavHandle_t handle, int areaNum ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->AreaCenter( areaNum ) : vec3_origin;
}

int idRecastNavigationManagerLocal::AreaFlags( recastNavHandle_t handle, int areaNum ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->AreaFlags( areaNum ) : 0;
}

int idRecastNavigationManagerLocal::AreaTravelFlags( recastNavHandle_t handle, int areaNum ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->AreaTravelFlags( areaNum ) : TFL_INVALID;
}

bool idRecastNavigationManagerLocal::Trace( recastNavHandle_t handle, aasTrace_t &trace, const idVec3 &start, const idVec3 &end ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->Trace( trace, start, end ) : false;
}

bool idRecastNavigationManagerLocal::SetAreaState( recastNavHandle_t handle, const idBounds &bounds, const int areaContents, bool disabled ) {
	idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->SetAreaState( bounds, areaContents, disabled ) : false;
}

recastObstacleHandle_t idRecastNavigationManagerLocal::AddObstacle( recastNavHandle_t handle, const idBounds &bounds ) {
	idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->AddObstacle( bounds ) : -1;
}

void idRecastNavigationManagerLocal::RemoveObstacle( recastNavHandle_t handle, const recastObstacleHandle_t obstacleHandle ) {
	idRecastNavMeshLocal *nav = Nav( handle );
	if ( nav ) {
		nav->RemoveObstacle( obstacleHandle );
	}
}

void idRecastNavigationManagerLocal::RemoveAllObstacles( recastNavHandle_t handle ) {
	idRecastNavMeshLocal *nav = Nav( handle );
	if ( nav ) {
		nav->RemoveAllObstacles();
	}
}

int idRecastNavigationManagerLocal::TravelTimeToGoalArea( recastNavHandle_t handle, int areaNum, const idVec3 &origin, int goalAreaNum, int travelFlags ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->TravelTimeToGoalArea( areaNum, origin, goalAreaNum, travelFlags ) : 0;
}

bool idRecastNavigationManagerLocal::RouteToGoalArea( recastNavHandle_t handle, int areaNum, const idVec3 origin, int goalAreaNum, int travelFlags, recastPath_t &route ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->RouteToGoalArea( areaNum, origin, goalAreaNum, travelFlags, route ) : false;
}

bool idRecastNavigationManagerLocal::PathToGoal( recastNavHandle_t handle, recastPath_t &path, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->PathToGoal( path, areaNum, origin, goalAreaNum, goalOrigin, travelFlags ) : false;
}

bool idRecastNavigationManagerLocal::PathValid( recastNavHandle_t handle, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, idVec3 &endPos, int &endAreaNum ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->PathValid( areaNum, origin, goalAreaNum, goalOrigin, travelFlags, endPos, endAreaNum ) : false;
}

bool idRecastNavigationManagerLocal::PathAreaList( recastNavHandle_t handle, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, int *areas, int &numAreas, int maxAreas ) const {
	const idRecastNavMeshLocal *nav = Nav( handle );
	return nav ? nav->PathAreaList( areaNum, origin, goalAreaNum, goalOrigin, travelFlags, areas, numAreas, maxAreas ) : false;
}