diff options
Diffstat (limited to 'mp/src/game/server/nav_area.h')
| -rw-r--r-- | mp/src/game/server/nav_area.h | 2130 |
1 files changed, 1065 insertions, 1065 deletions
diff --git a/mp/src/game/server/nav_area.h b/mp/src/game/server/nav_area.h index 6eba5966..7c18a5e0 100644 --- a/mp/src/game/server/nav_area.h +++ b/mp/src/game/server/nav_area.h @@ -1,1065 +1,1065 @@ -//========= Copyright Valve Corporation, All rights reserved. ============//
-//
-// Purpose:
-//
-// $NoKeywords: $
-//
-//=============================================================================//
-// nav_area.h
-// Navigation areas
-// Author: Michael S. Booth ([email protected]), January 2003
-
-#ifndef _NAV_AREA_H_
-#define _NAV_AREA_H_
-
-#include "nav_ladder.h"
-#include "tier1/memstack.h"
-
-// BOTPORT: Clean up relationship between team index and danger storage in nav areas
-enum { MAX_NAV_TEAMS = 2 };
-
-
-class CFuncElevator;
-class CFuncNavPrerequisite;
-class CFuncNavCost;
-
-class CNavVectorNoEditAllocator
-{
-public:
- CNavVectorNoEditAllocator();
-
- static void Reset();
- static void *Alloc( size_t nSize );
- static void *Realloc( void *pMem, size_t nSize );
- static void Free( void *pMem );
- static size_t GetSize( void *pMem );
-
-private:
- static CMemoryStack m_memory;
- static void *m_pCurrent;
- static int m_nBytesCurrent;
-};
-
-#if !defined(_X360)
-typedef CUtlVectorUltraConservativeAllocator CNavVectorAllocator;
-#else
-typedef CNavVectorNoEditAllocator CNavVectorAllocator;
-#endif
-
-
-//-------------------------------------------------------------------------------------------------------------------
-/**
- * Functor interface for iteration
- */
-class IForEachNavArea
-{
-public:
- virtual bool Inspect( const CNavArea *area ) = 0; // Invoked once on each area of the iterated set. Return false to stop iterating.
- virtual void PostIteration( bool wasCompleteIteration ) { } // Invoked after the iteration has ended. 'wasCompleteIteration' will be true if the entire set was iterated (ie: Inspect() never returned false)
-};
-
-
-//-------------------------------------------------------------------------------------------------------------------
-/**
- * The NavConnect union is used to refer to connections to areas
- */
-struct NavConnect
-{
- NavConnect()
- {
- id = 0;
- length = -1;
- }
-
- union
- {
- unsigned int id;
- CNavArea *area;
- };
-
- mutable float length;
-
- bool operator==( const NavConnect &other ) const
- {
- return (area == other.area) ? true : false;
- }
-};
-
-typedef CUtlVectorUltraConservative<NavConnect, CNavVectorAllocator> NavConnectVector;
-
-
-//-------------------------------------------------------------------------------------------------------------------
-/**
- * The NavLadderConnect union is used to refer to connections to ladders
- */
-union NavLadderConnect
-{
- unsigned int id;
- CNavLadder *ladder;
-
- bool operator==( const NavLadderConnect &other ) const
- {
- return (ladder == other.ladder) ? true : false;
- }
-};
-typedef CUtlVectorUltraConservative<NavLadderConnect, CNavVectorAllocator> NavLadderConnectVector;
-
-
-//--------------------------------------------------------------------------------------------------------------
-/**
- * A HidingSpot is a good place for a bot to crouch and wait for enemies
- */
-class HidingSpot
-{
-public:
- virtual ~HidingSpot() { }
-
- enum
- {
- IN_COVER = 0x01, // in a corner with good hard cover nearby
- GOOD_SNIPER_SPOT = 0x02, // had at least one decent sniping corridor
- IDEAL_SNIPER_SPOT = 0x04, // can see either very far, or a large area, or both
- EXPOSED = 0x08 // spot in the open, usually on a ledge or cliff
- };
-
- bool HasGoodCover( void ) const { return (m_flags & IN_COVER) ? true : false; } // return true if hiding spot in in cover
- bool IsGoodSniperSpot( void ) const { return (m_flags & GOOD_SNIPER_SPOT) ? true : false; }
- bool IsIdealSniperSpot( void ) const { return (m_flags & IDEAL_SNIPER_SPOT) ? true : false; }
- bool IsExposed( void ) const { return (m_flags & EXPOSED) ? true : false; }
-
- int GetFlags( void ) const { return m_flags; }
-
- void Save( CUtlBuffer &fileBuffer, unsigned int version ) const;
- void Load( CUtlBuffer &fileBuffer, unsigned int version );
- NavErrorType PostLoad( void );
-
- const Vector &GetPosition( void ) const { return m_pos; } // get the position of the hiding spot
- unsigned int GetID( void ) const { return m_id; }
- const CNavArea *GetArea( void ) const { return m_area; } // return nav area this hiding spot is within
-
- void Mark( void ) { m_marker = m_masterMarker; }
- bool IsMarked( void ) const { return (m_marker == m_masterMarker) ? true : false; }
- static void ChangeMasterMarker( void ) { ++m_masterMarker; }
-
-
-public:
- void SetFlags( int flags ) { m_flags |= flags; } // FOR INTERNAL USE ONLY
- void SetPosition( const Vector &pos ) { m_pos = pos; } // FOR INTERNAL USE ONLY
-
-private:
- friend class CNavMesh;
- friend void ClassifySniperSpot( HidingSpot *spot );
-
- HidingSpot( void ); // must use factory to create
-
- Vector m_pos; // world coordinates of the spot
- unsigned int m_id; // this spot's unique ID
- unsigned int m_marker; // this spot's unique marker
- CNavArea *m_area; // the nav area containing this hiding spot
-
- unsigned char m_flags; // bit flags
-
- static unsigned int m_nextID; // used when allocating spot ID's
- static unsigned int m_masterMarker; // used to mark spots
-};
-typedef CUtlVectorUltraConservative< HidingSpot * > HidingSpotVector;
-extern HidingSpotVector TheHidingSpots;
-
-extern HidingSpot *GetHidingSpotByID( unsigned int id );
-
-
-//--------------------------------------------------------------------------------------------------------------
-/**
- * Stores a pointer to an interesting "spot", and a parametric distance along a path
- */
-struct SpotOrder
-{
- float t; // parametric distance along ray where this spot first has LOS to our path
- union
- {
- HidingSpot *spot; // the spot to look at
- unsigned int id; // spot ID for save/load
- };
-};
-typedef CUtlVector< SpotOrder > SpotOrderVector;
-
-/**
- * This struct stores possible path segments thru a CNavArea, and the dangerous spots
- * to look at as we traverse that path segment.
- */
-struct SpotEncounter
-{
- NavConnect from;
- NavDirType fromDir;
- NavConnect to;
- NavDirType toDir;
- Ray path; // the path segment
- SpotOrderVector spots; // list of spots to look at, in order of occurrence
-};
-typedef CUtlVectorUltraConservative< SpotEncounter * > SpotEncounterVector;
-
-
-//-------------------------------------------------------------------------------------------------------------------
-/**
- * A CNavArea is a rectangular region defining a walkable area in the environment
- */
-
-class CNavAreaCriticalData
-{
-protected:
- // --- Begin critical data, which is heavily hit during pathing operations and carefully arranged for cache performance [7/24/2008 tom] ---
-
- /* 0 */ Vector m_nwCorner; // north-west corner position (2D mins)
- /* 12 */ Vector m_seCorner; // south-east corner position (2D maxs)
- /* 24 */ float m_invDxCorners;
- /* 28 */ float m_invDyCorners;
- /* 32 */ float m_neZ; // height of the implicit corner defined by (m_seCorner.x, m_nwCorner.y, m_neZ)
- /* 36 */ float m_swZ; // height of the implicit corner defined by (m_nwCorner.x, m_seCorner.y, m_neZ)
- /* 40 */ Vector m_center; // centroid of area
-
- /* 52 */ unsigned char m_playerCount[ MAX_NAV_TEAMS ]; // the number of players currently in this area
-
- /* 54 */ bool m_isBlocked[ MAX_NAV_TEAMS ]; // if true, some part of the world is preventing movement through this nav area
-
- /* 56 */ unsigned int m_marker; // used to flag the area as visited
- /* 60 */ float m_totalCost; // the distance so far plus an estimate of the distance left
- /* 64 */ float m_costSoFar; // distance travelled so far
-
- /* 68 */ CNavArea *m_nextOpen, *m_prevOpen; // only valid if m_openMarker == m_masterMarker
- /* 76 */ unsigned int m_openMarker; // if this equals the current marker value, we are on the open list
-
- /* 80 */ int m_attributeFlags; // set of attribute bit flags (see NavAttributeType)
-
- //- connections to adjacent areas -------------------------------------------------------------------
- /* 84 */ NavConnectVector m_connect[ NUM_DIRECTIONS ]; // a list of adjacent areas for each direction
- /* 100*/ NavLadderConnectVector m_ladder[ CNavLadder::NUM_LADDER_DIRECTIONS ]; // list of ladders leading up and down from this area
- /* 108*/ NavConnectVector m_elevatorAreas; // a list of areas reachable via elevator from this area
-
- /* 112*/ unsigned int m_nearNavSearchMarker; // used in GetNearestNavArea()
-
- /* 116*/ CNavArea *m_parent; // the area just prior to this on in the search path
- /* 120*/ NavTraverseType m_parentHow; // how we get from parent to us
-
- /* 124*/ float m_pathLengthSoFar; // length of path so far, needed for limiting pathfind max path length
-
- /* *************** 360 cache line *************** */
-
- /* 128*/ CFuncElevator *m_elevator; // if non-NULL, this area is in an elevator's path. The elevator can transport us vertically to another area.
-
- // --- End critical data ---
-};
-
-
-class CNavArea : protected CNavAreaCriticalData
-{
-public:
- DECLARE_CLASS_NOBASE( CNavArea )
-
- CNavArea( void );
- virtual ~CNavArea();
-
- virtual void OnServerActivate( void ); // (EXTEND) invoked when map is initially loaded
- virtual void OnRoundRestart( void ); // (EXTEND) invoked for each area when the round restarts
- virtual void OnRoundRestartPreEntity( void ) { } // invoked for each area when the round restarts, but before entities are deleted and recreated
- virtual void OnEnter( CBaseCombatCharacter *who, CNavArea *areaJustLeft ) { } // invoked when player enters this area
- virtual void OnExit( CBaseCombatCharacter *who, CNavArea *areaJustEntered ) { } // invoked when player exits this area
-
- virtual void OnDestroyNotify( CNavArea *dead ); // invoked when given area is going away
- virtual void OnDestroyNotify( CNavLadder *dead ); // invoked when given ladder is going away
-
- 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 Save( CUtlBuffer &fileBuffer, unsigned int version ) const; // (EXTEND)
- virtual NavErrorType Load( CUtlBuffer &fileBuffer, unsigned int version, unsigned int subVersion ); // (EXTEND)
- virtual NavErrorType PostLoad( void ); // (EXTEND) invoked after all areas have been loaded - for pointer binding, etc
-
- virtual void SaveToSelectedSet( KeyValues *areaKey ) const; // (EXTEND) saves attributes for the area to a KeyValues
- virtual void RestoreFromSelectedSet( KeyValues *areaKey ); // (EXTEND) restores attributes from a KeyValues
-
- // for interactively building or generating nav areas
- void Build( CNavNode *nwNode, CNavNode *neNode, CNavNode *seNode, CNavNode *swNode );
- void Build( const Vector &corner, const Vector &otherCorner );
- void Build( const Vector &nwCorner, const Vector &neCorner, const Vector &seCorner, const Vector &swCorner );
-
- void ConnectTo( CNavArea *area, NavDirType dir ); // connect this area to given area in given direction
- void Disconnect( CNavArea *area ); // disconnect this area from given area
-
- void ConnectTo( CNavLadder *ladder ); // connect this area to given ladder
- void Disconnect( CNavLadder *ladder ); // disconnect this area from given ladder
-
- unsigned int GetID( void ) const { return m_id; } // return this area's unique ID
- static void CompressIDs( void ); // re-orders area ID's so they are continuous
- unsigned int GetDebugID( void ) const { return m_debugid; }
-
- void SetAttributes( int bits ) { m_attributeFlags = bits; }
- int GetAttributes( void ) const { return m_attributeFlags; }
- bool HasAttributes( int bits ) const { return ( m_attributeFlags & bits ) ? true : false; }
- void RemoveAttributes( int bits ) { m_attributeFlags &= ( ~bits ); }
-
- void SetPlace( Place place ) { m_place = place; } // set place descriptor
- Place GetPlace( void ) const { return m_place; } // get place descriptor
-
- void MarkAsBlocked( int teamID, CBaseEntity *blocker, bool bGenerateEvent = true ); // An entity can force a nav area to be blocked
- virtual void UpdateBlocked( bool force = false, int teamID = TEAM_ANY ); // Updates the (un)blocked status of the nav area (throttled)
- virtual bool IsBlocked( int teamID, bool ignoreNavBlockers = false ) const;
- void UnblockArea( int teamID = TEAM_ANY ); // clear blocked status for the given team(s)
-
- void CheckFloor( CBaseEntity *ignore ); // Checks if there is a floor under the nav area, in case a breakable floor is gone
-
- void MarkObstacleToAvoid( float obstructionHeight );
- void UpdateAvoidanceObstacles( void );
- bool HasAvoidanceObstacle( float maxObstructionHeight = StepHeight ) const; // is there a large, immobile object obstructing this area
- float GetAvoidanceObstacleHeight( void ) const; // returns the maximum height of the obstruction above the ground
-
-#ifdef NEXT_BOT
- bool HasPrerequisite( CBaseCombatCharacter *actor = NULL ) const; // return true if this area has a prerequisite that applies to the given actor
- const CUtlVector< CHandle< CFuncNavPrerequisite > > &GetPrerequisiteVector( void ) const; // return vector of prerequisites that must be met before this area can be traversed
- void RemoveAllPrerequisites( void );
- void AddPrerequisite( CFuncNavPrerequisite *prereq );
-#endif
-
- void ClearAllNavCostEntities( void ); // clear set of func_nav_cost entities that affect this area
- void AddFuncNavCostEntity( CFuncNavCost *cost ); // add the given func_nav_cost entity to the cost of this area
- float ComputeFuncNavCost( CBaseCombatCharacter *who ) const; // return the cost multiplier of this area's func_nav_cost entities for the given actor
- bool HasFuncNavAvoid( void ) const;
- bool HasFuncNavPrefer( void ) const;
-
- void CheckWaterLevel( void );
- bool IsUnderwater( void ) const { return m_isUnderwater; }
-
- bool IsOverlapping( const Vector &pos, float tolerance = 0.0f ) const; // return true if 'pos' is within 2D extents of area.
- bool IsOverlapping( const CNavArea *area ) const; // return true if 'area' overlaps our 2D extents
- bool IsOverlapping( const Extent &extent ) const; // return true if 'extent' overlaps our 2D extents
- bool IsOverlappingX( const CNavArea *area ) const; // return true if 'area' overlaps our X extent
- bool IsOverlappingY( const CNavArea *area ) const; // return true if 'area' overlaps our Y extent
- inline float GetZ( const Vector * RESTRICT pPos ) const ; // return Z of area at (x,y) of 'pos'
- inline float GetZ( const Vector &pos ) const; // return Z of area at (x,y) of 'pos'
- float GetZ( float x, float y ) const RESTRICT; // return Z of area at (x,y) of 'pos'
- bool Contains( const Vector &pos ) const; // return true if given point is on or above this area, but no others
- bool Contains( const CNavArea *area ) const;
- bool IsCoplanar( const CNavArea *area ) const; // return true if this area and given area are approximately co-planar
- void GetClosestPointOnArea( const Vector * RESTRICT pPos, Vector *close ) const RESTRICT; // return closest point to 'pos' on this area - returned point in 'close'
- void GetClosestPointOnArea( const Vector &pos, Vector *close ) const { return GetClosestPointOnArea( &pos, close ); }
- float GetDistanceSquaredToPoint( const Vector &pos ) const; // return shortest distance between point and this area
- bool IsDegenerate( void ) const; // return true if this area is badly formed
- bool IsRoughlySquare( void ) const; // return true if this area is approximately square
- bool IsFlat( void ) const; // return true if this area is approximately flat
- bool HasNodes( void ) const;
- void GetNodes( NavDirType dir, CUtlVector< CNavNode * > *nodes ) const; // build a vector of nodes along the given direction
- CNavNode *FindClosestNode( const Vector &pos, NavDirType dir ) const; // returns the closest node along the given edge to the given point
-
- bool IsContiguous( const CNavArea *other ) const; // return true if the given area and 'other' share a colinear edge (ie: no drop-down or step/jump/climb)
- float ComputeAdjacentConnectionHeightChange( const CNavArea *destinationArea ) const; // return height change between edges of adjacent nav areas (not actual underlying ground)
-
- bool IsEdge( NavDirType dir ) const; // return true if there are no bi-directional links on the given side
-
- bool IsDamaging( void ) const; // Return true if continuous damage (ie: fire) is in this area
- void MarkAsDamaging( float duration ); // Mark this area is damaging for the next 'duration' seconds
-
- bool IsVisible( const Vector &eye, Vector *visSpot = NULL ) const; // return true if area is visible from the given eyepoint, return visible spot
-
- int GetAdjacentCount( NavDirType dir ) const { return m_connect[ dir ].Count(); } // return number of connected areas in given direction
- CNavArea *GetAdjacentArea( NavDirType dir, int i ) const; // return the i'th adjacent area in the given direction
- CNavArea *GetRandomAdjacentArea( NavDirType dir ) const;
- void CollectAdjacentAreas( CUtlVector< CNavArea * > *adjVector ) const; // build a vector of all adjacent areas
-
- const NavConnectVector *GetAdjacentAreas( NavDirType dir ) const { return &m_connect[dir]; }
- bool IsConnected( const CNavArea *area, NavDirType dir ) const; // return true if given area is connected in given direction
- bool IsConnected( const CNavLadder *ladder, CNavLadder::LadderDirectionType dir ) const; // return true if given ladder is connected in given direction
- float ComputeGroundHeightChange( const CNavArea *area ); // compute change in actual ground height from this area to given area
-
- const NavConnectVector *GetIncomingConnections( NavDirType dir ) const { return &m_incomingConnect[dir]; } // get areas connected TO this area by a ONE-WAY link (ie: we have no connection back to them)
- void AddIncomingConnection( CNavArea *source, NavDirType incomingEdgeDir );
-
- const NavLadderConnectVector *GetLadders( CNavLadder::LadderDirectionType dir ) const { return &m_ladder[dir]; }
- CFuncElevator *GetElevator( void ) const { Assert( !( m_attributeFlags & NAV_MESH_HAS_ELEVATOR ) == (m_elevator == NULL) ); return ( m_attributeFlags & NAV_MESH_HAS_ELEVATOR ) ? m_elevator : NULL; }
- const NavConnectVector &GetElevatorAreas( void ) const { return m_elevatorAreas; } // return collection of areas reachable via elevator from this area
-
- void ComputePortal( const CNavArea *to, NavDirType dir, Vector *center, float *halfWidth ) const; // compute portal to adjacent area
- NavDirType ComputeLargestPortal( const CNavArea *to, Vector *center, float *halfWidth ) const; // compute largest portal to adjacent area, returning direction
- void ComputeClosestPointInPortal( const CNavArea *to, NavDirType dir, const Vector &fromPos, Vector *closePos ) const; // compute closest point within the "portal" between to adjacent areas
- NavDirType ComputeDirection( Vector *point ) const; // return direction from this area to the given point
-
- //- for hunting algorithm ---------------------------------------------------------------------------
- void SetClearedTimestamp( int teamID ); // set this area's "clear" timestamp to now
- float GetClearedTimestamp( int teamID ) const; // get time this area was marked "clear"
-
- //- hiding spots ------------------------------------------------------------------------------------
- const HidingSpotVector *GetHidingSpots( void ) const { return &m_hidingSpots; }
-
- SpotEncounter *GetSpotEncounter( const CNavArea *from, const CNavArea *to ); // given the areas we are moving between, return the spots we will encounter
- int GetSpotEncounterCount( void ) const { return m_spotEncounters.Count(); }
-
- //- "danger" ----------------------------------------------------------------------------------------
- void IncreaseDanger( int teamID, float amount ); // increase the danger of this area for the given team
- float GetDanger( int teamID ); // return the danger of this area (decays over time)
- virtual float GetDangerDecayRate( void ) const; // return danger decay rate per second
-
- //- extents -----------------------------------------------------------------------------------------
- float GetSizeX( void ) const { return m_seCorner.x - m_nwCorner.x; }
- float GetSizeY( void ) const { return m_seCorner.y - m_nwCorner.y; }
- void GetExtent( Extent *extent ) const; // return a computed extent (XY is in m_nwCorner and m_seCorner, Z is computed)
- const Vector &GetCenter( void ) const { return m_center; }
- Vector GetRandomPoint( void ) const;
- Vector GetCorner( NavCornerType corner ) const;
- void SetCorner( NavCornerType corner, const Vector& newPosition );
- void ComputeNormal( Vector *normal, bool alternate = false ) const; // Computes the area's normal based on m_nwCorner. If 'alternate' is specified, m_seCorner is used instead.
- void RemoveOrthogonalConnections( NavDirType dir );
-
- //- occupy time ------------------------------------------------------------------------------------
- float GetEarliestOccupyTime( int teamID ) const; // returns the minimum time for someone of the given team to reach this spot from their spawn
- bool IsBattlefront( void ) const { return m_isBattlefront; } // true if this area is a "battlefront" - where rushing teams initially meet
-
- //- player counting --------------------------------------------------------------------------------
- void IncrementPlayerCount( int teamID, int entIndex ); // add one player to this area's count
- void DecrementPlayerCount( int teamID, int entIndex ); // subtract one player from this area's count
- unsigned char GetPlayerCount( int teamID = 0 ) const; // return number of players of given team currently within this area (team of zero means any/all)
-
- //- lighting ----------------------------------------------------------------------------------------
- float GetLightIntensity( const Vector &pos ) const; // returns a 0..1 light intensity for the given point
- float GetLightIntensity( float x, float y ) const; // returns a 0..1 light intensity for the given point
- float GetLightIntensity( void ) const; // returns a 0..1 light intensity averaged over the whole area
-
- //- A* pathfinding algorithm ------------------------------------------------------------------------
- static void MakeNewMarker( void ) { ++m_masterMarker; if (m_masterMarker == 0) m_masterMarker = 1; }
- void Mark( void ) { m_marker = m_masterMarker; }
- BOOL IsMarked( void ) const { return (m_marker == m_masterMarker) ? true : false; }
-
- void SetParent( CNavArea *parent, NavTraverseType how = NUM_TRAVERSE_TYPES ) { m_parent = parent; m_parentHow = how; }
- CNavArea *GetParent( void ) const { return m_parent; }
- NavTraverseType GetParentHow( void ) const { return m_parentHow; }
-
- bool IsOpen( void ) const; // true if on "open list"
- void AddToOpenList( void ); // add to open list in decreasing value order
- void AddToOpenListTail( void ); // add to tail of the open list
- void UpdateOnOpenList( void ); // a smaller value has been found, update this area on the open list
- void RemoveFromOpenList( void );
- static bool IsOpenListEmpty( void );
- static CNavArea *PopOpenList( void ); // remove and return the first element of the open list
-
- bool IsClosed( void ) const; // true if on "closed list"
- void AddToClosedList( void ); // add to the closed list
- void RemoveFromClosedList( void );
-
- static void ClearSearchLists( void ); // clears the open and closed lists for a new search
-
- void SetTotalCost( float value ) { Assert( value >= 0.0 && !IS_NAN(value) ); m_totalCost = value; }
- float GetTotalCost( void ) const { return m_totalCost; }
-
- void SetCostSoFar( float value ) { Assert( value >= 0.0 && !IS_NAN(value) ); m_costSoFar = value; }
- float GetCostSoFar( void ) const { return m_costSoFar; }
-
- void SetPathLengthSoFar( float value ) { Assert( value >= 0.0 && !IS_NAN(value) ); m_pathLengthSoFar = value; }
- float GetPathLengthSoFar( void ) const { return m_pathLengthSoFar; }
-
- //- editing -----------------------------------------------------------------------------------------
- virtual void Draw( void ) const; // draw area for debugging & editing
- virtual void DrawFilled( int r, int g, int b, int a, float deltaT = 0.1f, bool noDepthTest = true, float margin = 5.0f ) const; // draw area as a filled rect of the given color
- virtual void DrawSelectedSet( const Vector &shift ) const; // draw this area as part of a selected set
- void DrawDragSelectionSet( Color &dragSelectionSetColor ) const;
- void DrawConnectedAreas( void ) const;
- void DrawHidingSpots( void ) const;
- bool SplitEdit( bool splitAlongX, float splitEdge, CNavArea **outAlpha = NULL, CNavArea **outBeta = NULL ); // split this area into two areas at the given edge
- bool MergeEdit( CNavArea *adj ); // merge this area and given adjacent area
- bool SpliceEdit( CNavArea *other ); // create a new area between this area and given area
- void RaiseCorner( NavCornerType corner, int amount, bool raiseAdjacentCorners = true ); // raise/lower a corner (or all corners if corner == NUM_CORNERS)
- void PlaceOnGround( NavCornerType corner, float inset = 0.0f ); // places a corner (or all corners if corner == NUM_CORNERS) on the ground
- NavCornerType GetCornerUnderCursor( void ) const;
- bool GetCornerHotspot( NavCornerType corner, Vector hotspot[NUM_CORNERS] ) const; // returns true if the corner is under the cursor
- void Shift( const Vector &shift ); // shift the nav area
-
- //- ladders -----------------------------------------------------------------------------------------
- void AddLadderUp( CNavLadder *ladder );
- void AddLadderDown( CNavLadder *ladder );
-
- //- generation and analysis -------------------------------------------------------------------------
- virtual void ComputeHidingSpots( void ); // analyze local area neighborhood to find "hiding spots" in this area - for map learning
- virtual void ComputeSniperSpots( void ); // analyze local area neighborhood to find "sniper spots" in this area - for map learning
- virtual void ComputeSpotEncounters( void ); // compute spot encounter data - for map learning
- virtual void ComputeEarliestOccupyTimes( void );
- virtual void CustomAnalysis( bool isIncremental = false ) { } // for game-specific analysis
- virtual bool ComputeLighting( void ); // compute 0..1 light intensity at corners and center (requires client via listenserver)
- bool TestStairs( void ); // Test an area for being on stairs
- virtual bool IsAbleToMergeWith( CNavArea *other ) const;
-
- virtual void InheritAttributes( CNavArea *first, CNavArea *second = NULL );
-
-
- //- visibility -------------------------------------------------------------------------------------
- enum VisibilityType
- {
- NOT_VISIBLE = 0x00,
- POTENTIALLY_VISIBLE = 0x01,
- COMPLETELY_VISIBLE = 0x02,
- };
-
- VisibilityType ComputeVisibility( const CNavArea *area, bool isPVSValid, bool bCheckPVS = true, bool *pOutsidePVS = NULL ) const; // do actual line-of-sight traces to determine if any part of given area is visible from this area
- void SetupPVS( void ) const;
- bool IsInPVS( void ) const; // return true if this area is within the current PVS
-
- struct AreaBindInfo // for pointer loading and binding
- {
- union
- {
- CNavArea *area;
- unsigned int id;
- };
-
- unsigned char attributes; // VisibilityType
-
- bool operator==( const AreaBindInfo &other ) const
- {
- return ( area == other.area );
- }
- };
-
- virtual bool IsEntirelyVisible( const Vector &eye, CBaseEntity *ignore = NULL ) const; // return true if entire area is visible from given eyepoint (CPU intensive)
- virtual bool IsPartiallyVisible( const Vector &eye, CBaseEntity *ignore = NULL ) const; // return true if any portion of the area is visible from given eyepoint (CPU intensive)
-
- virtual bool IsPotentiallyVisible( const CNavArea *area ) const; // return true if given area is potentially visible from somewhere in this area (very fast)
- virtual bool IsPotentiallyVisibleToTeam( int team ) const; // return true if any portion of this area is visible to anyone on the given team (very fast)
-
- virtual bool IsCompletelyVisible( const CNavArea *area ) const; // return true if given area is completely visible from somewhere in this area (very fast)
- virtual bool IsCompletelyVisibleToTeam( int team ) const; // return true if given area is completely visible from somewhere in this area by someone on the team (very fast)
-
- //-------------------------------------------------------------------------------------
- /**
- * Apply the functor to all navigation areas that are potentially
- * visible from this area.
- */
- template < typename Functor >
- bool ForAllPotentiallyVisibleAreas( Functor &func )
- {
- int i;
-
- ++s_nCurrVisTestCounter;
-
- for ( i=0; i<m_potentiallyVisibleAreas.Count(); ++i )
- {
- CNavArea *area = m_potentiallyVisibleAreas[i].area;
- if ( !area )
- continue;
-
- // If this assertion triggers, an area is in here twice!
- Assert( area->m_nVisTestCounter != s_nCurrVisTestCounter );
- area->m_nVisTestCounter = s_nCurrVisTestCounter;
-
- if ( m_potentiallyVisibleAreas[i].attributes == NOT_VISIBLE )
- continue;
-
- if ( func( area ) == false )
- return false;
- }
-
- // for each inherited area
- if ( !m_inheritVisibilityFrom.area )
- return true;
-
- CAreaBindInfoArray &inherited = m_inheritVisibilityFrom.area->m_potentiallyVisibleAreas;
-
- for ( i=0; i<inherited.Count(); ++i )
- {
- if ( !inherited[i].area )
- continue;
-
- // We may have visited this from m_potentiallyVisibleAreas
- if ( inherited[i].area->m_nVisTestCounter == s_nCurrVisTestCounter )
- continue;
-
- // Theoretically, this shouldn't matter. But, just in case!
- inherited[i].area->m_nVisTestCounter = s_nCurrVisTestCounter;
-
- if ( inherited[i].attributes == NOT_VISIBLE )
- continue;
-
- if ( func( inherited[i].area ) == false )
- return false;
- }
-
- return true;
- }
-
- //-------------------------------------------------------------------------------------
- /**
- * Apply the functor to all navigation areas that are
- * completely visible from somewhere in this area.
- */
- template < typename Functor >
- bool ForAllCompletelyVisibleAreas( Functor &func )
- {
- int i;
-
- ++s_nCurrVisTestCounter;
-
- for ( i=0; i<m_potentiallyVisibleAreas.Count(); ++i )
- {
- CNavArea *area = m_potentiallyVisibleAreas[i].area;
- if ( !area )
- continue;
-
- // If this assertion triggers, an area is in here twice!
- Assert( area->m_nVisTestCounter != s_nCurrVisTestCounter );
- area->m_nVisTestCounter = s_nCurrVisTestCounter;
-
- if ( ( m_potentiallyVisibleAreas[i].attributes & COMPLETELY_VISIBLE ) == 0 )
- continue;
-
- if ( func( area ) == false )
- return false;
- }
-
- if ( !m_inheritVisibilityFrom.area )
- return true;
-
- // for each inherited area
- CAreaBindInfoArray &inherited = m_inheritVisibilityFrom.area->m_potentiallyVisibleAreas;
-
- for ( i=0; i<inherited.Count(); ++i )
- {
- if ( !inherited[i].area )
- continue;
-
- // We may have visited this from m_potentiallyVisibleAreas
- if ( inherited[i].area->m_nVisTestCounter == s_nCurrVisTestCounter )
- continue;
-
- // Theoretically, this shouldn't matter. But, just in case!
- inherited[i].area->m_nVisTestCounter = s_nCurrVisTestCounter;
-
- if ( ( inherited[i].attributes & COMPLETELY_VISIBLE ) == 0 )
- continue;
-
- if ( func( inherited[i].area ) == false )
- return false;
- }
-
- return true;
- }
-
-
-private:
- friend class CNavMesh;
- friend class CNavLadder;
- friend class CCSNavArea; // allow CS load code to complete replace our default load behavior
-
- static bool m_isReset; // if true, don't bother cleaning up in destructor since everything is going away
-
- /*
- m_nwCorner
- nw ne
- +-----------+
- | +-->x |
- | | |
- | v |
- | y |
- | |
- +-----------+
- sw se
- m_seCorner
- */
-
- static unsigned int m_nextID; // used to allocate unique IDs
- unsigned int m_id; // unique area ID
- unsigned int m_debugid;
-
- Place m_place; // place descriptor
-
- CountdownTimer m_blockedTimer; // Throttle checks on our blocked state while blocked
- void UpdateBlockedFromNavBlockers( void ); // checks if nav blockers are still blocking the area
-
- bool m_isUnderwater; // true if the center of the area is underwater
-
- bool m_isBattlefront;
-
- float m_avoidanceObstacleHeight; // if nonzero, a prop is obstructing movement through this nav area
- CountdownTimer m_avoidanceObstacleTimer; // Throttle checks on our obstructed state while obstructed
-
- //- for hunting -------------------------------------------------------------------------------------
- float m_clearedTimestamp[ MAX_NAV_TEAMS ]; // time this area was last "cleared" of enemies
-
- //- "danger" ----------------------------------------------------------------------------------------
- float m_danger[ MAX_NAV_TEAMS ]; // danger of this area, allowing bots to avoid areas where they died in the past - zero is no danger
- float m_dangerTimestamp[ MAX_NAV_TEAMS ]; // time when danger value was set - used for decaying
- void DecayDanger( void );
-
- //- hiding spots ------------------------------------------------------------------------------------
- HidingSpotVector m_hidingSpots;
- bool IsHidingSpotCollision( const Vector &pos ) const; // returns true if an existing hiding spot is too close to given position
-
- //- encounter spots ---------------------------------------------------------------------------------
- SpotEncounterVector m_spotEncounters; // list of possible ways to move thru this area, and the spots to look at as we do
- void AddSpotEncounters( const CNavArea *from, NavDirType fromDir, const CNavArea *to, NavDirType toDir ); // add spot encounter data when moving from area to area
-
- float m_earliestOccupyTime[ MAX_NAV_TEAMS ]; // min time to reach this spot from spawn
-
-#ifdef DEBUG_AREA_PLAYERCOUNTS
- CUtlVector< int > m_playerEntIndices[ MAX_NAV_TEAMS ];
-#endif
-
- //- lighting ----------------------------------------------------------------------------------------
- float m_lightIntensity[ NUM_CORNERS ]; // 0..1 light intensity at corners
-
- //- A* pathfinding algorithm ------------------------------------------------------------------------
- static unsigned int m_masterMarker;
-
- static CNavArea *m_openList;
- static CNavArea *m_openListTail;
-
- //- connections to adjacent areas -------------------------------------------------------------------
- NavConnectVector m_incomingConnect[ NUM_DIRECTIONS ]; // a list of adjacent areas for each direction that connect TO us, but we have no connection back to them
-
- //---------------------------------------------------------------------------------------------------
- CNavNode *m_node[ NUM_CORNERS ]; // nav nodes at each corner of the area
-
- void ResetNodes( void ); // nodes are going away as part of an incremental nav generation
- void Strip( void ); // remove "analyzed" data from nav area
-
- void FinishMerge( CNavArea *adjArea ); // recompute internal data once nodes have been adjusted during merge
- void MergeAdjacentConnections( CNavArea *adjArea ); // for merging with "adjArea" - pick up all of "adjArea"s connections
- void AssignNodes( CNavArea *area ); // assign internal nodes to the given area
-
- void FinishSplitEdit( CNavArea *newArea, NavDirType ignoreEdge ); // given the portion of the original area, update its internal data
-
- void CalcDebugID();
-
-#ifdef NEXT_BOT
- CUtlVector< CHandle< CFuncNavPrerequisite > > m_prerequisiteVector; // list of prerequisites that must be met before this area can be traversed
-#endif
-
- CNavArea *m_prevHash, *m_nextHash; // for hash table in CNavMesh
-
- void ConnectElevators( void ); // find elevator connections between areas
-
- int m_damagingTickCount; // this area is damaging through this tick count
-
-
- //- visibility --------------------------------------------------------------------------------------
- void ComputeVisibilityToMesh( void ); // compute visibility to surrounding mesh
- void ResetPotentiallyVisibleAreas();
- static void ComputeVisToArea( CNavArea *&pOtherArea );
-
-#ifndef _X360
- typedef CUtlVectorConservative<AreaBindInfo> CAreaBindInfoArray; // shaves 8 bytes off structure caused by need to support editing
-#else
- typedef CUtlVector<AreaBindInfo> CAreaBindInfoArray; // Need to use this on 360 to support external allocation pattern
-#endif
-
- AreaBindInfo m_inheritVisibilityFrom; // if non-NULL, m_potentiallyVisibleAreas becomes a list of additions and deletions (NOT_VISIBLE) to the list of this area
- CAreaBindInfoArray m_potentiallyVisibleAreas; // list of areas potentially visible from inside this area (after PostLoad(), use area portion of union)
- bool m_isInheritedFrom; // latch used during visibility inheritance computation
-
- const CAreaBindInfoArray &ComputeVisibilityDelta( const CNavArea *other ) const; // return a list of the delta between our visibility list and the given adjacent area
-
- uint32 m_nVisTestCounter;
- static uint32 s_nCurrVisTestCounter;
-
- CUtlVector< CHandle< CFuncNavCost > > m_funcNavCostVector; // active, overlapping cost entities
-};
-
-typedef CUtlVector< CNavArea * > NavAreaVector;
-extern NavAreaVector TheNavAreas;
-
-
-//--------------------------------------------------------------------------------------------------------------
-//--------------------------------------------------------------------------------------------------------------
-//
-// Inlines
-//
-
-#ifdef NEXT_BOT
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::HasPrerequisite( CBaseCombatCharacter *actor ) const
-{
- return m_prerequisiteVector.Count() > 0;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline const CUtlVector< CHandle< CFuncNavPrerequisite > > &CNavArea::GetPrerequisiteVector( void ) const
-{
- return m_prerequisiteVector;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline void CNavArea::RemoveAllPrerequisites( void )
-{
- m_prerequisiteVector.RemoveAll();
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline void CNavArea::AddPrerequisite( CFuncNavPrerequisite *prereq )
-{
- if ( m_prerequisiteVector.Find( prereq ) == m_prerequisiteVector.InvalidIndex() )
- {
- m_prerequisiteVector.AddToTail( prereq );
- }
-}
-#endif
-
-//--------------------------------------------------------------------------------------------------------------
-inline float CNavArea::GetDangerDecayRate( void ) const
-{
- // one kill == 1.0, which we will forget about in two minutes
- return 1.0f / 120.0f;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::IsDegenerate( void ) const
-{
- return (m_nwCorner.x >= m_seCorner.x || m_nwCorner.y >= m_seCorner.y);
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline CNavArea *CNavArea::GetAdjacentArea( NavDirType dir, int i ) const
-{
- for( int iter = 0; iter < m_connect[dir].Count(); ++iter )
- {
- if (i == 0)
- return m_connect[dir][iter].area;
- --i;
- }
-
- return NULL;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::IsOpen( void ) const
-{
- return (m_openMarker == m_masterMarker) ? true : false;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::IsOpenListEmpty( void )
-{
- Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL );
- return (m_openList) ? false : true;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline CNavArea *CNavArea::PopOpenList( void )
-{
- Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL );
-
- if ( m_openList )
- {
- CNavArea *area = m_openList;
-
- // disconnect from list
- area->RemoveFromOpenList();
- area->m_prevOpen = NULL;
- area->m_nextOpen = NULL;
-
- Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL );
-
- return area;
- }
-
- Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL );
-
- return NULL;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::IsClosed( void ) const
-{
- if (IsMarked() && !IsOpen())
- return true;
-
- return false;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline void CNavArea::AddToClosedList( void )
-{
- Mark();
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline void CNavArea::RemoveFromClosedList( void )
-{
- // since "closed" is defined as visited (marked) and not on open list, do nothing
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline void CNavArea::SetClearedTimestamp( int teamID )
-{
- m_clearedTimestamp[ teamID % MAX_NAV_TEAMS ] = gpGlobals->curtime;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline float CNavArea::GetClearedTimestamp( int teamID ) const
-{
- return m_clearedTimestamp[ teamID % MAX_NAV_TEAMS ];
-}
-
-//--------------------------------------------------------------------------------------------------------------
-inline float CNavArea::GetEarliestOccupyTime( int teamID ) const
-{
- return m_earliestOccupyTime[ teamID % MAX_NAV_TEAMS ];
-}
-
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::IsDamaging( void ) const
-{
- return ( gpGlobals->tickcount <= m_damagingTickCount );
-}
-
-
-//--------------------------------------------------------------------------------------------------------------
-inline void CNavArea::MarkAsDamaging( float duration )
-{
- m_damagingTickCount = gpGlobals->tickcount + TIME_TO_TICKS( duration );
-}
-
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::HasAvoidanceObstacle( float maxObstructionHeight ) const
-{
- return m_avoidanceObstacleHeight > maxObstructionHeight;
-}
-
-
-//--------------------------------------------------------------------------------------------------------------
-inline float CNavArea::GetAvoidanceObstacleHeight( void ) const
-{
- return m_avoidanceObstacleHeight;
-}
-
-
-//--------------------------------------------------------------------------------------------------------------
-inline bool CNavArea::IsVisible( const Vector &eye, Vector *visSpot ) const
-{
- Vector corner;
- trace_t result;
- CTraceFilterNoNPCsOrPlayer traceFilter( NULL, COLLISION_GROUP_NONE );
- const float offset = 0.75f * HumanHeight;
-
- // check center first
- UTIL_TraceLine( eye, GetCenter() + Vector( 0, 0, offset ), MASK_BLOCKLOS_AND_NPCS|CONTENTS_IGNORE_NODRAW_OPAQUE, &traceFilter, &result );
- if (result.fraction == 1.0f)
- {
- // we can see this area
- if (visSpot)
- {
- *visSpot = GetCenter();
- }
- return true;
- }
-
- for( int c=0; c<NUM_CORNERS; ++c )
- {
- corner = GetCorner( (NavCornerType)c );
- UTIL_TraceLine( eye, corner + Vector( 0, 0, offset ), MASK_BLOCKLOS_AND_NPCS|CONTENTS_IGNORE_NODRAW_OPAQUE, &traceFilter, &result );
- if (result.fraction == 1.0f)
- {
- // we can see this area
- if (visSpot)
- {
- *visSpot = corner;
- }
- return true;
- }
- }
-
- return false;
-}
-
-#ifndef DEBUG_AREA_PLAYERCOUNTS
-inline void CNavArea::IncrementPlayerCount( int teamID, int entIndex )
-{
- teamID = teamID % MAX_NAV_TEAMS;
-
- if (m_playerCount[ teamID ] == 255)
- {
- DevMsg( "CNavArea::IncrementPlayerCount: Overflow\n" );
- return;
- }
-
- ++m_playerCount[ teamID ];
-}
-
-inline void CNavArea::DecrementPlayerCount( int teamID, int entIndex )
-{
- teamID = teamID % MAX_NAV_TEAMS;
-
- if (m_playerCount[ teamID ] == 0)
- {
- DevMsg( "CNavArea::IncrementPlayerCount: Underflow\n" );
- return;
- }
-
- --m_playerCount[ teamID ];
-}
-#endif // !DEBUG_AREA_PLAYERCOUNTS
-
-inline unsigned char CNavArea::GetPlayerCount( int teamID ) const
-{
- if (teamID)
- {
- return m_playerCount[ teamID % MAX_NAV_TEAMS ];
- }
-
- // sum all players
- unsigned char total = 0;
- for( int i=0; i<MAX_NAV_TEAMS; ++i )
- {
- total += m_playerCount[i];
- }
-
- return total;
-}
-
-//--------------------------------------------------------------------------------------------------------------
-/**
-* Return Z of area at (x,y) of 'pos'
-* Trilinear interpolation of Z values at quad edges.
-* NOTE: pos->z is not used.
-*/
-inline float CNavArea::GetZ( const Vector * RESTRICT pos ) const RESTRICT
-{
- return GetZ( pos->x, pos->y );
-}
-
-inline float CNavArea::GetZ( const Vector & pos ) const RESTRICT
-{
- return GetZ( pos.x, pos.y );
-}
-
-//--------------------------------------------------------------------------------------------------------------
-/**
-* Return the coordinates of the area's corner.
-*/
-inline Vector CNavArea::GetCorner( NavCornerType corner ) const
-{
- // @TODO: Confirm compiler does the "right thing" in release builds, or change this function to to take a pointer [2/4/2009 tom]
- Vector pos;
-
- switch( corner )
- {
- default:
- Assert( false && "GetCorner: Invalid type" );
- case NORTH_WEST:
- return m_nwCorner;
-
- case NORTH_EAST:
- pos.x = m_seCorner.x;
- pos.y = m_nwCorner.y;
- pos.z = m_neZ;
- return pos;
-
- case SOUTH_WEST:
- pos.x = m_nwCorner.x;
- pos.y = m_seCorner.y;
- pos.z = m_swZ;
- return pos;
-
- case SOUTH_EAST:
- return m_seCorner;
- }
-}
-
-
-#endif // _NAV_AREA_H_
+//========= Copyright Valve Corporation, All rights reserved. ============// +// +// Purpose: +// +// $NoKeywords: $ +// +//=============================================================================// +// nav_area.h +// Navigation areas +// Author: Michael S. Booth ([email protected]), January 2003 + +#ifndef _NAV_AREA_H_ +#define _NAV_AREA_H_ + +#include "nav_ladder.h" +#include "tier1/memstack.h" + +// BOTPORT: Clean up relationship between team index and danger storage in nav areas +enum { MAX_NAV_TEAMS = 2 }; + + +class CFuncElevator; +class CFuncNavPrerequisite; +class CFuncNavCost; + +class CNavVectorNoEditAllocator +{ +public: + CNavVectorNoEditAllocator(); + + static void Reset(); + static void *Alloc( size_t nSize ); + static void *Realloc( void *pMem, size_t nSize ); + static void Free( void *pMem ); + static size_t GetSize( void *pMem ); + +private: + static CMemoryStack m_memory; + static void *m_pCurrent; + static int m_nBytesCurrent; +}; + +#if !defined(_X360) +typedef CUtlVectorUltraConservativeAllocator CNavVectorAllocator; +#else +typedef CNavVectorNoEditAllocator CNavVectorAllocator; +#endif + + +//------------------------------------------------------------------------------------------------------------------- +/** + * Functor interface for iteration + */ +class IForEachNavArea +{ +public: + virtual bool Inspect( const CNavArea *area ) = 0; // Invoked once on each area of the iterated set. Return false to stop iterating. + virtual void PostIteration( bool wasCompleteIteration ) { } // Invoked after the iteration has ended. 'wasCompleteIteration' will be true if the entire set was iterated (ie: Inspect() never returned false) +}; + + +//------------------------------------------------------------------------------------------------------------------- +/** + * The NavConnect union is used to refer to connections to areas + */ +struct NavConnect +{ + NavConnect() + { + id = 0; + length = -1; + } + + union + { + unsigned int id; + CNavArea *area; + }; + + mutable float length; + + bool operator==( const NavConnect &other ) const + { + return (area == other.area) ? true : false; + } +}; + +typedef CUtlVectorUltraConservative<NavConnect, CNavVectorAllocator> NavConnectVector; + + +//------------------------------------------------------------------------------------------------------------------- +/** + * The NavLadderConnect union is used to refer to connections to ladders + */ +union NavLadderConnect +{ + unsigned int id; + CNavLadder *ladder; + + bool operator==( const NavLadderConnect &other ) const + { + return (ladder == other.ladder) ? true : false; + } +}; +typedef CUtlVectorUltraConservative<NavLadderConnect, CNavVectorAllocator> NavLadderConnectVector; + + +//-------------------------------------------------------------------------------------------------------------- +/** + * A HidingSpot is a good place for a bot to crouch and wait for enemies + */ +class HidingSpot +{ +public: + virtual ~HidingSpot() { } + + enum + { + IN_COVER = 0x01, // in a corner with good hard cover nearby + GOOD_SNIPER_SPOT = 0x02, // had at least one decent sniping corridor + IDEAL_SNIPER_SPOT = 0x04, // can see either very far, or a large area, or both + EXPOSED = 0x08 // spot in the open, usually on a ledge or cliff + }; + + bool HasGoodCover( void ) const { return (m_flags & IN_COVER) ? true : false; } // return true if hiding spot in in cover + bool IsGoodSniperSpot( void ) const { return (m_flags & GOOD_SNIPER_SPOT) ? true : false; } + bool IsIdealSniperSpot( void ) const { return (m_flags & IDEAL_SNIPER_SPOT) ? true : false; } + bool IsExposed( void ) const { return (m_flags & EXPOSED) ? true : false; } + + int GetFlags( void ) const { return m_flags; } + + void Save( CUtlBuffer &fileBuffer, unsigned int version ) const; + void Load( CUtlBuffer &fileBuffer, unsigned int version ); + NavErrorType PostLoad( void ); + + const Vector &GetPosition( void ) const { return m_pos; } // get the position of the hiding spot + unsigned int GetID( void ) const { return m_id; } + const CNavArea *GetArea( void ) const { return m_area; } // return nav area this hiding spot is within + + void Mark( void ) { m_marker = m_masterMarker; } + bool IsMarked( void ) const { return (m_marker == m_masterMarker) ? true : false; } + static void ChangeMasterMarker( void ) { ++m_masterMarker; } + + +public: + void SetFlags( int flags ) { m_flags |= flags; } // FOR INTERNAL USE ONLY + void SetPosition( const Vector &pos ) { m_pos = pos; } // FOR INTERNAL USE ONLY + +private: + friend class CNavMesh; + friend void ClassifySniperSpot( HidingSpot *spot ); + + HidingSpot( void ); // must use factory to create + + Vector m_pos; // world coordinates of the spot + unsigned int m_id; // this spot's unique ID + unsigned int m_marker; // this spot's unique marker + CNavArea *m_area; // the nav area containing this hiding spot + + unsigned char m_flags; // bit flags + + static unsigned int m_nextID; // used when allocating spot ID's + static unsigned int m_masterMarker; // used to mark spots +}; +typedef CUtlVectorUltraConservative< HidingSpot * > HidingSpotVector; +extern HidingSpotVector TheHidingSpots; + +extern HidingSpot *GetHidingSpotByID( unsigned int id ); + + +//-------------------------------------------------------------------------------------------------------------- +/** + * Stores a pointer to an interesting "spot", and a parametric distance along a path + */ +struct SpotOrder +{ + float t; // parametric distance along ray where this spot first has LOS to our path + union + { + HidingSpot *spot; // the spot to look at + unsigned int id; // spot ID for save/load + }; +}; +typedef CUtlVector< SpotOrder > SpotOrderVector; + +/** + * This struct stores possible path segments thru a CNavArea, and the dangerous spots + * to look at as we traverse that path segment. + */ +struct SpotEncounter +{ + NavConnect from; + NavDirType fromDir; + NavConnect to; + NavDirType toDir; + Ray path; // the path segment + SpotOrderVector spots; // list of spots to look at, in order of occurrence +}; +typedef CUtlVectorUltraConservative< SpotEncounter * > SpotEncounterVector; + + +//------------------------------------------------------------------------------------------------------------------- +/** + * A CNavArea is a rectangular region defining a walkable area in the environment + */ + +class CNavAreaCriticalData +{ +protected: + // --- Begin critical data, which is heavily hit during pathing operations and carefully arranged for cache performance [7/24/2008 tom] --- + + /* 0 */ Vector m_nwCorner; // north-west corner position (2D mins) + /* 12 */ Vector m_seCorner; // south-east corner position (2D maxs) + /* 24 */ float m_invDxCorners; + /* 28 */ float m_invDyCorners; + /* 32 */ float m_neZ; // height of the implicit corner defined by (m_seCorner.x, m_nwCorner.y, m_neZ) + /* 36 */ float m_swZ; // height of the implicit corner defined by (m_nwCorner.x, m_seCorner.y, m_neZ) + /* 40 */ Vector m_center; // centroid of area + + /* 52 */ unsigned char m_playerCount[ MAX_NAV_TEAMS ]; // the number of players currently in this area + + /* 54 */ bool m_isBlocked[ MAX_NAV_TEAMS ]; // if true, some part of the world is preventing movement through this nav area + + /* 56 */ unsigned int m_marker; // used to flag the area as visited + /* 60 */ float m_totalCost; // the distance so far plus an estimate of the distance left + /* 64 */ float m_costSoFar; // distance travelled so far + + /* 68 */ CNavArea *m_nextOpen, *m_prevOpen; // only valid if m_openMarker == m_masterMarker + /* 76 */ unsigned int m_openMarker; // if this equals the current marker value, we are on the open list + + /* 80 */ int m_attributeFlags; // set of attribute bit flags (see NavAttributeType) + + //- connections to adjacent areas ------------------------------------------------------------------- + /* 84 */ NavConnectVector m_connect[ NUM_DIRECTIONS ]; // a list of adjacent areas for each direction + /* 100*/ NavLadderConnectVector m_ladder[ CNavLadder::NUM_LADDER_DIRECTIONS ]; // list of ladders leading up and down from this area + /* 108*/ NavConnectVector m_elevatorAreas; // a list of areas reachable via elevator from this area + + /* 112*/ unsigned int m_nearNavSearchMarker; // used in GetNearestNavArea() + + /* 116*/ CNavArea *m_parent; // the area just prior to this on in the search path + /* 120*/ NavTraverseType m_parentHow; // how we get from parent to us + + /* 124*/ float m_pathLengthSoFar; // length of path so far, needed for limiting pathfind max path length + + /* *************** 360 cache line *************** */ + + /* 128*/ CFuncElevator *m_elevator; // if non-NULL, this area is in an elevator's path. The elevator can transport us vertically to another area. + + // --- End critical data --- +}; + + +class CNavArea : protected CNavAreaCriticalData +{ +public: + DECLARE_CLASS_NOBASE( CNavArea ) + + CNavArea( void ); + virtual ~CNavArea(); + + virtual void OnServerActivate( void ); // (EXTEND) invoked when map is initially loaded + virtual void OnRoundRestart( void ); // (EXTEND) invoked for each area when the round restarts + virtual void OnRoundRestartPreEntity( void ) { } // invoked for each area when the round restarts, but before entities are deleted and recreated + virtual void OnEnter( CBaseCombatCharacter *who, CNavArea *areaJustLeft ) { } // invoked when player enters this area + virtual void OnExit( CBaseCombatCharacter *who, CNavArea *areaJustEntered ) { } // invoked when player exits this area + + virtual void OnDestroyNotify( CNavArea *dead ); // invoked when given area is going away + virtual void OnDestroyNotify( CNavLadder *dead ); // invoked when given ladder is going away + + 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 Save( CUtlBuffer &fileBuffer, unsigned int version ) const; // (EXTEND) + virtual NavErrorType Load( CUtlBuffer &fileBuffer, unsigned int version, unsigned int subVersion ); // (EXTEND) + virtual NavErrorType PostLoad( void ); // (EXTEND) invoked after all areas have been loaded - for pointer binding, etc + + virtual void SaveToSelectedSet( KeyValues *areaKey ) const; // (EXTEND) saves attributes for the area to a KeyValues + virtual void RestoreFromSelectedSet( KeyValues *areaKey ); // (EXTEND) restores attributes from a KeyValues + + // for interactively building or generating nav areas + void Build( CNavNode *nwNode, CNavNode *neNode, CNavNode *seNode, CNavNode *swNode ); + void Build( const Vector &corner, const Vector &otherCorner ); + void Build( const Vector &nwCorner, const Vector &neCorner, const Vector &seCorner, const Vector &swCorner ); + + void ConnectTo( CNavArea *area, NavDirType dir ); // connect this area to given area in given direction + void Disconnect( CNavArea *area ); // disconnect this area from given area + + void ConnectTo( CNavLadder *ladder ); // connect this area to given ladder + void Disconnect( CNavLadder *ladder ); // disconnect this area from given ladder + + unsigned int GetID( void ) const { return m_id; } // return this area's unique ID + static void CompressIDs( void ); // re-orders area ID's so they are continuous + unsigned int GetDebugID( void ) const { return m_debugid; } + + void SetAttributes( int bits ) { m_attributeFlags = bits; } + int GetAttributes( void ) const { return m_attributeFlags; } + bool HasAttributes( int bits ) const { return ( m_attributeFlags & bits ) ? true : false; } + void RemoveAttributes( int bits ) { m_attributeFlags &= ( ~bits ); } + + void SetPlace( Place place ) { m_place = place; } // set place descriptor + Place GetPlace( void ) const { return m_place; } // get place descriptor + + void MarkAsBlocked( int teamID, CBaseEntity *blocker, bool bGenerateEvent = true ); // An entity can force a nav area to be blocked + virtual void UpdateBlocked( bool force = false, int teamID = TEAM_ANY ); // Updates the (un)blocked status of the nav area (throttled) + virtual bool IsBlocked( int teamID, bool ignoreNavBlockers = false ) const; + void UnblockArea( int teamID = TEAM_ANY ); // clear blocked status for the given team(s) + + void CheckFloor( CBaseEntity *ignore ); // Checks if there is a floor under the nav area, in case a breakable floor is gone + + void MarkObstacleToAvoid( float obstructionHeight ); + void UpdateAvoidanceObstacles( void ); + bool HasAvoidanceObstacle( float maxObstructionHeight = StepHeight ) const; // is there a large, immobile object obstructing this area + float GetAvoidanceObstacleHeight( void ) const; // returns the maximum height of the obstruction above the ground + +#ifdef NEXT_BOT + bool HasPrerequisite( CBaseCombatCharacter *actor = NULL ) const; // return true if this area has a prerequisite that applies to the given actor + const CUtlVector< CHandle< CFuncNavPrerequisite > > &GetPrerequisiteVector( void ) const; // return vector of prerequisites that must be met before this area can be traversed + void RemoveAllPrerequisites( void ); + void AddPrerequisite( CFuncNavPrerequisite *prereq ); +#endif + + void ClearAllNavCostEntities( void ); // clear set of func_nav_cost entities that affect this area + void AddFuncNavCostEntity( CFuncNavCost *cost ); // add the given func_nav_cost entity to the cost of this area + float ComputeFuncNavCost( CBaseCombatCharacter *who ) const; // return the cost multiplier of this area's func_nav_cost entities for the given actor + bool HasFuncNavAvoid( void ) const; + bool HasFuncNavPrefer( void ) const; + + void CheckWaterLevel( void ); + bool IsUnderwater( void ) const { return m_isUnderwater; } + + bool IsOverlapping( const Vector &pos, float tolerance = 0.0f ) const; // return true if 'pos' is within 2D extents of area. + bool IsOverlapping( const CNavArea *area ) const; // return true if 'area' overlaps our 2D extents + bool IsOverlapping( const Extent &extent ) const; // return true if 'extent' overlaps our 2D extents + bool IsOverlappingX( const CNavArea *area ) const; // return true if 'area' overlaps our X extent + bool IsOverlappingY( const CNavArea *area ) const; // return true if 'area' overlaps our Y extent + inline float GetZ( const Vector * RESTRICT pPos ) const ; // return Z of area at (x,y) of 'pos' + inline float GetZ( const Vector &pos ) const; // return Z of area at (x,y) of 'pos' + float GetZ( float x, float y ) const RESTRICT; // return Z of area at (x,y) of 'pos' + bool Contains( const Vector &pos ) const; // return true if given point is on or above this area, but no others + bool Contains( const CNavArea *area ) const; + bool IsCoplanar( const CNavArea *area ) const; // return true if this area and given area are approximately co-planar + void GetClosestPointOnArea( const Vector * RESTRICT pPos, Vector *close ) const RESTRICT; // return closest point to 'pos' on this area - returned point in 'close' + void GetClosestPointOnArea( const Vector &pos, Vector *close ) const { return GetClosestPointOnArea( &pos, close ); } + float GetDistanceSquaredToPoint( const Vector &pos ) const; // return shortest distance between point and this area + bool IsDegenerate( void ) const; // return true if this area is badly formed + bool IsRoughlySquare( void ) const; // return true if this area is approximately square + bool IsFlat( void ) const; // return true if this area is approximately flat + bool HasNodes( void ) const; + void GetNodes( NavDirType dir, CUtlVector< CNavNode * > *nodes ) const; // build a vector of nodes along the given direction + CNavNode *FindClosestNode( const Vector &pos, NavDirType dir ) const; // returns the closest node along the given edge to the given point + + bool IsContiguous( const CNavArea *other ) const; // return true if the given area and 'other' share a colinear edge (ie: no drop-down or step/jump/climb) + float ComputeAdjacentConnectionHeightChange( const CNavArea *destinationArea ) const; // return height change between edges of adjacent nav areas (not actual underlying ground) + + bool IsEdge( NavDirType dir ) const; // return true if there are no bi-directional links on the given side + + bool IsDamaging( void ) const; // Return true if continuous damage (ie: fire) is in this area + void MarkAsDamaging( float duration ); // Mark this area is damaging for the next 'duration' seconds + + bool IsVisible( const Vector &eye, Vector *visSpot = NULL ) const; // return true if area is visible from the given eyepoint, return visible spot + + int GetAdjacentCount( NavDirType dir ) const { return m_connect[ dir ].Count(); } // return number of connected areas in given direction + CNavArea *GetAdjacentArea( NavDirType dir, int i ) const; // return the i'th adjacent area in the given direction + CNavArea *GetRandomAdjacentArea( NavDirType dir ) const; + void CollectAdjacentAreas( CUtlVector< CNavArea * > *adjVector ) const; // build a vector of all adjacent areas + + const NavConnectVector *GetAdjacentAreas( NavDirType dir ) const { return &m_connect[dir]; } + bool IsConnected( const CNavArea *area, NavDirType dir ) const; // return true if given area is connected in given direction + bool IsConnected( const CNavLadder *ladder, CNavLadder::LadderDirectionType dir ) const; // return true if given ladder is connected in given direction + float ComputeGroundHeightChange( const CNavArea *area ); // compute change in actual ground height from this area to given area + + const NavConnectVector *GetIncomingConnections( NavDirType dir ) const { return &m_incomingConnect[dir]; } // get areas connected TO this area by a ONE-WAY link (ie: we have no connection back to them) + void AddIncomingConnection( CNavArea *source, NavDirType incomingEdgeDir ); + + const NavLadderConnectVector *GetLadders( CNavLadder::LadderDirectionType dir ) const { return &m_ladder[dir]; } + CFuncElevator *GetElevator( void ) const { Assert( !( m_attributeFlags & NAV_MESH_HAS_ELEVATOR ) == (m_elevator == NULL) ); return ( m_attributeFlags & NAV_MESH_HAS_ELEVATOR ) ? m_elevator : NULL; } + const NavConnectVector &GetElevatorAreas( void ) const { return m_elevatorAreas; } // return collection of areas reachable via elevator from this area + + void ComputePortal( const CNavArea *to, NavDirType dir, Vector *center, float *halfWidth ) const; // compute portal to adjacent area + NavDirType ComputeLargestPortal( const CNavArea *to, Vector *center, float *halfWidth ) const; // compute largest portal to adjacent area, returning direction + void ComputeClosestPointInPortal( const CNavArea *to, NavDirType dir, const Vector &fromPos, Vector *closePos ) const; // compute closest point within the "portal" between to adjacent areas + NavDirType ComputeDirection( Vector *point ) const; // return direction from this area to the given point + + //- for hunting algorithm --------------------------------------------------------------------------- + void SetClearedTimestamp( int teamID ); // set this area's "clear" timestamp to now + float GetClearedTimestamp( int teamID ) const; // get time this area was marked "clear" + + //- hiding spots ------------------------------------------------------------------------------------ + const HidingSpotVector *GetHidingSpots( void ) const { return &m_hidingSpots; } + + SpotEncounter *GetSpotEncounter( const CNavArea *from, const CNavArea *to ); // given the areas we are moving between, return the spots we will encounter + int GetSpotEncounterCount( void ) const { return m_spotEncounters.Count(); } + + //- "danger" ---------------------------------------------------------------------------------------- + void IncreaseDanger( int teamID, float amount ); // increase the danger of this area for the given team + float GetDanger( int teamID ); // return the danger of this area (decays over time) + virtual float GetDangerDecayRate( void ) const; // return danger decay rate per second + + //- extents ----------------------------------------------------------------------------------------- + float GetSizeX( void ) const { return m_seCorner.x - m_nwCorner.x; } + float GetSizeY( void ) const { return m_seCorner.y - m_nwCorner.y; } + void GetExtent( Extent *extent ) const; // return a computed extent (XY is in m_nwCorner and m_seCorner, Z is computed) + const Vector &GetCenter( void ) const { return m_center; } + Vector GetRandomPoint( void ) const; + Vector GetCorner( NavCornerType corner ) const; + void SetCorner( NavCornerType corner, const Vector& newPosition ); + void ComputeNormal( Vector *normal, bool alternate = false ) const; // Computes the area's normal based on m_nwCorner. If 'alternate' is specified, m_seCorner is used instead. + void RemoveOrthogonalConnections( NavDirType dir ); + + //- occupy time ------------------------------------------------------------------------------------ + float GetEarliestOccupyTime( int teamID ) const; // returns the minimum time for someone of the given team to reach this spot from their spawn + bool IsBattlefront( void ) const { return m_isBattlefront; } // true if this area is a "battlefront" - where rushing teams initially meet + + //- player counting -------------------------------------------------------------------------------- + void IncrementPlayerCount( int teamID, int entIndex ); // add one player to this area's count + void DecrementPlayerCount( int teamID, int entIndex ); // subtract one player from this area's count + unsigned char GetPlayerCount( int teamID = 0 ) const; // return number of players of given team currently within this area (team of zero means any/all) + + //- lighting ---------------------------------------------------------------------------------------- + float GetLightIntensity( const Vector &pos ) const; // returns a 0..1 light intensity for the given point + float GetLightIntensity( float x, float y ) const; // returns a 0..1 light intensity for the given point + float GetLightIntensity( void ) const; // returns a 0..1 light intensity averaged over the whole area + + //- A* pathfinding algorithm ------------------------------------------------------------------------ + static void MakeNewMarker( void ) { ++m_masterMarker; if (m_masterMarker == 0) m_masterMarker = 1; } + void Mark( void ) { m_marker = m_masterMarker; } + BOOL IsMarked( void ) const { return (m_marker == m_masterMarker) ? true : false; } + + void SetParent( CNavArea *parent, NavTraverseType how = NUM_TRAVERSE_TYPES ) { m_parent = parent; m_parentHow = how; } + CNavArea *GetParent( void ) const { return m_parent; } + NavTraverseType GetParentHow( void ) const { return m_parentHow; } + + bool IsOpen( void ) const; // true if on "open list" + void AddToOpenList( void ); // add to open list in decreasing value order + void AddToOpenListTail( void ); // add to tail of the open list + void UpdateOnOpenList( void ); // a smaller value has been found, update this area on the open list + void RemoveFromOpenList( void ); + static bool IsOpenListEmpty( void ); + static CNavArea *PopOpenList( void ); // remove and return the first element of the open list + + bool IsClosed( void ) const; // true if on "closed list" + void AddToClosedList( void ); // add to the closed list + void RemoveFromClosedList( void ); + + static void ClearSearchLists( void ); // clears the open and closed lists for a new search + + void SetTotalCost( float value ) { Assert( value >= 0.0 && !IS_NAN(value) ); m_totalCost = value; } + float GetTotalCost( void ) const { return m_totalCost; } + + void SetCostSoFar( float value ) { Assert( value >= 0.0 && !IS_NAN(value) ); m_costSoFar = value; } + float GetCostSoFar( void ) const { return m_costSoFar; } + + void SetPathLengthSoFar( float value ) { Assert( value >= 0.0 && !IS_NAN(value) ); m_pathLengthSoFar = value; } + float GetPathLengthSoFar( void ) const { return m_pathLengthSoFar; } + + //- editing ----------------------------------------------------------------------------------------- + virtual void Draw( void ) const; // draw area for debugging & editing + virtual void DrawFilled( int r, int g, int b, int a, float deltaT = 0.1f, bool noDepthTest = true, float margin = 5.0f ) const; // draw area as a filled rect of the given color + virtual void DrawSelectedSet( const Vector &shift ) const; // draw this area as part of a selected set + void DrawDragSelectionSet( Color &dragSelectionSetColor ) const; + void DrawConnectedAreas( void ) const; + void DrawHidingSpots( void ) const; + bool SplitEdit( bool splitAlongX, float splitEdge, CNavArea **outAlpha = NULL, CNavArea **outBeta = NULL ); // split this area into two areas at the given edge + bool MergeEdit( CNavArea *adj ); // merge this area and given adjacent area + bool SpliceEdit( CNavArea *other ); // create a new area between this area and given area + void RaiseCorner( NavCornerType corner, int amount, bool raiseAdjacentCorners = true ); // raise/lower a corner (or all corners if corner == NUM_CORNERS) + void PlaceOnGround( NavCornerType corner, float inset = 0.0f ); // places a corner (or all corners if corner == NUM_CORNERS) on the ground + NavCornerType GetCornerUnderCursor( void ) const; + bool GetCornerHotspot( NavCornerType corner, Vector hotspot[NUM_CORNERS] ) const; // returns true if the corner is under the cursor + void Shift( const Vector &shift ); // shift the nav area + + //- ladders ----------------------------------------------------------------------------------------- + void AddLadderUp( CNavLadder *ladder ); + void AddLadderDown( CNavLadder *ladder ); + + //- generation and analysis ------------------------------------------------------------------------- + virtual void ComputeHidingSpots( void ); // analyze local area neighborhood to find "hiding spots" in this area - for map learning + virtual void ComputeSniperSpots( void ); // analyze local area neighborhood to find "sniper spots" in this area - for map learning + virtual void ComputeSpotEncounters( void ); // compute spot encounter data - for map learning + virtual void ComputeEarliestOccupyTimes( void ); + virtual void CustomAnalysis( bool isIncremental = false ) { } // for game-specific analysis + virtual bool ComputeLighting( void ); // compute 0..1 light intensity at corners and center (requires client via listenserver) + bool TestStairs( void ); // Test an area for being on stairs + virtual bool IsAbleToMergeWith( CNavArea *other ) const; + + virtual void InheritAttributes( CNavArea *first, CNavArea *second = NULL ); + + + //- visibility ------------------------------------------------------------------------------------- + enum VisibilityType + { + NOT_VISIBLE = 0x00, + POTENTIALLY_VISIBLE = 0x01, + COMPLETELY_VISIBLE = 0x02, + }; + + VisibilityType ComputeVisibility( const CNavArea *area, bool isPVSValid, bool bCheckPVS = true, bool *pOutsidePVS = NULL ) const; // do actual line-of-sight traces to determine if any part of given area is visible from this area + void SetupPVS( void ) const; + bool IsInPVS( void ) const; // return true if this area is within the current PVS + + struct AreaBindInfo // for pointer loading and binding + { + union + { + CNavArea *area; + unsigned int id; + }; + + unsigned char attributes; // VisibilityType + + bool operator==( const AreaBindInfo &other ) const + { + return ( area == other.area ); + } + }; + + virtual bool IsEntirelyVisible( const Vector &eye, CBaseEntity *ignore = NULL ) const; // return true if entire area is visible from given eyepoint (CPU intensive) + virtual bool IsPartiallyVisible( const Vector &eye, CBaseEntity *ignore = NULL ) const; // return true if any portion of the area is visible from given eyepoint (CPU intensive) + + virtual bool IsPotentiallyVisible( const CNavArea *area ) const; // return true if given area is potentially visible from somewhere in this area (very fast) + virtual bool IsPotentiallyVisibleToTeam( int team ) const; // return true if any portion of this area is visible to anyone on the given team (very fast) + + virtual bool IsCompletelyVisible( const CNavArea *area ) const; // return true if given area is completely visible from somewhere in this area (very fast) + virtual bool IsCompletelyVisibleToTeam( int team ) const; // return true if given area is completely visible from somewhere in this area by someone on the team (very fast) + + //------------------------------------------------------------------------------------- + /** + * Apply the functor to all navigation areas that are potentially + * visible from this area. + */ + template < typename Functor > + bool ForAllPotentiallyVisibleAreas( Functor &func ) + { + int i; + + ++s_nCurrVisTestCounter; + + for ( i=0; i<m_potentiallyVisibleAreas.Count(); ++i ) + { + CNavArea *area = m_potentiallyVisibleAreas[i].area; + if ( !area ) + continue; + + // If this assertion triggers, an area is in here twice! + Assert( area->m_nVisTestCounter != s_nCurrVisTestCounter ); + area->m_nVisTestCounter = s_nCurrVisTestCounter; + + if ( m_potentiallyVisibleAreas[i].attributes == NOT_VISIBLE ) + continue; + + if ( func( area ) == false ) + return false; + } + + // for each inherited area + if ( !m_inheritVisibilityFrom.area ) + return true; + + CAreaBindInfoArray &inherited = m_inheritVisibilityFrom.area->m_potentiallyVisibleAreas; + + for ( i=0; i<inherited.Count(); ++i ) + { + if ( !inherited[i].area ) + continue; + + // We may have visited this from m_potentiallyVisibleAreas + if ( inherited[i].area->m_nVisTestCounter == s_nCurrVisTestCounter ) + continue; + + // Theoretically, this shouldn't matter. But, just in case! + inherited[i].area->m_nVisTestCounter = s_nCurrVisTestCounter; + + if ( inherited[i].attributes == NOT_VISIBLE ) + continue; + + if ( func( inherited[i].area ) == false ) + return false; + } + + return true; + } + + //------------------------------------------------------------------------------------- + /** + * Apply the functor to all navigation areas that are + * completely visible from somewhere in this area. + */ + template < typename Functor > + bool ForAllCompletelyVisibleAreas( Functor &func ) + { + int i; + + ++s_nCurrVisTestCounter; + + for ( i=0; i<m_potentiallyVisibleAreas.Count(); ++i ) + { + CNavArea *area = m_potentiallyVisibleAreas[i].area; + if ( !area ) + continue; + + // If this assertion triggers, an area is in here twice! + Assert( area->m_nVisTestCounter != s_nCurrVisTestCounter ); + area->m_nVisTestCounter = s_nCurrVisTestCounter; + + if ( ( m_potentiallyVisibleAreas[i].attributes & COMPLETELY_VISIBLE ) == 0 ) + continue; + + if ( func( area ) == false ) + return false; + } + + if ( !m_inheritVisibilityFrom.area ) + return true; + + // for each inherited area + CAreaBindInfoArray &inherited = m_inheritVisibilityFrom.area->m_potentiallyVisibleAreas; + + for ( i=0; i<inherited.Count(); ++i ) + { + if ( !inherited[i].area ) + continue; + + // We may have visited this from m_potentiallyVisibleAreas + if ( inherited[i].area->m_nVisTestCounter == s_nCurrVisTestCounter ) + continue; + + // Theoretically, this shouldn't matter. But, just in case! + inherited[i].area->m_nVisTestCounter = s_nCurrVisTestCounter; + + if ( ( inherited[i].attributes & COMPLETELY_VISIBLE ) == 0 ) + continue; + + if ( func( inherited[i].area ) == false ) + return false; + } + + return true; + } + + +private: + friend class CNavMesh; + friend class CNavLadder; + friend class CCSNavArea; // allow CS load code to complete replace our default load behavior + + static bool m_isReset; // if true, don't bother cleaning up in destructor since everything is going away + + /* + m_nwCorner + nw ne + +-----------+ + | +-->x | + | | | + | v | + | y | + | | + +-----------+ + sw se + m_seCorner + */ + + static unsigned int m_nextID; // used to allocate unique IDs + unsigned int m_id; // unique area ID + unsigned int m_debugid; + + Place m_place; // place descriptor + + CountdownTimer m_blockedTimer; // Throttle checks on our blocked state while blocked + void UpdateBlockedFromNavBlockers( void ); // checks if nav blockers are still blocking the area + + bool m_isUnderwater; // true if the center of the area is underwater + + bool m_isBattlefront; + + float m_avoidanceObstacleHeight; // if nonzero, a prop is obstructing movement through this nav area + CountdownTimer m_avoidanceObstacleTimer; // Throttle checks on our obstructed state while obstructed + + //- for hunting ------------------------------------------------------------------------------------- + float m_clearedTimestamp[ MAX_NAV_TEAMS ]; // time this area was last "cleared" of enemies + + //- "danger" ---------------------------------------------------------------------------------------- + float m_danger[ MAX_NAV_TEAMS ]; // danger of this area, allowing bots to avoid areas where they died in the past - zero is no danger + float m_dangerTimestamp[ MAX_NAV_TEAMS ]; // time when danger value was set - used for decaying + void DecayDanger( void ); + + //- hiding spots ------------------------------------------------------------------------------------ + HidingSpotVector m_hidingSpots; + bool IsHidingSpotCollision( const Vector &pos ) const; // returns true if an existing hiding spot is too close to given position + + //- encounter spots --------------------------------------------------------------------------------- + SpotEncounterVector m_spotEncounters; // list of possible ways to move thru this area, and the spots to look at as we do + void AddSpotEncounters( const CNavArea *from, NavDirType fromDir, const CNavArea *to, NavDirType toDir ); // add spot encounter data when moving from area to area + + float m_earliestOccupyTime[ MAX_NAV_TEAMS ]; // min time to reach this spot from spawn + +#ifdef DEBUG_AREA_PLAYERCOUNTS + CUtlVector< int > m_playerEntIndices[ MAX_NAV_TEAMS ]; +#endif + + //- lighting ---------------------------------------------------------------------------------------- + float m_lightIntensity[ NUM_CORNERS ]; // 0..1 light intensity at corners + + //- A* pathfinding algorithm ------------------------------------------------------------------------ + static unsigned int m_masterMarker; + + static CNavArea *m_openList; + static CNavArea *m_openListTail; + + //- connections to adjacent areas ------------------------------------------------------------------- + NavConnectVector m_incomingConnect[ NUM_DIRECTIONS ]; // a list of adjacent areas for each direction that connect TO us, but we have no connection back to them + + //--------------------------------------------------------------------------------------------------- + CNavNode *m_node[ NUM_CORNERS ]; // nav nodes at each corner of the area + + void ResetNodes( void ); // nodes are going away as part of an incremental nav generation + void Strip( void ); // remove "analyzed" data from nav area + + void FinishMerge( CNavArea *adjArea ); // recompute internal data once nodes have been adjusted during merge + void MergeAdjacentConnections( CNavArea *adjArea ); // for merging with "adjArea" - pick up all of "adjArea"s connections + void AssignNodes( CNavArea *area ); // assign internal nodes to the given area + + void FinishSplitEdit( CNavArea *newArea, NavDirType ignoreEdge ); // given the portion of the original area, update its internal data + + void CalcDebugID(); + +#ifdef NEXT_BOT + CUtlVector< CHandle< CFuncNavPrerequisite > > m_prerequisiteVector; // list of prerequisites that must be met before this area can be traversed +#endif + + CNavArea *m_prevHash, *m_nextHash; // for hash table in CNavMesh + + void ConnectElevators( void ); // find elevator connections between areas + + int m_damagingTickCount; // this area is damaging through this tick count + + + //- visibility -------------------------------------------------------------------------------------- + void ComputeVisibilityToMesh( void ); // compute visibility to surrounding mesh + void ResetPotentiallyVisibleAreas(); + static void ComputeVisToArea( CNavArea *&pOtherArea ); + +#ifndef _X360 + typedef CUtlVectorConservative<AreaBindInfo> CAreaBindInfoArray; // shaves 8 bytes off structure caused by need to support editing +#else + typedef CUtlVector<AreaBindInfo> CAreaBindInfoArray; // Need to use this on 360 to support external allocation pattern +#endif + + AreaBindInfo m_inheritVisibilityFrom; // if non-NULL, m_potentiallyVisibleAreas becomes a list of additions and deletions (NOT_VISIBLE) to the list of this area + CAreaBindInfoArray m_potentiallyVisibleAreas; // list of areas potentially visible from inside this area (after PostLoad(), use area portion of union) + bool m_isInheritedFrom; // latch used during visibility inheritance computation + + const CAreaBindInfoArray &ComputeVisibilityDelta( const CNavArea *other ) const; // return a list of the delta between our visibility list and the given adjacent area + + uint32 m_nVisTestCounter; + static uint32 s_nCurrVisTestCounter; + + CUtlVector< CHandle< CFuncNavCost > > m_funcNavCostVector; // active, overlapping cost entities +}; + +typedef CUtlVector< CNavArea * > NavAreaVector; +extern NavAreaVector TheNavAreas; + + +//-------------------------------------------------------------------------------------------------------------- +//-------------------------------------------------------------------------------------------------------------- +// +// Inlines +// + +#ifdef NEXT_BOT + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::HasPrerequisite( CBaseCombatCharacter *actor ) const +{ + return m_prerequisiteVector.Count() > 0; +} + +//-------------------------------------------------------------------------------------------------------------- +inline const CUtlVector< CHandle< CFuncNavPrerequisite > > &CNavArea::GetPrerequisiteVector( void ) const +{ + return m_prerequisiteVector; +} + +//-------------------------------------------------------------------------------------------------------------- +inline void CNavArea::RemoveAllPrerequisites( void ) +{ + m_prerequisiteVector.RemoveAll(); +} + +//-------------------------------------------------------------------------------------------------------------- +inline void CNavArea::AddPrerequisite( CFuncNavPrerequisite *prereq ) +{ + if ( m_prerequisiteVector.Find( prereq ) == m_prerequisiteVector.InvalidIndex() ) + { + m_prerequisiteVector.AddToTail( prereq ); + } +} +#endif + +//-------------------------------------------------------------------------------------------------------------- +inline float CNavArea::GetDangerDecayRate( void ) const +{ + // one kill == 1.0, which we will forget about in two minutes + return 1.0f / 120.0f; +} + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::IsDegenerate( void ) const +{ + return (m_nwCorner.x >= m_seCorner.x || m_nwCorner.y >= m_seCorner.y); +} + +//-------------------------------------------------------------------------------------------------------------- +inline CNavArea *CNavArea::GetAdjacentArea( NavDirType dir, int i ) const +{ + for( int iter = 0; iter < m_connect[dir].Count(); ++iter ) + { + if (i == 0) + return m_connect[dir][iter].area; + --i; + } + + return NULL; +} + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::IsOpen( void ) const +{ + return (m_openMarker == m_masterMarker) ? true : false; +} + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::IsOpenListEmpty( void ) +{ + Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL ); + return (m_openList) ? false : true; +} + +//-------------------------------------------------------------------------------------------------------------- +inline CNavArea *CNavArea::PopOpenList( void ) +{ + Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL ); + + if ( m_openList ) + { + CNavArea *area = m_openList; + + // disconnect from list + area->RemoveFromOpenList(); + area->m_prevOpen = NULL; + area->m_nextOpen = NULL; + + Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL ); + + return area; + } + + Assert( (m_openList && m_openList->m_prevOpen == NULL) || m_openList == NULL ); + + return NULL; +} + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::IsClosed( void ) const +{ + if (IsMarked() && !IsOpen()) + return true; + + return false; +} + +//-------------------------------------------------------------------------------------------------------------- +inline void CNavArea::AddToClosedList( void ) +{ + Mark(); +} + +//-------------------------------------------------------------------------------------------------------------- +inline void CNavArea::RemoveFromClosedList( void ) +{ + // since "closed" is defined as visited (marked) and not on open list, do nothing +} + +//-------------------------------------------------------------------------------------------------------------- +inline void CNavArea::SetClearedTimestamp( int teamID ) +{ + m_clearedTimestamp[ teamID % MAX_NAV_TEAMS ] = gpGlobals->curtime; +} + +//-------------------------------------------------------------------------------------------------------------- +inline float CNavArea::GetClearedTimestamp( int teamID ) const +{ + return m_clearedTimestamp[ teamID % MAX_NAV_TEAMS ]; +} + +//-------------------------------------------------------------------------------------------------------------- +inline float CNavArea::GetEarliestOccupyTime( int teamID ) const +{ + return m_earliestOccupyTime[ teamID % MAX_NAV_TEAMS ]; +} + + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::IsDamaging( void ) const +{ + return ( gpGlobals->tickcount <= m_damagingTickCount ); +} + + +//-------------------------------------------------------------------------------------------------------------- +inline void CNavArea::MarkAsDamaging( float duration ) +{ + m_damagingTickCount = gpGlobals->tickcount + TIME_TO_TICKS( duration ); +} + + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::HasAvoidanceObstacle( float maxObstructionHeight ) const +{ + return m_avoidanceObstacleHeight > maxObstructionHeight; +} + + +//-------------------------------------------------------------------------------------------------------------- +inline float CNavArea::GetAvoidanceObstacleHeight( void ) const +{ + return m_avoidanceObstacleHeight; +} + + +//-------------------------------------------------------------------------------------------------------------- +inline bool CNavArea::IsVisible( const Vector &eye, Vector *visSpot ) const +{ + Vector corner; + trace_t result; + CTraceFilterNoNPCsOrPlayer traceFilter( NULL, COLLISION_GROUP_NONE ); + const float offset = 0.75f * HumanHeight; + + // check center first + UTIL_TraceLine( eye, GetCenter() + Vector( 0, 0, offset ), MASK_BLOCKLOS_AND_NPCS|CONTENTS_IGNORE_NODRAW_OPAQUE, &traceFilter, &result ); + if (result.fraction == 1.0f) + { + // we can see this area + if (visSpot) + { + *visSpot = GetCenter(); + } + return true; + } + + for( int c=0; c<NUM_CORNERS; ++c ) + { + corner = GetCorner( (NavCornerType)c ); + UTIL_TraceLine( eye, corner + Vector( 0, 0, offset ), MASK_BLOCKLOS_AND_NPCS|CONTENTS_IGNORE_NODRAW_OPAQUE, &traceFilter, &result ); + if (result.fraction == 1.0f) + { + // we can see this area + if (visSpot) + { + *visSpot = corner; + } + return true; + } + } + + return false; +} + +#ifndef DEBUG_AREA_PLAYERCOUNTS +inline void CNavArea::IncrementPlayerCount( int teamID, int entIndex ) +{ + teamID = teamID % MAX_NAV_TEAMS; + + if (m_playerCount[ teamID ] == 255) + { + DevMsg( "CNavArea::IncrementPlayerCount: Overflow\n" ); + return; + } + + ++m_playerCount[ teamID ]; +} + +inline void CNavArea::DecrementPlayerCount( int teamID, int entIndex ) +{ + teamID = teamID % MAX_NAV_TEAMS; + + if (m_playerCount[ teamID ] == 0) + { + DevMsg( "CNavArea::IncrementPlayerCount: Underflow\n" ); + return; + } + + --m_playerCount[ teamID ]; +} +#endif // !DEBUG_AREA_PLAYERCOUNTS + +inline unsigned char CNavArea::GetPlayerCount( int teamID ) const +{ + if (teamID) + { + return m_playerCount[ teamID % MAX_NAV_TEAMS ]; + } + + // sum all players + unsigned char total = 0; + for( int i=0; i<MAX_NAV_TEAMS; ++i ) + { + total += m_playerCount[i]; + } + + return total; +} + +//-------------------------------------------------------------------------------------------------------------- +/** +* Return Z of area at (x,y) of 'pos' +* Trilinear interpolation of Z values at quad edges. +* NOTE: pos->z is not used. +*/ +inline float CNavArea::GetZ( const Vector * RESTRICT pos ) const RESTRICT +{ + return GetZ( pos->x, pos->y ); +} + +inline float CNavArea::GetZ( const Vector & pos ) const RESTRICT +{ + return GetZ( pos.x, pos.y ); +} + +//-------------------------------------------------------------------------------------------------------------- +/** +* Return the coordinates of the area's corner. +*/ +inline Vector CNavArea::GetCorner( NavCornerType corner ) const +{ + // @TODO: Confirm compiler does the "right thing" in release builds, or change this function to to take a pointer [2/4/2009 tom] + Vector pos; + + switch( corner ) + { + default: + Assert( false && "GetCorner: Invalid type" ); + case NORTH_WEST: + return m_nwCorner; + + case NORTH_EAST: + pos.x = m_seCorner.x; + pos.y = m_nwCorner.y; + pos.z = m_neZ; + return pos; + + case SOUTH_WEST: + pos.x = m_nwCorner.x; + pos.y = m_seCorner.y; + pos.z = m_swZ; + return pos; + + case SOUTH_EAST: + return m_seCorner; + } +} + + +#endif // _NAV_AREA_H_ |