DetourNavMesh.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
// Modified version of Recast/Detour's source 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 DETOURNAVMESH_H
#define DETOURNAVMESH_H
 
#include "CoreMinimal.h"
#include "Detour/DetourAlloc.h"
#include "Detour/DetourStatus.h"
#include "DetourLargeWorldCoordinates.h"
#include "Logging/LogMacros.h"
 
NAVMESH_API DECLARE_LOG_CATEGORY_EXTERN(LogDetour, Log, All);
 
#if WITH_NAVMESH_SEGMENT_LINKS
NAVMESH_API DECLARE_LOG_CATEGORY_EXTERN(LogSegmentLink, Warning, All);
#endif
 
// Note: If you want to use 64-bit refs, change the types of both dtPolyRef & dtTileRef.
// It is also recommended that you change dtHashRef() to a proper 64-bit hash.
 
#ifndef USE_64BIT_ADDRESS
#define USE_64BIT_ADDRESS 1
#endif
 
#if USE_64BIT_ADDRESS
 
#if defined(__LP64__)
// LP64 (Linux/OS X): UE will define its uint64 type as "unsigned long long" so we need to match this
typedef unsigned long long UEType_uint64;
#else
#include <stdint.h>
typedef uint64_t UEType_uint64;
#endif
 
typedef UEType_uint64 dtPolyRef;
 
typedef UEType_uint64 dtTileRef;
 
typedef UEType_uint64 dtClusterRef;
 
#else
 
typedef unsigned int dtPolyRef;
 
typedef unsigned int dtTileRef;
 
typedef unsigned int dtClusterRef;
 
#endif // USE_64BIT_ADDRESS
 
static const int DT_VERTS_PER_POLYGON = 6;
 
 
//static const int DT_NAVMESH_MAGIC = 'D'<<24 | 'N'<<16 | 'A'<<8 | 'V';
 
static const int DT_NAVMESH_VERSION = 7;
 
static const int DT_NAVMESH_STATE_MAGIC = 'D'<<24 | 'N'<<16 | 'M'<<8 | 'S';
 
static const int DT_NAVMESH_STATE_VERSION = 1;
 
 
static const unsigned short DT_EXT_LINK = 0x8000;
 
inline const unsigned int DT_NULL_LINK = 0xffffffff;
 
static const unsigned char DT_OFFMESH_CON_BIDIR     = 0x01;
static const unsigned char DT_OFFMESH_CON_POINT     = 0x02;     //UE
static const unsigned char DT_OFFMESH_CON_SEGMENT   = 0x04;     //UE
static const unsigned char DT_OFFMESH_CON_CHEAPAREA = 0x08;     //UE
static const unsigned char DT_OFFMESH_CON_GENERATED = 0x10;     //UE
 
static const int DT_MAX_AREAS = 64;
 
//@UE BEGIN
static const int DT_MIN_SALT_BITS = 5;
static const int DT_SALT_BASE = 1;
 
static const int DT_RESOLUTION_COUNT = 3; 
 
#if WITH_NAVMESH_SEGMENT_LINKS
static const int DT_MAX_OFFMESH_SEGMENT_PARTS = 4;
static const int DT_INVALID_SEGMENT_PART = 0xffff;
#endif // WITH_NAVMESH_SEGMENT_LINKS
 
static const unsigned char DT_CONNECTION_INTERNAL = (1 << 7);
static const unsigned char DT_LINK_FLAG_OFFMESH_CON = (1 << 6);
static const unsigned char DT_LINK_FLAG_OFFMESH_CON_BIDIR = (1 << 5);
static const unsigned char DT_LINK_FLAG_OFFMESH_CON_BACKTRACKER = (1 << 4);
static const unsigned char DT_LINK_FLAG_OFFMESH_CON_ENABLED = (1 << 3);
static const unsigned char DT_LINK_FLAG_SIDE_MASK = 7;
 
#if WITH_NAVMESH_CLUSTER_LINKS
static const unsigned char DT_CLINK_VALID_FWD = 0x01;
static const unsigned char DT_CLINK_VALID_BCK = 0x02;
 
static const unsigned int DT_CLINK_FIRST = 0x80000000;
#endif // WITH_NAVMESH_CLUSTER_LINKS
//@UE END
 
//@UE BEGIN Adding support for memory tracking.
struct dtMeshTile;
 
typedef void (dtStatsPostAddTileFunc)(const dtMeshTile& TileAdd);
 
