#include <PathGenerator.h>

Public Member Functions
	PathGenerator (Unit const *owner)

	~PathGenerator ()

bool	CalculatePath (float destX, float destY, float destZ, bool forceDest=false, bool straightLine=false)

void	SetUseStraightPath (bool useStraightPath)

void	SetPathLengthLimit (float distance)

G3D::Vector3 const &	GetStartPosition () const

G3D::Vector3 const &	GetEndPosition () const

G3D::Vector3 const &	GetActualEndPosition () const

Movement::PointsArray const &	GetPath () const

PathType	GetPathType () const

void	ReducePathLenghtByDist (float dist)

Private Member Functions
void	SetStartPosition (G3D::Vector3 const &point)

void	SetEndPosition (G3D::Vector3 const &point)

void	SetActualEndPosition (G3D::Vector3 const &point)

void	NormalizePath ()

void	Clear ()

bool	InRange (G3D::Vector3 const &p1, G3D::Vector3 const &p2, float r, float h) const

float	Dist3DSqr (G3D::Vector3 const &p1, G3D::Vector3 const &p2) const

bool	InRangeYZX (float const v1, float const v2, float r, float h) const

dtPolyRef	GetPathPolyByPosition (dtPolyRef const polyPath, uint32 polyPathSize, float const Point, float *Distance=NULL) const

dtPolyRef	GetPolyByLocation (float const Point, float Distance) const

bool	HaveTile (G3D::Vector3 const &p) const

void	BuildPolyPath (G3D::Vector3 const &startPos, G3D::Vector3 const &endPos)

void	BuildPointPath (float const startPoint, float const endPoint)

void	BuildShortcut ()

NavTerrain	GetNavTerrain (float x, float y, float z)

void	CreateFilter ()

void	UpdateFilter ()

uint32	FixupCorridor (dtPolyRef path, uint32 npath, uint32 maxPath, dtPolyRef const visited, uint32 nvisited)

bool	GetSteerTarget (float const startPos, float const endPos, float minTargetDist, dtPolyRef const path, uint32 pathSize, float steerPos, unsigned char &steerPosFlag, dtPolyRef &steerPosRef)

dtStatus	FindSmoothPath (float const startPos, float const endPos, dtPolyRef const polyPath, uint32 polyPathSize, float smoothPath, int *smoothPathSize, uint32 smoothPathMaxSize)

Constructor & Destructor Documentation

PathGenerator::PathGenerator ( Unit const * owner )

explicit

  :
  _polyLength(0), _type(PATHFIND_BLANK), _useStraightPath(false),
  _forceDestination(false), _pointPathLimit(MAX_POINT_PATH_LENGTH), _straightLine(false),
  _endPosition(G3D::Vector3::zero()), _sourceUnit(owner), _navMesh(NULL),
  _navMeshQuery(NULL)
 {
  memset(_pathPolyRefs, 0, sizeof(_pathPolyRefs));
 
  TC_LOG_DEBUG("maps", "++ PathGenerator::PathGenerator for %s", _sourceUnit->GetGUID().ToString().c_str());
 
  uint32 mapId = _sourceUnit->GetMapId();
  if (DisableMgr::IsPathfindingEnabled(mapId))
  {
  MMAP::MMapManager* mmap = MMAP::MMapFactory::createOrGetMMapManager();
  _navMesh = mmap->GetNavMesh(mapId, _sourceUnit->GetTerrainSwaps());
  _navMeshQuery = mmap->GetNavMeshQuery(mapId, _sourceUnit->GetInstanceId(), _sourceUnit->GetTerrainSwaps());
  }
 
  CreateFilter();
 }

Here is the call graph for this function:

PathGenerator::~PathGenerator ( )

 {
  TC_LOG_DEBUG("maps", "++ PathGenerator::~PathGenerator() for %s", _sourceUnit->GetGUID().ToString().c_str());
 }

Here is the call graph for this function:

Member Function Documentation

void PathGenerator::BuildPointPath	(	float const *	startPoint,
		float const *	endPoint
	)

private

