305c61e5eb569e03246e08e7241bb092e8beacee
[blender.git] / extern / recastnavigation / Detour / Include / DetourTileNavMesh.h
1 //
2 // Copyright (c) 2009 Mikko Mononen memon@inside.org
3 //
4 // This software is provided 'as-is', without any express or implied
5 // warranty.  In no event will the authors be held liable for any damages
6 // arising from the use of this software.
7 // Permission is granted to anyone to use this software for any purpose,
8 // including commercial applications, and to alter it and redistribute it
9 // freely, subject to the following restrictions:
10 // 1. The origin of this software must not be misrepresented; you must not
11 //    claim that you wrote the original software. If you use this software
12 //    in a product, an acknowledgment in the product documentation would be
13 //    appreciated but is not required.
14 // 2. Altered source versions must be plainly marked as such, and must not be
15 //    misrepresented as being the original software.
16 // 3. This notice may not be removed or altered from any source distribution.
17 //
18
19 #ifndef DETOURTILENAVMESH_H
20 #define DETOURTILENAVMESH_H
21
22 // Reference to navigation polygon.
23 typedef unsigned int dtTilePolyRef;
24
25 // The bits used in the poly ref.
26 static const int DT_TILE_REF_SALT_BITS = 12;
27 static const int DT_TILE_REF_TILE_BITS = 12;
28 static const int DT_TILE_REF_POLY_BITS = 8;
29 static const int DT_TILE_REF_SALT_MASK = (1<<DT_TILE_REF_SALT_BITS)-1;
30 static const int DT_TILE_REF_TILE_MASK = (1<<DT_TILE_REF_TILE_BITS)-1;
31 static const int DT_TILE_REF_POLY_MASK = (1<<DT_TILE_REF_POLY_BITS)-1;
32
33 // Maximum number of vertices per navigation polygon.
34 static const int DT_TILE_VERTS_PER_POLYGON = 6;
35
36 static const int DT_MAX_TILES = 1 << DT_TILE_REF_TILE_BITS;
37 static const int DT_MAX_POLYGONS = 1 << DT_TILE_REF_POLY_BITS;
38
39 static const int DT_TILE_NAVMESH_MAGIC = (('N'<<24) | ('A'<<16) | ('V'<<8) | 'M');
40 static const int DT_TILE_NAVMESH_VERSION = 2;
41
42 // Structure holding the navigation polygon data.
43 struct dtTilePoly
44 {
45         unsigned short v[DT_TILE_VERTS_PER_POLYGON];    // Indices to vertices of the poly.
46         unsigned short n[DT_TILE_VERTS_PER_POLYGON];    // Refs to neighbours of the poly.
47         unsigned short links;                                                   // Base index to header 'links' array. 
48         unsigned char nlinks;                                                   // Number of links for 
49         unsigned char nv;                                                               // Number of vertices.
50         unsigned char flags;                                                    // Flags (not used).
51 };
52
53 struct dtTilePolyDetail
54 {
55         unsigned short vbase;   // Offset to detail vertex array.
56         unsigned short nverts;  // Number of vertices in the detail mesh.
57         unsigned short tbase;   // Offset to detail triangle array.
58         unsigned short ntris;   // Number of triangles.
59 };
60
61 // Stucture holding a link to another polygon.
62 struct dtTileLink
63 {
64         dtTilePolyRef ref;                      // Neighbour reference.
65         unsigned short p;                       // Index to polygon which owns this link.
66         unsigned char e;                        // Index to polygon edge which owns this link. 
67         unsigned char side;                     // If boundary link, defines on which side the link is.
68         unsigned char bmin, bmax;       // If boundary link, defines the sub edge area.
69 };
70
71 struct dtTileHeader
72 {
73         int magic;                                      // Magic number, used to identify the data.
74         int version;                            // Data version number.
75         int npolys;                                     // Number of polygons in the tile.
76         int nverts;                                     // Number of vertices in the tile.
77         int nlinks;                                     // Number of links in the tile (will be updated when tile is added).
78         int maxlinks;                           // Number of allocated links.
79         int ndmeshes;
80         int ndverts;
81         int ndtris;
82         float bmin[3], bmax[3];         // Bounding box of the tile.
83         dtTilePoly* polys;                      // Pointer to the polygons (will be updated when tile is added).
84         float* verts;                           // Pointer to the vertices (will be updated when tile added).
85         dtTileLink* links;                      // Pointer to the links (will be updated when tile added).
86         dtTilePolyDetail* dmeshes;
87         float* dverts;
88         unsigned char* dtris;
89 };
90
91 struct dtTile
92 {
93         int salt;                               // Counter describing modifications to the tile.
94         int x,y;                                // Grid location of the tile.
95         dtTileHeader* header;   // Pointer to tile header.
96         unsigned char* data;    // Pointer to tile data.
97         int dataSize;                   // Size of the tile data.
98         bool ownsData;                  // Flag indicating of the navmesh should release the data.
99         dtTile* next;                   // Next free tile or, next tile in spatial grid.
100 };
101
102 // Encodes a tile id.
103 inline dtTilePolyRef dtEncodeTileId(unsigned int salt, unsigned int it, unsigned int ip)
104 {
105         return (salt << (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) | ((it+1) << DT_TILE_REF_POLY_BITS) | ip;
106 }
107
108 // Decodes a tile id.
109 inline void dtDecodeTileId(dtTilePolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip)
110 {
111         salt = (ref >> (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) & DT_TILE_REF_SALT_MASK;
112         it = ((ref >> DT_TILE_REF_POLY_BITS) & DT_TILE_REF_TILE_MASK) - 1;
113         ip = ref & DT_TILE_REF_POLY_MASK;
114 }
115
116 static const int DT_TILE_LOOKUP_SIZE = DT_MAX_TILES/4;
117
118 class dtTiledNavMesh
119 {
120 public:
121         dtTiledNavMesh();
122         ~dtTiledNavMesh();
123
124         // Initializes the nav mesh.
125         // Params:
126         //  orig - (in) origin of the nav mesh tile space.
127         //  tileSiz - (in) size of a tile.
128         //  portalheight - (in) height of the portal region between tiles.
129         // Returns: True if succeed, else false.
130         bool init(const float* orig, float tileSize, float portalHeight);
131
132         // Adds new tile into the navmesh.
133         // The add will fail if the data is in wrong format,
134         // there is not enough tiles left, or if there is a tile already at the location.
135         // Params:
136         //  x,y - (in) Location of the new tile.
137         //  data - (in) Data of the new tile mesh.
138         //  dataSize - (in) Data size of the new tile mesh.
139         //      ownsData - (in) Flag indicating if the navmesh should own and delete the data.
140         // Returns: True if tile was added, else false. 
141         bool addTileAt(int x, int y, unsigned char* data, int dataSize, bool ownsData);
142         
143         // Removes tile at specified location.
144         // Params:
145         //  x,y - (in) Location of the tile to remove.
146         //  data - (out) Data associated with deleted tile.
147         //  dataSize - (out) Size of the data associated with deleted tile. 
148         // Returns: True if remove suceed, else false.
149         bool removeTileAt(int x, int y, unsigned char** data, int* dataSize);
150
151         // Returns pointer to tile at specified location.
152         // Params:
153         //  x,y - (in) Location of the tile to get.
154         // Returns: pointer to tile if tile exists or 0 tile does not exists.
155         dtTile* getTileAt(int x, int y);
156
157         // Returns pointer to tile in the tile array.
158         // Params:
159         //  i - (in) Index to the tile to retrieve, must be in range [0,DT_MAX_TILES[
160         // Returns: Pointer to specified tile.
161         dtTile* getTile(int i);
162         const dtTile* getTile(int i) const;
163         
164         // Finds the nearest navigation polygon around the center location.
165         // Params:
166         //      center - (in) The center of the search box.
167         //      extents - (in) The extents of the search box.
168         // Returns: Reference identifier for the polygon, or 0 if no polygons found.
169         dtTilePolyRef findNearestPoly(const float* center, const float* extents);
170         
171         // Returns polygons which touch the query box.
172         // Params:
173         //      center - (in) the center of the search box.
174         //      extents - (in) the extents of the search box.
175         //      polys - (out) array holding the search result.
176         //      maxPolys - (in) The max number of polygons the polys array can hold.
177         // Returns: Number of polygons in search result array.
178         int queryPolygons(const float* center, const float* extents,
179                                           dtTilePolyRef* polys, const int maxPolys);
180         
181         // Finds path from start polygon to end polygon.
182         // If target polygon canno be reached through the navigation graph,
183         // the last node on the array is nearest node to the end polygon.
184         // Params:
185         //      startRef - (in) ref to path start polygon.
186         //      endRef - (in) ref to path end polygon.
187         //      path - (out) array holding the search result.
188         //      maxPathSize - (in) The max number of polygons the path array can hold.
189         // Returns: Number of polygons in search result array.
190         int findPath(dtTilePolyRef startRef, dtTilePolyRef endRef,
191                                  const float* startPos, const float* endPos,
192                                  dtTilePolyRef* path, const int maxPathSize);
193
194         // Finds a straight path from start to end locations within the corridor
195         // described by the path polygons.
196         // Start and end locations will be clamped on the corridor.
197         // Params:
198         //      startPos - (in) Path start location.
199         //      endPos - (in) Path end location.
200         //      path - (in) Array of connected polygons describing the corridor.
201         //      pathSize - (in) Number of polygons in path array.
202         //      straightPath - (out) Points describing the straight path.
203         //      maxStraightPathSize - (in) The max number of points the straight path array can hold.
204         // Returns: Number of points in the path.
205         int findStraightPath(const float* startPos, const float* endPos,
206                                                  const dtTilePolyRef* path, const int pathSize,
207                                                  float* straightPath, const int maxStraightPathSize);
208
209         // Finds intersection againts walls starting from start pos.
210         // Params:
211         //      startRef - (in) ref to the polygon where the start lies.
212         //      startPos - (in) start position of the query.
213         //      endPos - (in) end position of the query.
214         //      t - (out) hit parameter along the segment, 0 if no hit.
215         //      endRef - (out) ref to the last polygon which was processed.
216         // Returns: Number of polygons in path or 0 if failed.
217         int raycast(dtTilePolyRef startRef, const float* startPos, const float* endPos,
218                                 float& t, dtTilePolyRef* path, const int pathSize);
219
220         // Returns distance to nearest wall from the specified location.
221         // Params:
222         //      centerRef - (in) ref to the polygon where the center lies.
223         //      centerPos - (in) center if the query circle.
224         //      maxRadius - (in) max search radius.
225         //      hitPos - (out) location of the nearest hit.
226         //      hitNormal - (out) normal of the nearest hit.
227         // Returns: Distance to nearest wall from the test location.
228         float findDistanceToWall(dtTilePolyRef centerRef, const float* centerPos, float maxRadius,
229                                                          float* hitPos, float* hitNormal);
230
231         // Finds polygons found along the navigation graph which touch the specified circle.
232         // Params:
233         //      centerRef - (in) ref to the polygon where the center lies.
234         //      centerPos - (in) center if the query circle
235         //      radius - (in) radius of the query circle
236         //      resultRef - (out, opt) refs to the polygons touched by the circle.
237         //      resultParent - (out, opt) parent of each result polygon.
238         //      resultCost - (out, opt) search cost at each result polygon.
239         //      maxResult - (int) maximum capacity of search results.
240         // Returns: Number of results.
241         int     findPolysAround(dtTilePolyRef centerRef, const float* centerPos, float radius,
242                                                 dtTilePolyRef* resultRef, dtTilePolyRef* resultParent, float* resultCost,
243                                                 const int maxResult);
244         
245         // Returns closest point on navigation polygon.
246         // Params:
247         //      ref - (in) ref to the polygon.
248         //      pos - (in) the point to check.
249         //      closest - (out) closest point.
250         // Returns: true if closest point found.
251         bool closestPointToPoly(dtTilePolyRef ref, const float* pos, float* closest) const;
252
253         // Returns height of the polygon at specified location.
254         // Params:
255         //      ref - (in) ref to the polygon.
256         //      pos - (in) the point where to locate the height.
257         //      height - (out) height at the location.
258         // Returns: true if over polygon.
259         bool getPolyHeight(dtTilePolyRef ref, const float* pos, float* height) const;
260         
261         // Returns pointer to a polygon based on ref.
262         const dtTilePoly* getPolyByRef(dtTilePolyRef ref) const;
263
264         // Returns pointer to a polygon vertices based on ref.
265         const float* getPolyVertsByRef(dtTilePolyRef ref) const;
266
267         // Returns pointer to a polygon link based on ref.
268         const dtTileLink* getPolyLinksByRef(dtTilePolyRef ref) const;
269         
270 private:
271
272         // Returns base id for the tile.
273         dtTilePolyRef getTileId(dtTile* tile);
274         // Returns neighbour tile based on side. 
275         dtTile* getNeighbourTileAt(int x, int y, int side);
276         // Returns all polygons in neighbour tile based on portal defined by the segment.
277         int findConnectingPolys(const float* va, const float* vb,
278                                                         dtTile* tile, int side,
279                                                         dtTilePolyRef* con, float* conarea, int maxcon);
280         // Builds internal polygons links for a tile.
281         void buildIntLinks(dtTile* tile);
282         // Builds external polygon links for a tile.
283         void buildExtLinks(dtTile* tile, dtTile* target, int side);
284         // Removes external links at specified side.
285         void removeExtLinks(dtTile* tile, int side);
286         // Queries polygons within a tile.
287         int queryTilePolygons(dtTile* tile, const float* qmin, const float* qmax,
288                                                   dtTilePolyRef* polys, const int maxPolys);
289                                                   
290         float getCost(dtTilePolyRef prev, dtTilePolyRef from, dtTilePolyRef to) const;
291         float getFirstCost(const float* pos, dtTilePolyRef from, dtTilePolyRef to) const;
292         float getLastCost(dtTilePolyRef from, dtTilePolyRef to, const float* pos) const;
293         float getHeuristic(const float* from, const float* to) const;
294         
295         // Returns portal points between two polygons.
296         bool getPortalPoints(dtTilePolyRef from, dtTilePolyRef to, float* left, float* right) const;
297         // Returns edge mid point between two polygons.
298         bool getEdgeMidPoint(dtTilePolyRef from, dtTilePolyRef to, float* mid) const;
299
300         float m_orig[3];
301         float m_tileSize;
302         float m_portalHeight;
303
304         dtTile* m_posLookup[DT_TILE_LOOKUP_SIZE];
305         dtTile* m_nextFree;
306         dtTile m_tiles[DT_MAX_TILES];
307         
308         dtTileLink* m_tmpLinks;
309         int m_ntmpLinks;
310
311         class dtNodePool* m_nodePool;
312         class dtNodeQueue* m_openList;
313 };
314
315 #endif // DETOURTILENAVMESH_H