DetourNavMeshQuery.h

Go to the documentation of this file.

//
// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
//
// This software is provided 'as-is', without any express or implied
// warranty.  In no event will the authors be held liable for any damages
// arising from the use of this software.
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
// 1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    in a product, an acknowledgment in the product documentation would be
//    appreciated but is not required.
// 2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//

#ifndef DETOURNAVMESHQUERY_H
#define DETOURNAVMESHQUERY_H

#include "DetourNavMesh.h"
#include "DetourStatus.h"


// Define DT_VIRTUAL_QUERYFILTER if you wish to derive a custom filter from dtQueryFilter.
// On certain platforms indirect or virtual function call is expensive. The default
// setting is to use non-virtual functions, the actual implementations of the functions
// are declared as inline for maximum speed. 

//#define DT_VIRTUAL_QUERYFILTER 1

class dtQueryFilter
{
    enum { MAX_AREA_COSTS = 64 };
    navAreaMask     m_costMask[MAX_AREA_COSTS];
    float           m_areaCost[MAX_AREA_COSTS];     
    navAreaMask     m_includeFlags;     
    navAreaMask     m_excludeFlags;     
    
public:
    dtQueryFilter();
    
#ifdef DT_VIRTUAL_QUERYFILTER
    virtual ~dtQueryFilter() { }
#endif
    
#ifdef DT_VIRTUAL_QUERYFILTER
    virtual bool passFilter(const dtPolyRef ref,
                            const dtMeshTile* tile,
                            const dtPoly* poly) const;
#else
    bool passFilter(const dtPolyRef ref,
                    const dtMeshTile* tile,
                    const dtPoly* poly) const;
#endif

#ifdef DT_VIRTUAL_QUERYFILTER
    virtual float getCost(const float* pa, const float* pb,
                          const dtPolyRef prevRef, const dtMeshTile* prevTile, const dtPoly* prevPoly,
                          const dtPolyRef curRef, const dtMeshTile* curTile, const dtPoly* curPoly,
                          const dtPolyRef nextRef, const dtMeshTile* nextTile, const dtPoly* nextPoly) const;
#else
    float getCost(const float* pa, const float* pb,
                  const dtPolyRef prevRef, const dtMeshTile* prevTile, const dtPoly* prevPoly,
                  const dtPolyRef curRef, const dtMeshTile* curTile, const dtPoly* curPoly,
                  const dtPolyRef nextRef, const dtMeshTile* nextTile, const dtPoly* nextPoly) const;
#endif


    inline float getAreaCost( navAreaMask areaMask ) const
    {
        for ( int i = 0; i < MAX_AREA_COSTS; ++i )
        {
            if ( ( m_costMask[ i ] & areaMask ) == areaMask )
            {
                return m_areaCost[ i ];
            }
        }
        return 1.0f;
    }

    inline void setAreaCost( navAreaMask areaMask, const float cost )
    {
        for ( int i = 0; i < MAX_AREA_COSTS; ++i )
        {
            if ( ( m_costMask[ i ] & areaMask ) == areaMask )
            {
                m_areaCost[ i ] = cost;
                return;
            }
        }
        for ( int i = 0; i < MAX_AREA_COSTS; ++i )
        {
            if ( m_costMask[ i ] == 0 )
            {
                m_costMask[ i ] = areaMask;
                m_areaCost[ i ] = cost;
                return;
            }
        }
    }

    inline navAreaMask getIncludeFlags() const { return m_includeFlags; }

    inline void setIncludeFlags(const navAreaMask flags) { m_includeFlags = flags; }

    inline navAreaMask getExcludeFlags() const { return m_excludeFlags; }

    inline void setExcludeFlags(const navAreaMask flags) { m_excludeFlags = flags; }    


};



struct dtRaycastHit
{
    float t; 
    
    float hitNormal[3];

    int hitEdgeIndex;
    
    dtPolyRef* path;
    
    int pathCount;

    int maxPath;

    float pathCost;
};

struct dtMultiPathGoal
{
    float       mDest[ 3 ];
    dtPolyRef   mDestPoly;
    float       mNavDist;
    float       mThreat;

    dtMultiPathGoal();
};

class dtNavMeshQuery
{
public:
    dtNavMeshQuery();
    ~dtNavMeshQuery();
    
    dtStatus init(const dtNavMesh* nav, const int maxNodes);
    
    // /@{

    dtStatus findPath(dtPolyRef startRef, dtPolyRef endRef,
                      const float* startPos, const float* endPos,
                      const dtQueryFilter* filter,
                      dtPolyRef* path, int* pathCount, const int maxPath) const;
    
    dtStatus findStraightPath(const float* startPos, const float* endPos,
                              const dtPolyRef* path, const int pathSize,
                              float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs,
                              int* straightPathCount, const int maxStraightPath, const int options = 0) const;


