aboutsummaryrefslogtreecommitdiff
path: root/mp/src/game/server/nav_mesh.h
diff options
context:
space:
mode:
Diffstat (limited to 'mp/src/game/server/nav_mesh.h')
-rw-r--r--mp/src/game/server/nav_mesh.h2692
1 files changed, 1346 insertions, 1346 deletions
diff --git a/mp/src/game/server/nav_mesh.h b/mp/src/game/server/nav_mesh.h
index 21dc200b..24faed41 100644
--- a/mp/src/game/server/nav_mesh.h
+++ b/mp/src/game/server/nav_mesh.h
@@ -1,1346 +1,1346 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//
-//
-// Purpose:
-//
-// $NoKeywords: $
-//
-//=============================================================================//
-// nav_mesh.h
-// The Navigation Mesh interface
-// Author: Michael S. Booth ([email protected]), January 2003
-
-//
-// Author: Michael S. Booth ([email protected]), 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 "utlbuffer.h"
-#include "filesystem.h"
-#include "GameEventListener.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< CNavArea * > 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< Place > *GetPlaces( void ) const
- {
- return &m_directory;
- }
-
- bool HasUnnamedPlaces( void ) const
- {
- return m_hasUnnamedAreas;
- }
-
-
-private:
- CUtlVector< Place > 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< Place > *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< INavAvoidanceObstacle * > &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 < typename Functor >
- 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 < typename Functor >
- 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 < typename Functor >
- 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 < typename Functor >
- 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< typename NavAreaType >
- void CollectAreasOverlappingExtent( const Extent &extent, CUtlVector< NavAreaType * > *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 < typename Functor >
- 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 < typename Functor >
- 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 < typename Functor >
- 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 < typename Functor >
- 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 < typename Functor > 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 < typename Functor >
- 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< CNavArea * >& 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<NavAreaVector> 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< CNavArea * > *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< WalkableSeedSpot > 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< CNavArea * > m_transientAreas;
-
- void UpdateAvoidanceObstacleAreas( void );
- CUtlVector< CNavArea * > m_avoidanceObstacleAreas;
- CUtlVector< INavAvoidanceObstacle * > m_avoidanceObstacles;
-
- void UpdateBlockedAreas( void );
- CUtlVector< CNavArea * > m_blockedAreas;
-
- CUtlVector< int > 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 );
-
-// for debugging the A* algorithm, if nonzero, show debug display and decrement for each pathfind
-extern int g_DebugPathfindCounter;
-
-
-//--------------------------------------------------------------------------------------------------------------
-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_
+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose:
+//
+// $NoKeywords: $
+//
+//=============================================================================//
+// nav_mesh.h
+// The Navigation Mesh interface
+// Author: Michael S. Booth ([email protected]), January 2003
+
+//
+// Author: Michael S. Booth ([email protected]), 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 "utlbuffer.h"
+#include "filesystem.h"
+#include "GameEventListener.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< CNavArea * > 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< Place > *GetPlaces( void ) const
+ {
+ return &m_directory;
+ }
+
+ bool HasUnnamedPlaces( void ) const
+ {
+ return m_hasUnnamedAreas;
+ }
+
+
+private:
+ CUtlVector< Place > 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< Place > *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< INavAvoidanceObstacle * > &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 < typename Functor >
+ 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 < typename Functor >
+ 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 < typename Functor >
+ 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 < typename Functor >
+ 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< typename NavAreaType >
+ void CollectAreasOverlappingExtent( const Extent &extent, CUtlVector< NavAreaType * > *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 < typename Functor >
+ 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 < typename Functor >
+ 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 < typename Functor >
+ 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 < typename Functor >
+ 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 < typename Functor > 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 < typename Functor >
+ 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< CNavArea * >& 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<NavAreaVector> 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< CNavArea * > *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< WalkableSeedSpot > 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< CNavArea * > m_transientAreas;
+
+ void UpdateAvoidanceObstacleAreas( void );
+ CUtlVector< CNavArea * > m_avoidanceObstacleAreas;
+ CUtlVector< INavAvoidanceObstacle * > m_avoidanceObstacles;
+
+ void UpdateBlockedAreas( void );
+ CUtlVector< CNavArea * > m_blockedAreas;
+
+ CUtlVector< int > 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 );
+
+// for debugging the A* algorithm, if nonzero, show debug display and decrement for each pathfind
+extern int g_DebugPathfindCounter;
+
+
+//--------------------------------------------------------------------------------------------------------------
+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_
generated by cgit v1.2.3 (git 2.25.1) at 2026-04-25 20:01:52 +0000