Path.h

Go to the documentation of this file.

#pragma once

/*
// Needed Fwds: cPath
enum class ePathFinderStatus;
class cPath;
*/


#include "../FastRandom.h"
#ifdef COMPILING_PATHFIND_DEBUGGER
    /* Note: the COMPILING_PATHFIND_DEBUGGER flag is used by Native / WiseOldMan95 to debug
    this class outside of Cuberite. This preprocessor flag is never set when compiling Cuberite. */
    #include "PathFinderIrrlicht_Head.h"
#endif

#include <unordered_map>

//fwd: ../Chunk.h
class cChunk;


/* Various little structs and classes */
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 considered solids. If m_IsSpecial is true, this is always true.
    bool m_IsSpecial;  // The cell is special - it acts as "solid" or "air" depending on direction, e.g. door or top of fence.
    BLOCKTYPE m_BlockType;
    NIBBLETYPE m_BlockMeta;
};




class compareHeuristics
{
public:
    bool operator()(cPathCell * & a_V1,  cPathCell * &  a_V2);
};





class cPath
{
public:
    cPath(
        cChunk & a_Chunk,
        const Vector3d & a_StartingPoint, const Vector3d & a_EndingPoint, int a_MaxSteps,
        double a_BoundingBoxWidth, double a_BoundingBoxHeight
    );

    cPath();

    cPath(const cPath & a_other) = delete;
    cPath(cPath && a_other) = delete;

    cPath & operator=(const cPath & a_other) = delete;
    cPath & operator=(cPath && a_other) = delete;

    ePathFinderStatus CalculationStep(cChunk & a_Chunk);

    Vector3i AcceptNearbyPath();

    // Point retrieval functions, inlined for performance:

    inline Vector3d GetNextPoint()
    {
        ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
        ASSERT(m_CurrentPoint < m_PathPoints.size());
        Vector3i Point = m_PathPoints[m_PathPoints.size() - 1 - m_CurrentPoint];
        ++m_CurrentPoint;
        return Vector3d(Point.x + m_HalfWidth, Point.y, Point.z + m_HalfWidth);
    }


    inline bool NoMoreWayPoints() const
    {
        ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
        return (m_CurrentPoint == m_PathPoints.size());
    }

    inline bool IsFirstPoint() const
    {
        ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
        return (m_CurrentPoint == 0);
    }

    inline bool IsValid() const
    {
        return m_IsValid;
    }

    inline size_t WayPointsLeft() const
    {
        ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
        return m_PathPoints.size() - m_CurrentPoint;
    }




private:

    /* General */
    bool StepOnce();  // 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);
    cPathCell * OpenListPop();
    bool ProcessIfWalkable(const Vector3i & a_Location, cPathCell * a_Source, int a_Cost);

    /* Map management */
    void ProcessCell(cPathCell * a_Cell,  cPathCell * a_Caller,  int a_GDelta);
    cPathCell * GetCell(const Vector3i & a_location);

    /* Pathfinding fields */
    std::priority_queue<cPathCell *,  std::vector<cPathCell *>,  compareHeuristics> m_OpenList;
    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;

    /* Control fields */
    ePathFinderStatus m_Status;
    bool m_IsValid;

    /* Final path fields */
    size_t m_CurrentPoint;
    std::vector<Vector3i> m_PathPoints;

    /* Interfacing with the world */
    void FillCellAttributes(cPathCell & a_Cell);  // Query our hosting world and fill the cell with info
    cChunk * m_Chunk;  // Only valid inside Step()!
    bool m_BadChunkFound;

    /* High level world queries */
    bool IsWalkable(const Vector3i & a_Location, const Vector3i & a_Source);
    bool BodyFitsIn(const Vector3i & a_Location, const Vector3i & a_Source);
    bool BlockTypeIsSpecial(BLOCKTYPE a_Type);
    bool SpecialIsSolidFromThisDirection(BLOCKTYPE a_Type, NIBBLETYPE a_Meta,  const Vector3i & a_Direction);
    bool HasSolidBelow(const Vector3i & a_Location);
    #ifdef COMPILING_PATHFIND_DEBUGGER
    #include "../path_irrlicht.cpp"
    #endif
};