1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */ 2 3 #ifndef QTPFS_NODE_HDR 4 #define QTPFS_NODE_HDR 5 6 #include <vector> 7 #include <fstream> 8 #include <boost/cstdint.hpp> 9 10 #include "PathEnums.hpp" 11 #include "PathDefines.hpp" 12 13 #include "System/float3.h" 14 #include "System/Rectangle.h" 15 16 #ifndef QTPFS_VIRTUAL_NODE_FUNCTIONS 17 #define QTNode INode 18 #endif 19 20 namespace QTPFS { 21 struct NodeLayer; 22 struct INode { 23 public: SetNodeNumberQTPFS::INode24 void SetNodeNumber(unsigned int n) { nodeNumber = n; } SetHeapIndexQTPFS::INode25 void SetHeapIndex(unsigned int n) { heapIndex = n; } GetNodeNumberQTPFS::INode26 unsigned int GetNodeNumber() const { return nodeNumber; } GetHeapIndexQTPFS::INode27 unsigned int GetHeapIndex() const { return heapIndex; } GetHeapPriorityQTPFS::INode28 float GetHeapPriority() const { return GetPathCost(NODE_PATH_COST_F); } 29 operator <QTPFS::INode30 bool operator < (const INode* n) const { return (fCost < n->fCost); } operator >QTPFS::INode31 bool operator > (const INode* n) const { return (fCost > n->fCost); } operator ==QTPFS::INode32 bool operator == (const INode* n) const { return (fCost == n->fCost); } operator <=QTPFS::INode33 bool operator <= (const INode* n) const { return (fCost <= n->fCost); } operator >=QTPFS::INode34 bool operator >= (const INode* n) const { return (fCost >= n->fCost); } 35 36 #ifdef QTPFS_VIRTUAL_NODE_FUNCTIONS 37 virtual void Serialize(std::fstream&, NodeLayer&, unsigned int*, bool) = 0; 38 virtual unsigned int GetNeighbors(const std::vector<INode*>&, std::vector<INode*>&) = 0; 39 virtual const std::vector<INode*>& GetNeighbors(const std::vector<INode*>& v) = 0; 40 virtual bool UpdateNeighborCache(const std::vector<INode*>& nodes) = 0; 41 42 virtual void SetNeighborEdgeTransitionPoint(unsigned int ngbIdx, const float3& point) = 0; 43 virtual const float3& GetNeighborEdgeTransitionPoint(unsigned int ngbIdx) const = 0; 44 #endif 45 46 unsigned int GetNeighborRelation(const INode* ngb) const; 47 unsigned int GetRectangleRelation(const SRectangle& r) const; 48 float GetDistance(const INode* n, unsigned int type) const; 49 float3 GetNeighborEdgeTransitionPoint(const INode* ngb, const float3& pos, float alpha) const; 50 SRectangle ClipRectangle(const SRectangle& r) const; 51 52 #ifdef QTPFS_VIRTUAL_NODE_FUNCTIONS 53 virtual unsigned int xmin() const = 0; 54 virtual unsigned int zmin() const = 0; 55 virtual unsigned int xmax() const = 0; 56 virtual unsigned int zmax() const = 0; 57 virtual unsigned int xmid() const = 0; 58 virtual unsigned int zmid() const = 0; 59 virtual unsigned int xsize() const = 0; 60 virtual unsigned int zsize() const = 0; 61 virtual unsigned int area() const = 0; 62 63 virtual bool AllSquaresAccessible() const = 0; 64 virtual bool AllSquaresImpassable() const = 0; 65 66 virtual void SetMoveCost(float cost) = 0; 67 virtual float GetMoveCost() const = 0; 68 69 virtual void SetSearchState(unsigned int) = 0; 70 virtual unsigned int GetSearchState() const = 0; 71 72 virtual void SetMagicNumber(unsigned int) = 0; 73 virtual unsigned int GetMagicNumber() const = 0; 74 #endif 75 SetPathCostsQTPFS::INode76 void SetPathCosts(float g, float h) { fCost = g + h; gCost = g; hCost = h; } 77 void SetPathCost(unsigned int type, float cost); GetPathCostsQTPFS::INode78 const float* GetPathCosts() const { return &fCost; } 79 float GetPathCost(unsigned int type) const; 80 SetPrevNodeQTPFS::INode81 void SetPrevNode(INode* n) { prevNode = n; } GetPrevNodeQTPFS::INode82 INode* GetPrevNode() { return prevNode; } 83 84 protected: 85 // NOTE: 86 // storing the heap-index is an *UGLY* break of abstraction, 87 // but the only way to keep the cost of resorting acceptable 88 unsigned int nodeNumber; 89 unsigned int heapIndex; 90 91 float fCost; 92 float gCost; 93 float hCost; 94 95 // points back to previous node in path 96 INode* prevNode; 97 98 #ifdef QTPFS_VIRTUAL_NODE_FUNCTIONS 99 }; 100 #endif 101 102 103 104 #ifdef QTPFS_VIRTUAL_NODE_FUNCTIONS 105 struct QTNode: public INode { 106 #endif 107 public: 108 QTNode( 109 const QTNode* parent, 110 unsigned int nn, 111 unsigned int x1, unsigned int z1, 112 unsigned int x2, unsigned int z2 113 ); 114 ~QTNode(); 115 116 static void InitStatic(); 117 118 // NOTE: 119 // root-node identifier is always 0 120 // <i> is a NODE_IDX index in [0, 3] GetChildIDQTPFS::QTNode121 unsigned int GetChildID(unsigned int i) const { return (nodeNumber << 2) + (i + 1); } GetParentIDQTPFS::QTNode122 unsigned int GetParentID() const { return ((nodeNumber - 1) >> 2); } 123 124 boost::uint64_t GetMemFootPrint() const; 125 boost::uint64_t GetCheckSum() const; 126 127 void Delete(); 128 void PreTesselate(NodeLayer& nl, const SRectangle& r, SRectangle& ur); 129 void Tesselate(NodeLayer& nl, const SRectangle& r); 130 void Serialize(std::fstream& fStream, NodeLayer& nodeLayer, unsigned int* streamSize, bool readMode); 131 132 bool IsLeaf() const; 133 bool CanSplit(bool forced) const; 134 135 bool Split(NodeLayer& nl, bool forced); 136 bool Merge(NodeLayer& nl); 137 138 unsigned int GetMaxNumNeighbors() const; 139 unsigned int GetNeighbors(const std::vector<INode*>&, std::vector<INode*>&); 140 const std::vector<INode*>& GetNeighbors(const std::vector<INode*>&); 141 bool UpdateNeighborCache(const std::vector<INode*>& nodes); 142 SetNeighborEdgeTransitionPointQTPFS::QTNode143 void SetNeighborEdgeTransitionPoint(unsigned int ngbIdx, const float3& point) { netpoints[ngbIdx] = point; } GetNeighborEdgeTransitionPointQTPFS::QTNode144 const float3& GetNeighborEdgeTransitionPoint(unsigned int ngbIdx) const { return netpoints[ngbIdx]; } 145 xminQTPFS::QTNode146 unsigned int xmin() const { return (_xminxmax & 0xFFFF); } zminQTPFS::QTNode147 unsigned int zmin() const { return (_zminzmax & 0xFFFF); } xmaxQTPFS::QTNode148 unsigned int xmax() const { return (_xminxmax >> 16); } zmaxQTPFS::QTNode149 unsigned int zmax() const { return (_zminzmax >> 16); } xmidQTPFS::QTNode150 unsigned int xmid() const { return ((xmin() + xmax()) >> 1); } zmidQTPFS::QTNode151 unsigned int zmid() const { return ((zmin() + zmax()) >> 1); } xsizeQTPFS::QTNode152 unsigned int xsize() const { return (xmax() - xmin()); } zsizeQTPFS::QTNode153 unsigned int zsize() const { return (zmax() - zmin()); } depthQTPFS::QTNode154 unsigned int depth() const { return _depth; } areaQTPFS::QTNode155 unsigned int area() const { return (xsize() * zsize()); } 156 157 // true iff this node is fully open (partially open nodes have larger but non-infinite cost) AllSquaresAccessibleQTPFS::QTNode158 bool AllSquaresAccessible() const { return (moveCostAvg < (QTPFS_CLOSED_NODE_COST / float(area()))); } AllSquaresImpassableQTPFS::QTNode159 bool AllSquaresImpassable() const { return (moveCostAvg == QTPFS_POSITIVE_INFINITY); } 160 SetMoveCostQTPFS::QTNode161 void SetMoveCost(float cost) { moveCostAvg = cost; } GetMoveCostQTPFS::QTNode162 float GetMoveCost() const { return moveCostAvg; } 163 SetSearchStateQTPFS::QTNode164 void SetSearchState(unsigned int state) { searchState = state; } GetSearchStateQTPFS::QTNode165 unsigned int GetSearchState() const { return searchState; } 166 SetMagicNumberQTPFS::QTNode167 void SetMagicNumber(unsigned int number) { currMagicNum = number; } GetMagicNumberQTPFS::QTNode168 unsigned int GetMagicNumber() const { return currMagicNum; } 169 MinSizeXQTPFS::QTNode170 static unsigned int MinSizeX() { return MIN_SIZE_X; } MinSizeZQTPFS::QTNode171 static unsigned int MinSizeZ() { return MIN_SIZE_Z; } 172 173 private: 174 bool UpdateMoveCost( 175 const NodeLayer& nl, 176 const SRectangle& r, 177 unsigned int& numNewBinSquares, 178 unsigned int& numDifBinSquares, 179 unsigned int& numClosedSquares, 180 bool& wantSplit, 181 bool& needSplit 182 ); 183 184 static unsigned int MIN_SIZE_X; 185 static unsigned int MIN_SIZE_Z; 186 static unsigned int MAX_DEPTH; 187 188 unsigned int _depth; 189 unsigned int _xminxmax; 190 unsigned int _zminzmax; 191 192 float speedModSum; 193 float speedModAvg; 194 float moveCostAvg; 195 196 unsigned int searchState; 197 unsigned int currMagicNum; 198 unsigned int prevMagicNum; 199 200 std::vector<QTNode*> children; 201 std::vector<INode*> neighbors; 202 203 // NOTE: 204 // these should be float2's, but profiling shows float3's to be *faster* and 205 // float3's are also more convenient to work with (so we take the memory hit) 206 std::vector<float3> netpoints; 207 }; 208 } 209 210 #endif 211 212