Todo:: check the exact cases

 {
  float pathPoints[MAX_POINT_PATH_LENGTH*VERTEX_SIZE];
  uint32 pointCount = 0;
  dtStatus dtResult = DT_FAILURE;
  if (_straightLine)
  {
  dtResult = DT_SUCCESS;
  pointCount = 1;
  memcpy(&pathPoints[VERTEX_SIZE * 0], startPoint, sizeof(float)* 3); // first point
 
  // path has to be split into polygons with dist SMOOTH_PATH_STEP_SIZE between them
  G3D::Vector3 startVec = G3D::Vector3(startPoint[0], startPoint[1], startPoint[2]);
  G3D::Vector3 endVec = G3D::Vector3(endPoint[0], endPoint[1], endPoint[2]);
  G3D::Vector3 diffVec = (endVec - startVec);
  G3D::Vector3 prevVec = startVec;
  float len = diffVec.length();
  diffVec *= SMOOTH_PATH_STEP_SIZE / len;
  while (len > SMOOTH_PATH_STEP_SIZE)
  {
  len -= SMOOTH_PATH_STEP_SIZE;
  prevVec += diffVec;
  pathPoints[VERTEX_SIZE * pointCount + 0] = prevVec.x;
  pathPoints[VERTEX_SIZE * pointCount + 1] = prevVec.y;
  pathPoints[VERTEX_SIZE * pointCount + 2] = prevVec.z;
  ++pointCount;
  }
 
  memcpy(&pathPoints[VERTEX_SIZE * pointCount], endPoint, sizeof(float)* 3); // last point
  ++pointCount;
  }
  else if (_useStraightPath)
  {
  dtResult = _navMeshQuery->findStraightPath(
  startPoint, // start position
  endPoint, // end position
  _pathPolyRefs, // current path
  _polyLength, // lenth of current path
  pathPoints, // [out] path corner points
  NULL, // [out] flags
  NULL, // [out] shortened path
  (int*)&pointCount,
  _pointPathLimit); // maximum number of points/polygons to use
  }
  else
  {
  dtResult = FindSmoothPath(
  startPoint, // start position
  endPoint, // end position
  _pathPolyRefs, // current path
  _polyLength, // length of current path
  pathPoints, // [out] path corner points
  (int*)&pointCount,
  _pointPathLimit); // maximum number of points
  }
 
  if (pointCount < 2 || dtStatusFailed(dtResult))
  {
  // only happens if pass bad data to findStraightPath or navmesh is broken
  // single point paths can be generated here
  TC_LOG_DEBUG("maps", "++ PathGenerator::BuildPointPath FAILED! path sized %d returned\n", pointCount);
  BuildShortcut();
  _type = PATHFIND_NOPATH;
  return;
  }
  else if (pointCount == _pointPathLimit)
  {
  TC_LOG_DEBUG("maps", "++ PathGenerator::BuildPointPath FAILED! path sized %d returned, lower than limit set to %d\n", pointCount, _pointPathLimit);
  BuildShortcut();
  _type = PATHFIND_SHORT;
  return;
  }
 
  _pathPoints.resize(pointCount);
  for (uint32 i = 0; i < pointCount; ++i)
  _pathPoints[i] = G3D::Vector3(pathPoints[i*VERTEX_SIZE+2], pathPoints[i*VERTEX_SIZE], pathPoints[i*VERTEX_SIZE+1]);
 
  NormalizePath();
 
  // first point is always our current location - we need the next one
  SetActualEndPosition(_pathPoints[pointCount-1]);
 
  // force the given destination, if needed
  if (_forceDestination &&
  (!(_type & PATHFIND_NORMAL) || !InRange(GetEndPosition(), GetActualEndPosition(), 1.0f, 1.0f)))
  {
  // we may want to keep partial subpath
  if (Dist3DSqr(GetActualEndPosition(), GetEndPosition()) < 0.3f * Dist3DSqr(GetStartPosition(), GetEndPosition()))
  {
  SetActualEndPosition(GetEndPosition());
  _pathPoints[_pathPoints.size()-1] = GetEndPosition();
  }
  else
  {
  SetActualEndPosition(GetEndPosition());
  BuildShortcut();
  }
 
  _type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH);
  }
 
  TC_LOG_DEBUG("maps", "++ PathGenerator::BuildPointPath path type %d size %d poly-size %d\n", _type, pointCount, _polyLength);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void PathGenerator::BuildPolyPath	(	G3D::Vector3 const &	startPos,
		G3D::Vector3 const &	endPos
	)

private

Todo:: we can merge it with getPathPolyByPosition() loop

