diff options
Diffstat (limited to 'src/Mobs/Path.h')
| -rw-r--r-- | src/Mobs/Path.h | 86 |
1 files changed, 53 insertions, 33 deletions
diff --git a/src/Mobs/Path.h b/src/Mobs/Path.h index 008722d29..d4ad066e3 100644 --- a/src/Mobs/Path.h +++ b/src/Mobs/Path.h @@ -1,16 +1,13 @@ #pragma once -/* Wanna use the pathfinder? Put this in your header file: - -// Fwd: cPath +/* +// Needed Fwds: cPath enum class ePathFinderStatus; class cPath; - -Put this in your .cpp: -#include "...Path.h" */ +#include "../FastRandom.h" #ifdef COMPILING_PATHFIND_DEBUGGER /* Note: the COMPILING_PATHFIND_DEBUGGER flag is used by Native / WiseOldMan95 to debug this class outside of MCServer. This preprocessor flag is never set when compiling MCServer. */ @@ -23,14 +20,31 @@ Put this in your .cpp: class cChunk; /* Various little structs and classes */ -enum class ePathFinderStatus {CALCULATING, PATH_FOUND, PATH_NOT_FOUND}; -struct cPathCell; // Defined inside Path.cpp +enum class ePathFinderStatus {CALCULATING, PATH_FOUND, PATH_NOT_FOUND, NEARBY_FOUND}; +enum class eCellStatus {OPENLIST, CLOSEDLIST, NOLIST}; +struct cPathCell +{ + Vector3i m_Location; // Location of the cell in the world. + int m_F, m_G, m_H; // F, G, H as defined in regular A*. + eCellStatus m_Status; // Which list is the cell in? Either non, open, or closed. + cPathCell * m_Parent; // Cell's parent, as defined in regular A*. + bool m_IsSolid; // Is the cell an air or a solid? Partial solids are currently considered solids. +}; + + + + + class compareHeuristics { public: bool operator()(cPathCell * & a_V1, cPathCell * & a_V2); }; + + + + class cPath { public: @@ -54,23 +68,32 @@ public: @param a_MaxSteps The maximum steps before giving up. */ cPath( cChunk & a_Chunk, - const Vector3i & a_StartingPoint, const Vector3i & a_EndingPoint, int a_MaxSteps, - double a_BoundingBoxWidth = 1, double a_BoundingBoxHeight = 2, + const Vector3d & a_StartingPoint, const Vector3d & a_EndingPoint, int a_MaxSteps, + double a_BoundingBoxWidth, double a_BoundingBoxHeight, int a_MaxUp = 1, int a_MaxDown = 1 ); /** Destroys the path and frees its memory. */ ~cPath(); - /** Performs part of the path calculation and returns true if the path computation has finished. */ + /** Performs part of the path calculation and returns the appropriate status. + If NEARBY_FOUND is returned, it means that the destination is not reachable, but a nearby destination + is reachable. If the user likes the alternative destination, they can call AcceptNearbyPath to treat the path as found, + and to make consequent calls to step return PATH_FOUND*/ ePathFinderStatus Step(cChunk & a_Chunk); + /** Called after the PathFinder's step returns NEARBY_FOUND. + Changes the PathFinder status from NEARBY_FOUND to PATH_FOUND, returns the nearby destination that + the PathFinder found a path to. */ + Vector3i AcceptNearbyPath(); + /* Point retrieval functions, inlined for performance. */ /** Returns the next point in the path. */ - inline Vector3i GetNextPoint() + inline Vector3d GetNextPoint() { ASSERT(m_Status == ePathFinderStatus::PATH_FOUND); - return m_PathPoints[m_PathPoints.size() - 1 - (++m_CurrentPoint)]; + Vector3i Point = m_PathPoints[m_PathPoints.size() - 1 - (++m_CurrentPoint)]; + return Vector3d(Point.x + m_HalfWidth, Point.y, Point.z + m_HalfWidth); } /** Checks whether this is the last point or not. Never call getnextPoint when this is true. */ inline bool IsLastPoint() @@ -84,34 +107,23 @@ public: return (m_CurrentPoint == 0); } /** Get the point at a_index. Remark: Internally, the indexes are reversed. */ - inline Vector3i GetPoint(size_t a_index) + inline Vector3d GetPoint(size_t a_index) { ASSERT(m_Status == ePathFinderStatus::PATH_FOUND); ASSERT(a_index < m_PathPoints.size()); - return m_PathPoints[m_PathPoints.size() - 1 - a_index]; + Vector3i Point = m_PathPoints[m_PathPoints.size() - 1 - a_index]; + return Vector3d(Point.x + m_HalfWidth, Point.y, Point.z + m_HalfWidth); } /** Returns the total number of points this path has. */ - inline int GetPointCount() + inline size_t GetPointCount() { - ASSERT(m_Status == ePathFinderStatus::PATH_FOUND); + if (m_Status != ePathFinderStatus::PATH_FOUND) + { + return 0; + } return m_PathPoints.size(); } - struct VectorHasher - { - std::size_t operator()(const Vector3i & a_Vector) const - { - // Guaranteed to have no hash collisions for any 128x128x128 area. Suitable for pathfinding. - int32_t t = 0; - t += (int8_t)a_Vector.x; - t = t << 8; - t += (int8_t)a_Vector.y; - t = t << 8; - t += (int8_t)a_Vector.z; - t = t << 8; - return (size_t)t; - } - }; private: /* General */ @@ -119,6 +131,8 @@ private: bool Step_Internal(); // The public version just calls this version * CALCULATIONS_PER_CALL times. void FinishCalculation(); // Clears the memory used for calculating the path. void FinishCalculation(ePathFinderStatus a_NewStatus); // Clears the memory used for calculating the path and changes the status. + void AttemptToFindAlternative(); + void BuildPath(); /* Openlist and closedlist management */ void OpenListAdd(cPathCell * a_Cell); @@ -131,10 +145,15 @@ private: /* Pathfinding fields */ std::priority_queue<cPathCell *, std::vector<cPathCell *>, compareHeuristics> m_OpenList; - std::unordered_map<Vector3i, UniquePtr<cPathCell>, VectorHasher> m_Map; + std::unordered_map<Vector3i, cPathCell, VectorHasher<int>> m_Map; Vector3i m_Destination; Vector3i m_Source; + int m_BoundingBoxWidth; + int m_BoundingBoxHeight; + double m_HalfWidth; int m_StepsLeft; + cPathCell * m_NearestPointToTarget; + cFastRandom m_Rand; /* Control fields */ ePathFinderStatus m_Status; @@ -145,6 +164,7 @@ private: /* Interfacing with the world */ cChunk * m_Chunk; // Only valid inside Step()! + bool m_BadChunkFound; #ifdef COMPILING_PATHFIND_DEBUGGER #include "../path_irrlicht.cpp" #endif |