aboutsummaryrefslogtreecommitdiff
path: root/primedev/server/ai_navmesh.h
blob: c3339110ae2ce42c0d8d39f9e8b9cece356cc0de (plain)
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#pragma once

// [Fifty]: Taken from https://github.com/ASpoonPlaysGames/r2recast

#include "core/math/vector.h"

struct dtMeshHeader;
struct dtMeshTile;
struct dtPoly;
struct dtBVNode;
struct dtLink;

typedef unsigned int dtPolyRef;

/// The maximum number of vertices per navigation polygon.
/// @ingroup detour
static const int DT_VERTS_PER_POLYGON = 6;

/// Flags representing the type of a navigation mesh polygon.
enum dtPolyTypes
{
	/// The polygon is a standard convex polygon that is part of the surface of the mesh.
	DT_POLYTYPE_GROUND = 0,
	/// The polygon is an off-mesh connection consisting of two vertices.
	DT_POLYTYPE_OFFMESH_CONNECTION = 1,
};

/// Configuration parameters used to define multi-tile navigation meshes.
/// The values are used to allocate space during the initialization of a navigation mesh.
/// @see dtNavMesh::init()
/// @ingroup detour
struct dtNavMeshParams
{
	float orig[3]; ///< The world space origin of the navigation mesh's tile space. [(x, y, z)]
	float tileWidth; ///< The width of each tile. (Along the x-axis.)
	float tileHeight; ///< The height of each tile. (Along the z-axis.)
	int maxTiles; ///< The maximum number of tiles the navigation mesh can contain. This and maxPolys are used to calculate how many bits
				  ///< are needed to identify tiles and polygons uniquely.
	int maxPolys; ///< The maximum number of polygons each tile can contain. This and maxTiles are used to calculate how many bits are
				  ///< needed to identify tiles and polygons uniquely.
	//
	//// i hate this
	int disjointPolyGroupCount = 0;
	int reachabilityTableSize = 0;
	int reachabilityTableCount = 0;
};

/// Defines an navigation mesh off-mesh connection within a dtMeshTile object.
/// An off-mesh connection is a user defined traversable connection made up to two vertices.
struct dtOffMeshConnection
{
	/// The endpoints of the connection.
	Vector3 origin;
	Vector3 dest;

	/// The radius of the endpoints. [Limit: >= 0]
	float rad;

	/// The polygon reference of the connection within the tile.
	unsigned short poly;

	/// Link flags.
	/// @note These are not the connection's user defined flags. Those are assigned via the
	/// connection's dtPoly definition. These are link flags used for internal purposes.
	unsigned char flags;

	/// End point side.
	unsigned char side;

	/// The id of the offmesh connection. (User assigned when the navigation mesh is built.)
	unsigned int userId;

	float unk[3];
	float another_unk;
};

/// A navigation mesh based on tiles of convex polygons.
/// @ingroup detour
class dtNavMesh
{
public:
	dtMeshTile** m_posLookup; ///< Tile hash lookup.
	dtMeshTile* m_nextFree; ///< Freelist of tiles.
	dtMeshTile* m_tiles; ///< List of tiles.

	void* disjointPolyGroup;
	int** reachabilityTable;

	__int64 unk;
	dtNavMeshParams m_params; ///< Current initialization params. TODO: do not store this info twice.
	float m_orig[3]; ///< Origin of the tile (0,0)
	float m_tileWidth, m_tileHight; ///< Dimensions of each tile.
	int m_pad;
	int m_maxTiles; ///< Max number of tiles.

	int m_tileLutSize; ///< Tile hash lookup size (must be pot).
	int m_tileLutMask; ///< Tile hash lookup mask.

	int m_saltBits; ///< Number of salt bits in the tile ID.
	int m_tileBits; ///< Number of tile bits in the tile ID.
	int m_polyBits; ///< Number of poly bits in the tile ID.
};

/// Defines the location of detail sub-mesh data within a dtMeshTile.
struct dtPolyDetail
{
	unsigned int vertBase; ///< The offset of the vertices in the dtMeshTile::detailVerts array.
	unsigned int triBase; ///< The offset of the triangles in the dtMeshTile::detailTris array.
	unsigned char vertCount; ///< The number of vertices in the sub-mesh.
	unsigned char triCount; ///< The number of triangles in the sub-mesh.
};

/// Defines a navigation mesh tile.
/// @ingroup detour
struct dtMeshTile
{
	int salt; ///< Counter describing modifications to the tile.
	unsigned int linksFreeList; ///< Index to the next free link.
	dtMeshHeader* header; ///< The tile header.
	dtPoly* polys; ///< The tile polygons. [Size: dtMeshHeader::polyCount]
	void* unkPolyThing;
	float* verts; ///< The tile vertices. [Size: dtMeshHeader::vertCount]
	dtLink* links; ///< The tile links. [Size: dtMeshHeader::maxLinkCount]
	dtPolyDetail* detailMeshes; ///< The tile's detail sub-meshes. [Size: dtMeshHeader::detailMeshCount]

	/// The detail mesh's unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount]
	float* detailVerts;