typedef void (dtStatsPreRemoveTileFunc)(const dtMeshTile& tileRemove);
 
NAVMESH_API void dtStatsSetCustom(dtStatsPostAddTileFunc* addFunc, dtStatsPreRemoveTileFunc* removeFunc);
//@UE END Adding support for memory tracking.
 
enum dtTileFlags
{   
    DT_TILE_FREE_DATA = 0x01,                   
};
 
enum dtStraightPathFlags
{
    DT_STRAIGHTPATH_START = 0x01,               
    DT_STRAIGHTPATH_END = 0x02,                 
    DT_STRAIGHTPATH_OFFMESH_CONNECTION = 0x04,  
};
 
enum dtStraightPathOptions
{
    DT_STRAIGHTPATH_AREA_CROSSINGS = 0x01,  
    DT_STRAIGHTPATH_ALL_CROSSINGS = 0x02,   
};
 
enum dtPolyTypes
{
    DT_POLYTYPE_GROUND = 0,
    DT_POLYTYPE_OFFMESH_POINT = 1,
 
    //@UE BEGIN
#if WITH_NAVMESH_SEGMENT_LINKS
    DT_POLYTYPE_OFFMESH_SEGMENT = 2,
#endif // WITH_NAVMESH_SEGMENT_LINKS
    //@UE END
};
 
 
struct dtPoly
{
    unsigned int firstLink;
 
    unsigned short verts[DT_VERTS_PER_POLYGON];
 
    unsigned short neis[DT_VERTS_PER_POLYGON];
 
    unsigned short flags;
 
    unsigned char vertCount;
 
    unsigned char areaAndtype;
 
    inline void setArea(unsigned char a) { areaAndtype = static_cast<unsigned char>((areaAndtype & 0xc0) | (a & 0x3f)); }
 
    inline void setType(unsigned char t) { areaAndtype = static_cast<unsigned char>((areaAndtype & 0x3f) | (t << 6)); }
 
    inline unsigned char getArea() const { return areaAndtype & 0x3f; }
 
    inline unsigned char getType() const { return areaAndtype >> 6; }
};
 
struct dtPolyDetail
{
    unsigned short vertBase;        
    unsigned short triBase;         
    unsigned char vertCount;        
    unsigned char triCount;         
};
 
struct dtLink
{
    dtPolyRef ref;                  
    unsigned int next;              
    unsigned char edge;             
    unsigned char side;             
    unsigned char bmin;             
    unsigned char bmax;             
};
 
struct dtBVNode
{
    unsigned short bmin[3];         
    unsigned short bmax[3];         
    int i;                          
};
 
//@UE BEGIN
#if WITH_NAVMESH_SEGMENT_LINKS
struct dtOffMeshSegmentConnection
{
    dtReal startA[3];               
    dtReal endA[3];                 
    dtReal startB[3];               
    dtReal endB[3];                 
 
    dtReal rad;
 
    unsigned int userId;    
    
    unsigned short firstPoly;
 
    unsigned char npolys;
 
    unsigned char flags;
 
    inline void setFlags(unsigned char conFlags)
    {
        flags = ((conFlags & DT_OFFMESH_CON_BIDIR) ? 0x80 : 0); 
    }
 
    inline bool getBiDirectional() const { return (flags & 0x80) != 0; }
};
#endif // WITH_NAVMESH_SEGMENT_LINKS
//@UE END
 
struct dtOffMeshConnection
{
    dtReal pos[6];
 
    dtReal rad;
 
    //@UE BEGIN
    dtReal height;
    //@UE END
 
    unsigned long long int userId;
 
    unsigned short poly;
 
    unsigned char side;
 
    unsigned char flags;
 
    //@UE BEGIN
    inline void setFlags(unsigned char conTypeFlags)
    {
        flags = ((conTypeFlags & DT_OFFMESH_CON_BIDIR) ? 0x80 : 0) |
                ((conTypeFlags & DT_OFFMESH_CON_CHEAPAREA) ? 0x40 : 0) |
                ((conTypeFlags & DT_OFFMESH_CON_GENERATED) ? 0x20 : 0);
    }
 
    inline bool getBiDirectional() const { return (flags & 0x80) != 0; }
 
    inline bool getSnapToCheapestArea() const { return (flags & 0x40) != 0; }
 
    inline bool getIsGenerated() const { return (flags & 0x20) != 0; }
    //@UE END
};
 
//@UE BEGIN
#if WITH_NAVMESH_CLUSTER_LINKS
struct dtCluster
{
    dtReal center[3];               
    unsigned int firstLink;         
    unsigned int numLinks;          
};
 