Todo:: play with the values here

 {
  // *** getting start/end poly logic ***
 
  float distToStartPoly, distToEndPoly;
  float startPoint[VERTEX_SIZE] = {startPos.y, startPos.z, startPos.x};
  float endPoint[VERTEX_SIZE] = {endPos.y, endPos.z, endPos.x};
 
  dtPolyRef startPoly = GetPolyByLocation(startPoint, &distToStartPoly);
  dtPolyRef endPoly = GetPolyByLocation(endPoint, &distToEndPoly);
 
  // we have a hole in our mesh
  // make shortcut path and mark it as NOPATH ( with flying and swimming exception )
  // its up to caller how he will use this info
  if (startPoly == INVALID_POLYREF || endPoly == INVALID_POLYREF)
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: (startPoly == 0 || endPoly == 0)\n");
  BuildShortcut();
  bool path = _sourceUnit->GetTypeId() == TYPEID_UNIT && _sourceUnit->ToCreature()->CanFly();
 
  bool waterPath = _sourceUnit->GetTypeId() == TYPEID_UNIT && _sourceUnit->ToCreature()->CanSwim();
  if (waterPath)
  {
  // Check both start and end points, if they're both in water, then we can *safely* let the creature move
  for (uint32 i = 0; i < _pathPoints.size(); ++i)
  {
  ZLiquidStatus status = _sourceUnit->GetBaseMap()->getLiquidStatus(_pathPoints[i].x, _pathPoints[i].y, _pathPoints[i].z, MAP_ALL_LIQUIDS, NULL);
  // One of the points is not in the water, cancel movement.
  if (status == LIQUID_MAP_NO_WATER)
  {
  waterPath = false;
  break;
  }
  }
  }
 
  _type = (path || waterPath) ? PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH) : PATHFIND_NOPATH;
  return;
  }
 
  // we may need a better number here
  bool farFromPoly = (distToStartPoly > 7.0f || distToEndPoly > 7.0f);
  if (farFromPoly)
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: farFromPoly distToStartPoly=%.3f distToEndPoly=%.3f\n", distToStartPoly, distToEndPoly);
 
  bool buildShotrcut = false;
  if (_sourceUnit->GetTypeId() == TYPEID_UNIT)
  {
  Creature* owner = (Creature*)_sourceUnit;
 
  G3D::Vector3 const& p = (distToStartPoly > 7.0f) ? startPos : endPos;
  if (_sourceUnit->GetBaseMap()->IsUnderWater(p.x, p.y, p.z))
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: underWater case\n");
  if (owner->CanSwim())
  buildShotrcut = true;
  }
  else
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: flying case\n");
  if (owner->CanFly())
  buildShotrcut = true;
  }
  }
 
  if (buildShotrcut)
  {
  BuildShortcut();
  _type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH);
  return;
  }
  else
  {
  float closestPoint[VERTEX_SIZE];
  // we may want to use closestPointOnPolyBoundary instead
  if (dtStatusSucceed(_navMeshQuery->closestPointOnPoly(endPoly, endPoint, closestPoint, NULL)))
  {
  dtVcopy(endPoint, closestPoint);
  SetActualEndPosition(G3D::Vector3(endPoint[2], endPoint[0], endPoint[1]));
  }
 
  _type = PATHFIND_INCOMPLETE;
  }
  }
 
  // *** poly path generating logic ***
 
  // start and end are on same polygon
  // just need to move in straight line
  if (startPoly == endPoly)
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: (startPoly == endPoly)\n");
 
  BuildShortcut();
 
  _pathPolyRefs[0] = startPoly;
  _polyLength = 1;
 
  _type = farFromPoly ? PATHFIND_INCOMPLETE : PATHFIND_NORMAL;
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: path type %d\n", _type);
  return;
  }
 
  // look for startPoly/endPoly in current path
  bool startPolyFound = false;
  bool endPolyFound = false;
  uint32 pathStartIndex = 0;
  uint32 pathEndIndex = 0;
 
  if (_polyLength)
  {
  for (; pathStartIndex < _polyLength; ++pathStartIndex)
  {
  // here to catch few bugs
  if (_pathPolyRefs[pathStartIndex] == INVALID_POLYREF)
  {
  TC_LOG_ERROR("maps", "Invalid poly ref in BuildPolyPath. _polyLength: %u, pathStartIndex: %u,"
  " startPos: %s, endPos: %s, mapid: %u",
  _polyLength, pathStartIndex, startPos.toString().c_str(), endPos.toString().c_str(),
  _sourceUnit->GetMapId());
 
  break;
  }
 
  if (_pathPolyRefs[pathStartIndex] == startPoly)
  {
  startPolyFound = true;
  break;
  }
  }
 
  for (pathEndIndex = _polyLength-1; pathEndIndex > pathStartIndex; --pathEndIndex)
  if (_pathPolyRefs[pathEndIndex] == endPoly)
  {
  endPolyFound = true;
  break;
  }
  }
 
  if (startPolyFound && endPolyFound)
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: (startPolyFound && endPolyFound)\n");
 
  // we moved along the path and the target did not move out of our old poly-path
  // our path is a simple subpath case, we have all the data we need
  // just "cut" it out
 
  _polyLength = pathEndIndex - pathStartIndex + 1;
  memmove(_pathPolyRefs, _pathPolyRefs + pathStartIndex, _polyLength * sizeof(dtPolyRef));
  }
  else if (startPolyFound && !endPolyFound)
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: (startPolyFound && !endPolyFound)\n");
 
  // we are moving on the old path but target moved out
  // so we have atleast part of poly-path ready
 
  _polyLength -= pathStartIndex;
 
  // try to adjust the suffix of the path instead of recalculating entire length
  // at given interval the target cannot get too far from its last location
  // thus we have less poly to cover
  // sub-path of optimal path is optimal
 
  // take ~80% of the original length
  uint32 prefixPolyLength = uint32(_polyLength * 0.8f + 0.5f);
  memmove(_pathPolyRefs, _pathPolyRefs+pathStartIndex, prefixPolyLength * sizeof(dtPolyRef));
 
  dtPolyRef suffixStartPoly = _pathPolyRefs[prefixPolyLength-1];
 
  // we need any point on our suffix start poly to generate poly-path, so we need last poly in prefix data
  float suffixEndPoint[VERTEX_SIZE];
  if (dtStatusFailed(_navMeshQuery->closestPointOnPoly(suffixStartPoly, endPoint, suffixEndPoint, NULL)))
  {
  // we can hit offmesh connection as last poly - closestPointOnPoly() don't like that
  // try to recover by using prev polyref
  --prefixPolyLength;
  suffixStartPoly = _pathPolyRefs[prefixPolyLength-1];
  if (dtStatusFailed(_navMeshQuery->closestPointOnPoly(suffixStartPoly, endPoint, suffixEndPoint, NULL)))
  {
  // suffixStartPoly is still invalid, error state
  BuildShortcut();
  _type = PATHFIND_NOPATH;
  return;
  }
  }
 
  // generate suffix
  uint32 suffixPolyLength = 0;
 
  dtStatus dtResult;
  if (_straightLine)
  {
  float hit = 0;
  float hitNormal[3];
  memset(hitNormal, 0, sizeof(hitNormal));
 
  dtResult = _navMeshQuery->raycast(
  suffixStartPoly,
  suffixEndPoint,
  endPoint,
  &_filter,
  &hit,
  hitNormal,
  _pathPolyRefs + prefixPolyLength - 1,
  (int*)&suffixPolyLength,
  MAX_PATH_LENGTH - prefixPolyLength);
 
  // raycast() sets hit to FLT_MAX if there is a ray between start and end
  if (hit != FLT_MAX)
  {
  // the ray hit something, return no path instead of the incomplete one
  _type = PATHFIND_NOPATH;
  return;
  }
  }
  else
  {
  dtResult = _navMeshQuery->findPath(
  suffixStartPoly, // start polygon
  endPoly, // end polygon
  suffixEndPoint, // start position
  endPoint, // end position
  &_filter, // polygon search filter
  _pathPolyRefs + prefixPolyLength - 1, // [out] path
  (int*)&suffixPolyLength,
  MAX_PATH_LENGTH - prefixPolyLength); // max number of polygons in output path
  }
 
  if (!suffixPolyLength || dtStatusFailed(dtResult))
  {
  // this is probably an error state, but we'll leave it
  // and hopefully recover on the next Update
  // we still need to copy our preffix
  TC_LOG_ERROR("maps", "%s's Path Build failed: 0 length path", _sourceUnit->GetGUID().ToString().c_str());
  }
 
  TC_LOG_DEBUG("maps", "++ m_polyLength=%u prefixPolyLength=%u suffixPolyLength=%u \n", _polyLength, prefixPolyLength, suffixPolyLength);
 
  // new path = prefix + suffix - overlap
  _polyLength = prefixPolyLength + suffixPolyLength - 1;
  }
  else
  {
  TC_LOG_DEBUG("maps", "++ BuildPolyPath :: (!startPolyFound && !endPolyFound)\n");
 
  // either we have no path at all -> first run
  // or something went really wrong -> we aren't moving along the path to the target
  // just generate new path
 
  // free and invalidate old path data
  Clear();
 
  dtStatus dtResult;
  if (_straightLine)
  {
  float hit = 0;
  float hitNormal[3];
  memset(hitNormal, 0, sizeof(hitNormal));
 
  dtResult = _navMeshQuery->raycast(
  startPoly,
  startPoint,
  endPoint,
  &_filter,
  &hit,
  hitNormal,
  _pathPolyRefs,
  (int*)&_polyLength,
  MAX_PATH_LENGTH);
 
  // raycast() sets hit to FLT_MAX if there is a ray between start and end
  if (hit != FLT_MAX)
  {
  // the ray hit something, return no path instead of the incomplete one
  _type = PATHFIND_NOPATH;
  return;
  }
  }
  else
  {
  dtResult = _navMeshQuery->findPath(
  startPoly, // start polygon
  endPoly, // end polygon
  startPoint, // start position
  endPoint, // end position
  &_filter, // polygon search filter
  _pathPolyRefs, // [out] path
  (int*)&_polyLength,
  MAX_PATH_LENGTH); // max number of polygons in output path
  }
 
  if (!_polyLength || dtStatusFailed(dtResult))
  {
  // only happens if we passed bad data to findPath(), or navmesh is messed up
  TC_LOG_ERROR("maps", "%s's Path Build failed: 0 length path", _sourceUnit->GetGUID().ToString().c_str());
  BuildShortcut();
  _type = PATHFIND_NOPATH;
  return;
  }
  }
 
  // by now we know what type of path we can get
  if (_pathPolyRefs[_polyLength - 1] == endPoly && !(_type & PATHFIND_INCOMPLETE))
  _type = PATHFIND_NORMAL;
  else
  _type = PATHFIND_INCOMPLETE;
 
  // generate the point-path out of our up-to-date poly-path
  BuildPointPath(startPoint, endPoint);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void PathGenerator::BuildShortcut ( )