	/// The detail mesh's triangles. [(vertA, vertB, vertC, triFlags) * dtMeshHeader::detailTriCount].
	/// See dtDetailTriEdgeFlags and dtGetDetailTriEdgeFlags.
	unsigned char* detailTris;

	/// The tile bounding volume nodes. [Size: dtMeshHeader::bvNodeCount]
	/// (Will be null if bounding volumes are disabled.)
	dtBVNode* bvTree;

	dtOffMeshConnection* offMeshConnections; ///< The tile off-mesh connections. [Size: dtMeshHeader::offMeshConCount]
	void* data; ///< The tile data. (Not directly accessed under normal situations.)
	int dataSize; ///< Size of the tile data.
	int flags; ///< Tile flags. (See: #dtTileFlags)
	dtMeshTile* next; ///< The next free tile, or the next tile in the spatial grid.
	__int64 unk;
};

/// Provides high level information related to a dtMeshTile object.
/// @ingroup detour
struct dtMeshHeader
{
	int magic; ///< Tile magic number. (Used to identify the data format.)
	int version; ///< Tile data format version number.
	int x; ///< The x-position of the tile within the dtNavMesh tile grid. (x, y, layer)
	int y; ///< The y-position of the tile within the dtNavMesh tile grid. (x, y, layer)
	int layer; ///< The layer of the tile within the dtNavMesh tile grid. (x, y, layer)
	unsigned int userId; ///< The user defined id of the tile.
	int polyCount; ///< The number of polygons in the tile.
	int sth_per_poly;
	int vertCount; ///< The number of vertices in the tile.
	int maxLinkCount; ///< The number of allocated links.

	int detailMeshCount;

	/// The number of unique vertices in the detail mesh. (In addition to the polygon vertices.)
	int detailVertCount;

	int detailTriCount; ///< The number of triangles in the detail mesh.
	int bvNodeCount; ///< The number of bounding volume nodes. (Zero if bounding volumes are disabled.)
	int offMeshConCount; ///< The number of off-mesh connections.
	// int unk1;
	int offMeshBase; ///< The index of the first polygon which is an off-mesh connection.

	float walkableHeight; ///< The height of the agents using the tile.
	float walkableRadius; ///< The radius of the agents using the tile.
	float walkableClimb; ///< The maximum climb height of the agents using the tile.
	float bmin[3]; ///< The minimum bounds of the tile's AABB. [(x, y, z)]
	float bmax[3]; ///< The maximum bounds of the tile's AABB. [(x, y, z)]

	/// The bounding volume quantization factor.
	float bvQuantFactor;
};

/// Defines a polygon within a dtMeshTile object.
/// @ingroup detour
struct dtPoly
{
	/// Index to first link in linked list. (Or #DT_NULL_LINK if there is no link.)
	unsigned int firstLink;

	/// The indices of the polygon's vertices.
	/// The actual vertices are located in dtMeshTile::verts.
	unsigned short verts[DT_VERTS_PER_POLYGON];

	/// Packed data representing neighbor polygons references and flags for each edge.
	unsigned short neis[DT_VERTS_PER_POLYGON];

	/// The user defined polygon flags.
	unsigned short flags;

	/// The number of vertices in the polygon.
	unsigned char vertCount;

	/// The bit packed area id and polygon type.
	/// @note Use the structure's set and get methods to acess this value.
	unsigned char areaAndtype;

	unsigned short disjointSetId;
	unsigned short unk; // IDK but looks filled
	Vector3 org; //

	/// Sets the user defined area id. [Limit: < #DT_MAX_AREAS]
	inline void setArea(unsigned char a) { areaAndtype = (areaAndtype & 0xc0) | (a & 0x3f); }

	/// Sets the polygon type. (See: #dtPolyTypes.)
	inline void setType(unsigned char t) { areaAndtype = (areaAndtype & 0x3f) | (t << 6); }

	/// Gets the user defined area id.
	inline unsigned char getArea() const { return areaAndtype & 0x3f; }

	/// Gets the polygon type. (See: #dtPolyTypes)
	inline unsigned char getType() const { return areaAndtype >> 6; }
};

/// Defines a link between polygons.
/// @note This structure is rarely if ever used by the end user.
/// @see dtMeshTile
struct dtLink
{
	dtPolyRef ref; ///< Neighbour reference. (The neighbor that is linked to.)
	unsigned int next; ///< Index of the next link.
	unsigned char edge; ///< Index of the polygon edge that owns this link.
	unsigned char side; ///< If a boundary link, defines on which side the link is.
	unsigned char bmin; ///< If a boundary link, defines the minimum sub-edge area.
	unsigned char bmax; ///< If a boundary link, defines the maximum sub-edge area.
	unsigned char jumpType;
	unsigned char otherUnk;
	unsigned short reverseLinkIndex;
};

/// Bounding volume node.
/// @note This structure is rarely if ever used by the end user.
/// @see dtMeshTile
struct dtBVNode
{
	unsigned short bmin[3]; ///< Minimum bounds of the node's AABB. [(x, y, z)]
	unsigned short bmax[3]; ///< Maximum bounds of the node's AABB. [(x, y, z)]
	int i; ///< The node's index. (Negative for escape sequence.)
};

inline dtNavMesh** g_pNavMesh = nullptr;