/****************************************************************************** Use 'PathMesh' to specify a path mesh for a single area. Use 'PathWorld' for pathfinding on many 'PathMesh'es. Use 'PathObstacle' for temporary obstacles in 'PathWorld's. /******************************************************************************/ enum PATH_MESH_TYPE { PM_OBSTACLE, // can not be crossed PM_GROUND , // can be crossed if traveller supports PMF_WALK PM_WATER , // can be crossed if traveller supports PMF_SWIM #if EE_PRIVATE PM_BLOCKED=63, // covered by obstacles #endif }; enum PATH_MESH_FLAG { PMF_WALK=0x0001, PMF_SWIM=0x0002, }; /******************************************************************************/ struct PathSettings { Flt areaSize ()C {return _area_size;} PathSettings& areaSize (Flt size ); // get/set area size (in meters ), 0..Inf , default=32 Flt ctrlRadius()C {return _ctrl_r ;} PathSettings& ctrlRadius(Flt r ); // get/set controller radius (in meters ), 0..Inf , default=0.33f Flt ctrlHeight()C {return _ctrl_h ;} PathSettings& ctrlHeight(Flt h ); // get/set controller height (in meters ), 0..Inf , default=2.0f Flt maxClimb ()C {return _max_climb;} PathSettings& maxClimb (Flt climb); // get/set max climb height (in meters ), 0..Inf , default=0.7f Flt maxSlope ()C {return _max_slope;} PathSettings& maxSlope (Flt slope); // get/set max slope angle (in radians), 0..PI_2, default=PI_4 Flt cellSize ()C {return _cell_size;} PathSettings& cellSize (Flt size ); // get/set path cell size (in meters ), 0..Inf , default=1.0f/3 Flt cellHeight()C {return _cell_h ;} PathSettings& cellHeight(Flt h ); // get/set path cell height (in meters ), 0..Inf , default=0.1f // operations PathSettings& reset(); // reset to default settings Bool operator==(C PathSettings &path)C; // if settings are equal Bool operator!=(C PathSettings &path)C; // if settings are different // io Bool save(File &f)C; // save to file, false on fail Bool load(File &f) ; // load from file, false on fail PathSettings() {reset();} private: Flt _area_size, _ctrl_r, _ctrl_h, _max_climb, _max_slope, _cell_size, _cell_h; }; /******************************************************************************/ struct PathObstacle { // manage void del (); // delete manually , deleting an obstacle requires rebuilding path meshes (avoid calling this frequently as it may decrease performance) Bool create(C Shape &shape, C PathWorld &world); // create path obstacle from 'shape' in 'world', creating an obstacle requires rebuilding path meshes (avoid calling this frequently as it may decrease performance) // get / set Shape shape( ); // get obstacle shape, SHAPE_NONE on fail (if doesn't exist) void shape(C Shape &shape); // set obstacle shape, adjusting the shape of the obstacle requires rebuilding path meshes (avoid calling this frequently as it may decrease performance), only following shape types are supported: SHAPE_POINT, SHAPE_EDGE, SHAPE_BOX, SHAPE_BALL, SHAPE_CAPSULE, SHAPE_TUBE, SHAPE_OBOX, SHAPE_PYRAMID, attempting to set a different type of shape is equivalent to calling 'del' method ~PathObstacle() {del();} PathObstacle() {_world=null; _shape=null;} private: PathWorld *_world; Shape *_shape; NO_COPY_CONSTRUCTOR(PathObstacle); }; /******************************************************************************/ #if EE_PRIVATE struct RecastCompactHeightfield : rcCompactHeightfield { void del(); Bool is()C; void clean(); Bool save(File &f)C; Bool load(File &f) ; void operator=(C RecastCompactHeightfield &src); void zero() {Zero(T);} ~RecastCompactHeightfield() {del ();} RecastCompactHeightfield() {zero();} RecastCompactHeightfield(C RecastCompactHeightfield &src) {zero(); T=src;} }; const_mem_addr struct _PathMesh { VecI2 xy; PathWorld *world; Mems data, obstacle_data, chf_compressed; RecastCompactHeightfield chf; // manage void del(); // operations void link(PathWorld *world); void preSave(); // compress data needed for saving // get Bool is ()C; // if has any mesh data Box box () ; // get mesh world box Bool getChf() ; // get chf (decompress if needed), false on fail // io Bool save(File &f)C; // save to file, false on fail Bool load(File &f) ; // load from file, false on fail ~_PathMesh() {del();} _PathMesh() {xy.zero(); world=null;} NO_COPY_CONSTRUCTOR(_PathMesh); }; #endif /******************************************************************************/ struct PathMesh { // manage void del (); // delete manually Bool create(MeshBase &mesh, C VecI2 &area_xy, C PathSettings &settings); // build path mesh from source 'mesh', at 'area_xy' area coordinates using 'settings' path build settings, false on fail ("mesh.tri.flag" and "mesh.quad.flag" can be manually set to PATH_MESH_TYPE to specify the type of the face) // get Bool is()C; // if has any mesh data // operation void preSave(); // saving 'PathMesh' typically requires compressing some data, which may take some time, you can call this method at an earlier stage to compress and prepare the data so saving later will be without any delays, this method is optional and does not need to be called // io Bool save(File &f)C; // save to file, false on fail Bool load(File &f) ; // load from file, false on fail ~PathMesh(); PathMesh(); private: #if EE_PRIVATE friend struct PathWorld; _PathMesh *_pm; #else Ptr _pm; #endif NO_COPY_CONSTRUCTOR(PathMesh); }; /******************************************************************************/ const_mem_addr struct PathWorld // !! must be stored in constant memory address !! { // manage void del ( ); // delete manually Bool create(Flt area_size); // initialize path world manager, 'area_size'=size of a single area (in meters), false on fail // operations Bool set(PathMesh *path_mesh, C VecI2 &area_xy); // set 'path_mesh' at specified 'area_xy' area coordinates (can be null for no path mesh at that location) #if EE_PRIVATE Bool _set (_PathMesh *path_mesh, C VecI2 &area_xy, Bool set_obstacles); // set 'path_mesh' at specified 'area_xy' area coordinates (can be null for no path mesh at that location), 'set_obstacles'=if set obstacles on that mesh before setting it void update ( ); // update changes in obstacles by rebuilding affected path meshes void changed (C Shape &shape ); // call when 'shape' obstacle was changed in the world void threadFunc(); void zero (); VecI2 worldToArea(C Vec2 &xz )C {return Floor(xz/areaSize());} // convert World Position to Area Coordinates VecI2 worldToArea(C Vec &pos )C {return worldToArea(pos .xz());} // convert World Position to Area Coordinates RectI worldToArea(C Rect &rect )C {return RectI(worldToArea(rect.min), worldToArea(rect.max));} // convert World Position to Area Coordinates RectI worldToArea(C Box &box )C {return RectI(worldToArea(box .min), worldToArea(box .max));} // convert World Position to Area Coordinates Box obstacleBox(C Shape &shape )C; _PathMesh* pathMesh (C VecI2 &area_xy)C; // get PathMesh at 'area_xy' area coordinates #endif // get Flt areaSize()C {return _area_size;} // get area size Bool find(C Vec &start, C Vec &end, MemPtr path, Int max_steps=-1, UInt walkable_flags=PMF_WALK, Bool allow_partial_paths=true, C Vec &end_extents=Vec(1, 16, 1))C; // find path from 'start' to 'end' world position, 'max_steps'=maximum number of allowed steps in the result path (use <=0 for unlimited), 'walkable_flags'=faces that are walkable (PATH_MESH_FLAG), 'allow_partial_paths'=if there is no direct path from 'start' to 'end' then return partial path to the point closest to the 'end', false on fail (path not found), 'end_extents'=extents used to find nearest walkable surface to the 'end' point Bool nearestSurface(C Vec &pos, C Vec &extents, Vec &surface_pos, UInt walkable_flags=PMF_WALK)C; // find nearest point on path surface, 'pos'=center position of the search, 'extents'=maximum distance to search in each dimension, 'surface_pos'=output position, 'walkable_flags'=faces that are walkable (PATH_MESH_FLAG), false on fail (point not found) Bool nearestWall(C Vec &pos, Flt max_distance, Flt *hit_distance=null, Vec *hit_pos=null, Vec *hit_normal=null, UInt walkable_flags=PMF_WALK)C; // calculate distance to nearest wall from 'pos' position, 'max_distance'=maximum distance to perform the search, 'hit_distance'=distance to wall, 'hit_pos'=hit position, 'hit_normal'=hit normal, 'walkable_flags'=faces that are walkable (PATH_MESH_FLAG), false on fail (wall not found) Bool ray(C Vec &start, C Vec &end, Flt *hit_frac=null, Vec *hit_pos=null, Vec *hit_normal=null, UInt walkable_flags=PMF_WALK)C; // perform a ray test on the path surface starting from 'start' towards 'end', 'hit_frac'=fraction of the movement (0..1), 'hit_pos'=hit position, 'hit_normal'=hit normal, 'walkable_flags'=faces that are walkable (PATH_MESH_FLAG), false on fail (no hit occurred) // draw void draw(Byte surface_color_alpha=64, Flt y_offset=0, C Color &outer_edge_color=Color(0,48,64,220), C Color &inner_edge_color=Color(0,48,64,32))C; // 'y_offset'=vertical offset applied when drawing paths (can be set to positive value to draw the paths above the ground, so they will not be occluded by ground meshes) ~PathWorld() {del();} PathWorld(); #if !EE_PRIVATE private: #endif Flt _area_size, _ctrl_r, _ctrl_h, _max_climb; #if EE_PRIVATE struct Build { RecastCompactHeightfield chf; Mems shapes; VecI2 xy; Ptr user; }; struct Built { Mems data; VecI2 xy; Ptr user; }; dtNavMesh *_mesh; dtNavMeshQuery *_query; dtQueryFilter *_filter; Memc<_PathMesh*> _changed; Memc _build; Memc _built; #else Ptr _mesh, _query, _filter; _Memc _changed, _build, _built; #endif Memx _obstacles; Thread _thread; SyncEvent _event; SyncLock _lock; NO_COPY_CONSTRUCTOR(PathWorld); }; /******************************************************************************/