Cuberite
A lightweight, fast and extensible game server for Minecraft
PathFinder.cpp
Go to the documentation of this file.
1 #include "Globals.h"
2 #include "PathFinder.h"
3 #include "BlockType.h"
4 #include "../BlockInfo.h"
5 #include "../Chunk.h"
6 
7 
8 
9 
10 
11 cPathFinder::cPathFinder(float a_MobWidth, float a_MobHeight) :
12  m_Width(a_MobWidth),
13  m_Height(a_MobHeight),
14  m_GiveUpCounter(0),
15  m_NotFoundCooldown(0)
16 {
17 }
18 
19 
20 
21 
22 
23 ePathFinderStatus cPathFinder::GetNextWayPoint(cChunk & a_Chunk, const Vector3d & a_Source, Vector3d * a_Destination, Vector3d * a_OutputWaypoint, bool a_DontCare)
24 {
25  m_FinalDestination = *a_Destination;
26  m_Source = a_Source;
27 
28  // If a recent PATH_NOT_FOUND was returned, we rest for a few ticks.
29  if (m_NotFoundCooldown > 0)
30  {
31  m_NotFoundCooldown -= 1;
33  }
34 
35  // Tweak the destination. If something is wrong with the destination or the chunk, rest for a while.
36  if (!(EnsureProperPoint(m_FinalDestination, a_Chunk) && EnsureProperPoint(m_Source, a_Chunk)))
37  {
38  m_NotFoundCooldown = 20;
40  }
41 
42  /* printf("%d %d %d -> %d %d %d\n",
43  static_cast<int>(m_Source.x),
44  static_cast<int>(m_Source.y),
45  static_cast<int>(m_Source.z),
46  static_cast<int>(m_FinalDestination.x),
47  static_cast<int>(m_FinalDestination.y),
48  static_cast<int>(m_FinalDestination.z)); */
49 
50  // Rest is over. Prepare m_Path by calling ResetPathFinding.
51  if (m_NotFoundCooldown == 0)
52  {
53  m_NotFoundCooldown = -1;
54  ResetPathFinding(a_Chunk);
55  }
56 
57  // If m_Path has not been initialized yet, initialize it.
58  if (!m_Path->IsValid())
59  {
60  ResetPathFinding(a_Chunk);
61  }
62 
63  switch (m_Path->CalculationStep(a_Chunk))
64  {
66  {
67  m_NoPathToTarget = true;
68  m_PathDestination = m_Path->AcceptNearbyPath();
69  if (a_DontCare)
70  {
72  *a_Destination = m_FinalDestination; // Modify the mob's final destination because it doesn't care about reaching an exact spot
73  }
74  else
75  {
76  m_DeviationOrigin = m_FinalDestination; // This is the only case in which m_DeviationOrigin != m_PathDestination
77  }
79  // The next call will trigger the PATH_FOUND case
80  }
81 
83  {
84  m_NotFoundCooldown = 20;
86  }
88  {
90  }
92  {
93  m_GiveUpCounter -= 1;
94 
95  if (m_GiveUpCounter == 0)
96  {
97  if (a_DontCare)
98  {
99  // We're having trouble reaching the next waypoint but the mob
100  // Doesn't care where to go, just tell him we got there ;)
102  *a_Destination = m_FinalDestination;
103  ResetPathFinding(a_Chunk);
105  }
106  else
107  {
108  ResetPathFinding(a_Chunk);
110  }
111  }
112 
113  if (PathIsTooOld())
114  {
115  ResetPathFinding(a_Chunk);
117  }
118 
119  if (m_Path->NoMoreWayPoints())
120  {
121  // We're always heading towards m_PathDestination.
122  // If m_PathDestination is exactly m_FinalDestination, then we're about to reach the destination.
124  {
125  *a_OutputWaypoint = m_FinalDestination;
127 
128  }
129  else
130  {
131  // Otherwise, we've finished our approximate path and time to recalc.
132  ResetPathFinding(a_Chunk);
134  }
135  }
136 
137  Vector3d Waypoint(m_WayPoint);
138  Vector3d Source(m_Source);
139  Waypoint.y = 0;
140  Source.y = 0;
141 
142  if (m_Path->IsFirstPoint() || (((Waypoint - Source).SqrLength() < WAYPOINT_RADIUS) && (m_Source.y >= m_WayPoint.y)))
143  {
144  // if the mob has just started or if the mob reached a waypoint, give them a new waypoint.
145  m_WayPoint = m_Path->GetNextPoint();
146  m_GiveUpCounter = 40;
148  }
149  else
150  {
151  // Otherwise, the mob is still walking towards its waypoint, we'll patiently wait. We won't update m_WayPoint.
152  *a_OutputWaypoint = m_WayPoint;
154  }
155  }
156  }
157  UNREACHABLE("Unsupported path finder status");
158 }
159 
160 
161 
162 
163 
165 {
166  m_GiveUpCounter = 40;
167  m_NoPathToTarget = false;
170  m_Path.reset(new cPath(a_Chunk, m_Source, m_PathDestination, 20, m_Width, m_Height));
171 }
172 
173 
174 
175 
176 
177 bool cPathFinder::EnsureProperPoint(Vector3d & a_Vector, cChunk & a_Chunk)
178 {
179  cChunk * Chunk = a_Chunk.GetNeighborChunk(FloorC(a_Vector.x), FloorC(a_Vector.z));
181  NIBBLETYPE BlockMeta;
182 
183  if ((Chunk == nullptr) || !Chunk->IsValid())
184  {
185  return false;
186  }
187 
188  // If destination in the air, first try to go 1 block north, or east, or west.
189  // This fixes the player leaning issue.
190  // If that failed, we instead go down to the lowest air block.
191  auto Below = a_Vector.Floor().addedY(-1);
192  if (!cChunkDef::IsValidHeight(Below))
193  {
194  return false;
195 
196  }
197  auto BelowRel = cChunkDef::AbsoluteToRelative(Below);
198 
199  Chunk->GetBlockTypeMeta(BelowRel, BlockType, BlockMeta);
200  if (!(IsWaterOrSolid(BlockType)))
201  {
202  constexpr std::array<Vector3i, 8> Offsets =
203  {
204  {
205  {-1, 0, 0},
206  {1, 0, 0},
207  {0, 0, -1},
208  {0, 0, 1},
209  {-1, 0, -1},
210  {-1, 0, 1},
211  {1, 0, -1},
212  {1, 0, 1},
213  }
214  };
215 
216  // Looks for a neighbouring block one block in x or z direction that is water or solid.
217  bool InTheAir = true;
218  for (const auto & Offset : Offsets)
219  {
220  auto InspectPos = Below + Offset;
221  Chunk = a_Chunk.GetNeighborChunk(InspectPos.x, InspectPos.z);
222  if ((Chunk == nullptr) || !Chunk->IsValid())
223  {
224  return false;
225  }
226  auto InspectRel = cChunkDef::AbsoluteToRelative(InspectPos);
227  Chunk->GetBlockTypeMeta(InspectRel, BlockType, BlockMeta);
228  if (IsWaterOrSolid((BlockType)))
229  {
230  BelowRel = InspectRel;
231  InTheAir = false;
232  break;
233  }
234  }
235 
236  // Go down to the lowest air block.
237  if (InTheAir)
238  {
239  while (cChunkDef::IsValidHeight(BelowRel.addedY(-1)))
240  {
241  Chunk->GetBlockTypeMeta(BelowRel.addedY(-1), BlockType, BlockMeta);
243  {
244  break;
245  }
246  BelowRel.y -= 1;
247  }
248  }
249  }
250 
251  // If destination in water or solid, go up to the first air block.
252  while (BelowRel.y < cChunkDef::Height)
253  {
254  Chunk->GetBlockTypeMeta(BelowRel, BlockType, BlockMeta);
256  {
257  break;
258  }
259  BelowRel.y += 1;
260  }
261 
262  return true;
263 }
264 
265 
266 
267 
268 
270 {
271  return ((a_BlockType == E_BLOCK_STATIONARY_WATER) || cBlockInfo::IsSolid(a_BlockType));
272 }
273 
274 
275 
276 
277 
279 {
280  size_t acceptableDeviation = m_Path->WayPointsLeft() / 2;
281  if (acceptableDeviation == 0)
282  {
283  acceptableDeviation = 1;
284  }
285  const auto DeviationSqr = (m_FinalDestination - m_DeviationOrigin).SqrLength();
286  return (DeviationSqr > (acceptableDeviation * acceptableDeviation));
287 }
@ E_BLOCK_STATIONARY_WATER
Definition: BlockType.h:19
unsigned char NIBBLETYPE
The datatype used by nibbledata (meta, light, skylight)
Definition: ChunkDef.h:44
unsigned char BLOCKTYPE
The datatype used by blockdata.
Definition: ChunkDef.h:41
#define UNREACHABLE(x)
Definition: Globals.h:288
std::enable_if< std::is_arithmetic< T >::value, C >::type FloorC(T a_Value)
Floors a value, then casts it to C (an int by default).
Definition: Globals.h:347
ePathFinderStatus
Definition: Path.h:26
#define WAYPOINT_RADIUS
Definition: PathFinder.h:5
BlockType
Definition: BlockTypes.h:4
static bool IsSolid(BLOCKTYPE Block)
Is this block solid (player cannot walk through)?
Definition: BlockInfo.cpp:892
Definition: Chunk.h:36
cChunk * GetNeighborChunk(int a_BlockX, int a_BlockZ)
Returns the chunk into which the specified block belongs, by walking the neighbors.
Definition: Chunk.cpp:1806
bool IsValid(void) const
Returns true iff the chunk block data is valid (loaded / generated)
Definition: Chunk.h:58
void GetBlockTypeMeta(Vector3i a_RelPos, BLOCKTYPE &a_BlockType, NIBBLETYPE &a_BlockMeta) const
Definition: Chunk.cpp:1757
static bool IsValidHeight(Vector3i a_BlockPosition)
Validates a height-coordinate.
Definition: ChunkDef.h:185
static void AbsoluteToRelative(int &a_X, int &a_Y, int &a_Z, int &a_ChunkX, int &a_ChunkZ)
Converts absolute block coords into relative (chunk + block) coords:
Definition: ChunkDef.h:147
static const int Height
Definition: ChunkDef.h:125
Definition: Path.h:69
Vector3d m_DeviationOrigin
When FinalDestination is too far from this, we recalculate.
Definition: PathFinder.h:66
std::unique_ptr< cPath > m_Path
The current cPath instance we have.
Definition: PathFinder.h:50
ePathFinderStatus GetNextWayPoint(cChunk &a_Chunk, const Vector3d &a_Source, Vector3d *a_Destination, Vector3d *a_OutputWaypoint, bool a_DontCare=false)
Updates the PathFinder's internal state and returns a waypoint.
Definition: PathFinder.cpp:23
bool IsWaterOrSolid(BLOCKTYPE a_BlockType)
Return true the the blocktype is either water or solid.
Definition: PathFinder.cpp:269
Vector3d m_PathDestination
Coordinates for where we are practically going.
Definition: PathFinder.h:62
int m_GiveUpCounter
If 0, will give up reaching the next m_WayPoint and will recalculate path.
Definition: PathFinder.h:53
float m_Height
The height of the Mob which owns this PathFinder.
Definition: PathFinder.h:47
bool m_NoPathToTarget
True if there's no path to target and we're walking to a nearby location instead.
Definition: PathFinder.h:73
Vector3d m_WayPoint
Coordinates of the next position that should be reached.
Definition: PathFinder.h:56
cPathFinder(float a_MobWidth, float a_MobHeight)
Creates a cPathFinder instance.
Definition: PathFinder.cpp:11
Vector3d m_Source
Coordinates for where the mob is currently at.
Definition: PathFinder.h:70
bool PathIsTooOld() const
Is the path too old and should be recalculated? When this is true ResetPathFinding() is called.
Definition: PathFinder.cpp:278
int m_NotFoundCooldown
When a path is not found, this cooldown prevents any recalculations for several ticks.
Definition: PathFinder.h:76
float m_Width
The width of the Mob which owns this PathFinder.
Definition: PathFinder.h:44
Vector3d m_FinalDestination
Coordinates for where we should go.
Definition: PathFinder.h:59
bool EnsureProperPoint(Vector3d &a_Vector, cChunk &a_Chunk)
Ensures the location is not in the air or under water.
Definition: PathFinder.cpp:177
void ResetPathFinding(cChunk &a_Chunk)
Resets a pathfinding task, typically because m_FinalDestination has deviated too much from m_Deviatio...
Definition: PathFinder.cpp:164
Vector3< T > addedY(T a_AddY) const
Returns a copy of this vector moved by the specified amount on the y axis.
Definition: Vector3.h:314
T x
Definition: Vector3.h:17
Vector3< int > Floor(void) const
Returns a new Vector3i with coords set to std::floor() of this vector's coords.
Definition: Vector3.h:177
T y
Definition: Vector3.h:17
T z
Definition: Vector3.h:17