1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
#pragma once
/*
// Needed Fwds: cPath
enum class ePathFinderStatus;
class cPath;
*/
#include "../FastRandom.h"
#ifdef COMPILING_PATHFIND_DEBUGGER
/* Note: the COMPILING_PATHFIND_DEBUGGER flag is used by Native / WiseOldMan95 to debug
this class outside of Cuberite. This preprocessor flag is never set when compiling Cuberite. */
#include "PathFinderIrrlicht_Head.h"
#endif
#include <unordered_map>
//fwd: ../Chunk.h
class cChunk;
/* Various little structs and classes */
enum class ePathFinderStatus {CALCULATING, PATH_FOUND, PATH_NOT_FOUND, NEARBY_FOUND};
enum class eCellStatus {OPENLIST, CLOSEDLIST, NOLIST};
struct cPathCell
{
Vector3i m_Location; // Location of the cell in the world.
int m_F, m_G, m_H; // F, G, H as defined in regular A*.
eCellStatus m_Status; // Which list is the cell in? Either non, open, or closed.
cPathCell * m_Parent; // Cell's parent, as defined in regular A*.
bool m_IsSolid; // Is the cell an air or a solid? Partial solids are currently considered solids.
};
class compareHeuristics
{
public:
bool operator()(cPathCell * & a_V1, cPathCell * & a_V2);
};
class cPath
{
public:
/** Creates a pathfinder instance. A Mob will probably need a single pathfinder instance for its entire life.
Note that if you have a man-sized mob (1x1x2, zombies, etc), you are advised to call this function without parameters
because the declaration might change in later version of the pathFinder, and a parameter-less call always assumes a man-sized mob.
If your mob is not man-sized, you are advised to use cPath(width, height), this would be compatible with future versions,
but please be aware that as of now those parameters will be ignored and your mob will be assumed to be man sized.
@param a_BoundingBoxWidth the character's boundingbox width in blocks. Currently the parameter is ignored and 1 is assumed.
@param a_BoundingBoxHeight the character's boundingbox width in blocks. Currently the parameter is ignored and 2 is assumed.
@param a_MaxUp the character's max jump height in blocks. Currently the parameter is ignored and 1 is assumed.
@param a_MaxDown How far is the character willing to fall? Currently the parameter is ignored and 1 is assumed. */
/** Attempts to find a path starting from source to destination.
After calling this, you are expected to call Step() once per tick or once per several ticks until it returns true. You should then call getPath() to obtain the path.
Calling this before a path is found resets the current path and starts another search.
@param a_StartingPoint The function expects this position to be the lowest block the mob is in, a rule of thumb: "The block where the Zombie's knees are at".
@param a_EndingPoint "The block where the Zombie's knees want to be".
@param a_MaxSteps The maximum steps before giving up. */
cPath(
cChunk & a_Chunk,
const Vector3d & a_StartingPoint, const Vector3d & a_EndingPoint, int a_MaxSteps,
double a_BoundingBoxWidth, double a_BoundingBoxHeight,
int a_MaxUp = 1, int a_MaxDown = 1
);
/** Creates a dummy path which does nothing except returning false when isValid is called. */
cPath();
/** delete default constructors */
cPath(const cPath & a_other) = delete;
cPath(cPath && a_other) = delete;
cPath & operator=(const cPath & a_other) = delete;
cPath & operator=(cPath && a_other) = delete;
/** Performs part of the path calculation and returns the appropriate status.
If NEARBY_FOUND is returned, it means that the destination is not reachable, but a nearby destination
is reachable. If the user likes the alternative destination, they can call AcceptNearbyPath to treat the path as found,
and to make consequent calls to step return PATH_FOUND */
ePathFinderStatus CalculationStep(cChunk & a_Chunk);
/** Called after the PathFinder's step returns NEARBY_FOUND.
Changes the PathFinder status from NEARBY_FOUND to PATH_FOUND, returns the nearby destination that
the PathFinder found a path to. */
Vector3i AcceptNearbyPath();
// Point retrieval functions, inlined for performance:
/** Returns the next point in the path. */
inline Vector3d GetNextPoint()
{
ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
ASSERT(m_CurrentPoint < m_PathPoints.size());
Vector3i Point = m_PathPoints[m_PathPoints.size() - 1 - m_CurrentPoint];
++m_CurrentPoint;
return Vector3d(Point.x + m_HalfWidth, Point.y, Point.z + m_HalfWidth);
}
/** Checks if we have no more waypoints to return. Never call getnextPoint when this is true. */
inline bool NoMoreWayPoints() const
{
ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
return (m_CurrentPoint == m_PathPoints.size());
}
/** Returns true if GetNextPoint() was never called for this Path. */
inline bool IsFirstPoint() const
{
ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
return (m_CurrentPoint == 0);
}
/** Returns true if this path is properly initialized.
Returns false if this path was initialized with an empty constructor.
If false, the path is unusable and you should not call any methods. */
inline bool IsValid() const
{
return m_IsValid;
}
/** The amount of waypoints left to return. */
inline size_t WayPointsLeft() const
{
ASSERT(m_Status == ePathFinderStatus::PATH_FOUND);
return m_PathPoints.size() - m_CurrentPoint;
}
private:
/* General */
bool IsSolid(const Vector3i & a_Location); // Query our hosting world and ask it if there's a solid at a_location.
bool StepOnce(); // The public version just calls this version * CALCULATIONS_PER_CALL times.
void FinishCalculation(); // Clears the memory used for calculating the path.
void FinishCalculation(ePathFinderStatus a_NewStatus); // Clears the memory used for calculating the path and changes the status.
void AttemptToFindAlternative();
void BuildPath();
/* Openlist and closedlist management */
void OpenListAdd(cPathCell * a_Cell);
cPathCell * OpenListPop();
bool ProcessIfWalkable(const Vector3i &a_Location, cPathCell * a_Parent, int a_Cost);
/* Map management */
void ProcessCell(cPathCell * a_Cell, cPathCell * a_Caller, int a_GDelta);
cPathCell * GetCell(const Vector3i & a_location);
/* Pathfinding fields */
std::priority_queue<cPathCell *, std::vector<cPathCell *>, compareHeuristics> m_OpenList;
std::unordered_map<Vector3i, cPathCell, VectorHasher<int>> m_Map;
Vector3i m_Destination;
Vector3i m_Source;
int m_BoundingBoxWidth;
int m_BoundingBoxHeight;
double m_HalfWidth;
int m_StepsLeft;
cPathCell * m_NearestPointToTarget;
cFastRandom m_Rand;
/* Control fields */
ePathFinderStatus m_Status;
bool m_IsValid;
/* Final path fields */
size_t m_CurrentPoint;
std::vector<Vector3i> m_PathPoints;
/* Interfacing with the world */
cChunk * m_Chunk; // Only valid inside Step()!
bool m_BadChunkFound;
/* High level world queries */
bool IsWalkable(const Vector3i & a_Location);
bool BodyFitsIn(const Vector3i & a_Location);
bool HasSolidBelow(const Vector3i & a_Location);
#ifdef COMPILING_PATHFIND_DEBUGGER
#include "../path_irrlicht.cpp"
#endif
};
|