    dtStatus initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef,
                                const float* startPos, const float* endPos,
                                const dtQueryFilter* filter, const unsigned int options = 0);

    dtStatus updateSlicedFindPath(const int maxIter, int* doneIters);

    dtStatus finalizeSlicedFindPath(dtPolyRef* path, int* pathCount, const int maxPath);
    
    dtStatus finalizeSlicedFindPathPartial(const dtPolyRef* existing, const int existingSize,
                                           dtPolyRef* path, int* pathCount, const int maxPath);


    dtStatus findPolysAroundCircle(dtPolyRef startRef, const float* centerPos, const float radius,
                                   const dtQueryFilter* filter,
                                   dtPolyRef* resultRef, dtPolyRef* resultParent, float* resultCost,
                                   int* resultCount, const int maxResult) const;

    dtStatus findMultiPath( dtPolyRef startRef, const float* startPos, const dtQueryFilter* filter, dtMultiPathGoal* goals, int numGoals ) const;
    
    dtStatus findPolysAroundShape(dtPolyRef startRef, const float* verts, const int nverts,
                                  const dtQueryFilter* filter,
                                  dtPolyRef* resultRef, dtPolyRef* resultParent, float* resultCost,
                                  int* resultCount, const int maxResult) const;
    

    dtStatus findNearestPoly(const float* center, const float* extents,
                             const dtQueryFilter* filter,
                             dtPolyRef* nearestRef, float* nearestPt) const;
    
    dtStatus queryPolygons(const float* center, const float* extents,
                           const dtQueryFilter* filter,
                           dtPolyRef* polys, int* polyCount, const int maxPolys) const;

    dtStatus findLocalNeighbourhood(dtPolyRef startRef, const float* centerPos, const float radius,
                                    const dtQueryFilter* filter,
                                    dtPolyRef* resultRef, dtPolyRef* resultParent,
                                    int* resultCount, const int maxResult) const;

    dtStatus moveAlongSurface(dtPolyRef startRef, const float* startPos, const float* endPos,
                              const dtQueryFilter* filter,
                              float* resultPos, dtPolyRef* visited, int* visitedCount, const int maxVisitedSize) const;
    
    dtStatus raycast(dtPolyRef startRef, const float* startPos, const float* endPos,
                     const dtQueryFilter* filter,
                     float* t, float* hitNormal, dtPolyRef* path, int* pathCount, const int maxPath) const;
    
    dtStatus raycast(dtPolyRef startRef, const float* startPos, const float* endPos,
                     const dtQueryFilter* filter, const unsigned int options,
                     dtRaycastHit* hit, dtPolyRef prevRef = 0) const;


    dtStatus findDistanceToWall(dtPolyRef startRef, const float* centerPos, const float maxRadius,
                                const dtQueryFilter* filter,
                                float* hitDist, float* hitPos, float* hitNormal) const;
    
    dtStatus getPolyWallSegments(dtPolyRef ref, const dtQueryFilter* filter,
                                 float* segmentVerts, dtPolyRef* segmentRefs, int* segmentCount,
                                 const int maxSegments) const;

    dtStatus findRandomPoint(const dtQueryFilter* filter, float (*frand)(),
                             dtPolyRef* randomRef, float* randomPt) const;

    dtStatus findRandomPointInPoly( const dtPolyRef ref, float( *frand )( ), float* randomPt ) const;

    dtStatus findRandomPointAroundCircle(dtPolyRef startRef, const float* centerPos, const float maxRadius,
                                         const dtQueryFilter* filter, float (*frand)(),
                                         dtPolyRef* randomRef, float* randomPt) const;
    
    dtStatus closestPointOnPoly(dtPolyRef ref, const float* pos, float* closest, bool* posOverPoly) const;
    
    dtStatus closestPointOnPolyBoundary(dtPolyRef ref, const float* pos, float* closest) const;
    
    dtStatus getPolyHeight(dtPolyRef ref, const float* pos, float* height) const;


    bool isValidPolyRef(dtPolyRef ref, const dtQueryFilter* filter) const;

    bool isInClosedList(dtPolyRef ref) const;
    
    class dtNodePool* getNodePool() const { return m_nodePool; }
    
    const dtNavMesh* getAttachedNavMesh() const { return m_nav; }

    
private:
    
    dtMeshTile* getNeighbourTileAt(int x, int y, int side) const;

    int queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax, const dtQueryFilter* filter,
                            dtPolyRef* polys, const int maxPolys) const;
    
    dtStatus getPortalPoints(dtPolyRef from, dtPolyRef to, float* left, float* right,
                             unsigned char& fromType, unsigned char& toType) const;
    dtStatus getPortalPoints(dtPolyRef from, const dtPoly* fromPoly, const dtMeshTile* fromTile,
                             dtPolyRef to, const dtPoly* toPoly, const dtMeshTile* toTile,
                             float* left, float* right) const;
    
    dtStatus getEdgeMidPoint(dtPolyRef from, dtPolyRef to, float* mid) const;
    dtStatus getEdgeMidPoint(dtPolyRef from, const dtPoly* fromPoly, const dtMeshTile* fromTile,
                             dtPolyRef to, const dtPoly* toPoly, const dtMeshTile* toTile,
                             float* mid) const;
    
    // Appends vertex to a straight path
    dtStatus appendVertex(const float* pos, const unsigned char flags, const dtPolyRef ref,
                          float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs,
                          int* straightPathCount, const int maxStraightPath) const;

    // Appends intermediate portal points to a straight path.
    dtStatus appendPortals(const int startIdx, const int endIdx, const float* endPos, const dtPolyRef* path,
                           float* straightPath, unsigned char* straightPathFlags, dtPolyRef* straightPathRefs,
                           int* straightPathCount, const int maxStraightPath, const int options) const;
    
    const dtNavMesh* m_nav;             

    struct dtQueryData
    {
        dtStatus status;
        struct dtNode* lastBestNode;
        float lastBestNodeCost;
        dtPolyRef startRef, endRef;
        float startPos[3], endPos[3];
        const dtQueryFilter* filter;
        unsigned int options;
        float raycastLimitSqr;
    };
    dtQueryData m_query;                

    class dtNodePool* m_tinyNodePool;   
    class dtNodePool* m_nodePool;       
    class dtNodeQueue* m_openList;      
};

dtNavMeshQuery* dtAllocNavMeshQuery();

void dtFreeNavMeshQuery(dtNavMeshQuery* query);

#endif // DETOURNAVMESHQUERY_H