gwnavruntime/querysystem/workingmemcontainers/astarnodeindexingrid.h Source File

astarnodeindexingrid.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 
8 #ifndef Navigation_AstarNodeIndexInGrid_H
9 #define Navigation_AstarNodeIndexInGrid_H
10 
14 
15 
16 namespace Kaim
17 {
18 
19 class AStarContextConfig
20 {
21 public:
22  AStarContextConfig() : m_abstractGraphTraversalMode(PATHFINDER_DO_NOT_TRAVERSE_ABSTRACT_GRAPHS) {}
23 
24  bool CanUseAbstractGraphs() const;
25 
26 public:
27  PathFinderAbstractGraphTraversalMode m_abstractGraphTraversalMode;
28  CellBox m_startActiveDataCellBoxForAbstractGraph;
29  CellBox m_destActiveDataCellBoxForAbstractGraph;
30 };
31 
32 class AstarNodeIndexInGrid
33 {
34 public:
35 
36  /*
37  AstarIndex on 32bits
38  */
39  KY_INLINE KyUInt32 GetNumberOfWordsForNodeIndices(KyUInt32 numberOfNodes) { return numberOfNodes; }
40 
41  struct NavGraphToNodeIndices
42  {
43  KY_INLINE AStarNodeIndex GetAStarNodeIndex(NavGraphVertexIdx navGraphVertexIdx) const { return GetNodeIndices()[navGraphVertexIdx]; }
44  KY_INLINE void SetAStarNodeIndex(NavGraphVertexIdx navGraphVertexIdx, AStarNodeIndex index) { GetNodeIndices()[navGraphVertexIdx] = index; }
45 
46  KY_INLINE AStarNodeIndex* GetNodeIndices() const { return (AStarNodeIndex*)((char*)this + m_offsetToNodeIndices); }
47 
48  KY_INLINE bool IsValid() const { return m_offsetToNodeIndices != KyUInt32MAXVAL; }
49  KyUInt32 m_offsetToNodeIndices;
50  };
51 
52  struct AbstractGraphToNodeIndices
53  {
54  KY_INLINE AStarNodeIndex GetAStarNodeIndex(AbstractGraphNodeIdx abstractGraphNodeIdx) const { return GetNodeIndices()[abstractGraphNodeIdx]; }
55  KY_INLINE void SetAStarNodeIndex(AbstractGraphNodeIdx abstractGraphNodeIdx, AStarNodeIndex index) { GetNodeIndices()[abstractGraphNodeIdx] = index; }
56 
57  KY_INLINE AStarNodeIndex* GetNodeIndices() const { return (AStarNodeIndex*)((char*)this + m_offsetToNodeIndices); }
58 
59  KY_INLINE bool IsValid() const { return m_offsetToNodeIndices != KyUInt32MAXVAL; }
60  KyUInt32 m_offsetToNodeIndices;
61  };
62 
63  struct NavFloorToNodeIndices
64  {
65  KY_INLINE AStarNodeIndex GetAStarNodeIndex(NavHalfEdgeIdx navHalfEdgeIdx) const { return GetNodeIndices()[navHalfEdgeIdx]; }
66  KY_INLINE void SetAStarNodeIndex(NavHalfEdgeIdx navHalfEdgeIdx, AStarNodeIndex index) { GetNodeIndices()[navHalfEdgeIdx] = index; }
67 
68  KY_INLINE AStarNodeIndex* GetNodeIndices() const { return (AStarNodeIndex*)((char*)this + m_offsetToNodeIndices); }
69  KY_INLINE bool IsValid() const { return m_offsetToNodeIndices != KyUInt32MAXVAL; }
70 
71  KyUInt32 m_offsetToNodeIndices;
72  };
73 
74  struct CellPosToNavFloors
75  {
76  KY_INLINE bool IsValid() const { return m_offSetToNavFloorToNodeIndices != KyUInt32MAXVAL; }
77  KY_INLINE NavFloorToNodeIndices* GetNavFloorToNodeIndices() const { return (NavFloorToNodeIndices*)((char*)this + m_offSetToNavFloorToNodeIndices); }
78 
79  KyUInt32 m_offSetToNavFloorToNodeIndices;
80  KyUInt32 m_navDataChangeIdx;
81  };
82 
83 public:
84  AstarNodeIndexInGrid() : m_numberOfNavGraph(0), m_numberOfAbstractGraph(0), m_currentOffsetFromBuffer(0) {}
85 
86  AstarNodeIndexInGrid(WorkingMemory* workingMemory, ActiveData* activeData, const AStarContextConfig& astarContextConfig) { Init(workingMemory, activeData, astarContextConfig); }
87 
88  void Init(WorkingMemory* workingMemory, ActiveData* activeData, const AStarContextConfig& astarContextConfig);
89 
90  void ReleaseWorkingMemoryBuffer();
91 
92  KyUInt32 GetAvailableSizeInBytes() const;
93 
94  bool IsEnoughPlaceForAllocation(KyUInt32 sizeInBytes);
95 
96  bool TryToResize();
97 
98  void MakeEmpty();
99 
100  void* AllocateInBufferAndMemsetTo1(KyUInt32 totalSizeToNewOffSet);
101 
102  AStarNodeIndex* AllocateAstarNodeIndices(KyUInt32 numberOfEdges);
103 
104  CellPosToNavFloors* AllocateCellPosToNavFloors(KyUInt32 numberOfCell);
105  NavFloorToNodeIndices* AllocateNavFloorToNodeIndex(KyUInt32 numberOfFloors);
106  NavGraphToNodeIndices* AllocateNavGraphToNodeIndex(KyUInt32 numberOfGraphs);
107  AbstractGraphToNodeIndices* AllocateAbstractGraphToNodeIndex(KyUInt32 numberOfAbstractGraphs);
108 
109  CellPosToNavFloors* GetCellPosToNavFloors(const CellPos& cellPos);
110 
111  KyResult GetNavFloorToNodeIndices(ActiveData* activeData, const NavFloorRawPtr& navFloorRawPtr, NavFloorToNodeIndices*& nodeIndices);
112  KyResult GetNavGraphToNodeIndices(const NavGraphVertexRawPtr& navGraphVertexRawPtr, NavGraphToNodeIndices*& nodeIndices);
113  KyResult GetAbstractGraphToNodeIndices(const AbstractGraphNodeRawPtr& abstractGraphNodeRawPtr, AbstractGraphToNodeIndices*& nodeIndices);
114 
115  NavGraphToNodeIndices* GetNavGraphToNodeIndices_Unsafe(const NavGraphVertexRawPtr& navGraphVertexRawPtr);
116  NavFloorToNodeIndices* GetNavFloorToNodeIndices_Unsafe(const NavFloorRawPtr& navFloorRawPtr);
117  AbstractGraphToNodeIndices* GetAbstractGraphToNodeIndices_Unsafe(const AbstractGraphNodeRawPtr& abstractGraphNodeRawPtr);
118 
119  bool IsInitialized() const { return m_workingMemContainerBase.IsInitialized(); }
120  bool HasNavDataChanged(Database* database);
121 
122 private:
123  NavGraphToNodeIndices* GetNavGraphToNodeIndicesBuffer();
124  AbstractGraphToNodeIndices* GetAbstractGraphToNodeIndicesBuffer();
125  CellPosToNavFloors* GetCellPosToNavFloorsBuffer();
126 
127 public:
128  WorkingMemContainerBase m_workingMemContainerBase;
129 
130  KyUInt32 m_numberOfNavGraph;
131  KyUInt32 m_navGraphChangeIdx;
132 
133  KyUInt32 m_numberOfAbstractGraph;
134  KyUInt32 m_abstractGraphChangeIdx;
135 
136  KyUInt32 m_currentOffsetFromBuffer;
137  CellBox m_activeDataCellBox;
138  CellBox m_activeDataCellBoxOfAbstractGraphDestination; // only used if m_numberOfAbstractGraph != 0
139 };
140 
141 KY_INLINE void AstarNodeIndexInGrid::ReleaseWorkingMemoryBuffer() { m_workingMemContainerBase.ReleaseBuffer(); }
142 
143 KY_INLINE KyUInt32 AstarNodeIndexInGrid::GetAvailableSizeInBytes() const { return m_workingMemContainerBase.GetBufferSize() - m_currentOffsetFromBuffer; }
144 
145 KY_INLINE bool AstarNodeIndexInGrid::IsEnoughPlaceForAllocation(KyUInt32 sizeInBytes)
146 {
147  while (GetAvailableSizeInBytes() < sizeInBytes)
148  {
149  if (TryToResize() == false)
150  return false;
151  }
152 
153  return true;
154 }
155 
156 KY_INLINE AStarNodeIndex* AstarNodeIndexInGrid::AllocateAstarNodeIndices(KyUInt32 numberOfEdges)
157 {
158  return (AStarNodeIndex*)AllocateInBufferAndMemsetTo1(sizeof(KyUInt32) * GetNumberOfWordsForNodeIndices(numberOfEdges));
159 }
160 
161 KY_INLINE AstarNodeIndexInGrid::NavFloorToNodeIndices* AstarNodeIndexInGrid::AllocateNavFloorToNodeIndex(KyUInt32 numberOfFloors)
162 {
163  return (NavFloorToNodeIndices*)AllocateInBufferAndMemsetTo1(sizeof(NavFloorToNodeIndices) * numberOfFloors);
164 }
165 
166 KY_INLINE AstarNodeIndexInGrid::NavGraphToNodeIndices* AstarNodeIndexInGrid::AllocateNavGraphToNodeIndex(KyUInt32 numberOfGraphs)
167 {
168  return (NavGraphToNodeIndices*)AllocateInBufferAndMemsetTo1(sizeof(NavGraphToNodeIndices) * numberOfGraphs);
169 }
170 
171 KY_INLINE AstarNodeIndexInGrid::AbstractGraphToNodeIndices* AstarNodeIndexInGrid::AllocateAbstractGraphToNodeIndex(KyUInt32 numberOfAbstractGraphs)
172 {
173  return (AbstractGraphToNodeIndices*)AllocateInBufferAndMemsetTo1(sizeof(AbstractGraphToNodeIndices) * numberOfAbstractGraphs);
174 }
175 
176 KY_INLINE AstarNodeIndexInGrid::CellPosToNavFloors* AstarNodeIndexInGrid::AllocateCellPosToNavFloors(KyUInt32 numberOfCell)
177 {
178  return (CellPosToNavFloors*)AllocateInBufferAndMemsetTo1(sizeof(CellPosToNavFloors) * numberOfCell);
179 }
180 
181 
182 KY_INLINE AstarNodeIndexInGrid::NavGraphToNodeIndices* AstarNodeIndexInGrid::GetNavGraphToNodeIndicesBuffer()
183 { return (NavGraphToNodeIndices*)m_workingMemContainerBase.GetBuffer(); }
184 
185 KY_INLINE AstarNodeIndexInGrid::AbstractGraphToNodeIndices* AstarNodeIndexInGrid::GetAbstractGraphToNodeIndicesBuffer()
186 { return (AbstractGraphToNodeIndices*) (GetNavGraphToNodeIndicesBuffer() + m_numberOfNavGraph); }
187 
188 KY_INLINE AstarNodeIndexInGrid::CellPosToNavFloors* AstarNodeIndexInGrid::GetCellPosToNavFloorsBuffer()
189 { return (CellPosToNavFloors*) (GetAbstractGraphToNodeIndicesBuffer() + m_numberOfAbstractGraph); }
190 
191 KY_INLINE AstarNodeIndexInGrid::CellPosToNavFloors* AstarNodeIndexInGrid::GetCellPosToNavFloors(const CellPos& cellPos)
192 {
193  CellPosToNavFloors* memoryStartForGrid = GetCellPosToNavFloorsBuffer();
194  if (m_numberOfAbstractGraph == 0 || m_activeDataCellBox.IsInside(cellPos) == true)
195  return memoryStartForGrid + m_activeDataCellBox.GetRowMajorIndex(cellPos);
196  else if (m_activeDataCellBoxOfAbstractGraphDestination.IsInside(cellPos) == true)
197  return memoryStartForGrid + (m_activeDataCellBox.CountX() * m_activeDataCellBox.CountY()) + m_activeDataCellBoxOfAbstractGraphDestination.GetRowMajorIndex(cellPos);
198  else
199  return KY_NULL;
200 }
201 
202 KY_INLINE AstarNodeIndexInGrid::NavGraphToNodeIndices* AstarNodeIndexInGrid::GetNavGraphToNodeIndices_Unsafe(const NavGraphVertexRawPtr& navGraphVertexRawPtr)
203 {
204  NavGraphToNodeIndices* memoryStartForGraphs = GetNavGraphToNodeIndicesBuffer();
205  return &memoryStartForGraphs[navGraphVertexRawPtr.GetNavGraph()->m_idxInTheActiveDataBuffer];
206 }
207 
208 KY_INLINE AstarNodeIndexInGrid::NavFloorToNodeIndices* AstarNodeIndexInGrid::GetNavFloorToNodeIndices_Unsafe(const NavFloorRawPtr& navFloorRawPtr)
209 {
210  KY_DEBUG_ASSERTN(m_activeDataCellBox.IsInside(navFloorRawPtr.GetCellPos()) || m_activeDataCellBoxOfAbstractGraphDestination.IsInside(navFloorRawPtr.GetCellPos()), ("Invalid CellBox"));
211 
212  NavFloor* navFloor = navFloorRawPtr.GetNavFloor();
213  const CellPos& cellPos = navFloor->GetCellPos();
214 
215  CellPosToNavFloors* cellPosToNavFloors = GetCellPosToNavFloors(cellPos);
216  KY_DEBUG_ASSERTN(cellPosToNavFloors->IsValid(), ("Bad usage of UnSafe function"));
217 
218  NavFloorToNodeIndices& navFloorToNodeIndices = cellPosToNavFloors->GetNavFloorToNodeIndices()[navFloor->GetIndexInCollection()];
219  KY_DEBUG_ASSERTN(navFloorToNodeIndices.IsValid(), ("Bad usage of UnSafe function"));
220 
221  return &navFloorToNodeIndices;
222 }
223 
224 KY_INLINE AstarNodeIndexInGrid::AbstractGraphToNodeIndices* AstarNodeIndexInGrid::GetAbstractGraphToNodeIndices_Unsafe(const AbstractGraphNodeRawPtr& abstractGraphNodeRawPtr)
225 {
226  AbstractGraphToNodeIndices* memoryStartForAbstractGraphs = GetAbstractGraphToNodeIndicesBuffer();
227  return &memoryStartForAbstractGraphs[abstractGraphNodeRawPtr.m_abstractGraph->m_abstractGraphIdx];
228 }
229 
230 }
231 
232 
233 #endif //Navigation_AstarNodeIndexInGrid_H
234 
KyUInt32 NavGraphVertexIdx
An index that uniquely identifies a single vertex within the set of vertices owned by a NavGraph...
Definition: navgraphtypes.h:47
KyInt32 KyResult
Defines a type that can be returned by methods or functions in the Gameware Navigation SDK to indicat...
Definition: types.h:254
Box2i CellBox
A type that represents a bounding box around cells in a 2D grid.
Definition: navmeshtypes.h:34
Vec2i CellPos
A type that represents the position of a cell within a 2D grid.
Definition: navmeshtypes.h:33
KyUInt32 NavHalfEdgeIdx
An index that uniquely identifies a single edge of a triangle within the set of edges owned by a NavF...
Definition: navmeshtypes.h:87
#define KY_NULL
Null value.
Definition: types.h:247
PathFinderAbstractGraphTraversalMode
Enumerates the possible way of dealing with AbstractGraphs.
Definition: pathfinderabstractgraphtraversalmode.h:16
Definition: gamekitcrowddispersion.h:20
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36
#define KyUInt32MAXVAL
The maximum value that can be stored in the KyUInt32 variable type.
Definition: types.h:226