Index: binaries/data/mods/public/simulation/data/pathfinder.xml =================================================================== --- binaries/data/mods/public/simulation/data/pathfinder.xml +++ binaries/data/mods/public/simulation/data/pathfinder.xml @@ -11,7 +11,7 @@ pathfinding 2 1.0 - 0.8 + 1.0 pathfinding Index: source/simulation2/components/CCmpObstruction.cpp =================================================================== --- source/simulation2/components/CCmpObstruction.cpp +++ source/simulation2/components/CCmpObstruction.cpp @@ -637,7 +637,7 @@ if (!GetObstructionSquare(square)) return ret; // error - cmpObstructionManager->GetUnitsOnObstruction(square, ret, filter, false); + cmpObstructionManager->GetUnitsOnObstruction(square, ret, filter); cmpObstructionManager->GetStaticObstructionsOnObstruction(square, ret, filter); return ret; Index: source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- source/simulation2/components/CCmpObstructionManager.cpp +++ source/simulation2/components/CCmpObstructionManager.cpp @@ -467,7 +467,7 @@ virtual fixed DistanceToPoint(entity_id_t ent, entity_pos_t px, entity_pos_t pz) const; - virtual bool TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, bool relaxClearanceForUnits = false) const; + virtual bool TestLineAgainstUnitShapes(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r) const; virtual bool TestStaticShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, std::vector* out) const; virtual bool TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, std::vector* out) const; @@ -475,7 +475,7 @@ virtual void GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const; virtual void GetUnitObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const; virtual void GetStaticObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const; - virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict = false) const; + virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) const; virtual void GetStaticObstructionsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) const; virtual void SetPassabilityCircular(bool enabled) @@ -671,7 +671,7 @@ return Geometry::DistanceToSquare(CFixedVector2D(px - s.x, pz - s.z), s.u, s.v, CFixedVector2D(s.hw, s.hh)); } -bool CCmpObstructionManager::TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, bool relaxClearanceForUnits) const +bool CCmpObstructionManager::TestLineAgainstUnitShapes(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r) const { PROFILE("TestLine"); @@ -682,10 +682,8 @@ CFixedVector2D posMin (std::min(x0, x1) - r, std::min(z0, z1) - r); CFixedVector2D posMax (std::max(x0, x1) + r, std::max(z0, z1) + r); - // actual radius used for unit-unit collisions. If relaxClearanceForUnits, will be smaller to allow more overlap. - entity_pos_t unitUnitRadius = r; - if (relaxClearanceForUnits) - unitUnitRadius -= entity_pos_t::FromInt(1)/2; + // Be a bit more tolerant when checking units as that looks better and improves pathfinding behaviour overall. + entity_pos_t unitUnitRadius = r - entity_pos_t::FromInt(1)/2; std::vector unitShapes; m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); @@ -703,22 +701,6 @@ return true; } - std::vector staticShapes; - m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); - for (const entity_id_t& shape : staticShapes) - { - std::map::const_iterator it = m_StaticShapes.find(shape); - ENSURE(it != m_StaticShapes.end()); - - if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) - continue; - - CFixedVector2D center(it->second.x, it->second.z); - CFixedVector2D halfSize(it->second.hw + r, it->second.hh + r); - if (Geometry::TestRaySquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, it->second.u, it->second.v, halfSize)) - return true; - } - return false; } @@ -1026,7 +1008,7 @@ } } -void CCmpObstructionManager::GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict) const +void CCmpObstructionManager::GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) const { PROFILE("GetUnitsOnObstruction"); @@ -1062,10 +1044,7 @@ // Foundations need to be non-strict, as otherwise it sometimes detects the builder units // as being on the shape, so it orders them away. SimRasterize::Spans& newSpans = rasterizedRects[shape.clearance]; - if (strict) - SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance, Pathfinding::NAVCELL_SIZE); - else - SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance-Pathfinding::CLEARANCE_EXTENSION_RADIUS, Pathfinding::NAVCELL_SIZE); + SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance, Pathfinding::NAVCELL_SIZE); } SimRasterize::Spans& spans = rasterizedRects[shape.clearance]; Index: source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- source/simulation2/components/CCmpPathfinder.cpp +++ source/simulation2/components/CCmpPathfinder.cpp @@ -839,16 +839,14 @@ { PROFILE2_IFSPIKE("Check Movement", 0.001); - // Test against obstructions first. filter may discard pathfinding-blocking obstructions. - // Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly. - // This makes movement smoother and more natural for units, overall. + // Test against unit shapes, so that units cannot ocupy the same position in space. + // filter may be used to discard some shapes. CmpPtr cmpObstructionManager(GetSystemEntity()); - if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true)) + if (!cmpObstructionManager || cmpObstructionManager->TestLineAgainstUnitShapes(filter, x0, z0, x1, z1, r)) return false; - // Then test against the terrain grid. This should not be necessary - // But in case we allow terrain to change it will become so. - return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid); + // Then test against the terrain and rasterised static obstructions. + return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_Grid); } ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter, Index: source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- source/simulation2/components/CCmpPathfinder_Common.h +++ source/simulation2/components/CCmpPathfinder_Common.h @@ -151,7 +151,7 @@ if (passability.m_Clearance > max) max = passability.m_Clearance; - return max + Pathfinding::CLEARANCE_EXTENSION_RADIUS; + return max; } virtual const Grid& GetPassabilityGrid(); Index: source/simulation2/components/CCmpUnitMotion.cpp =================================================================== --- source/simulation2/components/CCmpUnitMotion.cpp +++ source/simulation2/components/CCmpUnitMotion.cpp @@ -982,7 +982,7 @@ square.z = m_LongPath.m_Waypoints.back().z; std::vector unitOnGoal; // don't ignore moving units as those might be units like us, ie not really moving. - cmpObstructionManager->GetUnitsOnObstruction(square, unitOnGoal, GetObstructionFilter(), true); + cmpObstructionManager->GetUnitsOnObstruction(square, unitOnGoal, GetObstructionFilter()); if (!unitOnGoal.empty()) m_LongPath.m_Waypoints.pop_back(); } Index: source/simulation2/components/ICmpObstructionManager.h =================================================================== --- source/simulation2/components/ICmpObstructionManager.h +++ source/simulation2/components/ICmpObstructionManager.h @@ -177,7 +177,7 @@ * @param relaxClearanceForUnits whether unit-unit collisions should be more permissive. * @return true if there is a collision */ - virtual bool TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, bool relaxClearanceForUnits) const = 0; + virtual bool TestLineAgainstUnitShapes(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r) const = 0; /** * Collision test a static square shape against the current set of shapes. @@ -254,9 +254,8 @@ * @param square the Obstruction squre we want to compare with. * @param out output list of obstructions * @param filter filter for the obstructing units - * @param strict whether to be strict in the check or more permissive (ie rasterize more or less). Default false. */ - virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict = false) const = 0; + virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) const = 0; /** * Get the obstruction square representing the given shape. Index: source/simulation2/helpers/Pathfinding.h =================================================================== --- source/simulation2/helpers/Pathfinding.h +++ source/simulation2/helpers/Pathfinding.h @@ -157,12 +157,6 @@ */ const entity_pos_t GOAL_DELTA = NAVCELL_SIZE/8; - /** - * To make sure the long-range pathfinder is more strict than the short-range one, - * we need to slightly over-rasterize. So we extend the clearance radius by 1. - */ - const entity_pos_t CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1); - /** * Compute the navcell indexes on the grid nearest to a given point * w, h are the grid dimensions, i.e. the number of navcells per side @@ -341,24 +335,7 @@ m_MaxShore = std::numeric_limits::max(); if (node.GetChild("Clearance").IsOk()) - { m_Clearance = node.GetChild("Clearance").ToFixed(); - - /* According to Philip who designed the original doc (in docs/pathfinder.pdf), - * clearance should usually be integer to ensure consistent behavior when rasterizing - * the passability map. - * This seems doubtful to me and my pathfinder fix makes having a clearance of 0.8 quite convenient - * so I comment out this check, but leave it here for the purpose of documentation should a bug arise. - - if (!(m_Clearance % Pathfinding::NAVCELL_SIZE).IsZero()) - { - // If clearance isn't an integer number of navcells then we'll - // probably get weird behaviour when expanding the navcell grid - // by clearance, vs expanding static obstructions by clearance - LOGWARNING("Pathfinder passability class has clearance %f, should be multiple of %f", - m_Clearance.ToFloat(), Pathfinding::NAVCELL_SIZE.ToFloat()); - }*/ - } else m_Clearance = fixed::Zero(); Index: source/simulation2/helpers/Rasterize.cpp =================================================================== --- source/simulation2/helpers/Rasterize.cpp +++ source/simulation2/helpers/Rasterize.cpp @@ -25,22 +25,9 @@ const ICmpObstructionManager::ObstructionSquare& shape, entity_pos_t clearance, entity_pos_t cellSize) { - // A long-standing issue with the pathfinding has been that the long-range one - // uses a AA navcell grid, while the short-range uses an accurate vector representation. - // This means we could get paths accepted by one but not both pathfinders. - // Since the new pathfinder, the short-range pathfinder's representation was usually - // encompassing the rasterisation of the long-range one for a building. - // This means that we could never get quite as close as the long-range pathfinder wanted. - // This could mean units tried going through impassable paths. - // To fix this, we need to make sure that the short-range pathfinder is always mostly - // included in the rasterisation. The easiest way is to rasterise more, thus this variable - // Since this is a very complicated subject, check out logs on 31/10/2015 for more detailled info. - // or ask wraitii about it. - // If the short-range pathfinder is sufficiently changed, this could become unnecessary and thus removed. - // A side effect is that the basic clearance has been set to 0.8, so removing this constant should be done - // in parallel with setting clearance back to 1 for the default passability class (though this isn't strictly necessary). - // Also: the code detecting foundation obstruction in CcmpObstructionManager had to be changed similarly. - entity_pos_t rasterClearance = clearance + Pathfinding::CLEARANCE_EXTENSION_RADIUS; + // Rasterise only navcells which are strictly inside the shape (+ clearance), so that navcells are more permissive than real obstructions. + // This makes the vertex pathfinder less permissive than the long-range pathfinder, which avoids stuck units. + entity_pos_t rasterClearance = clearance; // Get the bounds of cells that might possibly be within the shape // (We'll then test each of those cells more precisely) @@ -55,7 +42,6 @@ if (j1 <= j0) return; // empty bounds - this shouldn't happen - rasterClearance = rasterClearance.Multiply(rasterClearance); spans.reserve(j1 - j0);