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
{
        float m_areaCost[DT_MAX_AREAS];         
        unsigned short m_includeFlags;          
        unsigned short m_excludeFlags;          
        
public:
        dtQueryFilter();
        
#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(const int i) const { return m_areaCost[i]; }

        inline void setAreaCost(const int i, const float cost) { m_areaCost[i] = cost; } 

        inline unsigned short getIncludeFlags() const { return m_includeFlags; }

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

        inline unsigned short getExcludeFlags() const { return m_excludeFlags; }

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


};

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;


        dtStatus initSlicedFindPath(dtPolyRef startRef, dtPolyRef endRef,
                                                                const float* startPos, const float* endPos,
                                                                const dtQueryFilter* filter);

        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 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 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 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) 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;
        dtPolyRef findNearestPolyInTile(const dtMeshTile* tile, const float* center, const float* extents,
                                                                        const dtQueryFilter* filter, float* nearestPt) const;
        void closestPointOnPolyInTile(const dtMeshTile* tile, const dtPoly* poly, const float* pos, float* closest) 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;
        
        const dtNavMesh* m_nav;                         

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

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

dtNavMeshQuery* dtAllocNavMeshQuery();

void dtFreeNavMeshQuery(dtNavMeshQuery* query);

#endif // DETOURNAVMESHQUERY_H