109 lines
4.4 KiB
C++
109 lines
4.4 KiB
C++
// Copyright (C) 2007 Id Software, Inc.
|
|
//
|
|
|
|
#ifndef __OBSTACLEAVOIDANCE_H__
|
|
#define __OBSTACLEAVOIDANCE_H__
|
|
|
|
/*
|
|
================================================================================
|
|
|
|
idObstacleAvoidance
|
|
|
|
================================================================================
|
|
*/
|
|
|
|
class idAAS;
|
|
|
|
class idObstacleAvoidance {
|
|
public:
|
|
static const int OBSTACLE_ID_INVALID = -1;
|
|
|
|
struct obstaclePath_t {
|
|
idVec3 seekPos; // seek position avoiding obstacles
|
|
idVec3 originalSeekPos; // original, non-capped seek pos
|
|
float targetDist; // how close the path around obstacles gets to the target
|
|
int firstObstacle; // if != OBSTACLE_ID_INVALID the first obstacle along the path
|
|
idVec3 startPosOutsideObstacles; // start position outside obstacles
|
|
int startPosObstacle; // if != OBSTACLE_ID_INVALID the obstacle containing the start position
|
|
idVec3 seekPosOutsideObstacles; // seek position outside obstacles
|
|
int seekPosObstacle; // if != OBSTACLE_ID_INVALID the obstacle containing the seek position
|
|
float pathLength; // length of the path
|
|
bool hasValidPath; //mal: did we find a valid path?
|
|
};
|
|
|
|
|
|
public:
|
|
idObstacleAvoidance( void ) { }
|
|
~idObstacleAvoidance( void ) { pathNodeAllocator.Shutdown(); }
|
|
|
|
void ClearObstacles( void );
|
|
void AddObstacle( const idBox &box, int id );
|
|
void RemoveObstacle( int id );
|
|
|
|
bool FindPathAroundObstacles( const idBounds &bounds, const float radius, const idAAS *aas, const idVec3 &startPos, const idVec3 &seekPos, obstaclePath_t &path, bool alwaysAvoidObstacles = false );
|
|
bool PointInObstacles( const idBounds &bounds, const float radius, const idAAS *aas, const idVec3 &pos );
|
|
|
|
bool SaveLastQuery( const char *fileName );
|
|
bool TestQuery( const char *fileName, const idAAS *aas );
|
|
|
|
private:
|
|
static const float PUSH_OUTSIDE_OBSTACLES;
|
|
static const float CLIP_BOUNDS_EPSILON;
|
|
static const int MAX_AAS_WALL_EDGES = 256;
|
|
static const int MAX_PATH_NODES = 256;
|
|
static const int MAX_OBSTACLE_PATH = 128;
|
|
|
|
struct obstacle_t {
|
|
idBox box; // oriented bounding box representing the obstacle
|
|
idVec2 bounds[2]; // two-dimensional bounds (in x-y plane) for obstacle
|
|
idWinding2D winding; // two-dimensional winding (in x-y plane) for obstacle
|
|
int id; // obstacle id
|
|
};
|
|
|
|
struct pathNode_t {
|
|
int dir;
|
|
idVec2 pos;
|
|
idVec2 delta;
|
|
float dist;
|
|
int obstacle;
|
|
int edgeNum;
|
|
int numNodes;
|
|
pathNode_t * parent;
|
|
pathNode_t * children[2];
|
|
idQueueNode<pathNode_t> queueNode;
|
|
void Init();
|
|
};
|
|
|
|
struct query_t {
|
|
idBounds bounds;
|
|
float radius;
|
|
idVec3 startPos;
|
|
idVec3 seekPos;
|
|
};
|
|
|
|
private:
|
|
bool LineIntersectsPath( const idVec2 &start, const idVec2 &end, const pathNode_t *node ) const;
|
|
int PointInsideObstacle( const idVec2 &point ) const;
|
|
bool LineIntersectsWall( const idVec2 &start, const idVec2 &end ) const;
|
|
void GetPointOutsideObstacles( idVec2 &point, int *obstacle, int *edgeNum );
|
|
bool GetFirstBlockingObstacle( int skipObstacle, const idVec2 &startPos,const idVec2 &delta, float &blockingScale, int &blockingObstacle, int &blockingEdgeNum );
|
|
void ProjectTopDown( idVec3 &point ) const;
|
|
void DrawBox() const;
|
|
int GetObstacles( const idBounds &bounds, float radius, const idAAS *aas, int areaNum, const idVec3 &startPos, const idVec3 &seekPos, idBounds &clipBounds );
|
|
void FreePathTree_r( pathNode_t *node );
|
|
void DrawPathTree( const pathNode_t *root, const float height );
|
|
bool GetPathNodeDelta( pathNode_t *node, const idVec2 &seekPos, bool blocked );
|
|
pathNode_t* BuildPathTree( const idBounds &clipBounds, const idVec2 &startPos, const idVec2 &seekPos, obstaclePath_t &path );
|
|
void PrunePathTree( pathNode_t *root, const idVec2 &seekPos );
|
|
int OptimizePath( const pathNode_t *root, const pathNode_t *leafNode, idVec2 optimizedPath[MAX_OBSTACLE_PATH] );
|
|
float PathLength( const idVec2 optimizedPath[MAX_OBSTACLE_PATH], int numPathPoints, const idVec2 &curDir );
|
|
void FindOptimalPath( const pathNode_t *root, const float height, const idVec3 &curDir, idVec3 &seekPos, float & targetDist, float &pathLength );
|
|
|
|
private:
|
|
idList<obstacle_t> obstacles;
|
|
idBlockAlloc<pathNode_t, 128> pathNodeAllocator;
|
|
|
|
query_t lastQuery;
|
|
};
|
|
|
|
#endif /* __OBSTACLEAVOIDANCE_H__ */
|