diff options
Diffstat (limited to 'src')
6 files changed, 1431 insertions, 0 deletions
diff --git a/src/server/collision/Management/MMapFactory.cpp b/src/server/collision/Management/MMapFactory.cpp new file mode 100644 index 00000000000..f4b2f3d47e4 --- /dev/null +++ b/src/server/collision/Management/MMapFactory.cpp @@ -0,0 +1,80 @@ +/* + * Copyright (C) 2008-2011 TrinityCore <http://www.trinitycore.org/> + * Copyright (C) 2005-2010 MaNGOS <http://getmangos.com/> + * + * 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, see <http://www.gnu.org/licenses/>. + */ + +#include "MMapFactory.h" +#include "World.h" +#include "Config.h" +#include <set> + +namespace MMAP +{ + // ######################## MMapFactory ######################## + // our global singleton copy + MMapManager *g_MMapManager = NULL; + + // stores list of mapids which do not use pathfinding + std::set<uint32>* g_mmapDisabledIds = NULL; + + MMapManager* MMapFactory::createOrGetMMapManager() + { + if (g_MMapManager == NULL) + g_MMapManager = new MMapManager(); + + return g_MMapManager; + } + + void MMapFactory::preventPathfindingOnMaps(const char* ignoreMapIds) + { + if (!g_mmapDisabledIds) + g_mmapDisabledIds = new std::set<uint32>(); + + uint32 strLenght = strlen(ignoreMapIds)+1; + char* mapList = new char[strLenght]; + memcpy(mapList, ignoreMapIds, sizeof(char)*strLenght); + + char* idstr = strtok(mapList, ","); + while (idstr) + { + g_mmapDisabledIds->insert(uint32(atoi(idstr))); + idstr = strtok(NULL, ","); + } + + delete[] mapList; + } + + bool MMapFactory::IsPathfindingEnabled(uint32 mapId) + { + return sWorld->getBoolConfig(CONFIG_ENABLE_MMAPS) + && g_mmapDisabledIds->find(mapId) == g_mmapDisabledIds->end(); + } + + void MMapFactory::clear() + { + if (g_mmapDisabledIds) + { + delete g_mmapDisabledIds; + g_mmapDisabledIds = NULL; + } + + if (g_MMapManager) + { + delete g_MMapManager; + g_MMapManager = NULL; + } + } +}
\ No newline at end of file diff --git a/src/server/collision/Management/MMapFactory.h b/src/server/collision/Management/MMapFactory.h new file mode 100644 index 00000000000..ab047333a19 --- /dev/null +++ b/src/server/collision/Management/MMapFactory.h @@ -0,0 +1,51 @@ +/* + * Copyright (C) 2008-2011 TrinityCore <http://www.trinitycore.org/> + * Copyright (C) 2005-2010 MaNGOS <http://getmangos.com/> + * + * 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, see <http://www.gnu.org/licenses/>. + */ + +#ifndef _MMAP_FACTORY_H +#define _MMAP_FACTORY_H + +#include "MMapManager.h" +#include "UnorderedMap.h" +#include "DetourAlloc.h" +#include "DetourNavMesh.h" +#include "DetourNavMeshQuery.h" + +namespace MMAP +{ + enum MMAP_LOAD_RESULT + { + MMAP_LOAD_RESULT_ERROR, + MMAP_LOAD_RESULT_OK, + MMAP_LOAD_RESULT_IGNORED, + }; + + // static class + // holds all mmap global data + // access point to MMapManager singleton + class MMapFactory + { + public: + static MMapManager* createOrGetMMapManager(); + static void clear(); + static void preventPathfindingOnMaps(const char* ignoreMapIds); + static bool IsPathfindingEnabled(uint32 mapId); + }; +} + +#endif + diff --git a/src/server/collision/Management/MMapManager.cpp b/src/server/collision/Management/MMapManager.cpp new file mode 100644 index 00000000000..aac5647a6de --- /dev/null +++ b/src/server/collision/Management/MMapManager.cpp @@ -0,0 +1,301 @@ +/* + * Copyright (C) 2008-2011 TrinityCore <http://www.trinitycore.org/> + * Copyright (C) 2005-2010 MaNGOS <http://getmangos.com/> + * + * 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, see <http://www.gnu.org/licenses/>. + */ + +#include "MMapManager.h" +#include "Log.h" +#include "World.h" + +namespace MMAP +{ + // ######################## MMapManager ######################## + MMapManager::~MMapManager() + { + for (MMapDataSet::iterator i = loadedMMaps.begin(); i != loadedMMaps.end(); ++i) + delete i->second; + + // by now we should not have maps loaded + // if we had, tiles in MMapData->mmapLoadedTiles, their actual data is lost! + } + + bool MMapManager::loadMapData(uint32 mapId) + { + // we already have this map loaded? + if (loadedMMaps.find(mapId) != loadedMMaps.end()) + return true; + + // load and init dtNavMesh - read parameters from file + uint32 pathLen = sWorld->GetDataPath().length() + strlen("mmaps/%03i.mmap")+1; + char *fileName = new char[pathLen]; + snprintf(fileName, pathLen, (sWorld->GetDataPath()+"mmaps/%03i.mmap").c_str(), mapId); + + FILE* file = fopen(fileName, "rb"); + if (!file) + { + sLog->outDebug(LOG_FILTER_MAPS, "MMAP:loadMapData: Error: Could not open mmap file '%s'", fileName); + delete [] fileName; + return false; + } + + dtNavMeshParams params; + fread(¶ms, sizeof(dtNavMeshParams), 1, file); + fclose(file); + + dtNavMesh* mesh = dtAllocNavMesh(); + ASSERT(mesh); + if (DT_SUCCESS != mesh->init(¶ms)) + { + dtFreeNavMesh(mesh); + sLog->outError("MMAP:loadMapData: Failed to initialize dtNavMesh for mmap %03u from file %s", mapId, fileName); + delete [] fileName; + return false; + } + + delete [] fileName; + + sLog->outDetail("MMAP:loadMapData: Loaded %03i.mmap", mapId); + + // store inside our map list + MMapData* mmap_data = new MMapData(mesh); + mmap_data->mmapLoadedTiles.clear(); + + loadedMMaps.insert(std::pair<uint32, MMapData*>(mapId, mmap_data)); + return true; + } + + uint32 MMapManager::packTileID(int32 x, int32 y) + { + return uint32(x << 16 | y); + } + + bool MMapManager::loadMap(uint32 mapId, int32 x, int32 y) + { + // make sure the mmap is loaded and ready to load tiles + if(!loadMapData(mapId)) + return false; + + // get this mmap data + MMapData* mmap = loadedMMaps[mapId]; + ASSERT(mmap->navMesh); + + // check if we already have this tile loaded + uint32 packedGridPos = packTileID(x, y); + if (mmap->mmapLoadedTiles.find(packedGridPos) != mmap->mmapLoadedTiles.end()) + { + //sLog->outError("MMAP:loadMap: Asked to load already loaded navmesh tile. %03u%02i%02i.mmtile", mapId, y, x); + return false; + } + + // load this tile :: mmaps/MMMXXYY.mmtile + uint32 pathLen = sWorld->GetDataPath().length() + strlen("mmaps/%03i%02i%02i.mmtile")+1; + char *fileName = new char[pathLen]; + // this change of y and x is needed because of mapbuilder.cpp (x and y are swapped there) so change it here so we dont need to re-extract. All swappes are done in other files. DONT CHANGE THIS! + snprintf(fileName, pathLen, (sWorld->GetDataPath()+"mmaps/%03i%02i%02i.mmtile").c_str(), mapId, y, x); + + FILE *file = fopen(fileName, "rb"); + if (!file) + { + sLog->outDebug(LOG_FILTER_MAPS, "MMAP:loadMap: Could not open mmtile file '%s'", fileName); + delete [] fileName; + return false; + } + delete [] fileName; + + // read header + MmapTileHeader fileHeader; + fread(&fileHeader, sizeof(MmapTileHeader), 1, file); + + if (fileHeader.mmapMagic != MMAP_MAGIC) + { + sLog->outError("MMAP:loadMap: Bad header in mmap %03u%02i%02i.mmtile", mapId, y, x); + return false; + } + + if (fileHeader.mmapVersion != MMAP_VERSION) + { + sLog->outError("MMAP:loadMap: %03u%02i%02i.mmtile was built with generator v%i, expected v%i", + mapId, x, y, fileHeader.mmapVersion, MMAP_VERSION); + return false; + } + + unsigned char* data = (unsigned char*)dtAlloc(fileHeader.size, DT_ALLOC_PERM); + ASSERT(data); + + size_t result = fread(data, fileHeader.size, 1, file); + if(!result) + { + sLog->outError("MMAP:loadMap: Bad header or data in mmap %03u%02i%02i.mmtile", mapId, y, x); + fclose(file); + return false; + } + + fclose(file); + + dtMeshHeader* header = (dtMeshHeader*)data; + dtTileRef tileRef = 0; + + // memory allocated for data is now managed by detour, and will be deallocated when the tile is removed + if (DT_SUCCESS == mmap->navMesh->addTile(data, fileHeader.size, DT_TILE_FREE_DATA, 0, &tileRef)) + { + mmap->mmapLoadedTiles.insert(std::pair<uint32, dtTileRef>(packedGridPos, tileRef)); + ++loadedTiles; + sLog->outDetail("MMAP:loadMap: Loaded mmtile %03i[%02i,%02i] into %03i[%02i,%02i]", mapId, y, x, mapId, header->x, header->y); + return true; + } + else + { + sLog->outError("MMAP:loadMap: Could not load %03u%02i%02i.mmtile into navmesh", mapId, y, x); + dtFree(data); + return false; + } + + return false; + } + + bool MMapManager::unloadMap(uint32 mapId, int32 x, int32 y) + { + // check if we have this map loaded + if (loadedMMaps.find(mapId) == loadedMMaps.end()) + { + // file may not exist, therefore not loaded + sLog->outDebug(LOG_FILTER_MAPS, "MMAP:unloadMap: Asked to unload not loaded navmesh map. %03u%02i%02i.mmtile", mapId, y, x); + return false; + } + + MMapData* mmap = loadedMMaps[mapId]; + + // check if we have this tile loaded + uint32 packedGridPos = packTileID(x, y); + if (mmap->mmapLoadedTiles.find(packedGridPos) == mmap->mmapLoadedTiles.end()) + { + // file may not exist, therefore not loaded + sLog->outDebug(LOG_FILTER_MAPS, "MMAP:unloadMap: Asked to unload not loaded navmesh tile. %03u%02i%02i.mmtile", mapId, y, x); + return false; + } + + dtTileRef tileRef = mmap->mmapLoadedTiles[packedGridPos]; + + // unload, and mark as non loaded + if (DT_SUCCESS != mmap->navMesh->removeTile(tileRef, NULL, NULL)) + { + // this is technically a memory leak + // if the grid is later reloaded, dtNavMesh::addTile will return error but no extra memory is used + // we cannot recover from this error - assert out + sLog->outError("MMAP:unloadMap: Could not unload %03u%02i%02i.mmtile from navmesh", mapId, y, x); + ASSERT(false); + } + else + { + mmap->mmapLoadedTiles.erase(packedGridPos); + --loadedTiles; + sLog->outDetail("MMAP:unloadMap: Unloaded mmtile %03i[%02i,%02i] from %03i", mapId, y, x, mapId); + return true; + } + + return false; + } + + bool MMapManager::unloadMap(uint32 mapId) + { + if (loadedMMaps.find(mapId) == loadedMMaps.end()) + { + // file may not exist, therefore not loaded + sLog->outDebug(LOG_FILTER_MAPS, "MMAP:unloadMap: Asked to unload not loaded navmesh map %03u", mapId); + return false; + } + + // unload all tiles from given map + MMapData* mmap = loadedMMaps[mapId]; + for (MMapTileSet::iterator i = mmap->mmapLoadedTiles.begin(); i != mmap->mmapLoadedTiles.end(); ++i) + { + uint32 x = (i->first >> 16); + uint32 y = (i->first & 0x0000FFFF); + if (DT_SUCCESS != mmap->navMesh->removeTile(i->second, NULL, NULL)) + sLog->outError("MMAP:unloadMap: Could not unload %03u%02i%02i.mmtile from navmesh", mapId, y, x); + else + { + --loadedTiles; + sLog->outDetail("MMAP:unloadMap: Unloaded mmtile %03i[%02i,%02i] from %03i", mapId, y, x, mapId); + } + } + + delete mmap; + loadedMMaps.erase(mapId); + sLog->outDetail("MMAP:unloadMap: Unloaded %03i.mmap", mapId); + + return true; + } + + bool MMapManager::unloadMapInstance(uint32 mapId, uint32 instanceId) + { + // check if we have this map loaded + if (loadedMMaps.find(mapId) == loadedMMaps.end()) + { + // file may not exist, therefore not loaded + sLog->outDebug(LOG_FILTER_MAPS, "MMAP:unloadMapInstance: Asked to unload not loaded navmesh map %03u", mapId); + return false; + } + + MMapData* mmap = loadedMMaps[mapId]; + if (mmap->navMeshQueries.find(instanceId) == mmap->navMeshQueries.end()) + { + sLog->outDebug(LOG_FILTER_MAPS, "MMAP:unloadMapInstance: Asked to unload not loaded dtNavMeshQuery mapId %03u instanceId %u", mapId, instanceId); + return false; + } + + dtNavMeshQuery* query = mmap->navMeshQueries[instanceId]; + + dtFreeNavMeshQuery(query); + mmap->navMeshQueries.erase(instanceId); + sLog->outDetail("MMAP:unloadMapInstance: Unloaded mapId %03u instanceId %u", mapId, instanceId); + + return true; + } + + dtNavMesh const* MMapManager::GetNavMesh(uint32 mapId) + { + if (loadedMMaps.find(mapId) == loadedMMaps.end()) + return NULL; + + return loadedMMaps[mapId]->navMesh; + } + + dtNavMeshQuery const* MMapManager::GetNavMeshQuery(uint32 mapId, uint32 instanceId) + { + if (loadedMMaps.find(mapId) == loadedMMaps.end()) + return NULL; + + MMapData* mmap = loadedMMaps[mapId]; + if (mmap->navMeshQueries.find(instanceId) == mmap->navMeshQueries.end()) + { + // allocate mesh query + dtNavMeshQuery* query = dtAllocNavMeshQuery(); + ASSERT(query); + if (DT_SUCCESS != query->init(mmap->navMesh, 1024)) + { + dtFreeNavMeshQuery(query); + sLog->outError("MMAP:GetNavMeshQuery: Failed to initialize dtNavMeshQuery for mapId %03u instanceId %u", mapId, instanceId); + return NULL; + } + + sLog->outDetail("MMAP:GetNavMeshQuery: created dtNavMeshQuery for mapId %03u instanceId %u", mapId, instanceId); + mmap->navMeshQueries.insert(std::pair<uint32, dtNavMeshQuery*>(instanceId, query)); + } + + return mmap->navMeshQueries[instanceId]; + } +}
\ No newline at end of file diff --git a/src/server/collision/Management/MMapManager.h b/src/server/collision/Management/MMapManager.h new file mode 100644 index 00000000000..8af452032d1 --- /dev/null +++ b/src/server/collision/Management/MMapManager.h @@ -0,0 +1,84 @@ +/* + * Copyright (C) 2008-2011 TrinityCore <http://www.trinitycore.org/> + * Copyright (C) 2005-2010 MaNGOS <http://getmangos.com/> + * + * 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, see <http://www.gnu.org/licenses/>. + */ + +#ifndef _MMAP_MANAGER_H +#define _MMAP_MANAGER_H + +#include "UnorderedMap.h" +#include "DetourAlloc.h" +#include "DetourNavMesh.h" +#include "DetourNavMeshQuery.h" + +// move map related classes +namespace MMAP +{ + typedef UNORDERED_MAP<uint32, dtTileRef> MMapTileSet; + typedef UNORDERED_MAP<uint32, dtNavMeshQuery*> NavMeshQuerySet; + + // dummy struct to hold map's mmap data + struct MMapData + { + MMapData(dtNavMesh* mesh) : navMesh(mesh) {} + ~MMapData() + { + for (NavMeshQuerySet::iterator i = navMeshQueries.begin(); i != navMeshQueries.end(); ++i) + dtFreeNavMeshQuery(i->second); + + if (navMesh) + dtFreeNavMesh(navMesh); + } + + dtNavMesh* navMesh; + + // we have to use single dtNavMeshQuery for every instance, since those are not thread safe + NavMeshQuerySet navMeshQueries; // instanceId to query + MMapTileSet mmapLoadedTiles; // maps [map grid coords] to [dtTile] + }; + + + typedef UNORDERED_MAP<uint32, MMapData*> MMapDataSet; + + // singleton class + // holds all all access to mmap loading unloading and meshes + class MMapManager + { + public: + MMapManager() : loadedTiles(0) {} + ~MMapManager(); + + bool loadMap(uint32 mapId, int32 x, int32 y); + bool unloadMap(uint32 mapId, int32 x, int32 y); + bool unloadMap(uint32 mapId); + bool unloadMapInstance(uint32 mapId, uint32 instanceId); + + // the returned [dtNavMeshQuery const*] is NOT threadsafe + dtNavMeshQuery const* GetNavMeshQuery(uint32 mapId, uint32 instanceId); + dtNavMesh const* GetNavMesh(uint32 mapId); + + uint32 getLoadedTilesCount() const { return loadedTiles; } + uint32 getLoadedMapsCount() const { return loadedMMaps.size(); } + private: + bool loadMapData(uint32 mapId); + uint32 packTileID(int32 x, int32 y); + + MMapDataSet loadedMMaps; + uint32 loadedTiles; + }; +} + +#endif
\ No newline at end of file diff --git a/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.cpp b/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.cpp new file mode 100644 index 00000000000..686c57cb634 --- /dev/null +++ b/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.cpp @@ -0,0 +1,780 @@ +/* + * Copyright (C) 2005-2011 MaNGOS <http://getmangos.com/> + * + * 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::calculate(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::calculate() 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_STAT_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->outStaticDebug("++ PathFinderMovementGenerator::calculate:: 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 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(); + m_type = (m_sourceUnit->GetTypeId() == TYPEID_UNIT && ((Creature*)m_sourceUnit)->canFly()) + ? 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("%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("%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]); + + // 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::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(); + + 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) + { + 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 new file mode 100644 index 00000000000..f4edd1a1789 --- /dev/null +++ b/src/server/game/Movement/MovementGenerators/PathFinderMovementGenerator.h @@ -0,0 +1,135 @@ +/* + * Copyright (C) 2005-2011 MaNGOS <http://getmangos.com/> + * + * 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 calculate(float destX, float destY, float destZ, bool forceDest = false); + + // option setters - use optional + void setUseStrightPath(bool useStraightPath) { m_useStraightPath = useStraightPath; }; + void setPathLengthLimit(float distance) { m_pointPathLimit = std::min<uint32>(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 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 |