From e0abbfd86c3ce23daa9bccbb9c181bfe08c2d0c4 Mon Sep 17 00:00:00 2001 From: Subv Date: Sat, 25 Aug 2012 21:55:03 -0500 Subject: Core/MMaps: Renamed PathFinderMovementGenerator to PathGenerator, since its not a MovementGenerator, and moved out of the MovementGenerators folder --- .../ConfusedMovementGenerator.cpp | 4 +- .../FleeingMovementGenerator.cpp | 4 +- .../PathFinderMovementGenerator.cpp | 808 --------------------- .../PathFinderMovementGenerator.h | 137 ---- .../TargetedMovementGenerator.cpp | 2 +- .../MovementGenerators/TargetedMovementGenerator.h | 4 +- src/server/game/Movement/PathGenerator.cpp | 808 +++++++++++++++++++++ src/server/game/Movement/PathGenerator.h | 137 ++++ src/server/game/Movement/Spline/MoveSplineInit.cpp | 2 +- src/server/game/Movement/Spline/MoveSplineInit.h | 2 +- 10 files changed, 954 insertions(+), 954 deletions(-) delete mode 100644 src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.cpp delete mode 100644 src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.h create mode 100644 src/server/game/Movement/PathGenerator.cpp create mode 100644 src/server/game/Movement/PathGenerator.h (limited to 'src') diff --git a/src/server/game/Movement/MovementGenerators/ConfusedMovementGenerator.cpp b/src/server/game/Movement/MovementGenerators/ConfusedMovementGenerator.cpp index a4f57a43701..b9b69baf0f8 100755 --- a/src/server/game/Movement/MovementGenerators/ConfusedMovementGenerator.cpp +++ b/src/server/game/Movement/MovementGenerators/ConfusedMovementGenerator.cpp @@ -19,7 +19,7 @@ #include "Creature.h" #include "MapManager.h" #include "ConfusedMovementGenerator.h" -#include "PathFinderMovementGenerator.h" +#include "PathGenerator.h" #include "VMapFactory.h" #include "MoveSplineInit.h" #include "MoveSpline.h" @@ -76,7 +76,7 @@ bool ConfusedMovementGenerator::Update(T &unit, const uint32 &diff) unit.UpdateAllowedPositionZ(x, y, z); - PathFinderMovementGenerator path(&unit); + PathGenerator path(&unit); path.setPathLengthLimit(30.0f); path.CalculatePath(x, y, z); if (path.getPathType() & PATHFIND_NOPATH) diff --git a/src/server/game/Movement/MovementGenerators/FleeingMovementGenerator.cpp b/src/server/game/Movement/MovementGenerators/FleeingMovementGenerator.cpp index 4e96c641be7..ae1e89c8562 100755 --- a/src/server/game/Movement/MovementGenerators/FleeingMovementGenerator.cpp +++ b/src/server/game/Movement/MovementGenerators/FleeingMovementGenerator.cpp @@ -20,7 +20,7 @@ #include "CreatureAI.h" #include "MapManager.h" #include "FleeingMovementGenerator.h" -#include "PathFinderMovementGenerator.h" +#include "PathGenerator.h" #include "ObjectAccessor.h" #include "MoveSplineInit.h" #include "MoveSpline.h" @@ -43,7 +43,7 @@ void FleeingMovementGenerator::_setTargetLocation(T &owner) owner.AddUnitState(UNIT_STATE_FLEEING_MOVE); - PathFinderMovementGenerator path(&owner); + PathGenerator path(&owner); path.setPathLengthLimit(30.0f); path.CalculatePath(x, y, z); if (path.getPathType() & PATHFIND_NOPATH) diff --git a/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.cpp b/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.cpp deleted file mode 100644 index adfd32c50b3..00000000000 --- a/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.cpp +++ /dev/null @@ -1,808 +0,0 @@ -/* - * Copyright (C) 2005-2011 MaNGOS - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include "PathFinderMovementGenerator.h" -#include "Map.h" -#include "Creature.h" -#include "MMapFactory.h" -#include "MMapManager.h" -#include "Log.h" - -#include "DetourCommon.h" -#include "DetourNavMeshQuery.h" - -////////////////// PathFinderMovementGenerator ////////////////// -PathFinderMovementGenerator::PathFinderMovementGenerator(const Unit* owner) : - m_polyLength(0), m_type(PATHFIND_BLANK), - m_useStraightPath(false), m_forceDestination(false), m_pointPathLimit(MAX_POINT_PATH_LENGTH), - m_sourceUnit(owner), m_navMesh(NULL), m_navMeshQuery(NULL) -{ - sLog->outDebug(LOG_FILTER_MAPS, "++ PathFinderMovementGenerator::PathFinderMovementGenerator for %u \n", m_sourceUnit->GetGUIDLow()); - - uint32 mapId = m_sourceUnit->GetMapId(); - if (MMAP::MMapFactory::IsPathfindingEnabled(mapId)) - { - MMAP::MMapManager* mmap = MMAP::MMapFactory::createOrGetMMapManager(); - m_navMesh = mmap->GetNavMesh(mapId); - m_navMeshQuery = mmap->GetNavMeshQuery(mapId, m_sourceUnit->GetInstanceId()); - } - - createFilter(); -} - -PathFinderMovementGenerator::~PathFinderMovementGenerator() -{ - sLog->outDebug(LOG_FILTER_MAPS, "++ PathFinderMovementGenerator::~PathFinderMovementGenerator() for %u \n", m_sourceUnit->GetGUIDLow()); -} - -bool PathFinderMovementGenerator::CalculatePath(float destX, float destY, float destZ, bool forceDest) -{ - if (!Trinity::IsValidMapCoord(destX, destY, destZ) || - !Trinity::IsValidMapCoord(m_sourceUnit->GetPositionX(), m_sourceUnit->GetPositionY(), m_sourceUnit->GetPositionZ())) - return false; - - Vector3 oldDest = getEndPosition(); - Vector3 dest(destX, destY, destZ); - setEndPosition(dest); - - float x, y, z; - m_sourceUnit->GetPosition(x, y, z); - Vector3 start(x, y, z); - setStartPosition(start); - - m_forceDestination = forceDest; - - sLog->outDebug(LOG_FILTER_MAPS, "++ PathFinderMovementGenerator::CalculatePath() for %u \n", m_sourceUnit->GetGUIDLow()); - - // 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 (!m_navMesh || !m_navMeshQuery || m_sourceUnit->HasUnitState(UNIT_STATE_IGNORE_PATHFINDING) || - !HaveTile(start) || !HaveTile(dest)) - { - BuildShortcut(); - m_type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH); - return true; - } - - updateFilter(); - - // check if destination moved - if not we can optimize something here - // we are following old, precalculated path? - float dist = m_sourceUnit->GetObjectSize(); - if (inRange(oldDest, dest, dist, dist) && m_pathPoints.size() > 2) - { - // our target is not moving - we just coming closer - // we are moving on precalculated path - enjoy the ride - sLog->outDebug(LOG_FILTER_MAPS, "++ PathFinderMovementGenerator::CalculatePath:: precalculated path\n"); - - m_pathPoints.erase(m_pathPoints.begin()); - return false; - } - else - { - // target moved, so we need to update the poly path - BuildPolyPath(start, dest); - return true; - } -} - -dtPolyRef PathFinderMovementGenerator::getPathPolyByPosition(const dtPolyRef *polyPath, uint32 polyPathSize, const float* point, float *distance) const -{ - 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 (DT_SUCCESS != m_navMeshQuery->closestPointOnPoly(polyPath[i], point, closestPoint)) - 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 = dtSqrt(minDist3d); - - return (minDist2d < 3.0f) ? nearestPoly : INVALID_POLYREF; -} - -dtPolyRef PathFinderMovementGenerator::getPolyByLocation(const float* point, float *distance) const -{ - // 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(m_pathPolyRefs, m_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}; - dtStatus result = m_navMeshQuery->findNearestPoly(point, extents, &m_filter, &polyRef, closestPoint); - if (DT_SUCCESS == result && polyRef != INVALID_POLYREF) - { - *distance = dtVdist(closestPoint, point); - return polyRef; - } - - // still nothing .. - // try with bigger search box - extents[1] = 200.0f; - result = m_navMeshQuery->findNearestPoly(point, extents, &m_filter, &polyRef, closestPoint); - if (DT_SUCCESS == result && polyRef != INVALID_POLYREF) - { - *distance = dtVdist(closestPoint, point); - return polyRef; - } - - return INVALID_POLYREF; -} - -void PathFinderMovementGenerator::BuildPolyPath(const Vector3 &startPos, const Vector3 &endPos) -{ - // *** 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) - { - sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: (startPoly == 0 || endPoly == 0)\n"); - BuildShortcut(); - bool path = m_sourceUnit->GetTypeId() == TYPEID_UNIT && m_sourceUnit->ToCreature()->CanFly(); - - bool waterPath = m_sourceUnit->GetTypeId() == TYPEID_UNIT && m_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 (int i = 0; i < m_pathPoints.size(); ++i) - { - LiquidData data; - m_sourceUnit->GetBaseMap()->getLiquidStatus(m_pathPoints[i].x, m_pathPoints[i].y, m_pathPoints[i].z, MAP_ALL_LIQUIDS, &data); - // One of the points is not in the water, cancel movement. - if (data.type_flags == MAP_LIQUID_TYPE_NO_WATER) - { - waterPath = false; - break; - } - } - } - - m_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) - { - sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: farFromPoly distToStartPoly=%.3f distToEndPoly=%.3f\n", distToStartPoly, distToEndPoly); - - bool buildShotrcut = false; - if (m_sourceUnit->GetTypeId() == TYPEID_UNIT) - { - Creature* owner = (Creature*)m_sourceUnit; - - Vector3 p = (distToStartPoly > 7.0f) ? startPos : endPos; - if (m_sourceUnit->GetBaseMap()->IsUnderWater(p.x, p.y, p.z)) - { - sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: underWater case\n"); - if (owner->canSwim()) - buildShotrcut = true; - } - else - { - sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: flying case\n"); - if (owner->CanFly()) - buildShotrcut = true; - } - } - - if (buildShotrcut) - { - BuildShortcut(); - m_type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH); - return; - } - else - { - float closestPoint[VERTEX_SIZE]; - // we may want to use closestPointOnPolyBoundary instead - if (DT_SUCCESS == m_navMeshQuery->closestPointOnPoly(endPoly, endPoint, closestPoint)) - { - dtVcopy(endPoint, closestPoint); - setActualEndPosition(Vector3(endPoint[2],endPoint[0],endPoint[1])); - } - - m_type = PATHFIND_INCOMPLETE; - } - } - - // *** poly path generating logic *** - - // start and end are on same polygon - // just need to move in straight line - if (startPoly == endPoly) - { - sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: (startPoly == endPoly)\n"); - - BuildShortcut(); - - m_pathPolyRefs[0] = startPoly; - m_polyLength = 1; - - m_type = farFromPoly ? PATHFIND_INCOMPLETE : PATHFIND_NORMAL; - sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: path type %d\n", m_type); - return; - } - - // look for startPoly/endPoly in current path - // TODO: we can merge it with getPathPolyByPosition() loop - bool startPolyFound = false; - bool endPolyFound = false; - uint32 pathStartIndex, pathEndIndex; - - if (m_polyLength) - { - for (pathStartIndex = 0; pathStartIndex < m_polyLength; ++pathStartIndex) - { - // here to carch few bugs - ASSERT(m_pathPolyRefs[pathStartIndex] != INVALID_POLYREF); - - if (m_pathPolyRefs[pathStartIndex] == startPoly) - { - startPolyFound = true; - break; - } - } - - for (pathEndIndex = m_polyLength-1; pathEndIndex > pathStartIndex; --pathEndIndex) - if (m_pathPolyRefs[pathEndIndex] == endPoly) - { - endPolyFound = true; - break; - } - } - - if (startPolyFound && endPolyFound) - { - sLog->outDebug(LOG_FILTER_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 - - m_polyLength = pathEndIndex - pathStartIndex + 1; - memmove(m_pathPolyRefs, m_pathPolyRefs+pathStartIndex, m_polyLength*sizeof(dtPolyRef)); - } - else if (startPolyFound && !endPolyFound) - { - sLog->outDebug(LOG_FILTER_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 - - m_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 - // TODO : play with the values here - uint32 prefixPolyLength = uint32(m_polyLength*0.8f + 0.5f); - memmove(m_pathPolyRefs, m_pathPolyRefs+pathStartIndex, prefixPolyLength*sizeof(dtPolyRef)); - - dtPolyRef suffixStartPoly = m_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 (DT_SUCCESS != m_navMeshQuery->closestPointOnPoly(suffixStartPoly, endPoint, suffixEndPoint)) - { - // we can hit offmesh connection as last poly - closestPointOnPoly() don't like that - // try to recover by using prev polyref - --prefixPolyLength; - suffixStartPoly = m_pathPolyRefs[prefixPolyLength-1]; - if (DT_SUCCESS != m_navMeshQuery->closestPointOnPoly(suffixStartPoly, endPoint, suffixEndPoint)) - { - // suffixStartPoly is still invalid, error state - BuildShortcut(); - m_type = PATHFIND_NOPATH; - return; - } - } - - // generate suffix - uint32 suffixPolyLength = 0; - dtStatus dtResult = m_navMeshQuery->findPath( - suffixStartPoly, // start polygon - endPoly, // end polygon - suffixEndPoint, // start position - endPoint, // end position - &m_filter, // polygon search filter - m_pathPolyRefs + prefixPolyLength - 1, // [out] path - (int*)&suffixPolyLength, - MAX_PATH_LENGTH-prefixPolyLength); // max number of polygons in output path - - if (!suffixPolyLength || dtResult != DT_SUCCESS) - { - // 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 - sLog->outError(LOG_FILTER_MAPS, "%u's Path Build failed: 0 length path", m_sourceUnit->GetGUIDLow()); - } - - sLog->outDebug(LOG_FILTER_MAPS, "++ m_polyLength=%u prefixPolyLength=%u suffixPolyLength=%u \n",m_polyLength, prefixPolyLength, suffixPolyLength); - - // new path = prefix + suffix - overlap - m_polyLength = prefixPolyLength + suffixPolyLength - 1; - } - else - { - sLog->outDebug(LOG_FILTER_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 = m_navMeshQuery->findPath( - startPoly, // start polygon - endPoly, // end polygon - startPoint, // start position - endPoint, // end position - &m_filter, // polygon search filter - m_pathPolyRefs, // [out] path - (int*)&m_polyLength, - MAX_PATH_LENGTH); // max number of polygons in output path - - if (!m_polyLength || dtResult != DT_SUCCESS) - { - // only happens if we passed bad data to findPath(), or navmesh is messed up - sLog->outError(LOG_FILTER_MAPS, "%u's Path Build failed: 0 length path", m_sourceUnit->GetGUIDLow()); - BuildShortcut(); - m_type = PATHFIND_NOPATH; - return; - } - } - - // by now we know what type of path we can get - if (m_pathPolyRefs[m_polyLength - 1] == endPoly && !(m_type & PATHFIND_INCOMPLETE)) - m_type = PATHFIND_NORMAL; - else - m_type = PATHFIND_INCOMPLETE; - - // generate the point-path out of our up-to-date poly-path - BuildPointPath(startPoint, endPoint); -} - -void PathFinderMovementGenerator::BuildPointPath(const float *startPoint, const float *endPoint) -{ - float pathPoints[MAX_POINT_PATH_LENGTH*VERTEX_SIZE]; - uint32 pointCount = 0; - dtStatus dtResult = DT_FAILURE; - if (m_useStraightPath) - { - dtResult = m_navMeshQuery->findStraightPath( - startPoint, // start position - endPoint, // end position - m_pathPolyRefs, // current path - m_polyLength, // lenth of current path - pathPoints, // [out] path corner points - NULL, // [out] flags - NULL, // [out] shortened path - (int*)&pointCount, - m_pointPathLimit); // maximum number of points/polygons to use - } - else - { - dtResult = findSmoothPath( - startPoint, // start position - endPoint, // end position - m_pathPolyRefs, // current path - m_polyLength, // length of current path - pathPoints, // [out] path corner points - (int*)&pointCount, - m_pointPathLimit); // maximum number of points - } - - if (pointCount < 2 || dtResult != DT_SUCCESS) - { - // only happens if pass bad data to findStraightPath or navmesh is broken - // single point paths can be generated here - // TODO : check the exact cases - sLog->outDebug(LOG_FILTER_MAPS, "++ PathFinderMovementGenerator::BuildPointPath FAILED! path sized %d returned\n", pointCount); - BuildShortcut(); - m_type = PATHFIND_NOPATH; - return; - } - - m_pathPoints.resize(pointCount); - for (uint32 i = 0; i < pointCount; ++i) - m_pathPoints[i] = 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(m_pathPoints[pointCount-1]); - - // force the given destination, if needed - if(m_forceDestination && - (!(m_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()); - m_pathPoints[m_pathPoints.size()-1] = getEndPosition(); - } - else - { - setActualEndPosition(getEndPosition()); - BuildShortcut(); - } - - m_type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH); - } - - sLog->outDebug(LOG_FILTER_MAPS, "++ PathFinderMovementGenerator::BuildPointPath path type %d size %d poly-size %d\n", m_type, pointCount, m_polyLength); -} - -void PathFinderMovementGenerator::NormalizePath() -{ - for (uint32 i = 0; i < m_pathPoints.size(); ++i) - m_sourceUnit->UpdateAllowedPositionZ(m_pathPoints[i].x, m_pathPoints[i].y, m_pathPoints[i].z); -} - -void PathFinderMovementGenerator::BuildShortcut() -{ - sLog->outDebug(LOG_FILTER_MAPS, "++ BuildShortcut :: making shortcut\n"); - - clear(); - - // make two point path, our curr pos is the start, and dest is the end - m_pathPoints.resize(2); - - // set start and a default next position - m_pathPoints[0] = getStartPosition(); - m_pathPoints[1] = getActualEndPosition(); - - NormalizePath(); - - m_type = PATHFIND_SHORTCUT; -} - -void PathFinderMovementGenerator::createFilter() -{ - uint16 includeFlags = 0; - uint16 excludeFlags = 0; - - if (m_sourceUnit->GetTypeId() == TYPEID_UNIT) - { - Creature* creature = (Creature*)m_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 if (m_sourceUnit->GetTypeId() == TYPEID_PLAYER) - { - // perfect support not possible, just stay 'safe' - includeFlags |= (NAV_GROUND | NAV_WATER); - } - - m_filter.setIncludeFlags(includeFlags); - m_filter.setExcludeFlags(excludeFlags); - - updateFilter(); -} - -void PathFinderMovementGenerator::updateFilter() -{ - // allow creatures to cheat and use different movement types if they are moved - // forcefully into terrain they can't normally move in - if (m_sourceUnit->IsInWater() || m_sourceUnit->IsUnderWater()) - { - uint16 includedFlags = m_filter.getIncludeFlags(); - includedFlags |= getNavTerrain(m_sourceUnit->GetPositionX(), - m_sourceUnit->GetPositionY(), - m_sourceUnit->GetPositionZ()); - - m_filter.setIncludeFlags(includedFlags); - } -} - -NavTerrain PathFinderMovementGenerator::getNavTerrain(float x, float y, float z) -{ - LiquidData data; - m_sourceUnit->GetBaseMap()->getLiquidStatus(x, y, z, MAP_ALL_LIQUIDS, &data); - - 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; - } -} - -bool PathFinderMovementGenerator::HaveTile(const Vector3 &p) const -{ - int tx, ty; - float point[VERTEX_SIZE] = {p.y, p.z, p.x}; - - m_navMesh->calcTileLoc(point, &tx, &ty); - return (m_navMesh->getTileAt(tx, ty) != NULL); -} - -uint32 PathFinderMovementGenerator::fixupCorridor(dtPolyRef* path, uint32 npath, uint32 maxPath, - const dtPolyRef* visited, uint32 nvisited) -{ - 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 > 0 ? 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; -} - -bool PathFinderMovementGenerator::getSteerTarget(const float* startPos, const float* endPos, - float minTargetDist, const dtPolyRef* path, uint32 pathSize, - float* steerPos, unsigned char& steerPosFlag, dtPolyRef& steerPosRef) -{ - // 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 = m_navMeshQuery->findStraightPath(startPos, endPos, path, pathSize, - steerPath, steerPathFlags, steerPathPolys, (int*)&nsteerPath, MAX_STEER_POINTS); - if (!nsteerPath || DT_SUCCESS != 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; -} - -dtStatus PathFinderMovementGenerator::findSmoothPath(const float* startPos, const float* endPos, - const dtPolyRef* polyPath, uint32 polyPathSize, - float* smoothPath, int* smoothPathSize, uint32 maxSmoothPathSize) -{ - *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 (DT_SUCCESS != m_navMeshQuery->closestPointOnPolyBoundary(polys[0], startPos, iterPos)) - return DT_FAILURE; - - if (DT_SUCCESS != m_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); - bool offMeshConnection = (steerPosFlag & DT_STRAIGHTPATH_OFFMESH_CONNECTION); - - // Find movement delta. - float delta[VERTEX_SIZE]; - dtVsub(delta, steerPos, iterPos); - float len = dtSqrt(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; - m_navMeshQuery->moveAlongSurface(polys[0], iterPos, moveTgt, &m_filter, result, visited, (int*)&nvisited, MAX_VISIT_POLY); - npolys = fixupCorridor(polys, npolys, MAX_PATH_LENGTH, visited, nvisited); - - m_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 startPos[VERTEX_SIZE], endPos[VERTEX_SIZE]; - if (DT_SUCCESS == m_navMesh->getOffMeshConnectionPolyEndPoints(prevRef, polyRef, startPos, endPos)) - { - if (nsmoothPath < maxSmoothPathSize) - { - dtVcopy(&smoothPath[nsmoothPath*VERTEX_SIZE], startPos); - nsmoothPath++; - } - // Move position at the other side of the off-mesh link. - dtVcopy(iterPos, endPos); - m_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; -} - -bool PathFinderMovementGenerator::inRangeYZX(const float* v1, const float* v2, float r, float h) const -{ - 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; -} - -bool PathFinderMovementGenerator::inRange(const Vector3 &p1, const Vector3 &p2, float r, float h) const -{ - Vector3 d = p1-p2; - return (d.x*d.x + d.y*d.y) < r*r && fabsf(d.z) < h; -} - -float PathFinderMovementGenerator::dist3DSqr(const Vector3 &p1, const Vector3 &p2) const -{ - return (p1-p2).squaredLength(); -} diff --git a/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.h b/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.h deleted file mode 100644 index 9029fc1804e..00000000000 --- a/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.h +++ /dev/null @@ -1,137 +0,0 @@ -/* - * Copyright (C) 2005-2011 MaNGOS - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#ifndef _PATH_INFO_H -#define _PATH_INFO_H - -#include "SharedDefines.h" -#include "DetourNavMesh.h" -#include "DetourNavMeshQuery.h" -#include "MoveSplineInitArgs.h" - -using Movement::Vector3; -using Movement::PointsArray; - -class Unit; - -// 74*4.0f=296y number_of_points*interval = max_path_len -// this is way more than actual evade range -// I think we can safely cut those down even more -#define MAX_PATH_LENGTH 74 -#define MAX_POINT_PATH_LENGTH 74 - -#define SMOOTH_PATH_STEP_SIZE 4.0f -#define SMOOTH_PATH_SLOP 0.3f - -#define VERTEX_SIZE 3 -#define INVALID_POLYREF 0 - -enum PathType -{ - PATHFIND_BLANK = 0x0000, // path not built yet - PATHFIND_NORMAL = 0x0001, // normal path - PATHFIND_SHORTCUT = 0x0002, // travel through obstacles, terrain, air, etc (old behavior) - PATHFIND_INCOMPLETE = 0x0004, // we have partial path to follow - getting closer to target - PATHFIND_NOPATH = 0x0008, // no valid path at all or error in generating one - PATHFIND_NOT_USING_PATH = 0x0010 // used when we are either flying/swiming or on map w/o mmaps -}; - -class PathFinderMovementGenerator -{ - public: - PathFinderMovementGenerator(Unit const* owner); - ~PathFinderMovementGenerator(); - - // Calculate the path from owner to given destination - // return: true if new path was calculated, false otherwise (no change needed) - bool CalculatePath(float destX, float destY, float destZ, bool forceDest = false); - - // option setters - use optional - void SetUseStraightPath(bool useStraightPath) { m_useStraightPath = useStraightPath; }; - void setPathLengthLimit(float distance) { m_pointPathLimit = std::min(uint32(distance/SMOOTH_PATH_STEP_SIZE), MAX_POINT_PATH_LENGTH); }; - - // result getters - Vector3 getStartPosition() const { return m_startPosition; } - Vector3 getEndPosition() const { return m_endPosition; } - Vector3 getActualEndPosition() const { return m_actualEndPosition; } - - PointsArray& getPath() { return m_pathPoints; } - PathType getPathType() const { return m_type; } - - private: - - dtPolyRef m_pathPolyRefs[MAX_PATH_LENGTH]; // array of detour polygon references - uint32 m_polyLength; // number of polygons in the path - - PointsArray m_pathPoints; // our actual (x,y,z) path to the target - PathType m_type; // tells what kind of path this is - - bool m_useStraightPath; // type of path will be generated - bool m_forceDestination; // when set, we will always arrive at given point - uint32 m_pointPathLimit; // limit point path size; min(this, MAX_POINT_PATH_LENGTH) - - Vector3 m_startPosition; // {x, y, z} of current location - Vector3 m_endPosition; // {x, y, z} of the destination - Vector3 m_actualEndPosition;// {x, y, z} of the closest possible point to given destination - - const Unit* const m_sourceUnit; // the unit that is moving - const dtNavMesh* m_navMesh; // the nav mesh - const dtNavMeshQuery* m_navMeshQuery; // the nav mesh query used to find the path - - dtQueryFilter m_filter; // use single filter for all movements, update it when needed - - void setStartPosition(Vector3 point) { m_startPosition = point; } - void setEndPosition(Vector3 point) { m_actualEndPosition = point; m_endPosition = point; } - void setActualEndPosition(Vector3 point) { m_actualEndPosition = point; } - - void NormalizePath(); - - void clear() - { - m_polyLength = 0; - m_pathPoints.clear(); - } - - bool inRange(const Vector3 &p1, const Vector3 &p2, float r, float h) const; - float dist3DSqr(const Vector3 &p1, const Vector3 &p2) const; - bool inRangeYZX(const float* v1, const float* v2, float r, float h) const; - - dtPolyRef getPathPolyByPosition(const dtPolyRef *polyPath, uint32 polyPathSize, const float* point, float *distance = NULL) const; - dtPolyRef getPolyByLocation(const float* point, float *distance) const; - bool HaveTile(const Vector3 &p) const; - - void BuildPolyPath(const Vector3 &startPos, const Vector3 &endPos); - void BuildPointPath(const float *startPoint, const float *endPoint); - void BuildShortcut(); - - NavTerrain getNavTerrain(float x, float y, float z); - void createFilter(); - void updateFilter(); - - // smooth path aux functions - uint32 fixupCorridor(dtPolyRef* path, uint32 npath, uint32 maxPath, - const dtPolyRef* visited, uint32 nvisited); - bool getSteerTarget(const float* startPos, const float* endPos, float minTargetDist, - const dtPolyRef* path, uint32 pathSize, float* steerPos, - unsigned char& steerPosFlag, dtPolyRef& steerPosRef); - dtStatus findSmoothPath(const float* startPos, const float* endPos, - const dtPolyRef* polyPath, uint32 polyPathSize, - float* smoothPath, int* smoothPathSize, uint32 smoothPathMaxSize); -}; - -#endif diff --git a/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.cpp b/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.cpp index 1b14cd385e8..6d322a56a80 100755 --- a/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.cpp +++ b/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.cpp @@ -64,7 +64,7 @@ void TargetedMovementGeneratorMedium::_setTargetLocation(T &owner) } if (!i_path) - i_path = new PathFinderMovementGenerator(&owner); + i_path = new PathGenerator(&owner); // allow pets following their master to cheat while generating paths bool forceDest = (owner.GetTypeId() == TYPEID_UNIT && ((Creature*)&owner)->isPet() diff --git a/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.h b/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.h index d855dfa1875..db5e05c7b23 100755 --- a/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.h +++ b/src/server/game/Movement/MovementGenerators/TargetedMovementGenerator.h @@ -23,7 +23,7 @@ #include "FollowerReference.h" #include "Timer.h" #include "Unit.h" -#include "PathFinderMovementGenerator.h" +#include "PathGenerator.h" class TargetedMovementGeneratorBase { @@ -61,7 +61,7 @@ class TargetedMovementGeneratorMedium : public MovementGeneratorMedium< T, D >, float i_angle; bool i_recalculateTravel : 1; bool i_targetReached : 1; - PathFinderMovementGenerator* i_path; + PathGenerator* i_path; }; template diff --git a/src/server/game/Movement/PathGenerator.cpp b/src/server/game/Movement/PathGenerator.cpp new file mode 100644 index 00000000000..4d7707020e1 --- /dev/null +++ b/src/server/game/Movement/PathGenerator.cpp @@ -0,0 +1,808 @@ +/* + * Copyright (C) 2005-2011 MaNGOS + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "PathGenerator.h" +#include "Map.h" +#include "Creature.h" +#include "MMapFactory.h" +#include "MMapManager.h" +#include "Log.h" + +#include "DetourCommon.h" +#include "DetourNavMeshQuery.h" + +////////////////// PathGenerator ////////////////// +PathGenerator::PathGenerator(const Unit* owner) : + m_polyLength(0), m_type(PATHFIND_BLANK), + m_useStraightPath(false), m_forceDestination(false), m_pointPathLimit(MAX_POINT_PATH_LENGTH), + m_sourceUnit(owner), m_navMesh(NULL), m_navMeshQuery(NULL) +{ + sLog->outDebug(LOG_FILTER_MAPS, "++ PathGenerator::PathGenerator for %u \n", m_sourceUnit->GetGUIDLow()); + + uint32 mapId = m_sourceUnit->GetMapId(); + if (MMAP::MMapFactory::IsPathfindingEnabled(mapId)) + { + MMAP::MMapManager* mmap = MMAP::MMapFactory::createOrGetMMapManager(); + m_navMesh = mmap->GetNavMesh(mapId); + m_navMeshQuery = mmap->GetNavMeshQuery(mapId, m_sourceUnit->GetInstanceId()); + } + + createFilter(); +} + +PathGenerator::~PathGenerator() +{ + sLog->outDebug(LOG_FILTER_MAPS, "++ PathGenerator::~PathGenerator() for %u \n", m_sourceUnit->GetGUIDLow()); +} + +bool PathGenerator::CalculatePath(float destX, float destY, float destZ, bool forceDest) +{ + if (!Trinity::IsValidMapCoord(destX, destY, destZ) || + !Trinity::IsValidMapCoord(m_sourceUnit->GetPositionX(), m_sourceUnit->GetPositionY(), m_sourceUnit->GetPositionZ())) + return false; + + Vector3 oldDest = getEndPosition(); + Vector3 dest(destX, destY, destZ); + setEndPosition(dest); + + float x, y, z; + m_sourceUnit->GetPosition(x, y, z); + Vector3 start(x, y, z); + setStartPosition(start); + + m_forceDestination = forceDest; + + sLog->outDebug(LOG_FILTER_MAPS, "++ PathGenerator::CalculatePath() for %u \n", m_sourceUnit->GetGUIDLow()); + + // 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 (!m_navMesh || !m_navMeshQuery || m_sourceUnit->HasUnitState(UNIT_STATE_IGNORE_PATHFINDING) || + !HaveTile(start) || !HaveTile(dest)) + { + BuildShortcut(); + m_type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH); + return true; + } + + updateFilter(); + + // check if destination moved - if not we can optimize something here + // we are following old, precalculated path? + float dist = m_sourceUnit->GetObjectSize(); + if (inRange(oldDest, dest, dist, dist) && m_pathPoints.size() > 2) + { + // our target is not moving - we just coming closer + // we are moving on precalculated path - enjoy the ride + sLog->outDebug(LOG_FILTER_MAPS, "++ PathGenerator::CalculatePath:: precalculated path\n"); + + m_pathPoints.erase(m_pathPoints.begin()); + return false; + } + else + { + // target moved, so we need to update the poly path + BuildPolyPath(start, dest); + return true; + } +} + +dtPolyRef PathGenerator::getPathPolyByPosition(const dtPolyRef *polyPath, uint32 polyPathSize, const float* point, float *distance) const +{ + 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 (DT_SUCCESS != m_navMeshQuery->closestPointOnPoly(polyPath[i], point, closestPoint)) + 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 = dtSqrt(minDist3d); + + return (minDist2d < 3.0f) ? nearestPoly : INVALID_POLYREF; +} + +dtPolyRef PathGenerator::getPolyByLocation(const float* point, float *distance) const +{ + // 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(m_pathPolyRefs, m_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}; + dtStatus result = m_navMeshQuery->findNearestPoly(point, extents, &m_filter, &polyRef, closestPoint); + if (DT_SUCCESS == result && polyRef != INVALID_POLYREF) + { + *distance = dtVdist(closestPoint, point); + return polyRef; + } + + // still nothing .. + // try with bigger search box + extents[1] = 200.0f; + result = m_navMeshQuery->findNearestPoly(point, extents, &m_filter, &polyRef, closestPoint); + if (DT_SUCCESS == result && polyRef != INVALID_POLYREF) + { + *distance = dtVdist(closestPoint, point); + return polyRef; + } + + return INVALID_POLYREF; +} + +void PathGenerator::BuildPolyPath(const Vector3 &startPos, const Vector3 &endPos) +{ + // *** 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) + { + sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: (startPoly == 0 || endPoly == 0)\n"); + BuildShortcut(); + bool path = m_sourceUnit->GetTypeId() == TYPEID_UNIT && m_sourceUnit->ToCreature()->CanFly(); + + bool waterPath = m_sourceUnit->GetTypeId() == TYPEID_UNIT && m_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 (int i = 0; i < m_pathPoints.size(); ++i) + { + LiquidData data; + m_sourceUnit->GetBaseMap()->getLiquidStatus(m_pathPoints[i].x, m_pathPoints[i].y, m_pathPoints[i].z, MAP_ALL_LIQUIDS, &data); + // One of the points is not in the water, cancel movement. + if (data.type_flags == MAP_LIQUID_TYPE_NO_WATER) + { + waterPath = false; + break; + } + } + } + + m_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) + { + sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: farFromPoly distToStartPoly=%.3f distToEndPoly=%.3f\n", distToStartPoly, distToEndPoly); + + bool buildShotrcut = false; + if (m_sourceUnit->GetTypeId() == TYPEID_UNIT) + { + Creature* owner = (Creature*)m_sourceUnit; + + Vector3 p = (distToStartPoly > 7.0f) ? startPos : endPos; + if (m_sourceUnit->GetBaseMap()->IsUnderWater(p.x, p.y, p.z)) + { + sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: underWater case\n"); + if (owner->canSwim()) + buildShotrcut = true; + } + else + { + sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: flying case\n"); + if (owner->CanFly()) + buildShotrcut = true; + } + } + + if (buildShotrcut) + { + BuildShortcut(); + m_type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH); + return; + } + else + { + float closestPoint[VERTEX_SIZE]; + // we may want to use closestPointOnPolyBoundary instead + if (DT_SUCCESS == m_navMeshQuery->closestPointOnPoly(endPoly, endPoint, closestPoint)) + { + dtVcopy(endPoint, closestPoint); + setActualEndPosition(Vector3(endPoint[2],endPoint[0],endPoint[1])); + } + + m_type = PATHFIND_INCOMPLETE; + } + } + + // *** poly path generating logic *** + + // start and end are on same polygon + // just need to move in straight line + if (startPoly == endPoly) + { + sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: (startPoly == endPoly)\n"); + + BuildShortcut(); + + m_pathPolyRefs[0] = startPoly; + m_polyLength = 1; + + m_type = farFromPoly ? PATHFIND_INCOMPLETE : PATHFIND_NORMAL; + sLog->outDebug(LOG_FILTER_MAPS, "++ BuildPolyPath :: path type %d\n", m_type); + return; + } + + // look for startPoly/endPoly in current path + // TODO: we can merge it with getPathPolyByPosition() loop + bool startPolyFound = false; + bool endPolyFound = false; + uint32 pathStartIndex, pathEndIndex; + + if (m_polyLength) + { + for (pathStartIndex = 0; pathStartIndex < m_polyLength; ++pathStartIndex) + { + // here to carch few bugs + ASSERT(m_pathPolyRefs[pathStartIndex] != INVALID_POLYREF); + + if (m_pathPolyRefs[pathStartIndex] == startPoly) + { + startPolyFound = true; + break; + } + } + + for (pathEndIndex = m_polyLength-1; pathEndIndex > pathStartIndex; --pathEndIndex) + if (m_pathPolyRefs[pathEndIndex] == endPoly) + { + endPolyFound = true; + break; + } + } + + if (startPolyFound && endPolyFound) + { + sLog->outDebug(LOG_FILTER_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 + + m_polyLength = pathEndIndex - pathStartIndex + 1; + memmove(m_pathPolyRefs, m_pathPolyRefs+pathStartIndex, m_polyLength*sizeof(dtPolyRef)); + } + else if (startPolyFound && !endPolyFound) + { + sLog->outDebug(LOG_FILTER_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 + + m_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 + // TODO : play with the values here + uint32 prefixPolyLength = uint32(m_polyLength*0.8f + 0.5f); + memmove(m_pathPolyRefs, m_pathPolyRefs+pathStartIndex, prefixPolyLength*sizeof(dtPolyRef)); + + dtPolyRef suffixStartPoly = m_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 (DT_SUCCESS != m_navMeshQuery->closestPointOnPoly(suffixStartPoly, endPoint, suffixEndPoint)) + { + // we can hit offmesh connection as last poly - closestPointOnPoly() don't like that + // try to recover by using prev polyref + --prefixPolyLength; + suffixStartPoly = m_pathPolyRefs[prefixPolyLength-1]; + if (DT_SUCCESS != m_navMeshQuery->closestPointOnPoly(suffixStartPoly, endPoint, suffixEndPoint)) + { + // suffixStartPoly is still invalid, error state + BuildShortcut(); + m_type = PATHFIND_NOPATH; + return; + } + } + + // generate suffix + uint32 suffixPolyLength = 0; + dtStatus dtResult = m_navMeshQuery->findPath( + suffixStartPoly, // start polygon + endPoly, // end polygon + suffixEndPoint, // start position + endPoint, // end position + &m_filter, // polygon search filter + m_pathPolyRefs + prefixPolyLength - 1, // [out] path + (int*)&suffixPolyLength, + MAX_PATH_LENGTH-prefixPolyLength); // max number of polygons in output path + + if (!suffixPolyLength || dtResult != DT_SUCCESS) + { + // 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 + sLog->outError(LOG_FILTER_MAPS, "%u's Path Build failed: 0 length path", m_sourceUnit->GetGUIDLow()); + } + + sLog->outDebug(LOG_FILTER_MAPS, "++ m_polyLength=%u prefixPolyLength=%u suffixPolyLength=%u \n",m_polyLength, prefixPolyLength, suffixPolyLength); + + // new path = prefix + suffix - overlap + m_polyLength = prefixPolyLength + suffixPolyLength - 1; + } + else + { + sLog->outDebug(LOG_FILTER_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 = m_navMeshQuery->findPath( + startPoly, // start polygon + endPoly, // end polygon + startPoint, // start position + endPoint, // end position + &m_filter, // polygon search filter + m_pathPolyRefs, // [out] path + (int*)&m_polyLength, + MAX_PATH_LENGTH); // max number of polygons in output path + + if (!m_polyLength || dtResult != DT_SUCCESS) + { + // only happens if we passed bad data to findPath(), or navmesh is messed up + sLog->outError(LOG_FILTER_MAPS, "%u's Path Build failed: 0 length path", m_sourceUnit->GetGUIDLow()); + BuildShortcut(); + m_type = PATHFIND_NOPATH; + return; + } + } + + // by now we know what type of path we can get + if (m_pathPolyRefs[m_polyLength - 1] == endPoly && !(m_type & PATHFIND_INCOMPLETE)) + m_type = PATHFIND_NORMAL; + else + m_type = PATHFIND_INCOMPLETE; + + // generate the point-path out of our up-to-date poly-path + BuildPointPath(startPoint, endPoint); +} + +void PathGenerator::BuildPointPath(const float *startPoint, const float *endPoint) +{ + float pathPoints[MAX_POINT_PATH_LENGTH*VERTEX_SIZE]; + uint32 pointCount = 0; + dtStatus dtResult = DT_FAILURE; + if (m_useStraightPath) + { + dtResult = m_navMeshQuery->findStraightPath( + startPoint, // start position + endPoint, // end position + m_pathPolyRefs, // current path + m_polyLength, // lenth of current path + pathPoints, // [out] path corner points + NULL, // [out] flags + NULL, // [out] shortened path + (int*)&pointCount, + m_pointPathLimit); // maximum number of points/polygons to use + } + else + { + dtResult = findSmoothPath( + startPoint, // start position + endPoint, // end position + m_pathPolyRefs, // current path + m_polyLength, // length of current path + pathPoints, // [out] path corner points + (int*)&pointCount, + m_pointPathLimit); // maximum number of points + } + + if (pointCount < 2 || dtResult != DT_SUCCESS) + { + // only happens if pass bad data to findStraightPath or navmesh is broken + // single point paths can be generated here + // TODO : check the exact cases + sLog->outDebug(LOG_FILTER_MAPS, "++ PathGenerator::BuildPointPath FAILED! path sized %d returned\n", pointCount); + BuildShortcut(); + m_type = PATHFIND_NOPATH; + return; + } + + m_pathPoints.resize(pointCount); + for (uint32 i = 0; i < pointCount; ++i) + m_pathPoints[i] = 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(m_pathPoints[pointCount-1]); + + // force the given destination, if needed + if(m_forceDestination && + (!(m_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()); + m_pathPoints[m_pathPoints.size()-1] = getEndPosition(); + } + else + { + setActualEndPosition(getEndPosition()); + BuildShortcut(); + } + + m_type = PathType(PATHFIND_NORMAL | PATHFIND_NOT_USING_PATH); + } + + sLog->outDebug(LOG_FILTER_MAPS, "++ PathGenerator::BuildPointPath path type %d size %d poly-size %d\n", m_type, pointCount, m_polyLength); +} + +void PathGenerator::NormalizePath() +{ + for (uint32 i = 0; i < m_pathPoints.size(); ++i) + m_sourceUnit->UpdateAllowedPositionZ(m_pathPoints[i].x, m_pathPoints[i].y, m_pathPoints[i].z); +} + +void PathGenerator::BuildShortcut() +{ + sLog->outDebug(LOG_FILTER_MAPS, "++ BuildShortcut :: making shortcut\n"); + + clear(); + + // make two point path, our curr pos is the start, and dest is the end + m_pathPoints.resize(2); + + // set start and a default next position + m_pathPoints[0] = getStartPosition(); + m_pathPoints[1] = getActualEndPosition(); + + NormalizePath(); + + m_type = PATHFIND_SHORTCUT; +} + +void PathGenerator::createFilter() +{ + uint16 includeFlags = 0; + uint16 excludeFlags = 0; + + if (m_sourceUnit->GetTypeId() == TYPEID_UNIT) + { + Creature* creature = (Creature*)m_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 if (m_sourceUnit->GetTypeId() == TYPEID_PLAYER) + { + // perfect support not possible, just stay 'safe' + includeFlags |= (NAV_GROUND | NAV_WATER); + } + + m_filter.setIncludeFlags(includeFlags); + m_filter.setExcludeFlags(excludeFlags); + + updateFilter(); +} + +void PathGenerator::updateFilter() +{ + // allow creatures to cheat and use different movement types if they are moved + // forcefully into terrain they can't normally move in + if (m_sourceUnit->IsInWater() || m_sourceUnit->IsUnderWater()) + { + uint16 includedFlags = m_filter.getIncludeFlags(); + includedFlags |= getNavTerrain(m_sourceUnit->GetPositionX(), + m_sourceUnit->GetPositionY(), + m_sourceUnit->GetPositionZ()); + + m_filter.setIncludeFlags(includedFlags); + } +} + +NavTerrain PathGenerator::getNavTerrain(float x, float y, float z) +{ + LiquidData data; + m_sourceUnit->GetBaseMap()->getLiquidStatus(x, y, z, MAP_ALL_LIQUIDS, &data); + + 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; + } +} + +bool PathGenerator::HaveTile(const Vector3 &p) const +{ + int tx, ty; + float point[VERTEX_SIZE] = {p.y, p.z, p.x}; + + m_navMesh->calcTileLoc(point, &tx, &ty); + return (m_navMesh->getTileAt(tx, ty) != NULL); +} + +uint32 PathGenerator::fixupCorridor(dtPolyRef* path, uint32 npath, uint32 maxPath, + const dtPolyRef* visited, uint32 nvisited) +{ + 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 > 0 ? 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; +} + +bool PathGenerator::getSteerTarget(const float* startPos, const float* endPos, + float minTargetDist, const dtPolyRef* path, uint32 pathSize, + float* steerPos, unsigned char& steerPosFlag, dtPolyRef& steerPosRef) +{ + // 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 = m_navMeshQuery->findStraightPath(startPos, endPos, path, pathSize, + steerPath, steerPathFlags, steerPathPolys, (int*)&nsteerPath, MAX_STEER_POINTS); + if (!nsteerPath || DT_SUCCESS != 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; +} + +dtStatus PathGenerator::findSmoothPath(const float* startPos, const float* endPos, + const dtPolyRef* polyPath, uint32 polyPathSize, + float* smoothPath, int* smoothPathSize, uint32 maxSmoothPathSize) +{ + *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 (DT_SUCCESS != m_navMeshQuery->closestPointOnPolyBoundary(polys[0], startPos, iterPos)) + return DT_FAILURE; + + if (DT_SUCCESS != m_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); + bool offMeshConnection = (steerPosFlag & DT_STRAIGHTPATH_OFFMESH_CONNECTION); + + // Find movement delta. + float delta[VERTEX_SIZE]; + dtVsub(delta, steerPos, iterPos); + float len = dtSqrt(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; + m_navMeshQuery->moveAlongSurface(polys[0], iterPos, moveTgt, &m_filter, result, visited, (int*)&nvisited, MAX_VISIT_POLY); + npolys = fixupCorridor(polys, npolys, MAX_PATH_LENGTH, visited, nvisited); + + m_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 startPos[VERTEX_SIZE], endPos[VERTEX_SIZE]; + if (DT_SUCCESS == m_navMesh->getOffMeshConnectionPolyEndPoints(prevRef, polyRef, startPos, endPos)) + { + if (nsmoothPath < maxSmoothPathSize) + { + dtVcopy(&smoothPath[nsmoothPath*VERTEX_SIZE], startPos); + nsmoothPath++; + } + // Move position at the other side of the off-mesh link. + dtVcopy(iterPos, endPos); + m_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; +} + +bool PathGenerator::inRangeYZX(const float* v1, const float* v2, float r, float h) const +{ + 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; +} + +bool PathGenerator::inRange(const Vector3 &p1, const Vector3 &p2, float r, float h) const +{ + Vector3 d = p1-p2; + return (d.x*d.x + d.y*d.y) < r*r && fabsf(d.z) < h; +} + +float PathGenerator::dist3DSqr(const Vector3 &p1, const Vector3 &p2) const +{ + return (p1-p2).squaredLength(); +} diff --git a/src/server/game/Movement/PathGenerator.h b/src/server/game/Movement/PathGenerator.h new file mode 100644 index 00000000000..a0d925cb11f --- /dev/null +++ b/src/server/game/Movement/PathGenerator.h @@ -0,0 +1,137 @@ +/* + * Copyright (C) 2005-2011 MaNGOS + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef _PATH_INFO_H +#define _PATH_INFO_H + +#include "SharedDefines.h" +#include "DetourNavMesh.h" +#include "DetourNavMeshQuery.h" +#include "MoveSplineInitArgs.h" + +using Movement::Vector3; +using Movement::PointsArray; + +class Unit; + +// 74*4.0f=296y number_of_points*interval = max_path_len +// this is way more than actual evade range +// I think we can safely cut those down even more +#define MAX_PATH_LENGTH 74 +#define MAX_POINT_PATH_LENGTH 74 + +#define SMOOTH_PATH_STEP_SIZE 4.0f +#define SMOOTH_PATH_SLOP 0.3f + +#define VERTEX_SIZE 3 +#define INVALID_POLYREF 0 + +enum PathType +{ + PATHFIND_BLANK = 0x0000, // path not built yet + PATHFIND_NORMAL = 0x0001, // normal path + PATHFIND_SHORTCUT = 0x0002, // travel through obstacles, terrain, air, etc (old behavior) + PATHFIND_INCOMPLETE = 0x0004, // we have partial path to follow - getting closer to target + PATHFIND_NOPATH = 0x0008, // no valid path at all or error in generating one + PATHFIND_NOT_USING_PATH = 0x0010 // used when we are either flying/swiming or on map w/o mmaps +}; + +class PathGenerator +{ + public: + PathGenerator(Unit const* owner); + ~PathGenerator(); + + // Calculate the path from owner to given destination + // return: true if new path was calculated, false otherwise (no change needed) + bool CalculatePath(float destX, float destY, float destZ, bool forceDest = false); + + // option setters - use optional + void SetUseStraightPath(bool useStraightPath) { m_useStraightPath = useStraightPath; }; + void setPathLengthLimit(float distance) { m_pointPathLimit = std::min(uint32(distance/SMOOTH_PATH_STEP_SIZE), MAX_POINT_PATH_LENGTH); }; + + // result getters + Vector3 getStartPosition() const { return m_startPosition; } + Vector3 getEndPosition() const { return m_endPosition; } + Vector3 getActualEndPosition() const { return m_actualEndPosition; } + + PointsArray& getPath() { return m_pathPoints; } + PathType getPathType() const { return m_type; } + + private: + + dtPolyRef m_pathPolyRefs[MAX_PATH_LENGTH]; // array of detour polygon references + uint32 m_polyLength; // number of polygons in the path + + PointsArray m_pathPoints; // our actual (x,y,z) path to the target + PathType m_type; // tells what kind of path this is + + bool m_useStraightPath; // type of path will be generated + bool m_forceDestination; // when set, we will always arrive at given point + uint32 m_pointPathLimit; // limit point path size; min(this, MAX_POINT_PATH_LENGTH) + + Vector3 m_startPosition; // {x, y, z} of current location + Vector3 m_endPosition; // {x, y, z} of the destination + Vector3 m_actualEndPosition;// {x, y, z} of the closest possible point to given destination + + const Unit* const m_sourceUnit; // the unit that is moving + const dtNavMesh* m_navMesh; // the nav mesh + const dtNavMeshQuery* m_navMeshQuery; // the nav mesh query used to find the path + + dtQueryFilter m_filter; // use single filter for all movements, update it when needed + + void setStartPosition(Vector3 point) { m_startPosition = point; } + void setEndPosition(Vector3 point) { m_actualEndPosition = point; m_endPosition = point; } + void setActualEndPosition(Vector3 point) { m_actualEndPosition = point; } + + void NormalizePath(); + + void clear() + { + m_polyLength = 0; + m_pathPoints.clear(); + } + + bool inRange(const Vector3 &p1, const Vector3 &p2, float r, float h) const; + float dist3DSqr(const Vector3 &p1, const Vector3 &p2) const; + bool inRangeYZX(const float* v1, const float* v2, float r, float h) const; + + dtPolyRef getPathPolyByPosition(const dtPolyRef *polyPath, uint32 polyPathSize, const float* point, float *distance = NULL) const; + dtPolyRef getPolyByLocation(const float* point, float *distance) const; + bool HaveTile(const Vector3 &p) const; + + void BuildPolyPath(const Vector3 &startPos, const Vector3 &endPos); + void BuildPointPath(const float *startPoint, const float *endPoint); + void BuildShortcut(); + + NavTerrain getNavTerrain(float x, float y, float z); + void createFilter(); + void updateFilter(); + + // smooth path aux functions + uint32 fixupCorridor(dtPolyRef* path, uint32 npath, uint32 maxPath, + const dtPolyRef* visited, uint32 nvisited); + bool getSteerTarget(const float* startPos, const float* endPos, float minTargetDist, + const dtPolyRef* path, uint32 pathSize, float* steerPos, + unsigned char& steerPosFlag, dtPolyRef& steerPosRef); + dtStatus findSmoothPath(const float* startPos, const float* endPos, + const dtPolyRef* polyPath, uint32 polyPathSize, + float* smoothPath, int* smoothPathSize, uint32 smoothPathMaxSize); +}; + +#endif diff --git a/src/server/game/Movement/Spline/MoveSplineInit.cpp b/src/server/game/Movement/Spline/MoveSplineInit.cpp index fa2197f815e..c5e314a8636 100644 --- a/src/server/game/Movement/Spline/MoveSplineInit.cpp +++ b/src/server/game/Movement/Spline/MoveSplineInit.cpp @@ -152,7 +152,7 @@ namespace Movement { if (generatePath) { - PathFinderMovementGenerator path(&unit); + PathGenerator path(&unit); path.CalculatePath(dest.x, dest.y, dest.z, forceDestination); MovebyPath(path.getPath()); } diff --git a/src/server/game/Movement/Spline/MoveSplineInit.h b/src/server/game/Movement/Spline/MoveSplineInit.h index 9130d2827e6..759fc73d7fd 100644 --- a/src/server/game/Movement/Spline/MoveSplineInit.h +++ b/src/server/game/Movement/Spline/MoveSplineInit.h @@ -20,7 +20,7 @@ #define TRINITYSERVER_MOVESPLINEINIT_H #include "MoveSplineInitArgs.h" -#include "PathFinderMovementGenerator.h" +#include "PathGenerator.h" class Unit; -- cgit v1.2.3