//========= Copyright Valve Corporation, All rights reserved. ============// // // Purpose: // // $NoKeywords: $ // //=============================================================================// // nav_mesh.h // The Navigation Mesh interface // Author: Michael S. Booth (mike@turtlerockstudios.com), January 2003 // // Author: Michael S. Booth (mike@turtlerockstudios.com), 2003 // // NOTE: The Navigation code uses Doxygen-style comments. If you run Doxygen // over this code, it will auto-generate documentation. Visit www.doxygen.org // to download the system for free. // #ifndef _NAV_MESH_H_ #define _NAV_MESH_H_ #include "GameEventListener.h" #include "filesystem.h" #include "utlbuffer.h" #include "nav.h" #include "nav_area.h" #include "nav_colors.h" class CNavArea; class CBaseEntity; class CBreakable; extern ConVar nav_edit; extern ConVar nav_quicksave; extern ConVar nav_show_approach_points; extern ConVar nav_show_danger; //-------------------------------------------------------------------------------------------------------- class NavAreaCollector { bool m_checkForDuplicates; public: NavAreaCollector(bool checkForDuplicates = false) { m_checkForDuplicates = checkForDuplicates; } bool operator()(CNavArea *area) { if (m_checkForDuplicates && m_area.HasElement(area)) return true; m_area.AddToTail(area); return true; } CUtlVector m_area; }; //-------------------------------------------------------------------------------------------------------- class EditDestroyNotification { CNavArea *m_deadArea; public: EditDestroyNotification(CNavArea *deadArea) { m_deadArea = deadArea; } bool operator()(CBaseCombatCharacter *actor) { actor->OnNavAreaRemoved(m_deadArea); return true; } }; //-------------------------------------------------------------------------------------------------------- class NavAttributeClearer { public: NavAttributeClearer(NavAttributeType attribute) { m_attribute = attribute; } bool operator()(CNavArea *area) { area->SetAttributes(area->GetAttributes() & (~m_attribute)); return true; } NavAttributeType m_attribute; }; //-------------------------------------------------------------------------------------------------------- class NavAttributeSetter { public: NavAttributeSetter(NavAttributeType attribute) { m_attribute = attribute; } bool operator()(CNavArea *area) { area->SetAttributes(area->GetAttributes() | m_attribute); return true; } NavAttributeType m_attribute; }; //-------------------------------------------------------------------------------------------------------- class NavAttributeToggler { public: NavAttributeToggler(NavAttributeType attribute) { m_attribute = attribute; } bool operator()(CNavArea *area); NavAttributeType m_attribute; }; //-------------------------------------------------------------------------------------------------------- struct NavAttributeLookup { const char *name; NavAttributeType attribute; }; extern NavAttributeLookup TheNavAttributeTable[]; //-------------------------------------------------------------------------------------------------------- class SelectOverlappingAreas { public: bool operator()(CNavArea *area); }; //-------------------------------------------------------------------------------------------------------- abstract_class INavAvoidanceObstacle { public: virtual bool IsPotentiallyAbleToObstructNavAreas(void) const = 0; // could we at some future time obstruct nav? virtual float GetNavObstructionHeight(void) const = 0; // height at which to obstruct nav areas virtual bool CanObstructNavAreas(void) const = 0; // can we obstruct nav right this instant? virtual CBaseEntity *GetObstructingEntity(void) = 0; virtual void OnNavMeshLoaded(void) = 0; }; //-------------------------------------------------------------------------------------------------------- enum GetNavAreaFlags_t { GETNAVAREA_CHECK_LOS = 0x1, GETNAVAREA_ALLOW_BLOCKED_AREAS = 0x2, GETNAVAREA_CHECK_GROUND = 0x4, }; //-------------------------------------------------------------------------------------------------------- // for nav mesh visibilty computation struct NavVisPair_t { void SetPair(CNavArea *pArea1, CNavArea *pArea2) { int iArea1 = (int)(pArea1 > pArea2); int iArea2 = (iArea1 + 1) % 2; pAreas[iArea1] = pArea1; pAreas[iArea2] = pArea2; } CNavArea *pAreas[2]; }; // for nav mesh visibilty computation class CVisPairHashFuncs { public: CVisPairHashFuncs(int) {} bool operator()(const NavVisPair_t &lhs, const NavVisPair_t &rhs) const { return (lhs.pAreas[0] == rhs.pAreas[0] && lhs.pAreas[1] == rhs.pAreas[1]); } unsigned int operator()(const NavVisPair_t &item) const { COMPILE_TIME_ASSERT(sizeof(CNavArea *) == 4); int key[2] = {(int)item.pAreas[0] + item.pAreas[1]->GetID(), (int)item.pAreas[1] + item.pAreas[0]->GetID()}; return Hash8(key); } }; //-------------------------------------------------------------------------------------------------------------- // // The 'place directory' is used to save and load places from // nav files in a size-efficient manner that also allows for the // order of the place ID's to change without invalidating the // nav files. // // The place directory is stored in the nav file as a list of // place name strings. Each nav area then contains an index // into that directory, or zero if no place has been assigned to // that area. // class PlaceDirectory { public: typedef unsigned short IndexType; // Loaded/Saved as UnsignedShort. Change // this and you'll have to version. PlaceDirectory(void); void Reset(void); bool IsKnown(Place place) const; /// return true if this place is already in the directory IndexType GetIndex( Place place) const; /// return the directory index corresponding to /// this Place (0 = no entry) void AddPlace( Place place); /// add the place to the directory if not already known Place IndexToPlace( IndexType entry) const; /// given an index, return the Place void Save(CUtlBuffer &fileBuffer); /// store the directory void Load(CUtlBuffer &fileBuffer, int version); /// load the directory const CUtlVector *GetPlaces(void) const { return &m_directory; } bool HasUnnamedPlaces(void) const { return m_hasUnnamedAreas; } private: CUtlVector m_directory; bool m_hasUnnamedAreas; }; extern PlaceDirectory placeDirectory; //-------------------------------------------------------------------------------------------------------- /** * The CNavMesh is the global interface to the Navigation Mesh. * @todo Make this an abstract base class interface, and derive mod-specific * implementations. */ class CNavMesh : public CGameEventListener { public: CNavMesh(void); virtual ~CNavMesh(); virtual void PreLoadAreas(int nAreas) {} virtual CNavArea *CreateArea(void) const; // CNavArea factory virtual void DestroyArea(CNavArea *) const; virtual HidingSpot *CreateHidingSpot(void) const; // Hiding Spot factory virtual void Reset( void); // destroy Navigation Mesh data and revert to initial state virtual void Update(void); // invoked on each game frame virtual void FireGameEvent(IGameEvent *event); // incoming event processing virtual NavErrorType Load(void); // load navigation data from a file virtual NavErrorType PostLoad( unsigned int version); // (EXTEND) invoked after all areas have been // loaded - for pointer binding, etc bool IsLoaded(void) const { return m_isLoaded; } // return true if a Navigation Mesh has been loaded bool IsAnalyzed(void) const { return m_isAnalyzed; } // return true if a Navigation Mesh has been analyzed /** * Return true if nav mesh can be trusted for all climbing/jumping decisions * because game environment is fairly simple. Authoritative meshes mean path * followers can skip CPU intensive realtime scanning of unpredictable * geometry. */ virtual bool IsAuthoritative(void) const { return false; } const CUtlVector *GetPlacesFromNavFile( bool *hasUnnamedPlaces); // Reads the used place names from the nav // file (can be used to selectively precache // before the nav is loaded) virtual bool Save(void) const; // store Navigation Mesh to a file bool IsOutOfDate(void) const { return m_isOutOfDate; } // return true if the Navigation Mesh is older than the current map // version virtual unsigned int GetSubVersionNumber( void) const; // returns sub-version number of data format used by // derived classes virtual void SaveCustomData(CUtlBuffer &fileBuffer) const { } // store custom mesh data for derived classes virtual void LoadCustomData(CUtlBuffer &fileBuffer, unsigned int subVersion) { } // load custom mesh data for derived classes virtual void SaveCustomDataPreArea(CUtlBuffer &fileBuffer) const { } // store custom mesh data for derived classes that needs to be loaded // before areas are read in virtual void LoadCustomDataPreArea(CUtlBuffer &fileBuffer, unsigned int subVersion) { } // load custom mesh data for derived classes that needs to be loaded // before areas are read in // events virtual void OnServerActivate( void); // (EXTEND) invoked when server loads a new map virtual void OnRoundRestart(void); // invoked when a game round restarts virtual void OnRoundRestartPreEntity( void); // invoked when a game round restarts, but before entities are // deleted and recreated virtual void OnBreakableCreated(CBaseEntity *breakable) { } // invoked when a breakable is created virtual void OnBreakableBroken(CBaseEntity *broken) { } // invoked when a breakable is broken virtual void OnAreaBlocked( CNavArea *area); // invoked when the area becomes blocked virtual void OnAreaUnblocked( CNavArea *area); // invoked when the area becomes un-blocked virtual void OnAvoidanceObstacleEnteredArea( CNavArea *area); // invoked when the area becomes obstructed virtual void OnAvoidanceObstacleLeftArea( CNavArea *area); // invoked when the area becomes un-obstructed virtual void OnEditCreateNotify( CNavArea *newArea); // invoked when given area has just been added to // the mesh in edit mode virtual void OnEditDestroyNotify( CNavArea *deadArea); // invoked when given area has just been deleted // from the mesh in edit mode virtual void OnEditDestroyNotify( CNavLadder *deadLadder); // invoked when given ladder has just been // deleted from the mesh in edit mode virtual void OnNodeAdded(CNavNode *node){}; // Obstructions void RegisterAvoidanceObstacle(INavAvoidanceObstacle *obstruction); void UnregisterAvoidanceObstacle(INavAvoidanceObstacle *obstruction); const CUtlVector &GetObstructions(void) const { return m_avoidanceObstacles; } unsigned int GetNavAreaCount(void) const { return m_areaCount; } // return total number of nav areas // See GetNavAreaFlags_t for flags CNavArea *GetNavArea(const Vector &pos, float beneathLimt = 120.0f) const; // given a position, return the nav area that IsOverlapping and // is *immediately* beneath it CNavArea *GetNavArea(CBaseEntity *pEntity, int nGetNavAreaFlags, float flBeneathLimit = 120.0f) const; CNavArea *GetNavAreaByID(unsigned int id) const; CNavArea *GetNearestNavArea(const Vector &pos, bool anyZ = false, float maxDist = 10000.0f, bool checkLOS = false, bool checkGround = true, int team = TEAM_ANY) const; CNavArea *GetNearestNavArea(CBaseEntity *pEntity, int nGetNavAreaFlags = GETNAVAREA_CHECK_GROUND, float maxDist = 10000.0f) const; Place GetPlace( const Vector &pos) const; // return Place at given coordinate const char *PlaceToName( Place place) const; // given a place, return its name Place NameToPlace( const char *name) const; // given a place name, return a place ID or // zero if no place is defined Place PartialNameToPlace( const char *name) const; // given the first part of a place name, // return a place ID or zero if no place is // defined, or the partial match is ambiguous void PrintAllPlaces(void) const; // output a list of names to the console int PlaceNameAutocomplete( char const *partial, char commands [COMMAND_COMPLETION_MAXITEMS] [COMMAND_COMPLETION_ITEM_LENGTH]); // Given a partial place name, // fill in possible place names // for ConCommand autocomplete bool GetGroundHeight( const Vector &pos, float *height, Vector *normal = NULL) const; // get the Z coordinate of the topmost // ground level below the given point bool GetSimpleGroundHeight( const Vector &pos, float *height, Vector *normal = NULL) const; // get the Z coordinate of the ground // level directly below the given point /// increase "danger" weights in the given nav area and nearby ones void IncreaseDangerNearby(int teamID, float amount, CNavArea *area, const Vector &pos, float maxRadius, float dangerLimit = -1.0f); void DrawDanger(void) const; // draw the current danger levels void DrawPlayerCounts( void) const; // draw the current player counts for each area void DrawFuncNavAvoid( void) const; // draw bot avoidance areas from func_nav_avoid entities void DrawFuncNavPrefer( void) const; // draw bot preference areas from func_nav_prefer entities #ifdef NEXT_BOT void DrawFuncNavPrerequisite( void) const; // draw bot prerequisite areas from func_nav_prerequisite // entities #endif //------------------------------------------------------------------------------------- // Auto-generation // #define INCREMENTAL_GENERATION true void BeginGeneration( bool incremental = false); // initiate the generation process void BeginAnalysis(bool quitWhenFinished = false); // re-analyze an existing Mesh. Determine // Hiding Spots, Encounter Spots, etc. bool IsGenerating(void) const { return m_generationMode != GENERATE_NONE; } // return true while a Navigation Mesh is being generated const char *GetPlayerSpawnName( void) const; // return name of player spawn entity void SetPlayerSpawnName( const char *name); // define the name of player spawn entities void AddWalkableSeed( const Vector &pos, const Vector &normal); // add given walkable position to list of seed // positions for map sampling virtual void AddWalkableSeeds( void); // adds walkable positions for any/all positions a mod specifies void ClearWalkableSeeds(void) { m_walkableSeeds.RemoveAll(); } // erase all walkable seed positions void MarkStairAreas(void); virtual unsigned int GetGenerationTraceMask( void) const; // return the mask used by traces when generating the mesh //------------------------------------------------------------------------------------- // Edit mode // unsigned int GetNavPlace(void) const { return m_navPlace; } void SetNavPlace(unsigned int place) { m_navPlace = place; } // Edit callbacks from ConCommands void CommandNavDelete(void); // delete current area void CommandNavDeleteMarked(void); // delete current marked area virtual void CommandNavFloodSelect( const CCommand &args); // select current area and all connected areas, recursively void CommandNavToggleSelectedSet( void); // toggles all areas into/out of the selected set void CommandNavStoreSelectedSet( void); // stores the current selected set for later void CommandNavRecallSelectedSet(void); // restores an older selected set void CommandNavAddToSelectedSet(void); // add current area to selected set void CommandNavAddToSelectedSetByID( const CCommand &args); // add specified area id to selected set void CommandNavRemoveFromSelectedSet( void); // remove current area from selected set void CommandNavToggleInSelectedSet( void); // add/remove current area from selected set void CommandNavClearSelectedSet(void); // clear the selected set to empty void CommandNavBeginSelecting( void); // start continuously selecting areas into the selected set void CommandNavEndSelecting( void); // stop continuously selecting areas into the selected set void CommandNavBeginDragSelecting(void); // start dragging a selection area void CommandNavEndDragSelecting(void); // stop dragging a selection area void CommandNavBeginDragDeselecting( void); // start dragging a deselection area void CommandNavEndDragDeselecting( void); // stop dragging a deselection area void CommandNavRaiseDragVolumeMax( void); // raise the top of the drag volume void CommandNavLowerDragVolumeMax( void); // lower the top of the drag volume void CommandNavRaiseDragVolumeMin( void); // raise the bottom of the drag volume void CommandNavLowerDragVolumeMin( void); // lower the bottom of the drag volume void CommandNavToggleSelecting( bool playSound = true); // start/stop continuously selecting areas into // the selected set void CommandNavBeginDeselecting( void); // start continuously de-selecting areas from the selected set void CommandNavEndDeselecting( void); // stop continuously de-selecting areas from the selected set void CommandNavToggleDeselecting( bool playSound = true); // start/stop continuously de-selecting areas // from the selected set void CommandNavSelectInvalidAreas( void); // adds invalid areas to the selected set void CommandNavSelectBlockedAreas( void); // adds blocked areas to the selected set void CommandNavSelectObstructedAreas( void); // adds obstructed areas to the selected set void CommandNavSelectDamagingAreas( void); // adds damaging areas to the selected set void CommandNavSelectHalfSpace( const CCommand &args); // selects all areas that intersect the half-space void CommandNavSelectStairs(void); // adds stairs areas to the selected set void CommandNavSelectOrphans( void); // adds areas not connected to mesh to the selected set void CommandNavSplit(void); // split current area void CommandNavMerge(void); // merge adjacent areas void CommandNavMark( const CCommand &args); // mark an area for further operations void CommandNavUnmark(void); // removes the mark void CommandNavBeginArea(void); // begin creating a new nav area void CommandNavEndArea(void); // end creation of the new nav area void CommandNavBeginShiftXY( void); // begin shifting selected set in the XY plane void CommandNavEndShiftXY( void); // end shifting selected set in the XY plane void CommandNavConnect(void); // connect marked area to selected area void CommandNavDisconnect( void); // disconnect marked area from selected area void CommandNavDisconnectOutgoingOneWays( void); // disconnect all outgoing one-way connects from each area in // the selected set void CommandNavSplice( void); // create new area in between marked and selected areas void CommandNavCrouch(void); // toggle crouch attribute on current area void CommandNavTogglePlaceMode( void); // switch between normal and place editing void CommandNavSetPlaceMode( void); // switch between normal and place editing void CommandNavPlaceFloodFill( void); // floodfill areas out from current area void CommandNavPlaceSet(void); // sets the Place for the selected set void CommandNavPlacePick(void); // "pick up" the place at the current area void CommandNavTogglePlacePainting( void); // switch between "painting" places onto areas void CommandNavMarkUnnamed( void); // mark an unnamed area for further operations void CommandNavCornerSelect(void); // select a corner on the current area void CommandNavCornerRaise( const CCommand &args); // raise a corner on the current area void CommandNavCornerLower( const CCommand &args); // lower a corner on the current area void CommandNavCornerPlaceOnGround( const CCommand &args); // position a corner on the current area at ground height void CommandNavWarpToMark( void); // warp a spectating local player to the selected mark void CommandNavLadderFlip(void); // Flips the direction a ladder faces void CommandNavToggleAttribute( NavAttributeType attribute); // toggle an attribute on current area void CommandNavMakeSniperSpots( void); // cuts up the marked area into individual areas suitable for // sniper spots void CommandNavBuildLadder( void); // builds a nav ladder on the climbable surface under the cursor void CommandNavRemoveJumpAreas( void); // removes jump areas, replacing them with connections void CommandNavSubdivide( const CCommand &args); // subdivide each nav area in X and Y to create // 4 new areas - limit min size void CommandNavSaveSelected( const CCommand &args); // Save selected set to disk void CommandNavMergeMesh( const CCommand &args); // Merge a saved selected set into the current mesh void CommandNavMarkWalkable(void); void AddToDragSelectionSet(CNavArea *pArea); void RemoveFromDragSelectionSet(CNavArea *pArea); void ClearDragSelectionSet(void); CNavArea *GetMarkedArea( void) const; // return area marked by user in edit mode CNavLadder *GetMarkedLadder(void) const { return m_markedLadder; } // return ladder marked by user in edit mode CNavArea *GetSelectedArea(void) const { return m_selectedArea; } // return area user is pointing at in edit mode CNavLadder *GetSelectedLadder(void) const { return m_selectedLadder; } // return ladder user is pointing at in edit mode void SetMarkedLadder( CNavLadder *ladder); // mark ladder for further edit operations void SetMarkedArea( CNavArea *area); // mark area for further edit operations bool IsContinuouslySelecting(void) const { return m_isContinuouslySelecting; } bool IsContinuouslyDeselecting(void) const { return m_isContinuouslyDeselecting; } void CreateLadder(const Vector &mins, const Vector &maxs, float maxHeightAboveTopArea); void CreateLadder(const Vector &top, const Vector &bottom, float width, const Vector2D &ladderDir, float maxHeightAboveTopArea); float SnapToGrid(float x, bool forceGrid = false) const; // snap given coordinate to generation grid boundary Vector SnapToGrid( const Vector &in, bool snapX = true, bool snapY = true, bool forceGrid = false) const; // snap given vector's X & Y coordinates // to generation grid boundary const Vector &GetEditCursorPosition(void) const { return m_editCursorPos; } // return position of edit cursor void StripNavigationAreas(void); const char *GetFilename( void) const; // return the filename for this map's "nav" file /// @todo Remove old select code and make all commands use this selected set void AddToSelectedSet( CNavArea *area); // add area to the currently selected set void RemoveFromSelectedSet( CNavArea *area); // remove area from the currently selected set void ClearSelectedSet(void); // clear the currently selected set to empty bool IsSelectedSetEmpty( void) const; // return true if the selected set is empty bool IsInSelectedSet(const CNavArea *area) const; // return true if the given area is in the selected set int GetSelecteSetSize(void) const; const NavAreaVector &GetSelectedSet(void) const; // return the selected set /** * Apply the functor to all navigation areas in the Selected Set, * or the current selected area. * If functor returns false, stop processing and return false. */ template bool ForAllSelectedAreas(Functor &func) { if (IsSelectedSetEmpty()) { CNavArea *area = GetSelectedArea(); if (area) { if (func(area) == false) return false; } } else { FOR_EACH_VEC(m_selectedSet, it) { CNavArea *area = m_selectedSet[it]; if (func(area) == false) return false; } } return true; } //------------------------------------------------------------------------------------- /** * Apply the functor to all navigation areas. * If functor returns false, stop processing and return false. */ template bool ForAllAreas(Functor &func) { FOR_EACH_VEC(TheNavAreas, it) { CNavArea *area = TheNavAreas[it]; if (func(area) == false) return false; } return true; } // const version of the above template bool ForAllAreas(Functor &func) const { FOR_EACH_VEC(TheNavAreas, it) { const CNavArea *area = TheNavAreas[it]; if (func(area) == false) return false; } return true; } //------------------------------------------------------------------------------------- /** * Apply the functor to all navigation areas that overlap the given extent. * If functor returns false, stop processing and return false. */ template bool ForAllAreasOverlappingExtent(Functor &func, const Extent &extent) { if (!m_grid.Count()) { #if _DEBUG Warning("Query before nav mesh is loaded! %d\n", TheNavAreas.Count()); #endif return true; } static unsigned int searchMarker = RandomInt(0, 1024 * 1024); if (++searchMarker == 0) { ++searchMarker; } Extent areaExtent; // get list in cell that contains position int startX = WorldToGridX(extent.lo.x); int endX = WorldToGridX(extent.hi.x); int startY = WorldToGridY(extent.lo.y); int endY = WorldToGridY(extent.hi.y); for (int x = startX; x <= endX; ++x) { for (int y = startY; y <= endY; ++y) { int iGrid = x + y * m_gridSizeX; if (iGrid >= m_grid.Count()) { ExecuteNTimes( 10, Warning("** Walked off of the CNavMesh::m_grid in " "ForAllAreasOverlappingExtent()\n")); return true; } NavAreaVector *areaVector = &m_grid[iGrid]; // find closest area in this cell FOR_EACH_VEC((*areaVector), it) { CNavArea *area = (*areaVector)[it]; // skip if we've already visited this area if (area->m_nearNavSearchMarker == searchMarker) continue; // mark as visited area->m_nearNavSearchMarker = searchMarker; area->GetExtent(&areaExtent); if (extent.IsOverlapping(areaExtent)) { if (func(area) == false) return false; } } } } return true; } //------------------------------------------------------------------------------------- /** * Populate the given vector with all navigation areas that overlap the * given extent. */ template void CollectAreasOverlappingExtent(const Extent &extent, CUtlVector *outVector) { if (!m_grid.Count()) { return; } static unsigned int searchMarker = RandomInt(0, 1024 * 1024); if (++searchMarker == 0) { ++searchMarker; } Extent areaExtent; // get list in cell that contains position int startX = WorldToGridX(extent.lo.x); int endX = WorldToGridX(extent.hi.x); int startY = WorldToGridY(extent.lo.y); int endY = WorldToGridY(extent.hi.y); for (int x = startX; x <= endX; ++x) { for (int y = startY; y <= endY; ++y) { int iGrid = x + y * m_gridSizeX; if (iGrid >= m_grid.Count()) { ExecuteNTimes( 10, Warning("** Walked off of the CNavMesh::m_grid in " "CollectAreasOverlappingExtent()\n")); return; } NavAreaVector *areaVector = &m_grid[iGrid]; // find closest area in this cell for (int v = 0; v < areaVector->Count(); ++v) { CNavArea *area = areaVector->Element(v); // skip if we've already visited this area if (area->m_nearNavSearchMarker == searchMarker) continue; // mark as visited area->m_nearNavSearchMarker = searchMarker; area->GetExtent(&areaExtent); if (extent.IsOverlapping(areaExtent)) { outVector->AddToTail((NavAreaType *)area); } } } } } template bool ForAllAreasInRadius(Functor &func, const Vector &pos, float radius) { // use a unique marker for this method, so it can be used within a // SearchSurroundingArea() call static unsigned int searchMarker = RandomInt(0, 1024 * 1024); ++searchMarker; if (searchMarker == 0) { ++searchMarker; } // get list in cell that contains position int originX = WorldToGridX(pos.x); int originY = WorldToGridY(pos.y); int shiftLimit = ceil(radius / m_gridCellSize); float radiusSq = radius * radius; if (radius == 0.0f) { shiftLimit = MAX(m_gridSizeX, m_gridSizeY); // range 0 means all areas } for (int x = originX - shiftLimit; x <= originX + shiftLimit; ++x) { if (x < 0 || x >= m_gridSizeX) continue; for (int y = originY - shiftLimit; y <= originY + shiftLimit; ++y) { if (y < 0 || y >= m_gridSizeY) continue; NavAreaVector *areaVector = &m_grid[x + y * m_gridSizeX]; // find closest area in this cell FOR_EACH_VEC((*areaVector), it) { CNavArea *area = (*areaVector)[it]; // skip if we've already visited this area if (area->m_nearNavSearchMarker == searchMarker) continue; // mark as visited area->m_nearNavSearchMarker = searchMarker; float distSq = (area->GetCenter() - pos).LengthSqr(); if ((distSq <= radiusSq) || (radiusSq == 0)) { if (func(area) == false) return false; } } } } return true; } //--------------------------------------------------------------------------------------------------------------- /* * Step through nav mesh along line between startArea and endArea. * Return true if enumeration reached endArea, false if doesn't reach it (no * mesh between, bad connection, etc) */ template bool ForAllAreasAlongLine(Functor &func, CNavArea *startArea, CNavArea *endArea) { if (!startArea || !endArea) return false; if (startArea == endArea) { func(startArea); return true; } Vector start = startArea->GetCenter(); Vector end = endArea->GetCenter(); Vector to = end - start; float range = to.NormalizeInPlace(); const float epsilon = 0.00001f; if (range < epsilon) { func(startArea); return true; } if (abs(to.x) < epsilon) { NavDirType dir = (to.y < 0.0f) ? NORTH : SOUTH; CNavArea *area = startArea; while (area) { func(area); if (area == endArea) return true; const NavConnectVector *adjVector = area->GetAdjacentAreas(dir); area = NULL; for (int i = 0; i < adjVector->Count(); ++i) { CNavArea *adjArea = adjVector->Element(i).area; const Vector &adjOrigin = adjArea->GetCorner(NORTH_WEST); if (adjOrigin.x <= start.x && adjOrigin.x + adjArea->GetSizeX() >= start.x) { area = adjArea; break; } } } return false; } else if (abs(to.y) < epsilon) { NavDirType dir = (to.x < 0.0f) ? WEST : EAST; CNavArea *area = startArea; while (area) { func(area); if (area == endArea) return true; const NavConnectVector *adjVector = area->GetAdjacentAreas(dir); area = NULL; for (int i = 0; i < adjVector->Count(); ++i) { CNavArea *adjArea = adjVector->Element(i).area; const Vector &adjOrigin = adjArea->GetCorner(NORTH_WEST); if (adjOrigin.y <= start.y && adjOrigin.y + adjArea->GetSizeY() >= start.y) { area = adjArea; break; } } } return false; } CNavArea *area = startArea; while (area) { func(area); if (area == endArea) return true; const Vector &origin = area->GetCorner(NORTH_WEST); float xMin = origin.x; float xMax = xMin + area->GetSizeX(); float yMin = origin.y; float yMax = yMin + area->GetSizeY(); // clip ray to area Vector exit; NavDirType edge = NUM_DIRECTIONS; if (to.x < 0.0f) { // find Y at west edge intersection float t = (xMin - start.x) / (end.x - start.x); if (t > 0.0f && t < 1.0f) { float y = start.y + t * (end.y - start.y); if (y >= yMin && y <= yMax) { // intersects this edge exit.x = xMin; exit.y = y; edge = WEST; } } } else { // find Y at east edge intersection float t = (xMax - start.x) / (end.x - start.x); if (t > 0.0f && t < 1.0f) { float y = start.y + t * (end.y - start.y); if (y >= yMin && y <= yMax) { // intersects this edge exit.x = xMax; exit.y = y; edge = EAST; } } } if (edge == NUM_DIRECTIONS) { if (to.y < 0.0f) { // find X at north edge intersection float t = (yMin - start.y) / (end.y - start.y); if (t > 0.0f && t < 1.0f) { float x = start.x + t * (end.x - start.x); if (x >= xMin && x <= xMax) { // intersects this edge exit.x = x; exit.y = yMin; edge = NORTH; } } } else { // find X at south edge intersection float t = (yMax - start.y) / (end.y - start.y); if (t > 0.0f && t < 1.0f) { float x = start.x + t * (end.x - start.x); if (x >= xMin && x <= xMax) { // intersects this edge exit.x = x; exit.y = yMax; edge = SOUTH; } } } } if (edge == NUM_DIRECTIONS) break; const NavConnectVector *adjVector = area->GetAdjacentAreas(edge); area = NULL; for (int i = 0; i < adjVector->Count(); ++i) { CNavArea *adjArea = adjVector->Element(i).area; const Vector &adjOrigin = adjArea->GetCorner(NORTH_WEST); if (edge == NORTH || edge == SOUTH) { if (adjOrigin.x <= exit.x && adjOrigin.x + adjArea->GetSizeX() >= exit.x) { area = adjArea; break; } } else { if (adjOrigin.y <= exit.y && adjOrigin.y + adjArea->GetSizeY() >= exit.y) { area = adjArea; break; } } } } return false; } //------------------------------------------------------------------------------------- /** * Apply the functor to all navigation ladders. * If functor returns false, stop processing and return false. */ template bool ForAllLadders(Functor &func) { for (int i = 0; i < m_ladders.Count(); ++i) { CNavLadder *ladder = m_ladders[i]; if (func(ladder) == false) return false; } return true; } //------------------------------------------------------------------------------------- /** * Apply the functor to all navigation ladders. * If functor returns false, stop processing and return false. */ template bool ForAllLadders(Functor &func) const { for (int i = 0; i < m_ladders.Count(); ++i) { const CNavLadder *ladder = m_ladders[i]; if (func(ladder) == false) return false; } return true; } //------------------------------------------------------------------------------------- /** * tests a new area for connections to adjacent pre-existing areas */ template void StitchAreaIntoMesh(CNavArea *area, NavDirType dir, Functor &func); //------------------------------------------------------------------------------------- /** * Use the functor to test if an area is needing stitching into the existing * nav mesh. The functor is different from how we normally use functors - it * does no processing, and it's return value is true if the area is in the * new set to be stiched, and false if it's a pre-existing area. */ template bool StitchMesh(Functor &func) { FOR_EACH_VEC(TheNavAreas, it) { CNavArea *area = TheNavAreas[it]; if (func(area)) { StitchAreaIntoMesh(area, NORTH, func); StitchAreaIntoMesh(area, SOUTH, func); StitchAreaIntoMesh(area, EAST, func); StitchAreaIntoMesh(area, WEST, func); } } return true; } NavLadderVector &GetLadders(void) { return m_ladders; } // Returns the list of ladders CNavLadder *GetLadderByID(unsigned int id) const; CUtlVector &GetTransientAreas(void) { return m_transientAreas; } enum EditModeType { NORMAL, // normal mesh editing PLACE_PAINTING, // in place painting mode CREATING_AREA, // creating a new nav area CREATING_LADDER, // creating a nav ladder DRAG_SELECTING, // drag selecting a set of areas SHIFTING_XY, // shifting selected set in XY plane SHIFTING_Z, // shifting selected set in Z plane }; EditModeType GetEditMode(void) const; // return the current edit mode void SetEditMode(EditModeType mode); // change the edit mode bool IsEditMode(EditModeType mode) const; // return true if current mode matches given mode bool FindNavAreaOrLadderAlongRay(const Vector &start, const Vector &end, CNavArea **area, CNavLadder **ladder, CNavArea *ignore = NULL); void PostProcessCliffAreas(); void SimplifySelectedAreas( void); // Simplifies the selected set by reducing to 1x1 areas and // re-merging them up with loosened tolerances protected: virtual void PostCustomAnalysis(void) { } // invoked when custom analysis step is complete bool FindActiveNavArea(void); // Finds the area or ladder the local player // is currently pointing at. Returns true if // a surface was hit by the traceline. virtual void RemoveNavArea(CNavArea *area); // remove an area from the grid bool FindGroundForNode(Vector *pos, Vector *normal); void GenerateNodes(const Extent &bounds); void RemoveNodes(void); private: friend class CNavArea; friend class CNavNode; friend class CNavUIBasePanel; mutable CUtlVector m_grid; float m_gridCellSize; // the width/height of a grid cell for spatially // partitioning nav areas for fast access int m_gridSizeX; int m_gridSizeY; float m_minX; float m_minY; unsigned int m_areaCount; // total number of nav areas bool m_isLoaded; // true if a Navigation Mesh has been loaded bool m_isOutOfDate; // true if the Navigation Mesh is older than the actual // BSP bool m_isAnalyzed; // true if the Navigation Mesh needs analysis enum { HASH_TABLE_SIZE = 256 }; CNavArea *m_hashTable[HASH_TABLE_SIZE]; // hash table to optimize lookup by ID int ComputeHashKey( unsigned int id) const; // returns a hash key for the given nav area ID int WorldToGridX(float wx) const; // given X component, return grid index int WorldToGridY(float wy) const; // given Y component, return grid index void AllocateGrid( float minX, float maxX, float minY, float maxY); // clear and reset the grid to the given extents void GridToWorld(int gridX, int gridY, Vector *pos) const; void AddNavArea(CNavArea *area); // add an area to the grid void DestroyNavigationMesh( bool incremental = false); // free all resources of the mesh and reset // it to empty state void DestroyHidingSpots(void); void ComputeBattlefrontAreas( void); // determine areas where rushing teams will first meet //---------------------------------------------------------------------------------- // Place directory // char **m_placeName; // master directory of place names (ie: "places") unsigned int m_placeCount; // number of "places" defined in placeName[] void LoadPlaceDatabase(void); // load the place names from a file //---------------------------------------------------------------------------------- // Edit mode // EditModeType m_editMode; // the current edit mode bool m_isEditing; // true if in edit mode unsigned int m_navPlace; // current navigation place for editing void OnEditModeStart(void); // called when edit mode has just been enabled void DrawEditMode(void); // draw navigation areas void OnEditModeEnd(void); // called when edit mode has just been disabled void UpdateDragSelectionSet( void); // update which areas are overlapping the drag selected bounds Vector m_editCursorPos; // current position of the cursor CNavArea *m_markedArea; // currently marked area for edit operations CNavArea *m_selectedArea; // area that is selected this frame CNavArea *m_lastSelectedArea; // area that was selected last frame NavCornerType m_markedCorner; // currently marked corner for edit operations Vector m_anchor; // first corner of an area being created bool m_isPlacePainting; // if true, we set an area's place by pointing at it bool m_splitAlongX; // direction the selected nav area would be split float m_splitEdge; // location of the possible split bool m_climbableSurface; // if true, the cursor is pointing at a climable // surface Vector m_surfaceNormal; // Normal of the surface the cursor is pointing at Vector m_ladderAnchor; // first corner of a ladder being created Vector m_ladderNormal; // Normal of the surface of the ladder being created CNavLadder *m_selectedLadder; // ladder that is selected this frame CNavLadder *m_lastSelectedLadder; // ladder that was selected last frame CNavLadder *m_markedLadder; // currently marked ladder for edit operations bool FindLadderCorners( Vector *c1, Vector *c2, Vector *c3); // computes the other corners of a ladder given // m_ladderAnchor, m_editCursorPos, and m_ladderNormal void GetEditVectors(Vector *pos, Vector *forward); // Gets the eye position and view // direction of the editing player CountdownTimer m_showAreaInfoTimer; // Timer that controls how long area // info is displayed NavAreaVector m_selectedSet; // all currently selected areas NavAreaVector m_dragSelectionSet; // all areas in the current drag selection bool m_isContinuouslySelecting; // if true, we are continuously adding to // the selected set bool m_isContinuouslyDeselecting; // if true, we are continuously removing // from the selected set bool m_bIsDragDeselecting; int m_nDragSelectionVolumeZMax; int m_nDragSelectionVolumeZMin; void DoToggleAttribute( CNavArea *area, NavAttributeType attribute); // toggle an attribute on given area //---------------------------------------------------------------------------------- // Auto-generation // bool UpdateGeneration( float maxTime = 0.25f); // process the auto-generation for 'maxTime' seconds. // return false if generation is complete. virtual void BeginCustomAnalysis(bool bIncremental) {} virtual void EndCustomAnalysis() {} CNavNode *m_currentNode; // the current node we are sampling from NavDirType m_generationDir; CNavNode *AddNode(const Vector &destPos, const Vector &destNormal, NavDirType dir, CNavNode *source, bool isOnDisplacement, float obstacleHeight, float flObstacleStartDist, float flObstacleEndDist); // add a nav node and connect // it, update current node NavLadderVector m_ladders; // list of ladder navigation representations void BuildLadders(void); void DestroyLadders(void); bool SampleStep(void); // sample the walkable areas of the map void CreateNavAreasFromNodes( void); // cover all of the sampled nodes with nav areas bool TestArea(CNavNode *node, int width, int height); // check if an area of size (width, height) can // fit, starting from node as upper left corner int BuildArea(CNavNode *node, int width, int height); // create a CNavArea of size (width, height) // starting fom node at upper left corner bool CheckObstacles(CNavNode *node, int width, int height, int x, int y); void MarkPlayerClipAreas(void); void MarkJumpAreas(void); void StichAndRemoveJumpAreas(void); void RemoveJumpAreas(void); void SquareUpAreas(void); void MergeGeneratedAreas(void); void ConnectGeneratedAreas(void); void FixUpGeneratedAreas(void); void FixCornerOnCornerAreas(void); void FixConnections(void); void SplitAreasUnderOverhangs(void); void ValidateNavAreaConnections(void); void StitchGeneratedAreas( void); // Stitches incrementally-generated areas into the existing mesh void StitchAreaSet( CUtlVector *areas); // Stitches an arbitrary set of areas // into the existing mesh void HandleObstacleTopAreas( void); // Handles fixing/generating areas on top of slim obstacles such // as fences and railings void RaiseAreasWithInternalObstacles(); void CreateObstacleTopAreas(); bool CreateObstacleTopAreaIfNecessary(CNavArea *area, CNavArea *areaOther, NavDirType dir, bool bMultiNode); void RemoveOverlappingObstacleTopAreas(); enum GenerationStateType { SAMPLE_WALKABLE_SPACE, CREATE_AREAS_FROM_SAMPLES, FIND_HIDING_SPOTS, FIND_ENCOUNTER_SPOTS, FIND_SNIPER_SPOTS, FIND_EARLIEST_OCCUPY_TIMES, FIND_LIGHT_INTENSITY, COMPUTE_MESH_VISIBILITY, CUSTOM, // mod-specific generation step SAVE_NAV_MESH, NUM_GENERATION_STATES } m_generationState; // the state of the generation process enum GenerationModeType { GENERATE_NONE, GENERATE_FULL, GENERATE_INCREMENTAL, GENERATE_SIMPLIFY, GENERATE_ANALYSIS_ONLY, } m_generationMode; // true while a Navigation Mesh is being generated int m_generationIndex; // used for iterating nav areas during generation // process int m_sampleTick; // counter for displaying pseudo-progress while sampling // walkable space bool m_bQuitWhenFinished; float m_generationStartTime; Extent m_simplifyGenerationExtent; char *m_spawnName; // name of player spawn entity, used to initiate sampling struct WalkableSeedSpot { Vector pos; Vector normal; }; CUtlVector m_walkableSeeds; // list of walkable seed spots for sampling CNavNode *GetNextWalkableSeedNode( void); // return the next walkable seed as a node int m_seedIdx; int m_hostThreadModeRestoreValue; // stores the value of host_threadmode // before we changed it void BuildTransientAreaList(void); CUtlVector m_transientAreas; void UpdateAvoidanceObstacleAreas(void); CUtlVector m_avoidanceObstacleAreas; CUtlVector m_avoidanceObstacles; void UpdateBlockedAreas(void); CUtlVector m_blockedAreas; CUtlVector m_storedSelectedSet; // "Stored" selected set, so we can do some // editing and then restore the old selected set. // Done by ID, so we don't have to worry about // split/delete/etc. void BeginVisibilityComputations(void); void EndVisibilityComputations(void); void TestAllAreasForBlockedStatus( void); // Used to update blocked areas after a round restart. Need to // delay so the map logic has all fired. CountdownTimer m_updateBlockedAreasTimer; }; // the global singleton interface extern CNavMesh *TheNavMesh; // factory for creating the Navigation Mesh extern CNavMesh *NavMeshFactory(void); #ifdef STAGING_ONLY // for debugging the A* algorithm, if nonzero, show debug display and decrement // for each pathfind extern int g_DebugPathfindCounter; #endif //-------------------------------------------------------------------------------------------------------------- inline bool CNavMesh::IsEditMode(EditModeType mode) const { return m_editMode == mode; } //-------------------------------------------------------------------------------------------------------------- inline CNavMesh::EditModeType CNavMesh::GetEditMode(void) const { return m_editMode; } //-------------------------------------------------------------------------------------------------------------- inline unsigned int CNavMesh::GetSubVersionNumber(void) const { return 0; } //-------------------------------------------------------------------------------------------------------------- inline CNavArea *CNavMesh::CreateArea(void) const { return new CNavArea; } //-------------------------------------------------------------------------------------------------------------- inline void CNavMesh::DestroyArea(CNavArea *pArea) const { delete pArea; } //-------------------------------------------------------------------------------------------------------------- inline int CNavMesh::ComputeHashKey(unsigned int id) const { return id & 0xFF; } //-------------------------------------------------------------------------------------------------------------- inline int CNavMesh::WorldToGridX(float wx) const { int x = (int)((wx - m_minX) / m_gridCellSize); if (x < 0) x = 0; else if (x >= m_gridSizeX) x = m_gridSizeX - 1; return x; } //-------------------------------------------------------------------------------------------------------------- inline int CNavMesh::WorldToGridY(float wy) const { int y = (int)((wy - m_minY) / m_gridCellSize); if (y < 0) y = 0; else if (y >= m_gridSizeY) y = m_gridSizeY - 1; return y; } //-------------------------------------------------------------------------------------------------------------- inline unsigned int CNavMesh::GetGenerationTraceMask(void) const { return MASK_NPCSOLID_BRUSHONLY; } //-------------------------------------------------------------------------------------------------------------- // // Function prototypes // extern void ApproachAreaAnalysisPrep(void); extern void CleanupApproachAreaAnalysisPrep(void); extern bool IsHeightDifferenceValid(float test, float other1, float other2, float other3); #endif // _NAV_MESH_H_