struct dtClusterLink
{
    dtClusterRef ref;               
    unsigned int next;              
    unsigned char flags;            
};
#endif // WITH_NAVMESH_CLUSTER_LINKS
//@UE END
 
struct dtMeshHeader
{
    unsigned short version; 
    unsigned short layer;           
 
    unsigned short polyCount;       
    unsigned short vertCount;       
 
    int x;                  
    int y;                  
            
    unsigned short maxLinkCount;        
    unsigned short detailMeshCount;     
    
    unsigned short detailVertCount;
    
    unsigned short detailTriCount;      
    unsigned short bvNodeCount;         
    unsigned short offMeshConCount;     
    unsigned short offMeshBase;         
 
    //@UE BEGIN
#if WITH_NAVMESH_SEGMENT_LINKS
    unsigned short offMeshSegConCount;  
    unsigned short offMeshSegPolyBase;  
    unsigned short offMeshSegVertBase;  
#endif // WITH_NAVMESH_SEGMENT_LINKS
 
#if WITH_NAVMESH_CLUSTER_LINKS
    unsigned short clusterCount;            
#endif // WITH_NAVMESH_CLUSTER_LINKS
 
    unsigned char resolution;           
    //@UE END
 
    // These should be at the bottom, as they are less often used than the rest of the data. The rest will fit in one cache line.
    dtReal bmin[3];             
    dtReal bmax[3];             
};
 
struct dtMeshTile
{
    unsigned int salt;                  
 
    unsigned int linksFreeList;         
    dtMeshHeader* header;               
    dtPoly* polys;                      
    dtReal* verts;                      
    dtLink* links;                      
    dtPolyDetail* detailMeshes;         
    
    dtReal* detailVerts;
 
    unsigned char* detailTris;  
 
    dtBVNode* bvTree;
 
    dtOffMeshConnection* offMeshCons;       
 
    unsigned char* data;                    
    int dataSize;                           
    int flags;                              
    dtMeshTile* next;                       
 
    //@UE BEGIN
#if WITH_NAVMESH_SEGMENT_LINKS
    dtOffMeshSegmentConnection* offMeshSeg;     
#endif // WITH_NAVMESH_SEGMENT_LINKS
 
#if WITH_NAVMESH_CLUSTER_LINKS
    dtCluster* clusters;                        
    unsigned short* polyClusters;               
 
    dtChunkArray<dtClusterLink, DT_ALLOC_PERM_TILE_DYNLINK_CLUSTER> dynamicLinksC; 
#endif // WITH_NAVMESH_CLUSTER_LINKS
 
    dtChunkArray<dtLink, DT_ALLOC_PERM_TILE_DYNLINK_OFFMESH> dynamicLinksO; 
    unsigned int dynamicFreeListO;              
 
#if WITH_NAVMESH_CLUSTER_LINKS
    unsigned int dynamicFreeListC;              
#endif // WITH_NAVMESH_CLUSTER_LINKS
 
    //@UE END
};
 
//@UE BEGIN
struct dtNavMeshResParams
{
    dtReal bvQuantFactor;           
};
//@UE END
 
struct dtNavMeshParams
{
    //@UE BEGIN
    dtReal walkableHeight;          
    dtReal walkableRadius;          
    dtReal walkableClimb;           
 
    dtNavMeshResParams resolutionParams[DT_RESOLUTION_COUNT]; 
    //@UE END
    
    dtReal orig[3];                 
    dtReal tileWidth;               
    dtReal tileHeight;              
    int maxTiles;                   
    int maxPolys;                   
};
 
class dtNavMesh
{
public:
    NAVMESH_API dtNavMesh();
    NAVMESH_API ~dtNavMesh();
 
 
    NAVMESH_API dtStatus init(const dtNavMeshParams* params);
 
    NAVMESH_API dtStatus init(unsigned char* data, const int dataSize, const int flags);
    
    NAVMESH_API const dtNavMeshParams* getParams() const;
 
    NAVMESH_API dtStatus addTile(unsigned char* data, int dataSize, int flags, dtTileRef lastRef, dtTileRef* result);
 
#if WITH_NAVMESH_SEGMENT_LINKS
    NAVMESH_API void processSegmentLinksForTile(dtTileRef tileRef, unsigned int maxSkippedNeighborTiles, dtTileRef* skippedNeighborTiles, unsigned int& numSkippedNeighborTiles);
#endif // WITH_NAVMESH_SEGMENT_LINKS
    
