DetourNavMesh.h

//
// 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 <AtomsUtils/Globals.h>
#include <AtomsUtils/NavigationMesh/Detour/DetourAlloc.h>
#include <AtomsUtils/NavigationMesh/Detour/DetourStatus.h>
 
namespace AtomsUtils {
 
// 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): unreal will define its uint64 type as "unsigned long long" so we need to match this
typedef unsigned long long Type_uint64;
#else
#include <stdint.h>
typedef uint64_t Type_uint64;
#endif
 
typedef Type_uint64 dtPolyRef;
 
typedef Type_uint64 dtTileRef;
 
typedef Type_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;
 
static 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;
static const unsigned char DT_OFFMESH_CON_SEGMENT = 0x04;
static const unsigned char DT_OFFMESH_CON_CHEAPAREA = 0x08;
 
static const int DT_MAX_AREAS = 64;
 
static const int DT_MIN_SALT_BITS = 5;
static const int DT_SALT_BASE = 1;
 
static const int DT_MAX_OFFMESH_SEGMENT_PARTS = 4;
static const int DT_INVALID_SEGMENT_PART = 0xffff;
 
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;
 
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;
 
 
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,
    DT_POLYTYPE_OFFMESH_SEGMENT = 2,
};
 
enum dtDetailTriEdgeFlags
{
    DT_DETAIL_EDGE_BOUNDARY = 0x01,     
};
 
 
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 = (areaAndtype & 0xc0) | (a & 0x3f); }
 
    inline void setType(unsigned char t) { areaAndtype = (areaAndtype & 0x3f) | (t << 6); }
 
    inline unsigned char getArea() const { return areaAndtype & 0x3f; }
 
    inline unsigned char getType() const { return areaAndtype >> 6; }
};
 
struct dtPolyDetail
{
    unsigned int vertBase;          
    unsigned int 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;                          
};
 
struct dtOffMeshSegmentConnection
{
    float startA[3];                
    float endA[3];                  
    float startB[3];                
    float endB[3];                  
 
    float rad;
 
    float height;
 
    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; }
};
 
struct dtOffMeshConnection
{
    float pos[6];
 
    float rad;      
 
    float height;
 
    unsigned int userId;
 
    unsigned short poly;
 
    unsigned char side;
 
    unsigned char flags;
 
    inline void setFlags(unsigned char conFlags)
    {
        flags = ((conFlags & DT_OFFMESH_CON_BIDIR) ? 0x80 : 0) |
            ((conFlags & DT_OFFMESH_CON_CHEAPAREA) ? 0x40 : 0);
    }
 
    inline bool getBiDirectional() const { return (flags & 0x80) != 0; }
 
    inline bool getSnapToCheapestArea() const { return (flags & 0x40) != 0; }
};
 
struct dtCluster
{
    float center[3];                
    unsigned int firstLink;         
    unsigned int numLinks;          
};
 
struct dtClusterLink
{
    dtClusterRef ref;               
    unsigned int next;              
    unsigned char flags;            
};
 
struct dtMeshHeader
{
    int magic;              
    int version;            
    int x;                  
    int y;                  
    int layer;              
    unsigned int userId;    
    int polyCount;          
    int vertCount;          
    int maxLinkCount;       
    int detailMeshCount;    
    
    int detailVertCount;
    
    int detailTriCount;         
    int bvNodeCount;            
    int offMeshConCount;        
    int offMeshSegConCount;     
    int offMeshBase;            
    int offMeshSegPolyBase;     
    int offMeshSegVertBase;     
    float walkableHeight;       
    float walkableRadius;       
    float walkableClimb;        
    float bmin[3];              
    float bmax[3];              
    
    float bvQuantFactor;
 
    int clusterCount;           
};
 
struct dtMeshTile
{
    unsigned int salt;                  
 
    unsigned int linksFreeList;         
    dtMeshHeader* header;               
    dtPoly* polys;                      
    float* verts;                       
    dtLink* links;                      
    dtPolyDetail* detailMeshes;         
    
    float* detailVerts; 
 
    unsigned char* detailTris;  
 
    dtBVNode* bvTree;
 
    dtOffMeshConnection* offMeshCons;       
    dtOffMeshSegmentConnection* offMeshSeg; 
        
    unsigned char* data;                    
    int dataSize;                           
    int flags;                              
    dtMeshTile* next;                       
 
    dtCluster* clusters;                    
    unsigned short* polyClusters;           
 
    dtChunkArray<dtLink> dynamicLinksO;         
    unsigned int dynamicFreeListO;              
    dtChunkArray<dtClusterLink> dynamicLinksC;  
    unsigned int dynamicFreeListC;              
};
 
struct dtNavMeshParams
{
    float orig[3];                  
    float tileWidth;                
    float tileHeight;               
    int maxTiles;                   
    int maxPolys;                   
};
 
class ATOMSUTILS_EXPORT dtNavMesh
{
public:
    dtNavMesh();
    ~dtNavMesh();
 
 
    dtStatus init(const dtNavMeshParams* params);
 
    dtStatus init(unsigned char* data, const int dataSize, const int flags);
    
    const dtNavMeshParams* getParams() const;
 
    dtStatus addTile(unsigned char* data, int dataSize, int flags, dtTileRef lastRef, dtTileRef* result);
    
    dtStatus removeTile(dtTileRef ref, unsigned char** data, int* dataSize);
 
 
 
    void calcTileLoc(const float* pos, int* tx, int* ty) const;
 
    const dtMeshTile* getTileAt(const int x, const int y, const int layer) const;
 
 
    int getTileCountAt(const int x, const int y) const;
 
 
    int getTilesAt(const int x, const int y,
                   dtMeshTile const** tiles, const int maxTiles) const;
    
    dtTileRef getTileRefAt(int x, int y, int layer) const;
 
    dtTileRef getTileRef(const dtMeshTile* tile) const;
 
    const dtMeshTile* getTileByRef(dtTileRef ref) const;
    
    int getMaxTiles() const;
    
    const dtMeshTile* getTile(int i) const;
 
    dtStatus getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile** tile, const dtPoly** poly) const;
    
    void getTileAndPolyByRefUnsafe(const dtPolyRef ref, const dtMeshTile** tile, const dtPoly** poly) const;
 
    bool isValidPolyRef(dtPolyRef ref) const;
    
    dtPolyRef getPolyRefBase(const dtMeshTile* tile) const;
    
    dtClusterRef getClusterRefBase(const dtMeshTile* tile) const;
 
    dtStatus getOffMeshConnectionPolyEndPoints(dtPolyRef prevRef, dtPolyRef polyRef, const float* currentPos, float* startPos, float* endPos) const;
 
    const dtOffMeshConnection* getOffMeshConnectionByRef(dtPolyRef ref) const;
 
    const dtOffMeshSegmentConnection* getOffMeshSegmentConnectionByRef(dtPolyRef ref) const;
 
    void updateOffMeshConnectionByUserId(unsigned int userId, unsigned char newArea, unsigned short newFlags);
 
    void updateOffMeshSegmentConnectionByUserId(unsigned int userId, unsigned char newArea, unsigned short newFlags);
 
 
 
    dtStatus setPolyFlags(dtPolyRef ref, unsigned short flags);
 
    dtStatus getPolyFlags(dtPolyRef ref, unsigned short* resultFlags) const;
 
    dtStatus setPolyArea(dtPolyRef ref, unsigned char area);
 
    dtStatus getPolyArea(dtPolyRef ref, unsigned char* resultArea) const;
 
    int getTileStateSize(const dtMeshTile* tile) const;
    
    dtStatus storeTileState(const dtMeshTile* tile, unsigned char* data, const int maxDataSize) const;
    
    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);
    }
 
    inline unsigned int decodeClusterIdCluster(dtClusterRef ref) const
    {
        return decodePolyIdPoly(ref);
    }
 
    
    void applyWorldOffset(const float* 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];
    }
 
    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];
    }
 
    void linkOffMeshHelper(dtMeshTile* tile0, unsigned int polyIdx0, 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;
    }
 
    void applyAreaCostOrder(unsigned char* costOrder);
    
    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);
    }
    
public:
 
    //  result struct for findConnectingPolys
    struct FConnectingPolyData
    {
        float min;
        float max;
        dtPolyRef ref;
    };
 
    dtMeshTile* getTile(int i);
 
    int getTilesAt(const int x, const int y,
                   dtMeshTile** tiles, const int maxTiles) const;
 
    int getNeighbourTilesAt(const int x, const int y, const int side,
                            dtMeshTile** tiles, const int maxTiles) const;
    
    int findConnectingPolys(const float* va, const float* vb,
        const dtMeshTile* fromTile, int fromPolyIdx,
        const dtMeshTile* tile, int side,
        dtChunkArray<FConnectingPolyData>& cons) const;
 
    void connectIntLinks(dtMeshTile* tile);
    void baseOffMeshLinks(dtMeshTile* tile);
 
    void connectExtLinks(dtMeshTile* tile, dtMeshTile* target, int side, bool updateCLinks);
    void connectExtOffMeshLinks(dtMeshTile* tile, dtMeshTile* target, int side, bool updateCLinks);
    
    void unconnectExtLinks(dtMeshTile* tile, dtMeshTile* target);
    
    void connectClusterLink(dtMeshTile* tile0, unsigned int cluster0,
                            dtMeshTile* tile1, unsigned int cluster1,
                            unsigned char flags, bool bCheckExisting = true);
    
    void unconnectClusterLinks(dtMeshTile* tile, dtMeshTile* target);
 
    // TODO: These methods are duplicates from dtNavMeshQuery, but are needed for off-mesh connection finding.
    
    int queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax,
                            dtPolyRef* polys, const int maxPolys, bool bExcludeUnwalkable = false) const;
    dtPolyRef findNearestPolyInTile(const dtMeshTile* tile, const float* center,
                                    const float* extents, float* nearestPt, bool bExcludeUnwalkable = false) const;
    dtPolyRef findCheapestNearPolyInTile(const dtMeshTile* tile, const float* center,
                                         const float* extents, float* nearestPt) const;
    void closestPointOnPolyInTile(const dtMeshTile* tile, unsigned int ip,
                                  const float* pos, float* closest) const;
    
    dtNavMeshParams m_params;           
    float m_orig[3];                    
    float 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;            
};
 
ATOMSUTILS_EXPORT dtNavMesh* dtAllocNavMesh();
 
ATOMSUTILS_EXPORT void dtFreeNavMesh(dtNavMesh* navmesh);
 
// 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);
    }
 
    dtMeshTile** PrepareArray(int RequestedSize)
    {
        if (RequestedSize < MaxTiles)
        {
            return Tiles;
        }
 
        if (NumAllocated < RequestedSize)
        {
            dtFree(AllocatedTiles);
            AllocatedTiles = (dtMeshTile**)dtAlloc(RequestedSize * sizeof(dtMeshTile*), DT_ALLOC_TEMP);
            NumAllocated = RequestedSize;
        }
 
        return AllocatedTiles;
    }
};
 
}
 
#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.