From e07d76836d3e2d9ee67f63489b5ced155c821c4a Mon Sep 17 00:00:00 2001 From: Sebastian Valle Date: Sat, 5 Oct 2013 18:11:39 -0500 Subject: Core/MMaps: Separate the path from the walls to prevent falling off the edges client-side and improve the behavior. Thanks to Game2Mesh user in ownedcore. --- src/server/game/Movement/PathGenerator.cpp | 129 +++++++++++++++++++++++++++++ src/server/game/Movement/PathGenerator.h | 9 ++ 2 files changed, 138 insertions(+) (limited to 'src/server/game') diff --git a/src/server/game/Movement/PathGenerator.cpp b/src/server/game/Movement/PathGenerator.cpp index b5735e74d99..9704bd1feb2 100644 --- a/src/server/game/Movement/PathGenerator.cpp +++ b/src/server/game/Movement/PathGenerator.cpp @@ -27,6 +27,8 @@ #include "DetourCommon.h" #include "DetourNavMeshQuery.h" +float PathGenerator::MinWallDistance = 2.5f; + ////////////////// PathGenerator ////////////////// PathGenerator::PathGenerator(const Unit* owner) : _type(PATHFIND_BLANK), _endPosition(G3D::Vector3::zero()), @@ -131,6 +133,8 @@ bool PathGenerator::CalculatePath(float destX, float destY, float destZ, bool fo return false; } + SmoothPath(polyPickExt, resultHopCount, straightPath); // Separate the path from the walls + for (uint32 i = 0; i < resultHopCount; ++i) _pathPoints.push_back(G3D::Vector3(-straightPath[i * 3 + 2], -straightPath[i * 3 + 0], straightPath[i * 3 + 1])); @@ -157,4 +161,129 @@ void PathGenerator::CreateFilter() void PathGenerator::UpdateFilter() { +} + +float PathGenerator::GetTriangleArea(float* verts, int nv) +{ + float area = 0; + for (int i = 0; i < nv - 1; i++) + area += verts[i * 3] * verts[i * 3 + 5] - verts[i * 3 + 3] * verts[i * 3 + 2]; + area += verts[(nv - 1) * 3] * verts[2] - verts[0] * verts[(nv - 1) * 3 + 2]; + return area * 0.5f; +} + +bool PathGenerator::PointInPoly(float* pos, float* verts, int nv, float err) +{ + // Poly area + float area = abs(PathGenerator::GetTriangleArea(verts, nv)); + + // Calculate each area of the triangles + float testTri[9]; + memcpy(testTri, pos, sizeof(float) * 3); + float area1 = 0; + for(int i = 0; i < nv - 1; ++i) + { + memcpy(&testTri[3], &verts[i * 3], sizeof(float) * 3); + memcpy(&testTri[6], &verts[i * 3 + 3], sizeof(float) * 3); + area1 += abs(PathGenerator::GetTriangleArea(testTri, 3)); + if (area1 - err > area) + return false; + } + + // Last one + memcpy(&testTri[3], verts, sizeof(float) * 3); + memcpy(&testTri[6], &verts[nv * 3 - 3] , sizeof(float) * 3); + area1 += abs(PathGenerator::GetTriangleArea(testTri, 3)); + + return abs(area1 - area) < err; +} + +float PathGenerator::DistanceToWall(float* polyPickExt, float* pos, float* hitPos, float* hitNormal) +{ + float distanceToWall = 0; + dtPolyRef ref; + + dtStatus status = _navMeshQuery->findNearestPoly(pos, polyPickExt, &_filter, &ref, 0); + + if (!dtStatusSucceed(status) || ref == 0) + return -1; + + const dtMeshTile* tile = 0; + const dtPoly* poly = 0; + if (dtStatusFailed(_navMesh->getTileAndPolyByRef(ref, &tile, &poly))) + return -1; + + // Collect vertices. + float verts[DT_VERTS_PER_POLYGON * 3]; + int nv = 0; + for (unsigned char i = 0; i < poly->vertCount; ++i) + { + dtVcopy(&verts[nv * 3], &tile->verts[poly->verts[i] * 3]); + nv++; + } + + bool inside = PathGenerator::PointInPoly(pos, verts, nv, 0.05f); + if (!inside) + return -1; + + if (!dtStatusSucceed(_navMeshQuery->findDistanceToWall(ref, pos, 100.0f, &_filter, &distanceToWall, hitPos, hitNormal))) + return -1; + + return distanceToWall; +} + +void PathGenerator::SmoothPath(float* polyPickExt, int pathLength, float*& straightPath) +{ + float hitPos[3]; + float hitNormal[3]; + float testPos[3]; + float distanceToWall = 0; + float up[]= { 0, 1, 0 }; + float origDis = 0; + + for (int i = 1; i < pathLength - 1; ++i) + { + dtPolyRef pt; + float* curPoi = &straightPath[i * 3]; + distanceToWall = DistanceToWall(polyPickExt, curPoi, hitPos, hitNormal); + + if (distanceToWall < PathGenerator::MinWallDistance && distanceToWall >= 0) + { + float vec[3]; + dtVsub(vec, &straightPath[i * 3 - 3], &straightPath[i * 3]); + // If distanceToWall is 0 means the point is in the edge, so we can't get the hitpos. + if (distanceToWall == 0) + { + // Test the left side + dtVcross(testPos, vec, up); + dtVadd(testPos, testPos, curPoi); + float ft = PathGenerator::MinWallDistance / dtVdist(testPos, curPoi); + dtVlerp(testPos, curPoi, testPos, ft); + distanceToWall = DistanceToWall(polyPickExt, testPos, hitPos, hitNormal); + if (abs(PathGenerator::MinWallDistance - distanceToWall) > 0.1f) + { + // Test the right side + dtVcross(testPos, up, vec); + dtVadd(testPos, testPos, curPoi); + ft = PathGenerator::MinWallDistance / dtVdist(testPos, curPoi); + dtVlerp(testPos, curPoi, testPos, ft); + distanceToWall = DistanceToWall(polyPickExt, testPos, hitPos, hitNormal); + } + + // If the test point is better than the orig point, replace it. + if (abs(distanceToWall - PathGenerator::MinWallDistance) < 0.1f) + dtVcopy(curPoi, testPos); + } + else + { + // We get the hitpos with a ray + float ft = PathGenerator::MinWallDistance / distanceToWall; + dtVlerp(testPos, hitPos, curPoi, ft); + distanceToWall = DistanceToWall(polyPickExt, testPos, hitPos, hitNormal); + + if (abs(distanceToWall - PathGenerator::MinWallDistance) < 0.1f) + dtVcopy(curPoi, testPos); + } + } + } } \ No newline at end of file diff --git a/src/server/game/Movement/PathGenerator.h b/src/server/game/Movement/PathGenerator.h index 90e0f3b8f75..075d6dabc9f 100644 --- a/src/server/game/Movement/PathGenerator.h +++ b/src/server/game/Movement/PathGenerator.h @@ -61,6 +61,8 @@ class PathGenerator Movement::PointsArray const& GetPath() const { return _pathPoints; } PathType GetPathType() const { return _type; } + + static float MinWallDistance; private: Movement::PointsArray _pathPoints; // our actual (x,y,z) path to the target @@ -80,6 +82,13 @@ class PathGenerator void SetEndPosition(G3D::Vector3 const& point) { _actualEndPosition = point; _endPosition = point; } void SetActualEndPosition(G3D::Vector3 const& point) { _actualEndPosition = point; } + // Path smoothing + void SmoothPath(float* polyPickExt, int pathLength, float*& straightPath); + float DistanceToWall(float* polyPickExt, float* pos, float* hitPos, float* hitNormal); + // dtPointInPolygon will return false when the point is too close to the edge, so we rewrite the test function. + static bool PointInPoly(float* pos, float* verts, int nv, float err); + static float GetTriangleArea(float* verts, int nv); + void CreateFilter(); void UpdateFilter(); }; -- cgit v1.2.3