    NAVMESH_API dtStatus removeTile(dtTileRef ref, unsigned char** data, int* dataSize);
 
 
 
    NAVMESH_API void calcTileLoc(const dtReal* pos, int* tx, int* ty) const;
 
 
    NAVMESH_API bool isTileLocInValidRange(const dtReal* pos) const;
 
    NAVMESH_API const dtMeshTile* getTileAt(const int x, const int y, const int layer) const;
 
// @UE BEGIN
    NAVMESH_API int getTileCountAt(const int x, const int y) const;
// @UE END
 
    NAVMESH_API int getTilesAt(const int x, const int y,
                   dtMeshTile const** tiles, const int maxTiles) const;
    
    NAVMESH_API dtTileRef getTileRefAt(int x, int y, int layer) const;
 
    NAVMESH_API dtTileRef getTileRef(const dtMeshTile* tile) const;
 
    NAVMESH_API const dtMeshTile* getTileByRef(dtTileRef ref) const;
 
    NAVMESH_API dtMeshTile* getMutableTileByRef(dtTileRef ref) const;
    
    NAVMESH_API int getMaxTiles() const;
    
    NAVMESH_API const dtMeshTile* getTile(int i) const;
 
    NAVMESH_API dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile** tile, const dtPoly** poly) const;
    
    NAVMESH_API void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile** tile, const dtPoly** poly) const;
 
    NAVMESH_API bool isValidPolyRef(dtPolyRef ref) const;
    
    NAVMESH_API dtPolyRef getPolyRefBase(const dtMeshTile* tile) const;
    
    NAVMESH_API dtClusterRef getClusterRefBase(const dtMeshTile* tile) const;
 
    NAVMESH_API dtStatus getOffMeshConnectionPolyEndPoints(dtPolyRef prevRef, dtPolyRef polyRef, const dtReal* currentPos, dtReal* startPos, dtReal* endPos) const;
 
    NAVMESH_API const dtOffMeshConnection* getOffMeshConnectionByRef(dtPolyRef ref) const;
 
    NAVMESH_API void updateOffMeshConnectionByUserId(unsigned long long int userId, unsigned char newArea, unsigned short newFlags);
 
    //@UE BEGIN
#if WITH_NAVMESH_SEGMENT_LINKS
    NAVMESH_API const dtOffMeshSegmentConnection* getOffMeshSegmentConnectionByRef(dtPolyRef ref) const;
 
    NAVMESH_API void updateOffMeshSegmentConnectionByUserId(unsigned int userId, unsigned char newArea, unsigned short newFlags);
#endif // WITH_NAVMESH_SEGMENT_LINKS
    //@UE END
 
 
 
    NAVMESH_API dtStatus setPolyFlags(dtPolyRef ref, unsigned short flags);
 
    NAVMESH_API dtStatus getPolyFlags(dtPolyRef ref, unsigned short* resultFlags) const;
 
    NAVMESH_API dtStatus setPolyArea(dtPolyRef ref, unsigned char area);
 
    NAVMESH_API dtStatus getPolyArea(dtPolyRef ref, unsigned char* resultArea) const;
 
    NAVMESH_API int getTileStateSize(const dtMeshTile* tile) const;
    
    NAVMESH_API dtStatus storeTileState(const dtMeshTile* tile, unsigned char* data, const int maxDataSize) const;
    
    NAVMESH_API dtStatus restoreTileState(dtMeshTile* tile, const unsigned char* data, const int maxDataSize);
    
 
 
    inline dtPolyRef encodePolyId(unsigned int salt, unsigned int it, unsigned int ip) const
    {
        return ((dtPolyRef)salt << (m_polyBits+m_tileBits)) | ((dtPolyRef)it << m_polyBits) | (dtPolyRef)ip;
    }
    
    inline void decodePolyId(dtPolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip) const
    {
        const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1;
        const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1;
        const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1;
        salt = (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask);
        it = (unsigned int)((ref >> m_polyBits) & tileMask);
        ip = (unsigned int)(ref & polyMask);
    }
 
    inline unsigned int decodePolyIdSalt(dtPolyRef ref) const
    {
        const dtPolyRef saltMask = ((dtPolyRef)1<<m_saltBits)-1;
        return (unsigned int)((ref >> (m_polyBits+m_tileBits)) & saltMask);
    }
    
    inline unsigned int decodePolyIdTile(dtPolyRef ref) const
    {
        const dtPolyRef tileMask = ((dtPolyRef)1<<m_tileBits)-1;
        return (unsigned int)((ref >> m_polyBits) & tileMask);
    }
    
    inline unsigned int decodePolyIdPoly(dtPolyRef ref) const
    {
        const dtPolyRef polyMask = ((dtPolyRef)1<<m_polyBits)-1;
        return (unsigned int)(ref & polyMask);
    }
 
    inline unsigned int decodeClusterIdTile(dtClusterRef ref) const
    {
        return decodePolyIdTile(ref);
    }
 
    //@UE BEGIN 
