// Graph.h: interface for the CGraph class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_GRAPH_H__6D059D2E_5A74_4352_B3BF_2C88D446A2E1__INCLUDED_) #define AFX_GRAPH_H__6D059D2E_5A74_4352_B3BF_2C88D446A2E1__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "IAgent.h" #include "Heuristic.h" #include #include #include #ifdef LINUX #include #endif #define BAI_FILE_VERSION 30 struct IRenderer; class CCryFile; #define PATHFINDER_STILLTRACING 0 #define PATHFINDER_WALKINGBACK 1 #define PATHFINDER_BEAUTIFYINGPATH 2 #define PATHFINDER_POPNEWREQUEST 3 #define PATHFINDER_CLEANING_GRAPH 4 #define PATHFINDER_PATHFOUND 10 #define PATHFINDER_NOPATH 11 #define PATHFINDER_ITERATIONS 30 class CAISystem; struct IStatObj; class ICrySizer; class CAIObject; struct IVisArea; typedef struct NodeDescriptor { int64 id; //AMD Port bool bCreated; int building; GameNodeData data; bool bEntrance; bool bExit; int nObstacles; int obstacle[10]; int pad; //padding to make it aligned to a multiple of 8 byte, be careful when changing it } NodeDescriptor; typedef std::list ListNodes; typedef std::vector VectorNodes; typedef struct NodeWithHistory { GraphNode *pNode; ListNodes lstParents; } NodeWithHistory; typedef struct LinkDescriptor { int64 nSourceNode; //AMD Port int64 nTargetNode; float fMaxPassRadius; char nStartIndex,nEndIndex; Vec3d vEdgeCenter; Vec3d vWayOut; } LinkDescriptor; class CHeuristic; typedef std::multimap CandidateMap; typedef std::multimap CandidateHistoryMap; // NOTE: INT_PTR here avoids a tiny performance impact on 32-bit platform // for the cost of loss of full compatibility: 64-bit generated BAI files // can't be used on 32-bit platform safely. Change the key to int64 to // make it fully compatible. The code that uses this map will be recompiled // to use the full 64-bit key on both 32-bit and 64-bit platforms. typedef std::multimap EntranceMap; typedef std::list ListPositions; typedef std::list ListObstacles; typedef std::list::iterator graphnodeit; typedef std::vector NodeBuffer; typedef std::vector NodeMemory; typedef std::vector LinkBuffer; typedef std::vector LinkDescBuffer; class CGraph : public IGraph { protected: int m_nAStarDistance; GraphNode *m_pCurrent; GraphNode *m_pPathfinderCurrent; // GraphNode *m_pFirst; GraphNode *m_pPathBegin; GraphNode *m_pWalkBackCurrent; CHeuristic *m_pHeuristic; CandidateHistoryMap m_mapCandidates; // used by pathfinder CandidateMap m_mapGreedyWalkCandidates; // used by get enclosing VectorNodes m_lstTagTracker; // for quick cleaning of the tag VectorNodes m_lstMarkTracker; // for quick cleaning of the mark ListNodes m_lstDeleteStack; // for non-recursive deletion of the graph (stack emulator) ListNodes m_lstNodeStack; ListNodes m_lstLastPath; NodeBuffer m_vBuffer; LinkBuffer m_vLinks; LinkDescBuffer m_vLinksDesc; EntranceMap m_mapReadNodes; // when the graph is read NodeMemory m_vNodes; Vec3d m_vBBoxMin; Vec3d m_vBBoxMax; CAISystem *m_pAISystem; ListNodes::iterator m_iFirst, m_iSecond, m_iThird; Vec3d m_vBeautifierStart; Vec3d m_vLastIntersection; bool m_bBeautifying; CAIObject* m_pRequester; // the puppet which whant's the path public: void SetRequester( CAIObject* rq) {m_pRequester = rq;} CAIObject* GetRequester( ) { return m_pRequester;} GraphNode * CheckClosest(GraphNode *pCurrent, const Vec3d &pos); void ClearDebugFlag(GraphNode *pNode); int WalkBack(GraphNode *pBegin,GraphNode *pEnd, int &nIterations); int ContinueAStar(GraphNode *pEnd, int &nIterations); bool ClearTags(); int WalkAStar(GraphNode *pBegin, GraphNode *pEnd,int &nIterations); void DEBUG_DrawCenters(GraphNode *pNode, IRenderer *pRenderer,int dist); void GetFieldCenter(Vec3d &pos); void DrawPath(IRenderer *pRenderer); void WriteToFile(const char *pname); void Connect(GraphNode *one, GraphNode *two); void DisableInSphere(const Vec3 &pos,float fRadius); void EnableInSphere(const Vec3 &pos,float fRadius); CGraph(CAISystem *); virtual ~CGraph(); CandidateMap m_lstVisited; // debug map... remove later EntranceMap m_mapEntrances; EntranceMap m_mapExits; GraphNode *m_pFirst; GraphNode *m_pSafeFirst; ListPositions m_lstPath; ListNodes m_lstTrapNodes; ListNodes m_lstSaveStack; ListNodes m_lstCurrentHistory; int nNodes; float m_fDistance; Vec3d m_vRealPathfinderEnd; ListNodes m_lstNodesInsideSphere; ListObstacles m_lstSelected; GraphNode *GetCurrent(); virtual GraphNode *GetEnclosing(const Vec3d &pos, GraphNode *pStart = 0 ,bool bOutsideOnly = false); protected: int GetNodesInSphere(const Vec3 &pos, float fRadius); void DeleteGraph(GraphNode *, int depth); void ClearPath(); void EvaluateNode(GraphNode *pNode,GraphNode *pEnd, GraphNode *pParent); GraphNode * ASTARStep(GraphNode *pBegin, GraphNode *pEnd); void DebugWalk(GraphNode *pNode, const Vec3d &pos); #ifndef __MWERKS__ GraphNode *WriteLine(GraphNode *pNode); #endif private: int m_nTagged; public: void TagNode(GraphNode *pNode); void Disconnect(GraphNode * pDisconnected, bool bDelete = true); // walk that will always produce a result, for indoors void IndoorDebugWalk(GraphNode * pNode, const Vec3d & pos, IVisArea *pArea = 0); // Clears the tags of the graph without time-slicing the operation void ClearTagsNow(void); // Check whether a position is within a node's triangle bool PointInTriangle(const Vec3d & pos, GraphNode * pNode); // uses mark for internal graph operation without disturbing the pathfinder void MarkNode(GraphNode * pNode); public: // clears the marked nodes void ClearMarks(bool bJustClear = false); protected: // iterative function to quickly converge on the target position in the graph GraphNode * GREEDYStep(GraphNode * pBegin, const Vec3d & pos, bool bIndoor = false); public: // adds an entrance for easy traversing later void AddIndoorEntrance(int nBuildingID, GraphNode* pNode, bool bExitOnly = false); // Reads the AI graph from a specified file bool ReadFromFile(const char * szName); // reads all the nodes in a map bool ReadNodes( CCryFile &file ); // defines bounding rectangle of this graph void SetBBox(const Vec3d & min, const Vec3d & max); // how is that for descriptive naming of functions ?? bool OutsideOfBBox(const Vec3d & pos); void FillGreedyMap(GraphNode * pNode, const Vec3d &pos, IVisArea *pTargetArea, bool bStayInArea); bool RemoveEntrance(int nBuildingID, GraphNode * pNode); void RemoveIndoorNodes(void); void REC_RemoveNodes(GraphNode * pNode); GraphNode * CreateNewNode(bool bFromTriangulation = false); void DeleteNode(GraphNode * pNode); int SelectNodesInSphere(const Vec3d & vCenter, float fRadius, GraphNode *pStart = 0); void SelectNodeRecursive(GraphNode* pNode, const Vec3d & vCenter, float fRadius); void SelectNodesRecursiveIndoors(GraphNode * pNode, const Vec3d & vCenter, float fRadius, float fDistance); void AddHidePoint(GraphNode* pOwner, const Vec3d & pos, const Vec3d & dir); void RemoveHidePoint(GraphNode * pOwner, const Vec3d & pos, const Vec3d & dir); void DisconnectUnreachable(void); void DisconnectLink(GraphNode * one, GraphNode * two, bool bOneWay = false); int BeautifyPath(int &nIterations, const Vec3d &start, const Vec3d &end); int BeautifyPathCar(int &nIterations, const Vec3d &start, const Vec3d &end); int BeautifyPathCarOld(int &nIterations, const Vec3d &start, const Vec3d &end); void ResolveLinkData(GraphNode* pOne, GraphNode* pTwo); // merging, optimization stuff typedef std::multimap< float, GraphNode* > NodesList; //****** typedef std::list ObstacleIndexList; int Rearrange( ListNodes& nodesList, const Vec3d& cutStart, const Vec3d& cutEnd ); bool ProcessRearrange( GraphNode *node1, GraphNode *node2, ListNodes& nodesList ); int ProcessRearrange( ListNodes& nodesList, const Vec3d& cutStart, const Vec3d& cutEnd ); // bool ProcessMerge( GraphNode *curNode, ListNodes& nodesList ); int ProcessMegaMerge( ListNodes& nodesList, const Vec3d& cutStart, const Vec3d& cutEnd ); // bool CreateOutline( ListNodes& insideNodes, ListNodes& nodesList, ListPositions& outline); //****** bool CreateOutline( ListNodes& insideNodes, ListNodes& nodesList, ObstacleIndexList& outline); //****** void TriangulateOutline( ListNodes& nodesList, ObstacleIndexList& outline, bool orientation ); bool ProcessMerge( GraphNode *curNode, CGraph::NodesList& ndList ); // GraphNode* CanMerge( GraphNode *curNode, int& curIdxToDelete, int& curIdxToKeep, int& nbrIdxToDelete, int& nbrIdxToKeep ); // bool CanMergeNbr( GraphNode *nbr1, GraphNode *nbr2 ); // GraphNode* DoMerge( GraphNode *node1, GraphNode *node2, int curIdxToDelete, int curIdxToKeep, int nbrIdxToDelete, int nbrIdxToKeep ); void ConnectNodes(ListNodes & lstNodes); void FillGraphNodeData(GraphNode* pNode); size_t MemStats( ); bool DbgCheckList( ListNodes& nodesList ) const; void SetCurrentHeuristic(unsigned int heuristic_type); void ResolveTotalLinkData(void); bool CanReuseLastPath(GraphNode * pBegin); GraphNode * GetThirdNode(const Vec3d & vFirst, const Vec3d & vSecond, const Vec3d & vThird); ListPositions m_DEBUG_outlineListL; ListPositions m_DEBUG_outlineListR; void Reset(void); void FindTrapNodes(GraphNode *pNode, int recCount); GraphNode * GetEntrance(int nBuildingID,const Vec3d &pos); void RemoveDegenerateTriangle(GraphNode * pDegenerate, bool bRecurse = true); void FixDegenerateTriangles(void); }; #endif // !defined(AFX_GRAPH_H__6D059D2E_5A74_4352_B3BF_2C88D446A2E1__INCLUDED_)