1 /* 2 =========================================================================== 3 Copyright (C) 2000 - 2013, Raven Software, Inc. 4 Copyright (C) 2001 - 2013, Activision, Inc. 5 Copyright (C) 2013 - 2015, OpenJK contributors 6 7 This file is part of the OpenJK source code. 8 9 OpenJK is free software; you can redistribute it and/or modify it 10 under the terms of the GNU General Public License version 2 as 11 published by the Free Software Foundation. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with this program; if not, see <http://www.gnu.org/licenses/>. 20 =========================================================================== 21 */ 22 23 #ifndef __G_NAVIGATOR__ 24 #define __G_NAVIGATOR__ 25 26 #define __NEWCOLLECT 1 27 28 #define _HARD_CONNECT 1 29 30 //Node flags 31 #define NF_ANY 0 32 //#define NF_CLEAR_LOS 0x00000001 33 #define NF_CLEAR_PATH 0x00000002 34 #define NF_RECALC 0x00000004 35 36 //Edge flags 37 #define EFLAG_NONE 0 38 #define EFLAG_BLOCKED 0x00000001 39 #define EFLAG_FAILED 0x00000002 40 41 //Miscellaneous defines 42 #define NODE_NONE -1 43 #define NAV_HEADER_ID INT_ID('J','N','V','5') 44 #define NODE_HEADER_ID INT_ID('N','O','D','E') 45 46 typedef std::multimap<int, int> EdgeMultimap; 47 typedef std::multimap<int, int>::iterator EdgeMultimapIt; 48 49 50 /* 51 ------------------------- 52 CEdge 53 ------------------------- 54 */ 55 56 class CEdge 57 { 58 59 public: 60 61 CEdge( void ); 62 CEdge( int first, int second, int cost ); 63 ~CEdge( void ); 64 65 int m_first; 66 int m_second; 67 int m_cost; 68 }; 69 70 /* 71 ------------------------- 72 CNode 73 ------------------------- 74 */ 75 76 class CNode 77 { 78 typedef struct edge_s 79 { 80 int ID; 81 int cost; 82 unsigned char flags; 83 } edge_t; 84 85 typedef std::vector< edge_t > edge_v; 86 87 public: 88 89 CNode( void ); 90 ~CNode( void ); 91 92 static CNode *Create( vec3_t position, int flags, int radius, int ID ); 93 static CNode *Create( void ); 94 95 void AddEdge( int ID, int cost, int flags = EFLAG_NONE ); 96 void AddRank( int ID, int rank ); 97 98 void Draw( qboolean radius ); 99 GetID(void)100 int GetID( void ) const { return m_ID; } GetPosition(vec3_t position)101 void GetPosition( vec3_t position ) const { if ( position ) VectorCopy( m_position, position ); } 102 GetNumEdges(void)103 int GetNumEdges( void ) const { return m_numEdges; } 104 int GetEdgeNumToNode( int ID ); 105 int GetEdge( int edgeNum ); 106 int GetEdgeCost( int edgeNum ); 107 unsigned char GetEdgeFlags( int edgeNum ); 108 void SetEdgeFlags( int edgeNum, int newFlags ); GetRadius(void)109 int GetRadius( void ) const { return m_radius; } 110 111 void InitRanks( int size ); 112 int GetRank( int ID ); 113 GetFlags(void)114 int GetFlags( void ) const { return m_flags; } AddFlag(int newFlag)115 void AddFlag( int newFlag ) { m_flags |= newFlag; } RemoveFlag(int oldFlag)116 void RemoveFlag( int oldFlag ) { m_flags &= ~oldFlag; } 117 118 int Save( int numNodes, fileHandle_t file ); 119 int Load( int numNodes, fileHandle_t file ); 120 121 protected: 122 123 vec3_t m_position; 124 int m_flags; 125 int m_radius; 126 int m_ID; 127 128 edge_v m_edges; 129 130 int *m_ranks; 131 int m_numEdges; 132 }; 133 134 /* 135 ------------------------- 136 CNavigator 137 ------------------------- 138 */ 139 #define MAX_FAILED_EDGES 32 140 typedef struct failedEdge_e 141 { 142 int startID; 143 int endID; 144 int checkTime; 145 int entID; 146 } failedEdge_t; 147 148 class CNavigator 149 { 150 typedef std::vector < CNode * > node_v; 151 typedef std::list < CEdge > edge_l; 152 153 #if __NEWCOLLECT 154 155 struct nodeList_t 156 { 157 int nodeID; 158 unsigned int distance; 159 }; 160 161 typedef std::list < nodeList_t > nodeChain_l; 162 163 #endif //__NEWCOLLECT 164 165 public: 166 167 CNavigator( void ); 168 ~CNavigator( void ); 169 170 void Init( void ); 171 void Free( void ); 172 173 bool Load( const char *filename, int checksum ); 174 bool Save( const char *filename, int checksum ); 175 176 int AddRawPoint( vec3_t point, int flags, int radius ); 177 void CalculatePaths( bool recalc=false ); 178 179 #if _HARD_CONNECT 180 181 void HardConnect( int first, int second ); 182 183 #endif 184 185 void ShowNodes( void ); 186 void ShowEdges( void ); 187 void ShowPath( int start, int end ); 188 189 int GetNearestNode( gentity_t *ent, int lastID, int flags, int targetID ); 190 191 int GetBestNode( int startID, int endID, int rejectID = NODE_NONE ); 192 193 int GetNodePosition( int nodeID, vec3_t out ); 194 int GetNodeNumEdges( int nodeID ); 195 int GetNodeEdge( int nodeID, int edge ); 196 float GetNodeLeadDistance( int nodeID ); 197 GetNumNodes(void)198 int GetNumNodes( void ) const { return (int)m_nodes.size(); } 199 200 bool Connected( int startID, int endID ); 201 202 unsigned int GetPathCost( int startID, int endID ); 203 unsigned int GetEdgeCost( int startID, int endID ); 204 205 int GetProjectedNode( vec3_t origin, int nodeID ); 206 //MCG Added BEGIN 207 void CheckFailedNodes( gentity_t *ent ); 208 void AddFailedNode( gentity_t *ent, int nodeID ); 209 qboolean NodeFailed( gentity_t *ent, int nodeID ); 210 qboolean NodesAreNeighbors( int startID, int endID ); 211 void ClearFailedEdge( failedEdge_t *failedEdge ); 212 void ClearAllFailedEdges( void ); 213 int EdgeFailed( int startID, int endID ); 214 void AddFailedEdge( int entID, int startID, int endID ); 215 qboolean CheckFailedEdge( failedEdge_t *failedEdge ); 216 void CheckAllFailedEdges( void ); 217 qboolean RouteBlocked( int startID, int testEdgeID, int endID, int rejectRank ); 218 int GetBestNodeAltRoute( int startID, int endID, int *pathCost, int rejectID = NODE_NONE ); 219 int GetBestNodeAltRoute( int startID, int endID, int rejectID = NODE_NONE ); 220 int GetBestPathBetweenEnts( gentity_t *ent, gentity_t *goal, int flags ); 221 int GetNodeRadius( int nodeID ); 222 void CheckBlockedEdges( void ); 223 void ClearCheckedNodes( void ); 224 byte CheckedNode(int wayPoint,int ent); 225 void SetCheckedNode(int wayPoint,int ent,byte value); 226 227 void FlagAllNodes( int newFlag ); 228 229 qboolean pathsCalculated; 230 failedEdge_t failedEdges[MAX_FAILED_EDGES]; 231 232 //MCG Added END 233 234 protected: 235 236 int TestNodePath( gentity_t *ent, int okToHitEntNum, vec3_t position, qboolean includeEnts ); 237 int TestNodeLOS( gentity_t *ent, vec3_t position ); 238 int TestBestFirst( gentity_t *ent, int lastID, int flags ); 239 240 #if __NEWCOLLECT 241 int CollectNearestNodes( vec3_t origin, int radius, int maxCollect, nodeChain_l &nodeChain ); 242 #else 243 int CollectNearestNodes( vec3_t origin, int radius, int maxCollect, int *nodeChain ); 244 #endif //__NEWCOLLECT 245 246 char GetChar( fileHandle_t file ); 247 int GetInt( fileHandle_t file ); 248 float GetFloat( fileHandle_t file ); 249 long GetLong( fileHandle_t file ); 250 251 //void ConnectNodes( void ); 252 void SetEdgeCost( int ID1, int ID2, int cost ); 253 int GetEdgeCost( CNode *first, CNode *second ); 254 void AddNodeEdges( CNode *node, int addDist, edge_l &edgeList, bool *checkedNodes ); 255 256 void CalculatePath( CNode *node ); 257 258 node_v m_nodes; 259 EdgeMultimap m_edgeLookupMap; 260 }; 261 262 ////////////////////////////////////////////////////////////////////// 263 // class Priority Queue 264 ////////////////////////////////////////////////////////////////////// 265 class CPriorityQueue 266 { 267 // CONSTRUCTION /DESTRUCTION 268 //-------------------------------------------------------------- 269 public: CPriorityQueue()270 CPriorityQueue() {}; 271 ~CPriorityQueue(); 272 273 // Functionality 274 //-------------------------------------------------------------- 275 public: 276 CEdge* Pop(); 277 CEdge* Find(int npNum); 278 void Push( CEdge* theEdge ); 279 void Update(CEdge* edge ); 280 bool Empty(); 281 282 283 // DATA 284 //-------------------------------------------------------------- 285 private: 286 std::vector<CEdge*> mHeap; 287 }; 288 289 #endif //__G_NAVIGATOR__ 290