#if WITH_NAVMESH_CLUSTER_LINKS
    inline unsigned int decodeClusterIdCluster(dtClusterRef ref) const
    {
        return decodePolyIdPoly(ref);
    }
#endif // WITH_NAVMESH_CLUSTER_LINKS
 
    NAVMESH_API void applyWorldOffset(const dtReal* offset);
 
    inline dtLink& getLink(dtMeshTile* tile, unsigned int linkIdx)
    {
        return (linkIdx < (unsigned int)tile->header->maxLinkCount) ? tile->links[linkIdx] : tile->dynamicLinksO[linkIdx - tile->header->maxLinkCount];
    }
 
    inline const dtLink& getLink(const dtMeshTile* tile, unsigned int linkIdx) const
    {
        return (linkIdx < (unsigned int)tile->header->maxLinkCount) ? tile->links[linkIdx] : tile->dynamicLinksO[linkIdx - tile->header->maxLinkCount];
    }
 
#if WITH_NAVMESH_CLUSTER_LINKS
    inline dtClusterLink& getClusterLink(dtMeshTile* tile, unsigned int linkIdx)
    {
        return tile->dynamicLinksC[linkIdx - DT_CLINK_FIRST];
    }
 
    inline const dtClusterLink& getClusterLink(const dtMeshTile* tile, unsigned int linkIdx) const
    {
        return tile->dynamicLinksC[linkIdx - DT_CLINK_FIRST];
    }
#endif // WITH_NAVMESH_CLUSTER_LINKS
 
    NAVMESH_API void linkOffMeshHelper(dtMeshTile* tile0, unsigned int polyIdx0, const dtMeshTile* tile1, unsigned int polyIdx1, unsigned char side, unsigned char edge);
 
    inline bool isEmpty() const
    {
        // has no tile grid set up
        return (m_tileWidth > 0 && m_tileHeight > 0) == false;
    }
 
    inline unsigned int getSaltBits() const
    {
        return m_saltBits;
    }
 
    NAVMESH_API void applyAreaCostOrder(unsigned char* costOrder);
    
    NAVMESH_API int getNeighbourTilesCountAt(const int x, const int y, const int side) const;
 
    bool getNeighbourCoords(const int x, const int y, const int side, int& outX, int& outY) const
    {
        outX = x;
        outY = y;
        switch (side)
        {
        case 0: ++outX; break;
        case 1: ++outX; ++outY; break;
        case 2: ++outY; break;
        case 3: --outX; ++outY; break;
        case 4: --outX; break;
        case 5: --outX; --outY; break;
        case 6: --outY; break;
        case 7: ++outX; --outY; break;
        };
        // @todo we might want to do some validation
        return true;
    }
 
    unsigned int getTileIndex(const dtMeshTile* tile) const
    {
        return (unsigned int)(tile - m_tiles);
    }
    //@UE END
 
    //@UE Begin LWCoords
    dtReal getWalkableHeight() const { return m_params.walkableHeight; }
    dtReal getWalkableRadius() const { return m_params.walkableRadius; }
    dtReal getWalkableClimb() const { return m_params.walkableClimb; }
    dtReal getBVQuantFactor(const unsigned char resolution) const { return m_params.resolutionParams[resolution].bvQuantFactor; }
    //@UE END LWCoords
 
private:
 
    // [UE] result struct for findConnectingPolys
    struct FConnectingPolyData
    {
        dtReal min;
        dtReal max;
        dtPolyRef ref;
    };
 
    NAVMESH_API dtMeshTile* getTile(int i);
 
    NAVMESH_API int getTilesAt(const int x, const int y,
                   dtMeshTile** tiles, const int maxTiles) const;
 
    NAVMESH_API int getNeighbourTilesAt(const int x, const int y, const int side,
                            dtMeshTile** tiles, const int maxTiles) const;
    
    NAVMESH_API int findConnectingPolys(const dtReal* va, const dtReal* vb,
        const dtMeshTile* fromTile, int fromPolyIdx,
        const dtMeshTile* tile, int side,
        dtChunkArray<FConnectingPolyData>& cons) const;
 
    NAVMESH_API void connectIntLinks(dtMeshTile* tile);
    NAVMESH_API void baseOffMeshLinks(dtMeshTile* tile);
 
    NAVMESH_API void connectExtLinks(dtMeshTile* tile, dtMeshTile* target, int side, bool updateCLinks);
    NAVMESH_API void connectExtOffMeshLinks(dtMeshTile* tile, dtMeshTile* target, int side, bool updateCLinks);
    
    NAVMESH_API void unconnectExtLinks(dtMeshTile* tile, dtMeshTile* target);
    
    //@UE BEGIN
#if WITH_NAVMESH_CLUSTER_LINKS
    NAVMESH_API void connectClusterLink(dtMeshTile* tile0, unsigned int cluster0,
                            dtMeshTile* tile1, unsigned int cluster1,
                            unsigned char flags, bool bCheckExisting = true);
    
    NAVMESH_API void unconnectClusterLinks(dtMeshTile* tile, dtMeshTile* target);
#endif // WITH_NAVMESH_CLUSTER_LINKS
    //@UE END
 
    // TODO: These methods are duplicates from dtNavMeshQuery, but are needed for off-mesh connection finding.
    
    NAVMESH_API int queryPolygonsInTile(const dtMeshTile* tile, const dtReal* qmin, const dtReal* qmax,
                            dtPolyRef* polys, const int maxPolys, bool bExcludeUnwalkable = false) const;
    NAVMESH_API dtPolyRef findNearestPolyInTile(const dtMeshTile* tile, const dtReal* center,
                                    const dtReal* extents, dtReal* nearestPt, bool bExcludeUnwalkable = false) const;
    NAVMESH_API dtPolyRef findCheapestNearPolyInTile(const dtMeshTile* tile, const dtReal* center,
                                         const dtReal* extents, dtReal* nearestPt) const;
    NAVMESH_API void closestPointOnPolyInTile(const dtMeshTile* tile, unsigned int ip,
                                  const dtReal* pos, dtReal* closest) const;
 
private:
    NAVMESH_API bool isTileLocInValidRange(const dtReal tx, const dtReal ty) const;
    NAVMESH_API void calcTileLoc(const dtReal* pos, dtReal* tx, dtReal* ty) const;
 
public:
    dtNavMeshParams m_params;           
    dtReal m_orig[3];                   
    dtReal m_tileWidth, m_tileHeight;   
 
    int m_maxTiles;                     
    int m_tileLutSize;                  
    int m_tileLutMask;                  
 
    unsigned char m_areaCostOrder[DT_MAX_AREAS];
 
    dtMeshTile** m_posLookup;           
    dtMeshTile* m_nextFree;             
    dtMeshTile* m_tiles;                
        
    unsigned int m_saltBits;            
    unsigned int m_tileBits;            
    unsigned int m_polyBits;            
};
 
NAVMESH_API dtNavMesh* dtAllocNavMesh();
 
NAVMESH_API void dtFreeNavMesh(dtNavMesh* navmesh);
 
// @UE BEGIN: helper for reading tiles
struct ReadTilesHelper
{
    static const int MaxTiles = 32;
    dtMeshTile* Tiles[MaxTiles];
 
    int NumAllocated;
    dtMeshTile** AllocatedTiles;
 
    ReadTilesHelper() : NumAllocated(0), AllocatedTiles(0) {}
    ~ReadTilesHelper()
    {
        dtFree(AllocatedTiles, DT_ALLOC_TEMP);
    }
 
    dtMeshTile** PrepareArray(int RequestedSize)
    {
        if (RequestedSize < MaxTiles)
        {
            return Tiles;
        }
 
        if (NumAllocated < RequestedSize)
        {
            dtFree(AllocatedTiles, DT_ALLOC_TEMP);
            AllocatedTiles = (dtMeshTile**)dtAlloc(RequestedSize * sizeof(dtMeshTile*), DT_ALLOC_TEMP);
            NumAllocated = AllocatedTiles != nullptr ? RequestedSize : 0;
        }
 
        return AllocatedTiles;
    }
};
// @UE END
 
#endif // DETOURNAVMESH_H
 
 
// This section contains detailed documentation for members that don't have
// a source file. It reduces clutter in the main section of the header.