private

 {
  TC_LOG_DEBUG("maps", "++ BuildShortcut :: making shortcut\n");
 
  Clear();
 
  // make two point path, our curr pos is the start, and dest is the end
  _pathPoints.resize(2);
 
  // set start and a default next position
  _pathPoints[0] = GetStartPosition();
  _pathPoints[1] = GetActualEndPosition();
 
  NormalizePath();
 
  _type = PATHFIND_SHORTCUT;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool PathGenerator::CalculatePath	(	float	destX,
		float	destY,
		float	destZ,
		bool	forceDest = `false`,
		bool	straightLine = `false`
	)

 {
  float x, y, z;
  _sourceUnit->GetPosition(x, y, z);
 
  if (!Trinity::IsValidMapCoord(destX, destY, destZ) || !Trinity::IsValidMapCoord(x, y, z))
  return false;
 
  G3D::Vector3 dest(destX, destY, destZ);
  SetEndPosition(dest);
 
  G3D::Vector3 start(x, y, z);
  SetStartPosition(start);
 
  _forceDestination = forceDest;
  _straightLine = straightLine;
 
  TC_LOG_DEBUG("maps", "++ PathGenerator::CalculatePath() for %s", _sourceUnit->GetGUID().ToString().c_str());
 
  // make sure navMesh works - we can run on map w/o mmap
  // check if the start and end point have a .mmtile loaded (can we pass via not loaded tile on the way?)
  if (!_navMesh || !_navMeshQuery || _sourceUnit->HasUnitState(UNIT_STATE_IGNORE_PATHFINDING) ||
  !HaveTile(start) || !HaveTile(dest))
  {
  BuildShortcut();
  _type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH);
  return true;
  }
 
  UpdateFilter();
 
  BuildPolyPath(start, dest);
  return true;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void PathGenerator::Clear ( )

inlineprivate

  {
  _polyLength = 0;
  _pathPoints.clear();
  }

Here is the caller graph for this function:

void PathGenerator::CreateFilter ( )

private

 {
  uint16 includeFlags = 0;
  uint16 excludeFlags = 0;
 
  if (_sourceUnit->GetTypeId() == TYPEID_UNIT)
  {
  Creature* creature = (Creature*)_sourceUnit;
  if (creature->CanWalk())
  includeFlags |= NAV_GROUND; // walk
 
  // creatures don't take environmental damage
  if (creature->CanSwim())
  includeFlags |= (NAV_WATER | NAV_MAGMA | NAV_SLIME); // swim
  }
  else // assume Player
  {
  // perfect support not possible, just stay 'safe'
  includeFlags |= (NAV_GROUND | NAV_WATER | NAV_MAGMA | NAV_SLIME);
  }
 
  _filter.setIncludeFlags(includeFlags);
  _filter.setExcludeFlags(excludeFlags);
 
  UpdateFilter();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

float PathGenerator::Dist3DSqr	(	G3D::Vector3 const &	p1,
		G3D::Vector3 const &	p2
	)		const

private

 {
  return (p1 - p2).squaredLength();
 }

Here is the caller graph for this function:

dtStatus PathGenerator::FindSmoothPath	(	float const *	startPos,
		float const *	endPos,
		dtPolyRef const *	polyPath,
		uint32	polyPathSize,
		float *	smoothPath,
		int *	smoothPathSize,
		uint32	smoothPathMaxSize
	)

private

 {
  *smoothPathSize = 0;
  uint32 nsmoothPath = 0;
 
  dtPolyRef polys[MAX_PATH_LENGTH];
  memcpy(polys, polyPath, sizeof(dtPolyRef)*polyPathSize);
  uint32 npolys = polyPathSize;
 
  float iterPos[VERTEX_SIZE], targetPos[VERTEX_SIZE];
  if (dtStatusFailed(_navMeshQuery->closestPointOnPolyBoundary(polys[0], startPos, iterPos)))
  return DT_FAILURE;
 
  if (dtStatusFailed(_navMeshQuery->closestPointOnPolyBoundary(polys[npolys-1], endPos, targetPos)))
  return DT_FAILURE;
 
  dtVcopy(&smoothPath[nsmoothPath*VERTEX_SIZE], iterPos);
  nsmoothPath++;
 
  // Move towards target a small advancement at a time until target reached or
  // when ran out of memory to store the path.
  while (npolys && nsmoothPath < maxSmoothPathSize)
  {
  // Find location to steer towards.
  float steerPos[VERTEX_SIZE];
  unsigned char steerPosFlag;
  dtPolyRef steerPosRef = INVALID_POLYREF;
 
  if (!GetSteerTarget(iterPos, targetPos, SMOOTH_PATH_SLOP, polys, npolys, steerPos, steerPosFlag, steerPosRef))
  break;
 
  bool endOfPath = (steerPosFlag & DT_STRAIGHTPATH_END) != 0;
  bool offMeshConnection = (steerPosFlag & DT_STRAIGHTPATH_OFFMESH_CONNECTION) != 0;
 
  // Find movement delta.
  float delta[VERTEX_SIZE];
  dtVsub(delta, steerPos, iterPos);
  float len = dtMathSqrtf(dtVdot(delta, delta));
  // If the steer target is end of path or off-mesh link, do not move past the location.
  if ((endOfPath || offMeshConnection) && len < SMOOTH_PATH_STEP_SIZE)
  len = 1.0f;
  else
  len = SMOOTH_PATH_STEP_SIZE / len;
 
  float moveTgt[VERTEX_SIZE];
  dtVmad(moveTgt, iterPos, delta, len);
 
  // Move
  float result[VERTEX_SIZE];
  const static uint32 MAX_VISIT_POLY = 16;
  dtPolyRef visited[MAX_VISIT_POLY];
 
  uint32 nvisited = 0;
  _navMeshQuery->moveAlongSurface(polys[0], iterPos, moveTgt, &_filter, result, visited, (int*)&nvisited, MAX_VISIT_POLY);
  npolys = FixupCorridor(polys, npolys, MAX_PATH_LENGTH, visited, nvisited);
 
  _navMeshQuery->getPolyHeight(polys[0], result, &result[1]);
  result[1] += 0.5f;
  dtVcopy(iterPos, result);
 
  // Handle end of path and off-mesh links when close enough.
  if (endOfPath && InRangeYZX(iterPos, steerPos, SMOOTH_PATH_SLOP, 1.0f))
  {
  // Reached end of path.
  dtVcopy(iterPos, targetPos);
  if (nsmoothPath < maxSmoothPathSize)
  {
  dtVcopy(&smoothPath[nsmoothPath*VERTEX_SIZE], iterPos);
  nsmoothPath++;
  }
  break;
  }
  else if (offMeshConnection && InRangeYZX(iterPos, steerPos, SMOOTH_PATH_SLOP, 1.0f))
  {
  // Advance the path up to and over the off-mesh connection.
  dtPolyRef prevRef = INVALID_POLYREF;
  dtPolyRef polyRef = polys[0];
  uint32 npos = 0;
  while (npos < npolys && polyRef != steerPosRef)
  {
  prevRef = polyRef;
  polyRef = polys[npos];
  npos++;
  }
 
  for (uint32 i = npos; i < npolys; ++i)
  polys[i-npos] = polys[i];
 
  npolys -= npos;
 
  // Handle the connection.
  float connectionStartPos[VERTEX_SIZE], connectionEndPos[VERTEX_SIZE];
  if (dtStatusSucceed(_navMesh->getOffMeshConnectionPolyEndPoints(prevRef, polyRef, connectionStartPos, connectionEndPos)))
  {
  if (nsmoothPath < maxSmoothPathSize)
  {
  dtVcopy(&smoothPath[nsmoothPath*VERTEX_SIZE], connectionStartPos);
  nsmoothPath++;
  }
  // Move position at the other side of the off-mesh link.
  dtVcopy(iterPos, connectionEndPos);
  _navMeshQuery->getPolyHeight(polys[0], iterPos, &iterPos[1]);
  iterPos[1] += 0.5f;
  }
  }
 
  // Store results.
  if (nsmoothPath < maxSmoothPathSize)
  {
  dtVcopy(&smoothPath[nsmoothPath*VERTEX_SIZE], iterPos);
  nsmoothPath++;
  }
  }
 
  *smoothPathSize = nsmoothPath;
 
  // this is most likely a loop
  return nsmoothPath < MAX_POINT_PATH_LENGTH ? DT_SUCCESS : DT_FAILURE;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

uint32 PathGenerator::FixupCorridor	(	dtPolyRef *	path,
		uint32	npath,
		uint32	maxPath,
		dtPolyRef const *	visited,
		uint32	nvisited
	)

private

 {
     int32 furthestPath = -1;
     int32 furthestVisited = -1;
 
     // Find furthest common polygon.
     for (int32 i = npath-1; i >= 0; --i)
     {
         bool found = false;
         for (int32 j = nvisited-1; j >= 0; --j)
         {
             if (path[i] == visited[j])
             {
                 furthestPath = i;
                 furthestVisited = j;
                 found = true;
             }
         }
         if (found)
             break;
     }
 
     // If no intersection found just return current path.
     if (furthestPath == -1 || furthestVisited == -1)
         return npath;
 
     // Concatenate paths.
 
     // Adjust beginning of the buffer to include the visited.
     uint32 req = nvisited - furthestVisited;
     uint32 orig = uint32(furthestPath + 1) < npath ? furthestPath + 1 : npath;
     uint32 size = npath > orig ? npath - orig : 0;
     if (req + size > maxPath)
         size = maxPath-req;
 
     if (size)
         memmove(path + req, path + orig, size * sizeof(dtPolyRef));
 
     // Store visited
     for (uint32 i = 0; i < req; ++i)
         path[i] = visited[(nvisited - 1) - i];
 
     return req+size;
 }

Here is the caller graph for this function:

G3D::Vector3 const& PathGenerator::GetActualEndPosition ( ) const

inline

69 { return _actualEndPosition; }

PathGenerator::_actualEndPosition

G3D::Vector3 _actualEndPosition

Definition: PathGenerator.h:92

Here is the caller graph for this function:

G3D::Vector3 const& PathGenerator::GetEndPosition ( ) const

inline

68 { return _endPosition; }

PathGenerator::_endPosition

G3D::Vector3 _endPosition

Definition: PathGenerator.h:91

Here is the caller graph for this function:

NavTerrain PathGenerator::GetNavTerrain	(	float	x,
		float	y,
		float	z
	)

private

 {
     LiquidData data;
     ZLiquidStatus liquidStatus = _sourceUnit->GetBaseMap()->getLiquidStatus(x, y, z, MAP_ALL_LIQUIDS, &data);
     if (liquidStatus == LIQUID_MAP_NO_WATER)
         return NAV_GROUND;
 
     switch (data.type_flags)
     {
         case MAP_LIQUID_TYPE_WATER:
         case MAP_LIQUID_TYPE_OCEAN:
             return NAV_WATER;
         case MAP_LIQUID_TYPE_MAGMA:
             return NAV_MAGMA;
         case MAP_LIQUID_TYPE_SLIME:
             return NAV_SLIME;
         default:
             return NAV_GROUND;
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Movement::PointsArray const& PathGenerator::GetPath ( ) const

inline

71 { return _pathPoints; }

PathGenerator::_pathPoints

Movement::PointsArray _pathPoints

Definition: PathGenerator.h:82

Here is the caller graph for this function:

dtPolyRef PathGenerator::GetPathPolyByPosition	(	dtPolyRef const *	polyPath,
		uint32	polyPathSize,
		float const *	Point,
		float *	Distance = `NULL`
	)		const

private

 {
     if (!polyPath || !polyPathSize)
         return INVALID_POLYREF;
 
     dtPolyRef nearestPoly = INVALID_POLYREF;
     float minDist2d = FLT_MAX;
     float minDist3d = 0.0f;
 
     for (uint32 i = 0; i < polyPathSize; ++i)
     {
         float closestPoint[VERTEX_SIZE];
         if (dtStatusFailed(_navMeshQuery->closestPointOnPoly(polyPath[i], point, closestPoint, NULL)))
             continue;
 
         float d = dtVdist2DSqr(point, closestPoint);
         if (d < minDist2d)
         {
             minDist2d = d;
             nearestPoly = polyPath[i];
             minDist3d = dtVdistSqr(point, closestPoint);
         }
 
         if (minDist2d < 1.0f) // shortcut out - close enough for us
             break;
     }
 
     if (distance)
         *distance = dtMathSqrtf(minDist3d);
 
     return (minDist2d < 3.0f) ? nearestPoly : INVALID_POLYREF;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

PathType PathGenerator::GetPathType ( ) const

inline

73 { return _type; }

PathGenerator::_type

PathType _type

Definition: PathGenerator.h:83

Here is the caller graph for this function:

dtPolyRef PathGenerator::GetPolyByLocation	(	float const *	Point,
		float *	Distance
	)		const

private

 {
     // first we check the current path
     // if the current path doesn't contain the current poly,
     // we need to use the expensive navMesh.findNearestPoly
     dtPolyRef polyRef = GetPathPolyByPosition(_pathPolyRefs, _polyLength, point, distance);
     if (polyRef != INVALID_POLYREF)
         return polyRef;
 
     // we don't have it in our old path
     // try to get it by findNearestPoly()
     // first try with low search box
     float extents[VERTEX_SIZE] = {3.0f, 5.0f, 3.0f};    // bounds of poly search area
     float closestPoint[VERTEX_SIZE] = {0.0f, 0.0f, 0.0f};
     if (dtStatusSucceed(_navMeshQuery->findNearestPoly(point, extents, &_filter, &polyRef, closestPoint)) && polyRef != INVALID_POLYREF)
     {
         *distance = dtVdist(closestPoint, point);
         return polyRef;
     }
 
     // still nothing ..
     // try with bigger search box
     // Note that the extent should not overlap more than 128 polygons in the navmesh (see dtNavMeshQuery::findNearestPoly)
     extents[1] = 50.0f;
 
     if (dtStatusSucceed(_navMeshQuery->findNearestPoly(point, extents, &_filter, &polyRef, closestPoint)) && polyRef != INVALID_POLYREF)
     {
         *distance = dtVdist(closestPoint, point);
         return polyRef;
     }
 
     return INVALID_POLYREF;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

G3D::Vector3 const& PathGenerator::GetStartPosition ( ) const

inline

67 { return _startPosition; }

PathGenerator::_startPosition

G3D::Vector3 _startPosition

Definition: PathGenerator.h:90

Here is the caller graph for this function:

bool PathGenerator::GetSteerTarget	(	float const *	startPos,
		float const *	endPos,
		float	minTargetDist,
		dtPolyRef const *	path,
		uint32	pathSize,
		float *	steerPos,
		unsigned char &	steerPosFlag,
		dtPolyRef &	steerPosRef
	)

private

 {
     // Find steer target.
     static const uint32 MAX_STEER_POINTS = 3;
     float steerPath[MAX_STEER_POINTS*VERTEX_SIZE];
     unsigned char steerPathFlags[MAX_STEER_POINTS];
     dtPolyRef steerPathPolys[MAX_STEER_POINTS];
     uint32 nsteerPath = 0;
     dtStatus dtResult = _navMeshQuery->findStraightPath(startPos, endPos, path, pathSize,
                                                 steerPath, steerPathFlags, steerPathPolys, (int*)&nsteerPath, MAX_STEER_POINTS);
     if (!nsteerPath || dtStatusFailed(dtResult))
         return false;
 
     // Find vertex far enough to steer to.
     uint32 ns = 0;
     while (ns < nsteerPath)
     {
         // Stop at Off-Mesh link or when point is further than slop away.
         if ((steerPathFlags[ns] & DT_STRAIGHTPATH_OFFMESH_CONNECTION) ||
             !InRangeYZX(&steerPath[ns*VERTEX_SIZE], startPos, minTargetDist, 1000.0f))
             break;
         ns++;
     }
     // Failed to find good point to steer to.
     if (ns >= nsteerPath)
         return false;
 
     dtVcopy(steerPos, &steerPath[ns*VERTEX_SIZE]);
     steerPos[1] = startPos[1];  // keep Z value
     steerPosFlag = steerPathFlags[ns];
     steerPosRef = steerPathPolys[ns];
 
     return true;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool PathGenerator::HaveTile ( G3D::Vector3 const & p ) const

private

Workaround For some reason, often the tx and ty variables wont get a valid value Use this check to prevent getting negative tile coords and crashing on getTileAt

 {
     int tx = -1, ty = -1;
     float point[VERTEX_SIZE] = {p.y, p.z, p.x};
 
     _navMesh->calcTileLoc(point, &tx, &ty);
 
     if (tx < 0 || ty < 0)
         return false;
 
     return (_navMesh->getTileAt(tx, ty, 0) != NULL);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool PathGenerator::InRange	(	G3D::Vector3 const &	p1,
		G3D::Vector3 const &	p2,
		float	r,
		float	h
	)		const

private

 {
     G3D::Vector3 d = p1 - p2;
     return (d.x * d.x + d.y * d.y) < r * r && fabsf(d.z) < h;
 }

Here is the caller graph for this function:

bool PathGenerator::InRangeYZX	(	float const *	v1,
		float const *	v2,
		float	r,
		float	h
	)		const

private

 {
     const float dx = v2[0] - v1[0];
     const float dy = v2[1] - v1[1]; // elevation
     const float dz = v2[2] - v1[2];
     return (dx * dx + dz * dz) < r * r && fabsf(dy) < h;
 }

Here is the caller graph for this function:

void PathGenerator::NormalizePath ( )

private

 {
     for (uint32 i = 0; i < _pathPoints.size(); ++i)
         _sourceUnit->UpdateAllowedPositionZ(_pathPoints[i].x, _pathPoints[i].y, _pathPoints[i].z);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void PathGenerator::ReducePathLenghtByDist ( float dist )

 {
     if (GetPathType() == PATHFIND_BLANK)
     {
         TC_LOG_ERROR("maps", "PathGenerator::ReducePathLenghtByDist called before path was built");
         return;
     }
 
     if (_pathPoints.size() < 2) // path building failure
         return;
 
     uint32 i = _pathPoints.size();
     G3D::Vector3 nextVec = _pathPoints[--i];
     while (i > 0)
     {
         G3D::Vector3 currVec = _pathPoints[--i];
         G3D::Vector3 diffVec = (nextVec - currVec);
         float len = diffVec.length();
         if (len > dist)
         {
             float step = dist / len;
             // same as nextVec
             _pathPoints[i + 1] -= diffVec * step;
             _sourceUnit->UpdateAllowedPositionZ(_pathPoints[i + 1].x, _pathPoints[i + 1].y, _pathPoints[i + 1].z);
             _pathPoints.resize(i + 2);
             break;
         }
         else if (i == 0) // at second point
         {
             _pathPoints[1] = _pathPoints[0];
             _pathPoints.resize(2);
             break;
         }
 
         dist -= len;
         nextVec = currVec; // we're going backwards
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void PathGenerator::SetActualEndPosition ( G3D::Vector3 const & point )

inlineprivate

102 { _actualEndPosition = point; }

PathGenerator::_actualEndPosition

G3D::Vector3 _actualEndPosition

Definition: PathGenerator.h:92

Here is the caller graph for this function:

void PathGenerator::SetEndPosition ( G3D::Vector3 const & point )

inlineprivate

101 { _actualEndPosition = point; _endPosition = point; }

PathGenerator::_actualEndPosition

G3D::Vector3 _actualEndPosition

Definition: PathGenerator.h:92

PathGenerator::_endPosition

G3D::Vector3 _endPosition

Definition: PathGenerator.h:91

Here is the caller graph for this function:

void PathGenerator::SetPathLengthLimit ( float distance )

inline

64 { _pointPathLimit = std::min<uint32>(uint32(distance/SMOOTH_PATH_STEP_SIZE), MAX_POINT_PATH_LENGTH); }

G3D::distance

double distance(double x, double y)

Definition: g3dmath.h:731

G3D::uint32

uint32_t uint32

Definition: g3dmath.h:168

SMOOTH_PATH_STEP_SIZE

#define SMOOTH_PATH_STEP_SIZE

Definition: PathGenerator.h:35

MAX_POINT_PATH_LENGTH

#define MAX_POINT_PATH_LENGTH

Definition: PathGenerator.h:33

PathGenerator::_pointPathLimit

uint32 _pointPathLimit

Definition: PathGenerator.h:87

Here is the caller graph for this function:

void PathGenerator::SetStartPosition ( G3D::Vector3 const & point )

inlineprivate

100 { _startPosition = point; }

PathGenerator::_startPosition

G3D::Vector3 _startPosition

Definition: PathGenerator.h:90

Here is the caller graph for this function:

void PathGenerator::SetUseStraightPath ( bool useStraightPath )

inline

63 { _useStraightPath = useStraightPath; }

PathGenerator::_useStraightPath

bool _useStraightPath

Definition: PathGenerator.h:85

Here is the caller graph for this function:

void PathGenerator::UpdateFilter ( )

private

 {
     // allow creatures to cheat and use different movement types if they are moved
     // forcefully into terrain they can't normally move in
     if (_sourceUnit->IsInWater() || _sourceUnit->IsUnderWater())
     {
         uint16 includedFlags = _filter.getIncludeFlags();
         includedFlags |= GetNavTerrain(_sourceUnit->GetPositionX(),
                                        _sourceUnit->GetPositionY(),
                                        _sourceUnit->GetPositionZ());
 
         _filter.setIncludeFlags(includedFlags);
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

G3D::Vector3 PathGenerator::_actualEndPosition

private

G3D::Vector3 PathGenerator::_endPosition

private

dtQueryFilter PathGenerator::_filter

private

bool PathGenerator::_forceDestination

private

dtNavMesh const* PathGenerator::_navMesh

private

dtNavMeshQuery const* PathGenerator::_navMeshQuery

private

Movement::PointsArray PathGenerator::_pathPoints

private

dtPolyRef PathGenerator::_pathPolyRefs[MAX_PATH_LENGTH]

private

uint32 PathGenerator::_pointPathLimit

private

uint32 PathGenerator::_polyLength

private

Unit const* const PathGenerator::_sourceUnit

private

G3D::Vector3 PathGenerator::_startPosition

private

bool PathGenerator::_straightLine

private

PathType PathGenerator::_type

private

bool PathGenerator::_useStraightPath

private

The documentation for this class was generated from the following files:

src/server/game/Movement/PathGenerator.h
src/server/game/Movement/PathGenerator.cpp

Private Attributes
dtPolyRef	_pathPolyRefs [MAX_PATH_LENGTH]

uint32	_polyLength

Movement::PointsArray	_pathPoints

PathType	_type

bool	_useStraightPath

bool	_forceDestination

uint32	_pointPathLimit

bool	_straightLine

G3D::Vector3	_startPosition

G3D::Vector3	_endPosition

G3D::Vector3	_actualEndPosition

Unit const *const	_sourceUnit

dtNavMesh const *	_navMesh

dtNavMeshQuery const *	_navMeshQuery

dtQueryFilter	_filter

Public Member Functions

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation