#include "PathGenerator.h"

Public Member Functions
	PathGenerator (WorldObject const *owner)

	~PathGenerator ()

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

bool	CalculatePath (float x, float y, float z, float destX, float destY, float destZ, bool forceDest)

bool	IsInvalidDestinationZ (Unit const *target) const

bool	IsWalkableClimb (float const v1, float const v2) const

bool	IsWalkableClimb (float x, float y, float z, float destX, float destY, float destZ) const

bool	IsWaterPath (Movement::PointsArray pathPoints) const

bool	IsSwimmableSegment (float const v1, float const v2, bool checkSwim=true) const
	predict if a certain segment is underwater and the unit can swim Must only be used for very short segments since this check doesn't work on long paths that alternate terrain and water. More...

bool	IsSwimmableSegment (float x, float y, float z, float destX, float destY, float destZ, bool checkSwim=true) const
	predict if a certain segment is underwater and the unit can swim Must only be used for very short segments since this check doesn't work on long paths that alternate terrain and water. More...

void	SetSlopeCheck (bool checkSlope)

void	SetUseStraightPath (bool useStraightPath)

void	SetPathLengthLimit (float distance)

void	SetUseRaycast (bool useRaycast)

G3D::Vector3 const &	GetStartPosition () const

G3D::Vector3 const &	GetEndPosition () const

G3D::Vector3 const &	GetActualEndPosition () const

Movement::PointsArray const &	GetPath () const

PathType	GetPathType () const

void	ShortenPathUntilDist (G3D::Vector3 const &point, float dist)

float	getPathLength () const

void	Clear ()

Static Public Member Functions
static bool	IsWalkableClimb (float x, float y, float z, float destX, float destY, float destZ, float sourceHeight)
	Check if a slope can be climbed based on source height This method is meant for short distances or linear paths. More...

static float	GetRequiredHeightToClimb (float x, float y, float z, float destX, float destY, float destZ, float sourceHeight)
	Return the height of a slope that can be climbed based on source height This method is meant for short distances or linear paths. More...

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

void	SetEndPosition (G3D::Vector3 const &point)

void	SetActualEndPosition (G3D::Vector3 const &point)

void	NormalizePath ()

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=nullptr) 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) const

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)

void	AddFarFromPolyFlags (bool startFarFromPoly, bool endFarFromPoly)

Private Attributes
dtPolyRef	_pathPolyRefs [MAX_PATH_LENGTH]

uint32	_polyLength

Movement::PointsArray	_pathPoints

PathType	_type

bool	_useStraightPath

bool	_forceDestination

bool	_slopeCheck

uint32	_pointPathLimit

bool	_useRaycast

G3D::Vector3	_startPosition

G3D::Vector3	_endPosition

G3D::Vector3	_actualEndPosition

WorldObject const *const	_source

dtNavMesh const *	_navMesh

dtNavMeshQuery const *	_navMeshQuery

dtQueryFilterExt	_filter

Detailed Description

Constructor & Destructor Documentation

◆ PathGenerator()

PathGenerator::PathGenerator ( WorldObject const * owner )

explicit

                                                     :
    _polyLength(0), _type(PATHFIND_BLANK), _useStraightPath(false), _forceDestination(false),
    _slopeCheck(false), _pointPathLimit(MAX_POINT_PATH_LENGTH), _useRaycast(false),
    _endPosition(G3D::Vector3::zero()), _source(owner), _navMesh(nullptr),
    _navMeshQuery(nullptr)
{
    memset(_pathPolyRefs, 0, sizeof(_pathPolyRefs));
 
    uint32 mapId = _source->GetMapId();
    //if (DisableMgr::IsPathfindingEnabled(_sourceUnit->FindMap()))
    {
        MMAP::MMapMgr* mmap = MMAP::MMapFactory::createOrGetMMapMgr();
        _navMesh = mmap->GetNavMesh(mapId);
        _navMeshQuery = mmap->GetNavMeshQuery(mapId, _source->GetInstanceId());
    }
 
    CreateFilter();
}

References _navMesh, _navMeshQuery, _pathPolyRefs, _source, CreateFilter(), MMAP::MMapFactory::createOrGetMMapMgr(), WorldObject::GetInstanceId(), WorldLocation::GetMapId(), MMAP::MMapMgr::GetNavMesh(), and MMAP::MMapMgr::GetNavMeshQuery().

◆ ~PathGenerator()

PathGenerator::~PathGenerator ( )

49{

50}

Member Function Documentation

◆ AddFarFromPolyFlags()

void PathGenerator::AddFarFromPolyFlags	(	bool	startFarFromPoly,
		bool	endFarFromPoly
	)

private

{
    if (startFarFromPoly)
    {
        _type = PathType(_type | PATHFIND_FARFROMPOLY_START);
    }
    if (endFarFromPoly)
    {
        _type = PathType(_type | PATHFIND_FARFROMPOLY_END);
    }
}

References _type, PATHFIND_FARFROMPOLY_END, and PATHFIND_FARFROMPOLY_START.

Referenced by BuildPolyPath().

◆ BuildPointPath()

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 (_useRaycast)
    {
        // _straightLine uses raycast and it currently doesn't support building a point path, only a 2-point path with start and hitpoint/end is returned
        LOG_ERROR("movement", "PathGenerator::BuildPointPath() called with _useRaycast for unit {}", _source->GetGUID().ToString());
        BuildShortcut();
        _type = PATHFIND_NOPATH;
        return;
    }
    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
            nullptr,               // [out] flags
            nullptr,               // [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
    }
 
    // Special case with start and end positions very close to each other
    if (_polyLength == 1 && pointCount == 1)
    {
        // First point is start position, append end position
        dtVcopy(&pathPoints[1 * VERTEX_SIZE], endPoint);
        pointCount++;
    }
    else if (pointCount < 2 || dtStatusFailed(dtResult))
    {
        // only happens if pass bad data to findStraightPath or navmesh is broken
        // single point paths can be generated here
        BuildShortcut();
        _type = PathType(_type | PATHFIND_NOPATH);
        return;
    }
    else if (pointCount >= _pointPathLimit)
    {
        BuildShortcut();
        _type = PathType(_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);
    }
}

References _forceDestination, _navMeshQuery, _pathPoints, _pathPolyRefs, _pointPathLimit, _polyLength, _source, _type, _useRaycast, _useStraightPath, BuildShortcut(), Dist3DSqr(), FindSmoothPath(), GetActualEndPosition(), GetEndPosition(), Object::GetGUID(), GetStartPosition(), InRange(), LOG_ERROR, MAX_POINT_PATH_LENGTH, NormalizePath(), PATHFIND_NOPATH, PATHFIND_NORMAL, PATHFIND_NOT_USING_PATH, PATHFIND_SHORT, SetActualEndPosition(), ObjectGuid::ToString(), and VERTEX_SIZE.

Referenced by BuildPolyPath().

◆ BuildPolyPath()

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);
 
    _type = PathType(PATHFIND_NORMAL);
 
    Creature const* creature = _source->ToCreature();
 
    // 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)
    {
        BuildShortcut();
 
        bool canSwim = creature ? creature->CanSwim() : true;
        bool path = creature ? creature->CanFly() : true;
        bool waterPath = IsWaterPath(_pathPoints);
        if (path || (waterPath && canSwim))
        {
            _type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH);
            return;
        }
 
        // raycast doesn't need endPoly to be valid
        if (!_useRaycast)
        {
            _type = PATHFIND_NOPATH;
            return;
        }
    }
 
    // we may need a better number here
    bool startFarFromPoly = distToStartPoly > 7.0f;
    bool endFarFromPoly = distToEndPoly > 7.0f;
 
    // create a shortcut if the path begins or end too far
    // away from the desired path points.
    // swimming creatures should not use a shortcut
    // because exiting the water must be done following a proper path
    // we just need to remove/normalize paths between 2 adjacent points
    if (startFarFromPoly || endFarFromPoly)
    {
        bool buildShortcut = false;
 
        auto liquidDataStart = _source->GetMap()->GetLiquidData(_source->GetPhaseMask(), startPos.x, startPos.y, startPos.z, _source->GetCollisionHeight(), MAP_ALL_LIQUIDS);
        auto liquidDataEnd = _source->GetMap()->GetLiquidData(_source->GetPhaseMask(), endPos.x, endPos.y, endPos.z, _source->GetCollisionHeight(), MAP_ALL_LIQUIDS);
 
        bool startUnderWaterEndInWater = liquidDataStart.Status == LIQUID_MAP_UNDER_WATER &&
                                         (liquidDataEnd.Status & MAP_LIQUID_STATUS_IN_CONTACT) != 0;
        bool startInWaterEndUnderWater = (liquidDataStart.Status & MAP_LIQUID_STATUS_IN_CONTACT) != 0 &&
                                         liquidDataEnd.Status == LIQUID_MAP_UNDER_WATER;
        bool waterPath = startUnderWaterEndInWater || startInWaterEndUnderWater;
        Unit const* _sourceUnit = _source->ToUnit();
 
        if (_sourceUnit)
        {
            bool isWater = (_sourceUnit->CanSwim() && waterPath);
 
            if (isWater || _sourceUnit->CanFly() || (_sourceUnit->IsFalling() && endPos.z < startPos.z))
            {
                buildShortcut = true;
            }
        }
 
        if (buildShortcut)
        {
            BuildShortcut();
            _type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH);
 
            AddFarFromPolyFlags(startFarFromPoly, endFarFromPoly);
 
            return;
        }
        else
        {
            float closestPoint[VERTEX_SIZE];
            // we may want to use closestPointOnPolyBoundary instead
            if (dtStatusSucceed(_navMeshQuery->closestPointOnPoly(endPoly, endPoint, closestPoint, nullptr)))
            {
                dtVcopy(endPoint, closestPoint);
                SetActualEndPosition(G3D::Vector3(endPoint[2], endPoint[0], endPoint[1]));
            }
 
            _type = PathType(PATHFIND_INCOMPLETE);
 
            AddFarFromPolyFlags(startFarFromPoly, endFarFromPoly);
        }
    }
 
    // *** poly path generating logic ***
 
    // start and end are on same polygon
    // handle this case as if they were 2 different polygons, building a line path split in some few points
    if (startPoly == endPoly && !_useRaycast)
    {
        _pathPolyRefs[0] = startPoly;
        _polyLength = 1;
 
        if (startFarFromPoly || endFarFromPoly)
        {
            _type = PathType(PATHFIND_INCOMPLETE);
 
            AddFarFromPolyFlags(startFarFromPoly, endFarFromPoly);
        }
        else
            _type = PATHFIND_NORMAL;
 
        BuildPointPath(startPoint, endPoint);
        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)
            {
                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)
    {
        // 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)
    {
        // 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, nullptr)))
        {
            // 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, nullptr)))
            {
                // suffixStartPoly is still invalid, error state
                BuildShortcut();
                _type = PATHFIND_NOPATH;
                return;
            }
        }
 
        // generate suffix
        uint32 suffixPolyLength = 0;
 
        dtStatus dtResult;
        if (_useRaycast)
        {
            BuildShortcut();
            _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
            LOG_ERROR("movement", "PathGenerator::BuildPolyPath: Path Build failed {}", _source->GetGUID().ToString());
        }
 
        // new path = prefix + suffix - overlap
        _polyLength = prefixPolyLength + suffixPolyLength - 1;
    }
    else
    {
        // 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 (_useRaycast)
        {
            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);
 
            if (!_polyLength || dtStatusFailed(dtResult))
            {
                BuildShortcut();
                _type = PATHFIND_NOPATH;
                AddFarFromPolyFlags(startFarFromPoly, endFarFromPoly);
                return;
            }
 
            // raycast() sets hit to FLT_MAX if there is a ray between start and end
            if (hit != FLT_MAX)
            {
                float hitPos[3];
 
                // Walk back a bit from the hit point to make sure it's in the mesh (sometimes the point is actually outside of the polygons due to float precision issues)
                hit *= 0.99f;
                dtVlerp(hitPos, startPoint, endPoint, hit);
 
                // if it fails again, clamp to poly boundary
                if (dtStatusFailed(_navMeshQuery->getPolyHeight(_pathPolyRefs[_polyLength - 1], hitPos, &hitPos[1])))
                    _navMeshQuery->closestPointOnPolyBoundary(_pathPolyRefs[_polyLength - 1], hitPos, hitPos);
 
                _pathPoints.resize(2);
                _pathPoints[0] = GetStartPosition();
                _pathPoints[1] = G3D::Vector3(hitPos[2], hitPos[0], hitPos[1]);
 
                NormalizePath();
                _type = PATHFIND_INCOMPLETE;
                AddFarFromPolyFlags(startFarFromPoly, false);
                return;
            }
            else
            {
                // clamp to poly boundary if we fail to get the height
                if (dtStatusFailed(_navMeshQuery->getPolyHeight(_pathPolyRefs[_polyLength - 1], endPoint, &endPoint[1])))
                    _navMeshQuery->closestPointOnPolyBoundary(_pathPolyRefs[_polyLength - 1], endPoint, endPoint);
 
                _pathPoints.resize(2);
                _pathPoints[0] = GetStartPosition();
                _pathPoints[1] = G3D::Vector3(endPoint[2], endPoint[0], endPoint[1]);
 
                NormalizePath();
                if (startFarFromPoly || endFarFromPoly)
                {
                    _type = PathType(PATHFIND_INCOMPLETE);
 
                    AddFarFromPolyFlags(startFarFromPoly, endFarFromPoly);
                }
                else
                    _type = PATHFIND_NORMAL;
                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
            LOG_ERROR("movement", "PathGenerator::BuildPolyPath: {} Path Build failed: 0 length path", _source->GetGUID().ToString());
            BuildShortcut();
            _type = PATHFIND_NOPATH;
            return;
        }
    }
 
    if (!_polyLength)
    {
        LOG_ERROR("movement", "PathGenerator::BuildPolyPath: {} Path Build failed: 0 length path", _source->GetGUID().ToString());
        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;
    }
 
    AddFarFromPolyFlags(startFarFromPoly, endFarFromPoly);
 
    // generate the point-path out of our up-to-date poly-path
    BuildPointPath(startPoint, endPoint);
}

References _filter, _navMeshQuery, _pathPoints, _pathPolyRefs, _polyLength, _source, _type, _useRaycast, AddFarFromPolyFlags(), BuildPointPath(), BuildShortcut(), Creature::CanFly(), Creature::CanSwim(), Clear(), WorldObject::GetCollisionHeight(), Object::GetGUID(), Map::GetLiquidData(), WorldObject::GetMap(), WorldObject::GetPhaseMask(), GetPolyByLocation(), GetStartPosition(), INVALID_POLYREF, IsWaterPath(), LIQUID_MAP_UNDER_WATER, LOG_ERROR, MAP_ALL_LIQUIDS, MAP_LIQUID_STATUS_IN_CONTACT, MAX_PATH_LENGTH, NormalizePath(), PATHFIND_INCOMPLETE, PATHFIND_NOPATH, PATHFIND_NORMAL, PATHFIND_NOT_USING_PATH, SetActualEndPosition(), LiquidData::Status, Object::ToCreature(), ObjectGuid::ToString(), Object::ToUnit(), and VERTEX_SIZE.

Referenced by CalculatePath().

◆ BuildShortcut()

void PathGenerator::BuildShortcut ( )

private

{
    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;
}

References _pathPoints, _type, Clear(), GetActualEndPosition(), GetStartPosition(), NormalizePath(), and PATHFIND_SHORTCUT.

Referenced by BuildPointPath(), BuildPolyPath(), and CalculatePath().

◆ CalculatePath() [1/2]

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

{
    float x, y, z;
    _source->GetPosition(x, y, z);
 
    return CalculatePath(x, y, z, destX, destY, destZ, forceDest);
}

References _source, CalculatePath(), and Position::GetPosition().

Referenced by CalculatePath(), Map::CheckCollisionAndGetValidCoords(), mmaps_commandscript::HandleMmapPathCommand(), mmaps_commandscript::HandleMmapTestArea(), and Movement::MoveSplineInit::MoveTo().

◆ CalculatePath() [2/2]

bool PathGenerator::CalculatePath	(	float	x,
		float	y,
		float	z,
		float	destX,
		float	destY,
		float	destZ,
		bool	forceDest
	)

{
    if (!Acore::IsValidMapCoord(destX, destY, destZ) || !Acore::IsValidMapCoord(x, y, z))
        return false;
 
    METRIC_DETAILED_EVENT("mmap_events", "CalculatePath", "");
 
    G3D::Vector3 dest(destX, destY, destZ);
    SetEndPosition(dest);
 
    G3D::Vector3 start(x, y, z);
    SetStartPosition(start);
 
    _forceDestination = forceDest;
 
    // 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?)
    Unit const* _sourceUnit = _source->ToUnit();
    if (!_navMesh || !_navMeshQuery || (_sourceUnit && _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;
}

References _forceDestination, _navMesh, _navMeshQuery, _source, _type, BuildPolyPath(), BuildShortcut(), Unit::HasUnitState(), HaveTile(), Acore::IsValidMapCoord(), METRIC_DETAILED_EVENT, PATHFIND_NORMAL, PATHFIND_NOT_USING_PATH, SetEndPosition(), SetStartPosition(), Object::ToUnit(), UNIT_STATE_IGNORE_PATHFINDING, and UpdateFilter().

◆ Clear()

void PathGenerator::Clear ( )

inline

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

References _pathPoints, and _polyLength.

Referenced by BuildPolyPath(), and BuildShortcut().

◆ CreateFilter()

void PathGenerator::CreateFilter ( )

private

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

References _filter, _source, Creature::CanEnterWater(), Creature::CanWalk(), Object::IsCreature(), NAV_GROUND, NAV_MAGMA, NAV_WATER, and UpdateFilter().

Referenced by PathGenerator().

◆ Dist3DSqr()

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

private

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

Referenced by BuildPointPath().

◆ FindSmoothPath()

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 (polyPathSize > 1)
    {
        // Pick the closest points on poly border
        if (dtStatusFailed(_navMeshQuery->closestPointOnPolyBoundary(polys[0], startPos, iterPos)))
        {
            return DT_FAILURE;
        }
 
        if (dtStatusFailed(_navMeshQuery->closestPointOnPolyBoundary(polys[npolys - 1], endPos, targetPos)))
        {
            return DT_FAILURE;
        }
    }
    else
    {
        // Case where the path is on the same poly
        dtVcopy(iterPos, startPos);
        dtVcopy(targetPos, endPos);
    }
 
    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;
        if (dtStatusFailed(_navMeshQuery->moveAlongSurface(polys[0], iterPos, moveTgt, &_filter, result, visited, (int*)&nvisited, MAX_VISIT_POLY)))
        {
            return DT_FAILURE;
        }
        npolys = FixupCorridor(polys, npolys, MAX_PATH_LENGTH, visited, nvisited);
 
        if (dtStatusFailed(_navMeshQuery->getPolyHeight(polys[0], result, &result[1])))
            LOG_DEBUG("maps", "PathGenerator::FindSmoothPath: Cannot find height at position X: {} Y: {} Z: {} for {}",
                result[2], result[0], result[1], _source->GetGUID().ToString());
        result[1] += 0.5f;
        dtVcopy(iterPos, result);
 
        bool canCheckSlope = _slopeCheck && (GetPathType() & ~(PATHFIND_NOT_USING_PATH));
 
        if (canCheckSlope && !IsSwimmableSegment(iterPos, steerPos) && !IsWalkableClimb(iterPos, steerPos))
        {
            return DT_FAILURE;
        }
 
        // 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);
                if (dtStatusFailed(_navMeshQuery->getPolyHeight(polys[0], iterPos, &iterPos[1])))
                    return DT_FAILURE;
                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;
}

References _filter, _navMesh, _navMeshQuery, _slopeCheck, _source, FixupCorridor(), Object::GetGUID(), GetPathType(), GetSteerTarget(), InRangeYZX(), INVALID_POLYREF, IsSwimmableSegment(), IsWalkableClimb(), LOG_DEBUG, MAX_PATH_LENGTH, MAX_POINT_PATH_LENGTH, PATHFIND_NOT_USING_PATH, SMOOTH_PATH_SLOP, SMOOTH_PATH_STEP_SIZE, ObjectGuid::ToString(), and VERTEX_SIZE.

Referenced by BuildPointPath().

◆ FixupCorridor()

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;
}

Referenced by FindSmoothPath().

◆ GetActualEndPosition()

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

inline

89{ return _actualEndPosition; }

PathGenerator::_actualEndPosition

G3D::Vector3 _actualEndPosition

Definition: PathGenerator.h:146

References _actualEndPosition.

Referenced by BuildPointPath(), BuildShortcut(), mmaps_commandscript::HandleMmapPathCommand(), IsInvalidDestinationZ(), and MotionMaster::MoveCharge().

◆ GetEndPosition()

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

inline

88{ return _endPosition; }

References _endPosition.

Referenced by BuildPointPath(), and mmaps_commandscript::HandleMmapPathCommand().

◆ GetNavTerrain()

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

private

{
    LiquidData const& liquidData = _source->GetMap()->GetLiquidData(_source->GetPhaseMask(), x, y, z, _source->GetCollisionHeight(), MAP_ALL_LIQUIDS);
    if (liquidData.Status == LIQUID_MAP_NO_WATER)
        return NAV_GROUND;
 
    switch (liquidData.Flags)
    {
        case MAP_LIQUID_TYPE_WATER:
        case MAP_LIQUID_TYPE_OCEAN:
            return NAV_WATER;
        case MAP_LIQUID_TYPE_MAGMA:
        case MAP_LIQUID_TYPE_SLIME:
            return NAV_MAGMA;
        default:
            return NAV_GROUND;
    }
}

References _source, LiquidData::Flags, WorldObject::GetCollisionHeight(), Map::GetLiquidData(), WorldObject::GetMap(), WorldObject::GetPhaseMask(), LIQUID_MAP_NO_WATER, MAP_ALL_LIQUIDS, MAP_LIQUID_TYPE_MAGMA, MAP_LIQUID_TYPE_OCEAN, MAP_LIQUID_TYPE_SLIME, MAP_LIQUID_TYPE_WATER, NAV_GROUND, NAV_MAGMA, NAV_WATER, and LiquidData::Status.

Referenced by IsWaterPath(), and UpdateFilter().

◆ GetPath()

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

inline

91{ return _pathPoints; }

References _pathPoints.

Referenced by Map::CanReachPositionAndGetValidCoords(), Map::CheckCollisionAndGetValidCoords(), mmaps_commandscript::HandleMmapPathCommand(), MotionMaster::MoveCharge(), and Movement::MoveSplineInit::MoveTo().

◆ getPathLength()

float PathGenerator::getPathLength ( ) const

inline

        {
            float len = 0.0f;
            float dx, dy, dz;
            uint32 size = _pathPoints.size();
            if (size)
            {
                dx = _pathPoints[0].x - _startPosition.x;
                dy = _pathPoints[0].y - _startPosition.y;
                dz = _pathPoints[0].z - _startPosition.z;
                len += std::sqrt( dx * dx + dy * dy + dz * dz );
            }
            else
            {
                return len;
            }
 
            for (uint32 i = 1; i < size; ++i)
            {
                dx = _pathPoints[i].x - _pathPoints[i - 1].x;
                dy = _pathPoints[i].y - _pathPoints[i - 1].y;
                dz = _pathPoints[i].z - _pathPoints[i - 1].z;
                len += std::sqrt( dx * dx + dy * dy + dz * dz );
            }
            return len;
        }

References _pathPoints, and _startPosition.

◆ GetPathPolyByPosition()

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

private

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

References _navMeshQuery, INVALID_POLYREF, and VERTEX_SIZE.

Referenced by GetPolyByLocation().

◆ GetPathType()

PathType PathGenerator::GetPathType ( ) const

inline

93{ return _type; }

References _type.

Referenced by Map::CheckCollisionAndGetValidCoords(), FindSmoothPath(), mmaps_commandscript::HandleMmapPathCommand(), Movement::MoveSplineInit::MoveTo(), and ShortenPathUntilDist().

◆ GetPolyByLocation()

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;
    }
 
    *distance = FLT_MAX;
    return INVALID_POLYREF;
}

References _filter, _navMeshQuery, _pathPolyRefs, _polyLength, GetPathPolyByPosition(), INVALID_POLYREF, and VERTEX_SIZE.

Referenced by BuildPolyPath().

◆ GetRequiredHeightToClimb()

float PathGenerator::GetRequiredHeightToClimb	(	float	x,
		float	y,
		float	z,
		float	destX,
		float	destY,
		float	destZ,
		float	sourceHeight
	)

static

Return the height of a slope that can be climbed based on source height This method is meant for short distances or linear paths.

Parameters

x	start x coord
y	start y coord
z	start z coord
destX	destination x coord
destY	destination y coord
destZ	destination z coord
sourceHeight	height of the source

Returns: float the maximum height that a source can climb based on slope angle

{
    float slopeAngle = getSlopeAngleAbs(x, y, z, destX, destY, destZ);
    float slopeAngleDegree = (slopeAngle * 180.0f / M_PI);
    float climbableHeight = sourceHeight - (sourceHeight * (slopeAngleDegree / 100));
    return climbableHeight;
}

References getSlopeAngleAbs().

Referenced by IsWalkableClimb().

◆ GetStartPosition()

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

inline

87{ return _startPosition; }

References _startPosition.

Referenced by BuildPointPath(), BuildPolyPath(), BuildShortcut(), Map::CanReachPositionAndGetValidCoords(), and mmaps_commandscript::HandleMmapPathCommand().

◆ GetSteerTarget()

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;
}

References _navMeshQuery, InRangeYZX(), and VERTEX_SIZE.

Referenced by FindSmoothPath().

◆ HaveTile()

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) != nullptr);
}

References _navMesh, and VERTEX_SIZE.

Referenced by CalculatePath().

◆ InRange()

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;
}

Referenced by BuildPointPath().

◆ InRangeYZX()

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;
}

Referenced by FindSmoothPath(), and GetSteerTarget().

◆ IsInvalidDestinationZ()

bool PathGenerator::IsInvalidDestinationZ ( Unit const * target ) const

{
    return (target->GetPositionZ() - GetActualEndPosition().z) > 5.0f;
}

References GetActualEndPosition(), and Position::GetPositionZ().

◆ IsSwimmableSegment() [1/2]

bool PathGenerator::IsSwimmableSegment	(	float const *	v1,
		float const *	v2,
		bool	checkSwim = `true`
	)		const

predict if a certain segment is underwater and the unit can swim Must only be used for very short segments since this check doesn't work on long paths that alternate terrain and water.

Parameters

v1
v2

Returns: true; false

{
    return IsSwimmableSegment(v1[2], v1[0], v1[1], v2[2], v2[0], v2[1], checkSwim);
}

References IsSwimmableSegment().

Referenced by FindSmoothPath(), IsSwimmableSegment(), and ShortenPathUntilDist().

◆ IsSwimmableSegment() [2/2]

bool PathGenerator::IsSwimmableSegment	(	float	x,
		float	y,
		float	z,
		float	destX,
		float	destY,
		float	destZ,
		bool	checkSwim = `true`
	)		const

predict if a certain segment is underwater and the unit can swim Must only be used for very short segments since this check doesn't work on long paths that alternate terrain and water.

Parameters

x
y
z
destX
destY
destZ
checkSwim	also check if the unit can swim

Returns: true if there's water at the end AND at the start of the segment; false if there's no water at the end OR at the start of the segment

{
    Creature const* _sourceCreature = _source->ToCreature();
    return _source->GetMap()->IsInWater(_source->GetPhaseMask(), x, y, z, _source->GetCollisionHeight()) &&
        _source->GetMap()->IsInWater(_source->GetPhaseMask(), destX, destY, destZ, _source->GetCollisionHeight()) &&
        (!checkSwim || !_sourceCreature || _sourceCreature->CanSwim());
}

References _source, Creature::CanSwim(), WorldObject::GetCollisionHeight(), WorldObject::GetMap(), WorldObject::GetPhaseMask(), Map::IsInWater(), and Object::ToCreature().

◆ IsWalkableClimb() [1/3]

bool PathGenerator::IsWalkableClimb	(	float const *	v1,
		float const *	v2
	)		const

{
    return IsWalkableClimb(v1[2], v1[0], v1[1], v2[2], v2[0], v2[1]);
}

References IsWalkableClimb().

Referenced by Map::CanReachPositionAndGetValidCoords(), FindSmoothPath(), IsWalkableClimb(), and ShortenPathUntilDist().

◆ IsWalkableClimb() [2/3]

bool PathGenerator::IsWalkableClimb	(	float	x,
		float	y,
		float	z,
		float	destX,
		float	destY,
		float	destZ
	)		const

{
    return IsWalkableClimb(x, y, z, destX, destY, destZ, _source->GetCollisionHeight());
}

References _source, WorldObject::GetCollisionHeight(), and IsWalkableClimb().

◆ IsWalkableClimb() [3/3]

bool PathGenerator::IsWalkableClimb	(	float	x,
		float	y,
		float	z,
		float	destX,
		float	destY,
		float	destZ,
		float	sourceHeight
	)

static

Check if a slope can be climbed based on source height This method is meant for short distances or linear paths.

Parameters

x	start x coord
y	start y coord
z	start z coord
destX	destination x coord
destY	destination y coord
destZ	destination z coord
sourceHeight	height of the source

Returns: bool check if you can climb the path

{
    float diffHeight = std::abs(destZ - z);
    float reqHeight = GetRequiredHeightToClimb(x, y, z, destX, destY, destZ, sourceHeight);
    // check walkable slopes, based on unit height
    return diffHeight <= reqHeight;
}

References GetRequiredHeightToClimb().

◆ IsWaterPath()

bool PathGenerator::IsWaterPath ( Movement::PointsArray pathPoints ) const

{
    bool waterPath = true;
    // 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)
    {
        NavTerrain terrain = GetNavTerrain(pathPoints[i].x, pathPoints[i].y, pathPoints[i].z);
        // One of the points is not in the water
        if (terrain != NAV_MAGMA && terrain != NAV_WATER)
        {
            waterPath = false;
            break;
        }
    }
 
    return waterPath;
}

References GetNavTerrain(), NAV_MAGMA, and NAV_WATER.

Referenced by BuildPolyPath().

◆ NormalizePath()

void PathGenerator::NormalizePath ( )

private

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

References _pathPoints, _source, and WorldObject::UpdateAllowedPositionZ().

Referenced by BuildPointPath(), BuildPolyPath(), and BuildShortcut().

◆ SetActualEndPosition()

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

inlineprivate

156{ _actualEndPosition = point; }

References _actualEndPosition.

Referenced by BuildPointPath(), and BuildPolyPath().

◆ SetEndPosition()

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

inlineprivate

155{ _actualEndPosition = point; _endPosition = point; }

References _actualEndPosition, and _endPosition.

Referenced by CalculatePath().

◆ SetPathLengthLimit()

void PathGenerator::SetPathLengthLimit ( float distance )

inline

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

References _pointPathLimit, MAX_POINT_PATH_LENGTH, and SMOOTH_PATH_STEP_SIZE.

◆ SetSlopeCheck()

void PathGenerator::SetSlopeCheck ( bool checkSlope )

inline

81{ _slopeCheck = checkSlope; }

References _slopeCheck.

◆ SetStartPosition()

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

inlineprivate

154{ _startPosition = point; }

References _startPosition.

Referenced by CalculatePath().

◆ SetUseRaycast()

void PathGenerator::SetUseRaycast ( bool useRaycast )

inline

84{ _useRaycast = useRaycast; }

References _useRaycast.

Referenced by Map::CheckCollisionAndGetValidCoords(), and mmaps_commandscript::HandleMmapPathCommand().

◆ SetUseStraightPath()

void PathGenerator::SetUseStraightPath ( bool useStraightPath )

inline

82{ _useStraightPath = useStraightPath; }

References _useStraightPath.

Referenced by mmaps_commandscript::HandleMmapPathCommand().

◆ ShortenPathUntilDist()

void PathGenerator::ShortenPathUntilDist	(	G3D::Vector3 const &	point,
		float	dist
	)

{
    if (GetPathType() == PATHFIND_BLANK || _pathPoints.size() < 2)
    {
        LOG_ERROR("movement", "PathGenerator::ReducePathLengthByDist called before path was successfully built");
        return;
    }
 
    float const distSq = dist * dist;
 
    // the first point of the path must be outside the specified range
    // (this should have really been checked by the caller...)
    if ((_pathPoints[0] - target).squaredLength() < distSq)
        return;
 
    // check if we even need to do anything
    if ((*_pathPoints.rbegin() - target).squaredLength() >= distSq)
        return;
 
    std::size_t i = _pathPoints.size() - 1;
    float x, y, z, collisionHeight = _source->GetCollisionHeight();
    // find the first i s.t.:
    //  - _pathPoints[i] is still too close
    //  - _pathPoints[i-1] is too far away
    // => the end point is somewhere on the line between the two
    while (1)
    {
        // we know that pathPoints[i] is too close already (from the previous iteration)
        if ((_pathPoints[i - 1] - target).squaredLength() >= distSq)
            break; // bingo!
 
        bool canCheckSlope = _slopeCheck && (GetPathType() & ~(PATHFIND_NOT_USING_PATH));
 
        // check if the shortened path is still in LoS with the target and it is walkable
        _source->GetHitSpherePointFor({ _pathPoints[i - 1].x, _pathPoints[i - 1].y, _pathPoints[i - 1].z + collisionHeight }, x, y, z);
        if (!_source->GetMap()->isInLineOfSight(x, y, z, _pathPoints[i - 1].x, _pathPoints[i - 1].y, _pathPoints[i - 1].z + collisionHeight,
            _source->GetPhaseMask(), LINEOFSIGHT_ALL_CHECKS, VMAP::ModelIgnoreFlags::Nothing) || (canCheckSlope &&
                !IsSwimmableSegment(_source->GetPositionX(), _source->GetPositionY(), _source->GetPositionZ(), _pathPoints[i - 1].x, _pathPoints[i - 1].y, _pathPoints[i - 1].z) &&
                !IsWalkableClimb(_source->GetPositionX(), _source->GetPositionY(), _source->GetPositionZ(), _pathPoints[i - 1].x, _pathPoints[i - 1].y, _pathPoints[i - 1].z)))
        {
            // whenver we find a point that is not valid anymore, simply use last valid path
            _pathPoints.resize(i + 1);
            return;
        }
 
        if (!--i)
        {
            // no point found that fulfills the condition
            _pathPoints[0] = _pathPoints[1];
            _pathPoints.resize(2);
            return;
        }
    }
 
    // ok, _pathPoints[i] is too close, _pathPoints[i-1] is not, so our target point is somewhere between the two...
    //   ... settle for a guesstimate since i'm not confident in doing trig on every chase motion tick...
    // (@todo review this)
    _pathPoints[i] += (_pathPoints[i - 1] - _pathPoints[i]).direction() * (dist - (_pathPoints[i] - target).length());
    _pathPoints.resize(i + 1);
}

References _pathPoints, _slopeCheck, _source, WorldObject::GetCollisionHeight(), WorldObject::GetHitSpherePointFor(), WorldObject::GetMap(), GetPathType(), WorldObject::GetPhaseMask(), Position::GetPositionX(), Position::GetPositionY(), Position::GetPositionZ(), Map::isInLineOfSight(), IsSwimmableSegment(), IsWalkableClimb(), LINEOFSIGHT_ALL_CHECKS, LOG_ERROR, VMAP::Nothing, PATHFIND_BLANK, and PATHFIND_NOT_USING_PATH.

◆ UpdateFilter()

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 (Unit const* _sourceUnit = _source->ToUnit())
    {
        if (_sourceUnit->IsInWater() || _sourceUnit->IsUnderWater())
        {
            uint16 includedFlags = _filter.getIncludeFlags();
            includedFlags |= GetNavTerrain(_source->GetPositionX(),
                _source->GetPositionY(),
                _source->GetPositionZ());
 
            _filter.setIncludeFlags(includedFlags);
        }
 
        /*if (Creature const* _sourceCreature = _source->ToCreature())
            if (_sourceCreature->IsInCombat() || _sourceCreature->IsInEvadeMode())
                _filter.setIncludeFlags(_filter.getIncludeFlags() | NAV_GROUND_STEEP);*/
    }
}

References _filter, _source, GetNavTerrain(), Position::GetPositionX(), Position::GetPositionY(), Position::GetPositionZ(), and Object::ToUnit().

Referenced by CalculatePath(), and CreateFilter().

Member Data Documentation

◆ _actualEndPosition

G3D::Vector3 PathGenerator::_actualEndPosition

private

Referenced by GetActualEndPosition(), SetActualEndPosition(), and SetEndPosition().

◆ _endPosition

G3D::Vector3 PathGenerator::_endPosition

private

Referenced by GetEndPosition(), and SetEndPosition().

◆ _filter

dtQueryFilterExt PathGenerator::_filter

private

Referenced by BuildPolyPath(), CreateFilter(), FindSmoothPath(), GetPolyByLocation(), and UpdateFilter().

◆ _forceDestination

bool PathGenerator::_forceDestination

private

Referenced by BuildPointPath(), and CalculatePath().

◆ _navMesh

dtNavMesh const* PathGenerator::_navMesh

private

Referenced by CalculatePath(), FindSmoothPath(), HaveTile(), and PathGenerator().

◆ _navMeshQuery

dtNavMeshQuery const* PathGenerator::_navMeshQuery

private

Referenced by BuildPointPath(), BuildPolyPath(), CalculatePath(), FindSmoothPath(), GetPathPolyByPosition(), GetPolyByLocation(), GetSteerTarget(), and PathGenerator().

◆ _pathPoints

Movement::PointsArray PathGenerator::_pathPoints

private

Referenced by BuildPointPath(), BuildPolyPath(), BuildShortcut(), Clear(), GetPath(), getPathLength(), NormalizePath(), and ShortenPathUntilDist().

◆ _pathPolyRefs

dtPolyRef PathGenerator::_pathPolyRefs[MAX_PATH_LENGTH]

private

Referenced by BuildPointPath(), BuildPolyPath(), GetPolyByLocation(), and PathGenerator().

◆ _pointPathLimit

uint32 PathGenerator::_pointPathLimit

private

Referenced by BuildPointPath(), and SetPathLengthLimit().

◆ _polyLength

uint32 PathGenerator::_polyLength

private

Referenced by BuildPointPath(), BuildPolyPath(), Clear(), and GetPolyByLocation().

◆ _slopeCheck

bool PathGenerator::_slopeCheck

private

Referenced by FindSmoothPath(), SetSlopeCheck(), and ShortenPathUntilDist().

◆ _source

WorldObject const* const PathGenerator::_source

private

Referenced by BuildPointPath(), BuildPolyPath(), CalculatePath(), CreateFilter(), FindSmoothPath(), GetNavTerrain(), IsSwimmableSegment(), IsWalkableClimb(), NormalizePath(), PathGenerator(), ShortenPathUntilDist(), and UpdateFilter().

◆ _startPosition

G3D::Vector3 PathGenerator::_startPosition

private

Referenced by getPathLength(), GetStartPosition(), and SetStartPosition().

◆ _type

PathType PathGenerator::_type

private

Referenced by AddFarFromPolyFlags(), BuildPointPath(), BuildPolyPath(), BuildShortcut(), CalculatePath(), and GetPathType().

◆ _useRaycast

bool PathGenerator::_useRaycast

private

Referenced by BuildPointPath(), BuildPolyPath(), and SetUseRaycast().

◆ _useStraightPath

bool PathGenerator::_useStraightPath

private

Referenced by BuildPointPath(), and SetUseStraightPath().

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PathGenerator()

◆ ~PathGenerator()

Member Function Documentation

◆ AddFarFromPolyFlags()

◆ BuildPointPath()

◆ BuildPolyPath()

◆ BuildShortcut()

◆ CalculatePath() [1/2]

◆ CalculatePath() [2/2]

◆ Clear()

◆ CreateFilter()

◆ Dist3DSqr()

◆ FindSmoothPath()

◆ FixupCorridor()

◆ GetActualEndPosition()

◆ GetEndPosition()

◆ GetNavTerrain()

◆ GetPath()

◆ getPathLength()

◆ GetPathPolyByPosition()

◆ GetPathType()

◆ GetPolyByLocation()

◆ GetRequiredHeightToClimb()

◆ GetStartPosition()

◆ GetSteerTarget()

◆ HaveTile()

◆ InRange()

◆ InRangeYZX()

◆ IsInvalidDestinationZ()

◆ IsSwimmableSegment() [1/2]

◆ IsSwimmableSegment() [2/2]

◆ IsWalkableClimb() [1/3]

◆ IsWalkableClimb() [2/3]

◆ IsWalkableClimb() [3/3]

◆ IsWaterPath()

◆ NormalizePath()

◆ SetActualEndPosition()

◆ SetEndPosition()

◆ SetPathLengthLimit()

◆ SetSlopeCheck()

◆ SetStartPosition()

◆ SetUseRaycast()

◆ SetUseStraightPath()

◆ ShortenPathUntilDist()

◆ UpdateFilter()

Member Data Documentation

◆ _actualEndPosition

◆ _endPosition

◆ _filter

◆ _forceDestination

◆ _navMesh

◆ _navMeshQuery

◆ _pathPoints

◆ _pathPolyRefs

◆ _pointPathLimit

◆ _polyLength

◆ _slopeCheck

◆ _source

◆ _startPosition

◆ _type

◆ _useRaycast

◆ _useStraightPath