BVB Source Codes

CRYENGINE Show NavMesh.h Source code

Return Download CRYENGINE: download NavMesh.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #ifndef __MNM_MESH_GRID_H
  4. #define __MNM_MESH_GRID_H
  5.  
  6. #pragma once
  7.  
  8. #include "MNM.h"
  9. #include "Tile.h"
  10. #include "MNMProfiler.h"
  11.  
  12. #include <CryMath/SimpleHashLookUp.h>
  13. #include <CryCore/Containers/VectorMap.h>
  14.  
  15. #include <CryAISystem/NavigationSystem/MNMNavMesh.h>
  16.  
  17. class OffMeshNavigationManager;
  18.  
  19. namespace MNM
  20. {
  21. struct OffMeshNavigation;
  22. class IslandConnections;
  23.  
  24. ///////////////////////////////////////////////////////////////////////
  25.  
  26. // Heuristics for dangers
  27. enum EWeightCalculationType
  28. {
  29.         eWCT_None = 0,
  30.         eWCT_Range,             // It returns 1 as a weight for the cost if the location to evaluate
  31.                                 //  is in the specific range from the threat, 0 otherwise
  32.         eWCT_InverseDistance,   // It returns the inverse of the distance as a weight for the cost
  33.         eWCT_Direction,         // It returns a value between [0,1] as a weight for the cost in relation of
  34.                                 // how the location to evaluate is in the threat direction. The range is not taken into
  35.                                 // account with this weight calculation type
  36.         eWCT_Last,
  37. };
  38.  
  39. template<EWeightCalculationType WeightType>
  40. struct DangerWeightCalculation
  41. {
  42.         MNM::real_t CalculateWeight(const Vec3& locationToEval, const Vec3& startingLocation, const Vec3& dangerPosition, const float rangeSq) const
  43.         {
  44.                 return MNM::real_t(.0f);
  45.         }
  46. };
  47.  
  48. template<>
  49. struct DangerWeightCalculation<eWCT_InverseDistance>
  50. {
  51.         MNM::real_t CalculateWeight(const Vec3& locationToEval, const Vec3& startingLocation, const Vec3& dangerPosition, const float rangeSq) const
  52.         {
  53.                 // TODO: This is currently not used, but if we see we need it, then we should think to change
  54.                 // the euclidean distance calculation with a faster approximation (Like the one used in the FindWay function)
  55.                 const float distance = (dangerPosition - locationToEval).len();
  56.                 bool isInRange = rangeSq > .0f ? sqr(distance) > rangeSq : true;
  57.                 return isInRange ? MNM::real_t(1 / distance) : MNM::real_t(.0f);
  58.         }
  59. };
  60.  
  61. template<>
  62. struct DangerWeightCalculation<eWCT_Range>
  63. {
  64.         MNM::real_t CalculateWeight(const Vec3& locationToEval, const Vec3& startingLocation, const Vec3& dangerPosition, const float rangeSq) const
  65.         {
  66.                 const Vec3 dangerToLocationDir = locationToEval - dangerPosition;
  67.                 const float weight = static_cast<float>(__fsel(dangerToLocationDir.len2() - rangeSq, 0.0f, 1.0f));
  68.                 return MNM::real_t(weight);
  69.         }
  70. };
  71.  
  72. template<>
  73. struct DangerWeightCalculation<eWCT_Direction>
  74. {
  75.         real_t CalculateWeight(const Vec3& locationToEval, const Vec3& startingLocation, const Vec3& dangerPosition, const float rangeSq) const
  76.         {
  77.                 Vec3 startLocationToNewLocation = (locationToEval - startingLocation);
  78.                 startLocationToNewLocation.NormalizeSafe();
  79.                 Vec3 startLocationToDangerPosition = (dangerPosition - startingLocation);
  80.                 startLocationToDangerPosition.NormalizeSafe();
  81.                 float dotProduct = startLocationToNewLocation.dot(startLocationToDangerPosition);
  82.                 return max(real_t(.0f), real_t(dotProduct));
  83.         }
  84. };
  85.  
  86. struct DangerArea
  87. {
  88.         virtual ~DangerArea() {}
  89.         virtual real_t      GetDangerHeuristicCost(const Vec3& locationToEval, const Vec3& startingLocation) const = 0;
  90.         virtual const Vec3& GetLocation() const = 0;
  91. };
  92. DECLARE_SHARED_POINTERS(DangerArea)
  93.  
  94. template<EWeightCalculationType WeightType>
  95. struct DangerAreaT : public DangerArea
  96. {
  97.         DangerAreaT()
  98.                 : location(ZERO)
  99.                 , effectRangeSq(.0f)
  100.                 , cost(0)
  101.                 , weightCalculator()
  102.         {}
  103.  
  104.         DangerAreaT(const Vec3& _location, const float _effectRange, const uint8 _cost)
  105.                 : location(_location)
  106.                 , effectRangeSq(sqr(_effectRange))
  107.                 , cost(_cost)
  108.                 , weightCalculator()
  109.         {}
  110.  
  111.         virtual real_t GetDangerHeuristicCost(const Vec3& locationToEval, const Vec3& startingLocation) const
  112.         {
  113.                 return real_t(cost) * weightCalculator.CalculateWeight(locationToEval, startingLocation, location, effectRangeSq);
  114.         }
  115.  
  116.         virtual const Vec3& GetLocation() const { return location; }
  117.  
  118. private:
  119.         const Vec3                                location;      // Position of the danger
  120.         const float                               effectRangeSq; // If zero the effect is on the whole level
  121.         const unsigned int                        cost;          // Absolute cost associated with the Danger represented by the DangerAreaT
  122.         const DangerWeightCalculation<WeightType> weightCalculator;
  123. };
  124.  
  125. enum { max_danger_amount = 5, };
  126.  
  127. typedef CryFixedArray<MNM::DangerAreaConstPtr, max_danger_amount> DangerousAreasList;
  128.  
  129. ///////////////////////////////////////////////////////////////////////
  130.  
  131. class CNavMesh : public MNM::INavMesh
  132. {
  133. public:
  134.         enum { x_bits = 11, };   // must add up to a 32 bit - the "tileName"
  135.         enum { y_bits = 11, };
  136.         enum { z_bits = 10, };
  137.  
  138.         enum { max_x = (1 << x_bits) - 1, };
  139.         enum { max_y = (1 << y_bits) - 1, };
  140.         enum { max_z = (1 << z_bits) - 1, };
  141.  
  142.         struct SGridParams
  143.         {
  144.                 SGridParams()
  145.                         : origin(ZERO)
  146.                         , tileSize(16)
  147.                         , tileCount(1024)
  148.                         , voxelSize(0.1f)
  149.                 {
  150.                 }
  151.  
  152.                 Vec3   origin;
  153.                 Vec3i  tileSize;
  154.                 Vec3   voxelSize;
  155.                 uint32 tileCount;
  156.         };
  157.  
  158.         enum { SideCount = 14, };
  159.  
  160.         enum EPredictionType
  161.         {
  162.                 ePredictionType_TriangleCenter = 0,
  163.                 ePredictionType_Advanced,
  164.                 ePredictionType_Latest,
  165.         };
  166.  
  167.         struct WayQueryRequest
  168.         {
  169.                 WayQueryRequest(const IAIPathAgent* pRequester, TriangleID _from, const vector3_t& _fromLocation, TriangleID _to,
  170.                                 const vector3_t& _toLocation, const OffMeshNavigation& _offMeshNavigation, const OffMeshNavigationManager& _offMeshNavigationManager,
  171.                                 const DangerousAreasList& dangerousAreas)
  172.                         : m_from(_from)
  173.                         , m_to(_to)
  174.                         , m_fromLocation(_fromLocation)
  175.                         , m_toLocation(_toLocation)
  176.                         , m_offMeshNavigation(_offMeshNavigation)
  177.                         , m_offMeshNavigationManager(_offMeshNavigationManager)
  178.                         , m_dangerousAreas(dangerousAreas)
  179.                         , m_pRequester(pRequester)
  180.                 {}
  181.  
  182.                 virtual ~WayQueryRequest(){}
  183.  
  184.                 virtual bool                    CanUseOffMeshLink(const OffMeshLinkID linkID, float* costMultiplier) const;
  185.                 bool                            IsPointValidForAgent(const Vec3& pos, uint32 flags) const;
  186.  
  187.                 ILINE const TriangleID          From() const                 { return m_from; }
  188.                 ILINE const TriangleID          To() const                   { return m_to; }
  189.                 ILINE const OffMeshNavigation&  GetOffMeshNavigation() const { return m_offMeshNavigation; }
  190.                 ILINE const DangerousAreasList& GetDangersInfos()            { return m_dangerousAreas; }
  191.                 ILINE const vector3_t&          GetFromLocation() const      { return m_fromLocation; };
  192.                 ILINE const vector3_t&          GetToLocation() const        { return m_toLocation; };
  193.  
  194.         private:
  195.                 const TriangleID                m_from;
  196.                 const TriangleID                m_to;
  197.                 const vector3_t                 m_fromLocation;
  198.                 const vector3_t                 m_toLocation;
  199.                 const OffMeshNavigation&        m_offMeshNavigation;
  200.                 const OffMeshNavigationManager& m_offMeshNavigationManager;
  201.                 DangerousAreasList              m_dangerousAreas;
  202.         protected:
  203.                 const IAIPathAgent*             m_pRequester;
  204.         };
  205.  
  206.         struct WayQueryWorkingSet
  207.         {
  208.                 WayQueryWorkingSet()
  209.                 {
  210.                         nextLinkedTriangles.reserve(32);
  211.                 }
  212.                 typedef std::vector<WayTriangleData> TNextLinkedTriangles;
  213.  
  214.                 void Reset()
  215.                 {
  216.                         aStarOpenList.Reset();
  217.                         nextLinkedTriangles.clear();
  218.                         nextLinkedTriangles.reserve(32);
  219.                 }
  220.  
  221.                 TNextLinkedTriangles nextLinkedTriangles;
  222.                 AStarOpenList        aStarOpenList;
  223.         };
  224.  
  225.         struct WayQueryResult
  226.         {
  227.                 WayQueryResult(const size_t wayMaxSize = 512)
  228.                         : m_wayMaxSize(wayMaxSize)
  229.                         , m_waySize(0)
  230.                 {
  231.                         m_pWayTriData.reset(new WayTriangleData[m_wayMaxSize]);
  232.                 }
  233.  
  234.                 ~WayQueryResult()
  235.                 {
  236.                 }
  237.  
  238.                 void Reset()
  239.                 {
  240.                         m_pWayTriData.reset(new WayTriangleData[m_wayMaxSize]);
  241.                         m_waySize = 0;
  242.                 }
  243.  
  244.                 ILINE WayTriangleData* GetWayData() const               { return m_pWayTriData.get(); }
  245.                 ILINE size_t           GetWaySize() const               { return m_waySize; }
  246.                 ILINE size_t           GetWayMaxSize() const            { return m_wayMaxSize; }
  247.  
  248.                 ILINE void             SetWaySize(const size_t waySize) { m_waySize = waySize; }
  249.  
  250.                 ILINE void             Clear()                          { m_waySize = 0; }
  251.         private:
  252.  
  253.                 std::shared_ptr<WayTriangleData> m_pWayTriData;
  254.                 size_t                           m_wayMaxSize;
  255.                 size_t                           m_waySize;
  256.         };
  257.  
  258.         enum EWayQueryResult
  259.         {
  260.                 eWQR_Continuing = 0,
  261.                 eWQR_Done,
  262.         };
  263.  
  264.         CNavMesh();
  265.         ~CNavMesh();
  266.  
  267.         void                 Init(const SGridParams& params);
  268.  
  269.         static inline size_t ComputeTileName(size_t x, size_t y, size_t z)
  270.         {
  271.                 return (x & ((1 << x_bits) - 1)) |
  272.                        ((y & ((1 << y_bits) - 1)) << x_bits) |
  273.                        ((z & ((1 << z_bits) - 1)) << (x_bits + y_bits));
  274.         }
  275.  
  276.         static inline void ComputeTileXYZ(size_t tileName, size_t& x, size_t& y, size_t& z)
  277.         {
  278.                 x = tileName & ((1 << x_bits) - 1);
  279.                 y = (tileName >> x_bits) & ((1 << y_bits) - 1);
  280.                 z = (tileName >> (x_bits + y_bits)) & ((1 << z_bits) - 1);
  281.         }
  282.  
  283.         size_t     GetTriangles(aabb_t aabb, TriangleID* triangles, size_t maxTriCount, float minIslandArea = 0.f) const;
  284.         TriangleID GetTriangleAt(const vector3_t& location, const real_t verticalDownwardRange, const real_t verticalUpwardRange, float minIslandArea = 0.f) const;
  285.         TriangleID GetClosestTriangle(const vector3_t& location, real_t vrange, real_t hrange, real_t* distance = 0, vector3_t* closest = 0, float minIslandArea = 0.f) const;
  286.  
  287.         TriangleID GetTriangleEdgeAlongLine(const vector3_t& startLocation, const vector3_t& endLocation,
  288.                                             const real_t verticalDownwardRange, const real_t verticalUpwardRange,
  289.                                             vector3_t& hit, float minIslandArea = 0.f) const;
  290.         bool IsTriangleAcceptableForLocation(const vector3_t& location, TriangleID triangleID) const;
  291.  
  292.         bool GetVertices(TriangleID triangleID, vector3_t& v0, vector3_t& v1, vector3_t& v2) const;
  293.         bool GetVertices(TriangleID triangleID, vector3_t* verts) const;
  294.         // Sets a bit in linkedEdges for each edge on this triangle that has a link.
  295.         // Bit 0: v0->v1, Bit 1: v1->v2, Bit 2: v2->v0
  296.         bool          GetLinkedEdges(TriangleID triangleID, size_t& linkedEdges) const;
  297.         bool          GetTriangle(TriangleID triangleID, Tile::STriangle& triangle) const;
  298.  
  299.         bool          PushPointInsideTriangle(const TriangleID triangleID, vector3_t& location, real_t amount) const;
  300.  
  301.         void          IncrementCountOfPathsPassingThroughTriangleId(TriangleID triangleID);
  302.         void          DecrementCountOfPathsPassingThroughTriangleId(TriangleID triangleID);
  303.  
  304.         inline size_t GetTriangleCount() const
  305.         {
  306.                 return m_triangleCount;
  307.         }
  308.  
  309.         void                      AddOffMeshLinkToTile(const TileID tileID, const TriangleID triangleID, const uint16 offMeshIndex);
  310.         void                      UpdateOffMeshLinkForTile(const TileID tileID, const TriangleID triangleID, const uint16 offMeshIndex);
  311.         void                      RemoveOffMeshLinkFromTile(const TileID tileID, const TriangleID triangleID);
  312.  
  313.         CNavMesh::EWayQueryResult FindWay(WayQueryRequest& inputRequest, WayQueryWorkingSet& workingSet, WayQueryResult& result) const;
  314.         real_t                    CalculateHeuristicCostForDangers(const vector3_t& locationToEval, const vector3_t& startingLocation, const Vec3& meshOrigin, const DangerousAreasList& dangersInfos) const;
  315.         void                      PullString(const vector3_t& from, const TriangleID fromTriID, const vector3_t& to, const TriangleID toTriID, vector3_t& middlePoint) const;
  316.  
  317.         struct RayHit
  318.         {
  319.                 TriangleID triangleID;
  320.                 real_t     distance;
  321.                 size_t     edge;
  322.         };
  323.  
  324.         /*
  325.          ********************************************************************************************
  326.            RayCastRequestBase holds the actual request information needed to perform a RayCast request.
  327.            It needs to be constructed through the RayCastRequest that assures the presence of the way.
  328.          ********************************************************************************************
  329.          */
  330.  
  331.         struct RaycastRequestBase
  332.         {
  333.         protected:
  334.                 // This class can't be instantiated directly.
  335.                 // cppcheck-suppress uninitMemberVar
  336.                 RaycastRequestBase(const size_t _maxWayTriCount)
  337.                         : maxWayTriCount(_maxWayTriCount)
  338.                         , way(NULL)
  339.                         , wayTriCount(0)
  340.                 {}
  341.  
  342.         public:
  343.                 RayHit       hit;
  344.                 TriangleID*  way;
  345.                 size_t       wayTriCount;
  346.                 const size_t maxWayTriCount;
  347.         };
  348.  
  349.         template<size_t MaximumNumberOfTrianglesInWay>
  350.         struct RayCastRequest : public RaycastRequestBase
  351.         {
  352.                 RayCastRequest()
  353.                         : RaycastRequestBase(MaximumNumberOfTrianglesInWay)
  354.                 {
  355.                         way = &(wayArray[0]);
  356.                         wayTriCount = 0;
  357.                 }
  358.         private:
  359.                 TriangleID wayArray[MaximumNumberOfTrianglesInWay];
  360.         };
  361.  
  362.         // ********************************************************************************************
  363.  
  364.         enum ERayCastResult
  365.         {
  366.                 eRayCastResult_NoHit = 0,
  367.                 eRayCastResult_Hit,
  368.                 eRayCastResult_RayTooLong,
  369.                 eRayCastResult_Unacceptable,
  370.                 eRayCastResult_InvalidStart,
  371.                 eRayCastResult_InvalidEnd,
  372.         };
  373.  
  374.         ERayCastResult RayCast(const vector3_t& from, TriangleID fromTri, const vector3_t& to, TriangleID toTri,
  375.                                RaycastRequestBase& wayRequest) const;
  376.         ERayCastResult RayCast_new(const vector3_t& from, TriangleID fromTriangleID, const vector3_t& to, TriangleID toTriangleID, RaycastRequestBase& wayRequest) const;
  377.         ERayCastResult RayCast_old(const vector3_t& from, TriangleID fromTri, const vector3_t& to, TriangleID toTri, RaycastRequestBase& wayRequest) const;
  378.  
  379.         TileID         SetTile(size_t x, size_t y, size_t z, STile& tile);
  380.         void           ClearTile(TileID tileID, bool clearNetwork = true);
  381.  
  382.         ILINE void     SetTotalIslands(uint32 totalIslands) { m_islands.resize(totalIslands); }
  383.         ILINE uint32   GetTotalIslands() const              { return m_islands.size(); }
  384.         float          GetIslandArea(StaticIslandID islandID) const;
  385.         float          GetIslandAreaForTriangle(TriangleID triangle) const;
  386.  
  387.         void           CreateNetwork();
  388.         void           ConnectToNetwork(TileID tileID);
  389.  
  390.         inline bool    Empty() const
  391.         {
  392.                 return m_tiles.GetTileCount() == 0;
  393.         }
  394.  
  395.         inline size_t GetTileCount() const
  396.         {
  397.                 return m_tiles.GetTileCount();
  398.         }
  399.  
  400.         TileID GetTileID(size_t x, size_t y, size_t z) const;
  401.         const STile&    GetTile(TileID) const;
  402.         STile&          GetTile(TileID);
  403.         const vector3_t GetTileContainerCoordinates(TileID) const;
  404.  
  405.         void                      Swap(CNavMesh& other);
  406.  
  407.         inline const SGridParams& GetGridParams() const
  408.         {
  409.                 return m_params;
  410.         }
  411.  
  412.         inline void OffsetOrigin(const Vec3& offset)
  413.         {
  414.                 m_params.origin += offset;
  415.         }
  416.  
  417.         void Draw(size_t drawFlags, TileID excludeID = 0) const;
  418.  
  419.         bool CalculateMidEdge(const TriangleID triangleID1, const TriangleID triangleID2, Vec3& result) const;
  420.  
  421.         enum ProfilerTimers
  422.         {
  423.                 NetworkConstruction = 0,
  424.         };
  425.  
  426.         enum ProfilerMemoryUsers
  427.         {
  428.                 TriangleMemory = 0,
  429.                 VertexMemory,
  430.                 BVTreeMemory,
  431.                 LinkMemory,
  432.                 GridMemory,
  433.         };
  434.  
  435.         enum ProfilerStats
  436.         {
  437.                 TileCount = 0,
  438.                 TriangleCount,
  439.                 VertexCount,
  440.                 BVTreeNodeCount,
  441.                 LinkCount,
  442.         };
  443.  
  444.         typedef MNMProfiler<ProfilerMemoryUsers, ProfilerTimers, ProfilerStats> ProfilerType;
  445.         const ProfilerType& GetProfiler() const;
  446.  
  447. #if MNM_USE_EXPORT_INFORMATION
  448.         enum EAccessibilityRequestValue
  449.         {
  450.                 eARNotAccessible = 0,
  451.                 eARAccessible    = 1
  452.         };
  453.  
  454.         struct AccessibilityRequest
  455.         {
  456.                 AccessibilityRequest(TriangleID _fromTriangleId, const OffMeshNavigation& _offMeshNavigation)
  457.                         : fromTriangle(_fromTriangleId)
  458.                         , offMeshNavigation(_offMeshNavigation)
  459.                 {}
  460.                 const TriangleID         fromTriangle;
  461.                 const OffMeshNavigation& offMeshNavigation;
  462.         };
  463.  
  464.         void ResetAccessibility(uint8 accessible);
  465.         void ComputeAccessibility(const AccessibilityRequest& inputRequest);
  466. #endif
  467.  
  468.         void   ResetConnectedIslandsIDs();
  469.         void   ComputeStaticIslandsAndConnections(const NavigationMeshID meshID, const OffMeshNavigationManager& offMeshNavigationManager, MNM::IslandConnections& islandConnections);
  470.  
  471.         TileID GetNeighbourTileID(size_t x, size_t y, size_t z, size_t side) const;
  472.  
  473.         // MNM::INavMesh
  474.         virtual void       GetMeshParams(NavMesh::SParams& outParams) const override;
  475.         virtual TileID     FindTileIDByTileGridCoord(const vector3_t& tileGridCoord) const override;
  476.         virtual size_t     QueryTriangles(const aabb_t& queryAabbWorld, MNM::NavMesh::IQueryTrianglesFilter* pOptionalFilter, const size_t maxTrianglesCount, TriangleID* pOutTriangles) const override;
  477.         virtual TriangleID FindClosestTriangle(const vector3_t& queryPosWorld, const TriangleID* pCandidateTriangles, const size_t candidateTrianglesCount, vector3_t* pOutClosestPosWorld, float* pOutClosestDistanceSq) const override;
  478.         virtual bool       GetTileData(const TileID tileId, Tile::STileData& outTileData) const override;
  479.         // ~MNM::INavMesh
  480.  
  481. private:
  482.  
  483.         struct Island
  484.         {
  485.                 Island() {}
  486.                 Island(StaticIslandID _id)
  487.                         : id(_id)
  488.                         , area(0.f)
  489.                 {}
  490.  
  491.                 StaticIslandID id;
  492.                 float          area;
  493.         };
  494.  
  495.         Island& GetNewIsland();
  496.         void    QueueIslandConnectionSetup(const StaticIslandID islandID, const TriangleID startingTriangleID, const uint16 offMeshLinkIndex);
  497.         void    ResolvePendingIslandConnectionRequests(const NavigationMeshID meshID, const OffMeshNavigationManager& offMeshNavigationManager, MNM::IslandConnections& islandConnections);
  498.         void    SearchForIslandConnectionsToRefresh(const TileID tileID);
  499.         void    ComputeStaticIslands();
  500.  
  501.         void    PredictNextTriangleEntryPosition(const TriangleID bestNodeTriangleID, const vector3_t& startPosition, const TriangleID nextTriangleID, const unsigned int vertexIndex, const vector3_t& finalLocation, vector3_t& outPosition) const;
  502.  
  503.         //! Filter for QueryTriangles, which accepts all triangles.
  504.         //! Note, that the signature of Check() function is same as IQueryTrianglesFilter::Check(), but it's not virtual.
  505.         //! This way, templated implementation functions can avoid unnecessary checks and virtual calls.
  506.         struct SAcceptAllQueryTrianglesFilter
  507.         {
  508.                 NavMesh::IQueryTrianglesFilter::EResult Check(TriangleID) { return NavMesh::IQueryTrianglesFilter::EResult::Accepted; }
  509.         };
  510.  
  511.         struct SMinIslandAreaQueryTrianglesFilter;
  512.  
  513.         size_t QueryTrianglesNoFilterInternal(const aabb_t& queryAabbWorld, const size_t maxTrianglesCount, TriangleID* pOutTriangles) const;
  514.  
  515.         template<typename TFilter>
  516.         size_t QueryTrianglesWithFilterInternal(const aabb_t& queryAabbWorld, TFilter& filter, const size_t maxTrianglesCount, TriangleID* pOutTriangles) const;
  517.  
  518.         template<typename TFilter>
  519.         size_t     QueryTileTriangles(const TileID tileID, const vector3_t& tileOrigin, const aabb_t& queryAabbWorld, TFilter& filter, const size_t maxTrianglesCount, TriangleID* pOutTriangles) const;
  520.         template<typename TFilter>
  521.         size_t     QueryTileTrianglesLinear(const TileID tileID, const STile& tile, const aabb_t& queryAabbTile, TFilter& filter, const size_t maxTrianglesCount, TriangleID* pOutTriangles) const;
  522.         template<typename TFilter>
  523.         size_t     QueryTileTrianglesBV(const TileID tileID, const STile& tile, const aabb_t& queryAabbTile, TFilter& filter, const size_t maxTrianglesCount, TriangleID* pOutTriangles) const;
  524.  
  525.         TriangleID FindClosestTriangleInternal(const vector3_t& queryPosWorld, const TriangleID* pCandidateTriangles, const size_t candidateTrianglesCount, vector3_t* pOutClosestPosWorld, real_t::unsigned_overflow_type* pOutClosestDistanceSq) const;
  526.  
  527. protected:
  528.         void ComputeAdjacency(size_t x, size_t y, size_t z, const real_t& toleranceSq, STile& tile);
  529.         void ReComputeAdjacency(size_t x, size_t y, size_t z, const real_t& toleranceSq, STile& tile,
  530.                                 size_t side, size_t tx, size_t ty, size_t tz, TileID targetID);
  531.  
  532.         bool           IsLocationInTriangle(const vector3_t& location, const TriangleID triangleID) const;
  533.         typedef VectorMap<TriangleID, TriangleID> RaycastCameFromMap;
  534.         ERayCastResult ReconstructRaycastResult(const TriangleID fromTriangleID, const TriangleID toTriangleID, const RaycastCameFromMap& comeFrom, RaycastRequestBase& raycastRequest) const;
  535.  
  536.         struct TileContainer
  537.         {
  538.                 TileContainer()
  539.                         : x(0)
  540.                         , y(0)
  541.                         , z(0)
  542.                 {
  543.                 }
  544.  
  545.                 uint32 x: x_bits;
  546.                 uint32 y: y_bits;
  547.                 uint32 z: z_bits;
  548.  
  549.                 STile  tile;
  550.         };
  551.  
  552.         // - manages memory used for TileContainer instances in one big block
  553.         // - kind of an optimized std::vector<TileContainer>
  554.         // - free TileContainers are treated as a list of free indexes
  555.         // - the free list and a counter of used elements specify a "high-water" mark such that the free list needs not grow unnecessarily
  556.         class TileContainerArray
  557.         {
  558.         public:
  559.                 TileContainerArray();
  560.  
  561.                 // Custom copy-construction that bypasses the m_tiles[] pointer and its data from the rhs argument.
  562.                 // Objects of this class are currently only copy-constructed in CNavMesh's copy-ctor.
  563.                 // When the assert() in our ctor's body fails, a copy-construction obviously occured in a different situation, and we will have to rethink about the use-cases.
  564.                 TileContainerArray(const TileContainerArray& rhs);
  565.  
  566.                 ~TileContainerArray();
  567.  
  568.                 // called only once (by CNavMesh::Init())
  569.                 void Init(size_t initialTileContainerCount);
  570.  
  571.                 // - allocates a new TileContainer (or re-uses an unused one)
  572.                 // - the returned TileID-1 can then be used as index for operator[]
  573.                 // - never returns a TileID of value 0
  574.                 const TileID AllocateTileContainer();
  575.  
  576.                 // - marks the TileContainer associated with given TileID as unused
  577.                 // - calling this function more than once in a row with the same TileID will fail an assert()
  578.                 void         FreeTileContainer(const TileID tileID);
  579.  
  580.                 const size_t GetTileCount() const;
  581.  
  582.                 // - access a TileContainer by index
  583.                 // - in most cases, you will have a TileID at hand, and must then pass in TileID-1
  584.                 TileContainer&       operator[](size_t index);
  585.                 const TileContainer& operator[](size_t index) const;
  586.  
  587.                 void                 Swap(TileContainerArray& other);
  588.                 void                 UpdateProfiler(ProfilerType& profiler) const;
  589.  
  590. #if DEBUG_MNM_DATA_CONSISTENCY_ENABLED
  591.                 void BreakOnInvalidTriangle(const TriangleID triangleID) const;
  592. #else
  593.                 void BreakOnInvalidTriangle(const TriangleID triangleID) const {}
  594. #endif
  595.  
  596.         private:
  597.                 // Assignment not supported (we'd have to think about potential use-cases first as it's not inherently clear what should happen with the m_tiles pointer)
  598.                 // (VC++ 2012 does not yet support defaulted and deleted functions, so we still need to declare it in the private scope and omit the implementation)
  599.                 TileContainerArray& operator=(const TileContainerArray&);
  600.  
  601.                 void                Grow(size_t amount);
  602.  
  603.         private:
  604.                 TileContainer* m_tiles;
  605.                 size_t         m_tileCount;
  606.                 size_t         m_tileCapacity;
  607.  
  608.                 typedef std::vector<size_t> FreeIndexes;    // dynamically-resizing array of indexes pointing to unused elements in m_tiles[]
  609.                 FreeIndexes m_freeIndexes;
  610.         };
  611.  
  612.         TileContainerArray m_tiles;
  613.         size_t             m_triangleCount;
  614.  
  615.         // replace with something more efficient will speed up path-finding, ray-casting and
  616.         // connectivity computation
  617.         typedef std::map<uint32, uint32> TileMap;
  618.         TileMap             m_tileMap;
  619.  
  620.         std::vector<Island> m_islands;
  621.  
  622.         struct IslandConnectionRequest
  623.         {
  624.                 IslandConnectionRequest(const StaticIslandID _startingIslandID, const TriangleID _startingTriangleID, const uint16 _offMeshLinkIndex)
  625.                         : startingIslandID(_startingIslandID)
  626.                         , startingTriangleID(_startingTriangleID)
  627.                         , offMeshLinkIndex(_offMeshLinkIndex)
  628.                 {
  629.                 }
  630.  
  631.                 StaticIslandID startingIslandID;
  632.                 TriangleID     startingTriangleID;
  633.                 uint16         offMeshLinkIndex;
  634.         };
  635.         std::vector<IslandConnectionRequest> m_islandConnectionRequests;
  636.  
  637.         SGridParams                          m_params;
  638.         ProfilerType                         m_profiler;
  639.  
  640.         static const real_t                  kMinPullingThreshold;
  641.         static const real_t                  kMaxPullingThreshold;
  642.         static const real_t                  kAdjecencyCalculationToleranceSq;
  643. };
  644. }
  645.  
  646. #endif  // #ifndef __MNM_MESH_GRID_H
  647.  
downloadNavMesh.h Source code - Download CRYENGINE Source code
Related Source Codes/Software:
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top