pathvalidityinterval.h

Go to the documentation of this file.

/*
* Copyright 2016 Autodesk, Inc. All rights reserved.
* Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
* or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
*/


#pragma once

#include "gwnavruntime/navmesh/identifiers/navtriangleptr.h"
#include "gwnavruntime/navmesh/traverselogic.h"
#include "gwnavruntime/path/patheventlist.h"
#include "gwnavruntime/path/positiononpath.h"
#include "gwnavruntime/queries/raycastquery.h"
#include "gwnavruntime/queries/trianglefromposquery.h"
#include "gwnavruntime/queries/raycangoonsegmentquery.h"
#include "gwnavruntime/queries/raycastonsegmentquery.h"
#include "gwnavruntime/navgraph/navgraphlink.h"
#include "gwnavruntime/channel/channelsectionptr.h"
#include "gwnavruntime/queries/utils/triangleintersector.h"
#include "gwnavruntime/queries/utils/convexquadintersector.h"
#include "gwnavruntime/queries/utils/polygonintersector.h"
#include "gwnavruntime/queries/utils/breadthfirstsearchedgecollisionvisitor.h"
#include "gwnavruntime/queries/utils/breadthfirstsearchtraversal.h"

namespace Kaim
{

class LivePath;


enum UpperBoundType
{
    UpperBoundType_PathLastNode = 0,    // UpperBound is the last node of the Path
    UpperBoundType_ValidityUpperBound,  // UpperBound is the upper limit of the validity interval, Path is known to be invalid after it
    UpperBoundType_PathInvalid,         // Whole Path is considered invalid, no UpperBound
    UpperBoundType_Temporary,           // UpperBound is at a temporary position, validity after it is unknown but will be validated further in next frames
    UpperBoundType_NoPath               // No path, no UpperBound
};

enum PathValidityStatus
{
    PathValidityStatus_NoPath = 0,

    PathIsValid,

    ValidityIntervalMustBeRecomputed,

    ValidityIsBeingChecked,

    Dirty_ProgressInvalid,

    Dirty_InvalidBeforeProgress_ProcessingAfter,

    Dirty_InvalidBeforeProgress_ValidAfter,

    Dirty_ValidBeforeProgress_InvalidAfter,

    Dirty_InvalidBeforeAndAfterProgress
};


inline const char* ToString(PathValidityStatus e)
{
    static const char* s_strs[] =
    {
        "PathValidityStatus_NoPath",
        "PathIsValid",
        "ValidityIntervalMustBeRecomputed",
        "ValidityIsBeingChecked",
        "Dirty_ProgressInvalid",
        "Dirty_InvalidBeforeProgress_ProcessingAfter",
        "Dirty_InvalidBeforeProgress_ValidAfter",
        "Dirty_ValidBeforeProgress_InvalidAfter",
        "Dirty_InvalidBeforeAndAfterProgress"
    };
    const KyInt32 enumCount = Dirty_InvalidBeforeAndAfterProgress + 1;
    KY_COMPILER_ASSERT(enumCount == sizeof(s_strs) / sizeof(const char*));
    KyInt32 idx = (KyInt32)e;
    return idx >= 0 && idx < enumCount ? s_strs[idx] : "PathValidityStatus_UNKNOWN";
}

template <class OSTREAM>
inline OSTREAM& operator<<(OSTREAM& os, PathValidityStatus e) { os << ToString(e); return os; }



class PathValidityInterval
{
public:
    // ------------------------------ Functions -----------------------------

    PathValidityInterval();
    ~PathValidityInterval();
    void Clear();
    void ClearBounds();
    void ClearBoundsAndEventList();

    UpperBoundType GetUpperBoundType() const;
    PathValidityStatus GetPathValidityStatus() const;

    void SetPathValidityStatus(PathValidityStatus status);

    template<class TraverseLogic>
    KyResult ReStartIntervalComputation(Path* path, void* traverseLogicUserData, const PositionOnPath& targetOnPath,
        KyFloat32 minDistanceFromTargetOnPathBackward, KyFloat32 minDistanceFromTargetOnPathForward);

    enum FirstNewIntervalExtendedStatus
    {
        FirstNewIntervalIsNotAnExtension,
        FirstNewIntervalIsAnExtension
    };

    // if minimumDistanceAdvancement is 0, validate until the end of the path
    template<class TraverseLogic>
    KyResult ValidateForward(Path* path, void* traverseLogicUserData,
        FirstNewIntervalExtendedStatus* firstIntervalStatus, KyFloat32 minimumDistanceAdvancement = 0.0f);


private:
    KyResult ValidateTargetOnPath(PositionOnPath& targetOnPath);

    // if minimumdrawBackDistance is 0, validate until the beginning of the path
    template<class TraverseLogic>
    KyResult ValidateBackWard(Path* path, void* traverseLogicUserData, KyFloat32 minimumdrawBackDistance = 0.0f);

    template<class TraverseLogic>
    KyResult TestCanGoToPrevPathNode(Path* path, void* traverseLogicUserData);
    template<class TraverseLogic>
    KyResult TestCanGoToNextPathNode(Path* path, void* traverseLogicUserData, FirstNewIntervalExtendedStatus* firstNewInterval);

    template<class TraverseLogic>
    void FindLastValidPositionForward(Path* path, void* traverseLogicUserData, FirstNewIntervalExtendedStatus* firstNewInterval);
    template<class TraverseLogic>
    void FindLastValidPositionBackward(Path* path, void* traverseLogicUserData);

    template<class TraverseLogic>
    void ValidateNavTagTransitionsBackward(void* traverseLogicUserData, const LogicDoNotUseCanEnterNavTag& navTagType);
    template<class TraverseLogic>
    void ValidateNavTagTransitionsBackward(void* traverseLogicUserData, const LogicDoUseCanEnterNavTag& navTagType);

    template<class TraverseLogic>
    KyResult ValidateNavTagTransitionForward(void* traverseLogicUserData, KyUInt32 firstNewEvent, const LogicDoNotUseCanEnterNavTag& navTagType);
    template<class TraverseLogic>
    KyResult ValidateNavTagTransitionForward(void* traverseLogicUserData, KyUInt32 firstNewEvent,
        const LogicDoUseCanEnterNavTag& navTagType);


    // No need for traverseLogic since we already check navTags going backwards from the targetOnPath
    KyResult BuildEventListFromLowerBoundToUpperBound(Path* path);

    void CreateIntervalForNavTagSubSegment(Path* path, KyUInt32 pathEdgeIdxToMoveOn, FirstNewIntervalExtendedStatus* firstNewInterval)
    {
        CreateIntervalsForNavTagSubsegmentButLast(path, pathEdgeIdxToMoveOn, firstNewInterval);
        const PathEventType lastEventType = GetEventTypeForLastNavTagSubSegment(path, pathEdgeIdxToMoveOn);
        CreateIntervalForLastNavTagSubSegment(path, pathEdgeIdxToMoveOn, lastEventType, firstNewInterval);
        m_needToCheckLastEventForRemoval = (lastEventType == PathEventType_OnNavMeshPathNode);
    }
    void CreateIntervalsForNavTagSubsegmentButLast(Path* path, KyUInt32 pathEdgeIdxToMoveOn, FirstNewIntervalExtendedStatus* firstNewInterval);
    void CreateIntervalForLastNavTagSubSegment(Path* path, KyUInt32 pathEdgeIdxToMoveOn, PathEventType typeOfLastEvent, FirstNewIntervalExtendedStatus* firstNewInterval);
    void CheckIfLastEventShouldBeRemoved(const NavTagSubSegment& incomingNavTagSubSegment, FirstNewIntervalExtendedStatus* firstNewInterval);

    PathEventType GetEventTypeForLastNavTagSubSegment(Path* path, KyUInt32 pathEdgeIdxToMoveOn);
    void CreateIntervalForGraphEdge(Path* path, KyUInt32 pathEdgeIdxToMoveOn);
    void CreateIntervalForOutsideAlongGraphEdge(Path* path, KyUInt32 pathEdgeIdxToMoveOn);
    void CreateIntervalForFromOutsidePathEdge(Path* path, KyUInt32 pathEdgeIdxToMoveOn);
    void CreateIntervalForToOutsidePathEdge(Path* path, KyUInt32 pathEdgeIdxToMoveOn);

    PathEventType GetEventTypeFromLowerBound(Path* path, const PositionOnPath& posOnPath);
    void SetPathEventStatusForLastEvent(PathEventStatusInList status);

    void CreateNewPathEvent(Path* path, KyUInt32 pathEdgeIdxToMoveOn, PathEventType pathEventType, const NavTagPtr& navTagptr);

    template<class TraverseLogic>
    KyResult ValidateChannelSection(void* traverseLogicUserData, Path* path, KyUInt32 edgeIdx);

    template<class TraverseLogic>
    KyResult ValidateChannelSection(void* traverseLogicUserData, Path* path, const ChannelSectionPtr &channelSectionPtr);
    template<class TraverseLogic>
    KyResult ValidateTriangle(void* traverseLogicUserData, Path* path, const Vec3f& a, const Vec3f& b, const Vec3f& c);
    template<class TraverseLogic>
    KyResult ValidateConvexQuad(void* traverseLogicUserData, Path* path, const Vec3f& a, const Vec3f& b, const Vec3f& c, const Vec3f& d);
    template<class TraverseLogic, class EdgeIntersector>
    KyResult PerformBreadthFirstSearchTraversal(void* traverseLogicUserData, Path* path, EdgeIntersector& intersector);

    template<class TraverseLogic>
    KyResult ValidateChannelExtension(void* traverseLogicUserData, Path* path, const KyArray<Vec2f>& polyline);

public: // internal
    PathEventList m_pathEventList;

    PositionOnPath m_upperBound;
    PositionOnPath m_lowerBound;

    NavTrianglePtr m_upperTrianglePtr;
    NavTrianglePtr m_lowerTrianglePtr;

    PathValidityStatus m_pathValidityStatus;

    bool m_needToCheckLastEventForRemoval;
    bool m_needToValidateChannelSections;
};

}

#include "gwnavruntime/path/pathvalidityinterval.inl"