aboutsummaryrefslogtreecommitdiff
path: root/primedev/server/ai_navmesh.h
diff options
context:
space:
mode:
authorJack <66967891+ASpoonPlaysGames@users.noreply.github.com>2024-02-05 17:01:22 +0000
committerGitHub <noreply@github.com>2024-02-05 18:01:22 +0100
commit73262ca616f0623a9715ceac90c17b0da4b320d7 (patch)
tree4624e5eec9329afdee0bfb67ccc64e9a935d4484 /primedev/server/ai_navmesh.h
parentedf013952ca2d110f190dc8cd16e5529846656e4 (diff)
downloadNorthstarLauncher-73262ca616f0623a9715ceac90c17b0da4b320d7.tar.gz
NorthstarLauncher-73262ca616f0623a9715ceac90c17b0da4b320d7.zip
Port navmesh debug renderer from primedev (#626)
Adds support for rendering navmeshes in-game using debug overlay Cherry-picked from primedev, originally written by F1F7Y Co-authored-by: F1F7Y <filip.bartos07@proton.me> Co-authored-by: Maya <11448698+RoyalBlue1@users.noreply.github.com>
Diffstat (limited to 'primedev/server/ai_navmesh.h')
-rw-r--r--primedev/server/ai_navmesh.h260
1 files changed, 260 insertions, 0 deletions
diff --git a/primedev/server/ai_navmesh.h b/primedev/server/ai_navmesh.h
new file mode 100644
index 00000000..65529f7a
--- /dev/null
+++ b/primedev/server/ai_navmesh.h
@@ -0,0 +1,260 @@
+#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;