Index: ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp (revision 17224) +++ ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp (revision 17225) @@ -1,1090 +1,1095 @@ /* Copyright (C) 2015 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpObstructionManager.h" #include "ICmpTerrain.h" #include "simulation2/MessageTypes.h" #include "simulation2/helpers/Geometry.h" #include "simulation2/helpers/Rasterize.h" #include "simulation2/helpers/Render.h" #include "simulation2/helpers/Spatial.h" #include "simulation2/serialization/SerializeTemplates.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "maths/MathUtil.h" #include "ps/Profile.h" #include "renderer/Scene.h" #include "ps/CLogger.h" // Externally, tags are opaque non-zero positive integers. // Internally, they are tagged (by shape) indexes into shape lists. // idx must be non-zero. #define TAG_IS_VALID(tag) ((tag).valid()) #define TAG_IS_UNIT(tag) (((tag).n & 1) == 0) #define TAG_IS_STATIC(tag) (((tag).n & 1) == 1) #define UNIT_INDEX_TO_TAG(idx) tag_t(((idx) << 1) | 0) #define STATIC_INDEX_TO_TAG(idx) tag_t(((idx) << 1) | 1) #define TAG_TO_INDEX(tag) ((tag).n >> 1) /** * Internal representation of axis-aligned circular shapes for moving units */ struct UnitShape { entity_id_t entity; entity_pos_t x, z; entity_pos_t clearance; ICmpObstructionManager::flags_t flags; entity_id_t group; // control group (typically the owner entity, or a formation controller entity) (units ignore collisions with others in the same group) }; /** * Internal representation of arbitrary-rotation static square shapes for buildings */ struct StaticShape { entity_id_t entity; entity_pos_t x, z; // world-space coordinates CFixedVector2D u, v; // orthogonal unit vectors - axes of local coordinate space entity_pos_t hw, hh; // half width/height in local coordinate space ICmpObstructionManager::flags_t flags; entity_id_t group; entity_id_t group2; }; /** * Serialization helper template for UnitShape */ struct SerializeUnitShape { template void operator()(S& serialize, const char* UNUSED(name), UnitShape& value) { serialize.NumberU32_Unbounded("entity", value.entity); serialize.NumberFixed_Unbounded("x", value.x); serialize.NumberFixed_Unbounded("z", value.z); serialize.NumberFixed_Unbounded("clearance", value.clearance); serialize.NumberU8_Unbounded("flags", value.flags); serialize.NumberU32_Unbounded("group", value.group); } }; /** * Serialization helper template for StaticShape */ struct SerializeStaticShape { template void operator()(S& serialize, const char* UNUSED(name), StaticShape& value) { serialize.NumberU32_Unbounded("entity", value.entity); serialize.NumberFixed_Unbounded("x", value.x); serialize.NumberFixed_Unbounded("z", value.z); serialize.NumberFixed_Unbounded("u.x", value.u.X); serialize.NumberFixed_Unbounded("u.y", value.u.Y); serialize.NumberFixed_Unbounded("v.x", value.v.X); serialize.NumberFixed_Unbounded("v.y", value.v.Y); serialize.NumberFixed_Unbounded("hw", value.hw); serialize.NumberFixed_Unbounded("hh", value.hh); serialize.NumberU8_Unbounded("flags", value.flags); serialize.NumberU32_Unbounded("group", value.group); serialize.NumberU32_Unbounded("group2", value.group2); } }; class CCmpObstructionManager : public ICmpObstructionManager { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays } DEFAULT_COMPONENT_ALLOCATOR(ObstructionManager) bool m_DebugOverlayEnabled; bool m_DebugOverlayDirty; std::vector m_DebugOverlayLines; SpatialSubdivision m_UnitSubdivision; SpatialSubdivision m_StaticSubdivision; // TODO: using std::map is a bit inefficient; is there a better way to store these? std::map m_UnitShapes; std::map m_StaticShapes; u32 m_UnitShapeNext; // next allocated id u32 m_StaticShapeNext; entity_pos_t m_MaxClearance; bool m_PassabilityCircular; entity_pos_t m_WorldX0; entity_pos_t m_WorldZ0; entity_pos_t m_WorldX1; entity_pos_t m_WorldZ1; u16 m_TerrainTiles; static std::string GetSchema() { return ""; } virtual void Init(const CParamNode& UNUSED(paramNode)) { m_DebugOverlayEnabled = false; m_DebugOverlayDirty = true; m_UnitShapeNext = 1; m_StaticShapeNext = 1; m_UpdateInformations.dirty = true; m_UpdateInformations.globallyDirty = true; m_UpdateInformations.globalRecompute = true; m_PassabilityCircular = false; m_WorldX0 = m_WorldZ0 = m_WorldX1 = m_WorldZ1 = entity_pos_t::Zero(); m_TerrainTiles = 0; // Initialise with bogus values (these will get replaced when // SetBounds is called) ResetSubdivisions(entity_pos_t::FromInt(1024), entity_pos_t::FromInt(1024)); } virtual void Deinit() { } template void SerializeCommon(S& serialize) { SerializeSpatialSubdivision()(serialize, "unit subdiv", m_UnitSubdivision); SerializeSpatialSubdivision()(serialize, "static subdiv", m_StaticSubdivision); serialize.NumberFixed_Unbounded("max clearance", m_MaxClearance); SerializeMap()(serialize, "unit shapes", m_UnitShapes); SerializeMap()(serialize, "static shapes", m_StaticShapes); serialize.NumberU32_Unbounded("unit shape next", m_UnitShapeNext); serialize.NumberU32_Unbounded("static shape next", m_StaticShapeNext); serialize.Bool("circular", m_PassabilityCircular); serialize.NumberFixed_Unbounded("world x0", m_WorldX0); serialize.NumberFixed_Unbounded("world z0", m_WorldZ0); serialize.NumberFixed_Unbounded("world x1", m_WorldX1); serialize.NumberFixed_Unbounded("world z1", m_WorldZ1); serialize.NumberU16_Unbounded("terrain tiles", m_TerrainTiles); } virtual void Serialize(ISerializer& serialize) { // TODO: this could perhaps be optimised by not storing all the obstructions, // and instead regenerating them from the other entities on Deserialize SerializeCommon(serialize); } virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) { Init(paramNode); SerializeCommon(deserialize); m_UpdateInformations.dirtinessGrid = Grid(m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE, m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE); } virtual void HandleMessage(const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_RenderSubmit: { const CMessageRenderSubmit& msgData = static_cast (msg); RenderSubmit(msgData.collector); break; } } } // NB: on deserialization, this function is not called after the component is reset. // So anything that happens here should be safely serialized. virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1) { m_WorldX0 = x0; m_WorldZ0 = z0; m_WorldX1 = x1; m_WorldZ1 = z1; MakeDirtyAll(); // Subdivision system bounds: ENSURE(x0.IsZero() && z0.IsZero()); // don't bother implementing non-zero offsets yet ResetSubdivisions(x1, z1); CmpPtr cmpTerrain(GetSystemEntity()); if (!cmpTerrain) return; m_TerrainTiles = cmpTerrain->GetTilesPerSide(); m_UpdateInformations.dirtinessGrid = Grid(m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE, m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE); CmpPtr cmpPathfinder(GetSystemEntity()); if (cmpPathfinder) m_MaxClearance = cmpPathfinder->GetMaximumClearance(); } void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1) { // Use 8x8 tile subdivisions // (TODO: find the optimal number instead of blindly guessing) m_UnitSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); m_StaticSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) { CFixedVector2D center(it->second.x, it->second.z); CFixedVector2D halfSize(it->second.clearance, it->second.clearance); m_UnitSubdivision.Add(it->first, center - halfSize, center + halfSize); } for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { CFixedVector2D center(it->second.x, it->second.z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(it->second.u, it->second.v, CFixedVector2D(it->second.hw, it->second.hh)); m_StaticSubdivision.Add(it->first, center - bbHalfSize, center + bbHalfSize); } } virtual tag_t AddUnitShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, flags_t flags, entity_id_t group) { UnitShape shape = { ent, x, z, clearance, flags, group }; u32 id = m_UnitShapeNext++; m_UnitShapes[id] = shape; m_UnitSubdivision.Add(id, CFixedVector2D(x - clearance, z - clearance), CFixedVector2D(x + clearance, z + clearance)); MakeDirtyUnit(flags, id, shape); return UNIT_INDEX_TO_TAG(id); } virtual tag_t AddStaticShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h, flags_t flags, entity_id_t group, entity_id_t group2 /* = INVALID_ENTITY */) { fixed s, c; sincos_approx(a, s, c); CFixedVector2D u(c, -s); CFixedVector2D v(s, c); StaticShape shape = { ent, x, z, u, v, w/2, h/2, flags, group, group2 }; u32 id = m_StaticShapeNext++; m_StaticShapes[id] = shape; CFixedVector2D center(x, z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(w/2, h/2)); m_StaticSubdivision.Add(id, center - bbHalfSize, center + bbHalfSize); MakeDirtyStatic(flags, id, shape); return STATIC_INDEX_TO_TAG(id); } virtual ObstructionSquare GetUnitShapeObstruction(entity_pos_t x, entity_pos_t z, entity_pos_t clearance) { CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero()); CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1)); ObstructionSquare o = { x, z, u, v, clearance, clearance }; return o; } virtual ObstructionSquare GetStaticShapeObstruction(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) { fixed s, c; sincos_approx(a, s, c); CFixedVector2D u(c, -s); CFixedVector2D v(s, c); ObstructionSquare o = { x, z, u, v, w/2, h/2 }; return o; } virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a) { ENSURE(TAG_IS_VALID(tag)); if (TAG_IS_UNIT(tag)) { UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region m_UnitSubdivision.Move(TAG_TO_INDEX(tag), CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance), CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance), CFixedVector2D(x - shape.clearance, z - shape.clearance), CFixedVector2D(x + shape.clearance, z + shape.clearance)); shape.x = x; shape.z = z; MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the new shape region } else { fixed s, c; sincos_approx(a, s, c); CFixedVector2D u(c, -s); CFixedVector2D v(s, c); StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region CFixedVector2D fromBbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh)); CFixedVector2D toBbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(shape.hw, shape.hh)); m_StaticSubdivision.Move(TAG_TO_INDEX(tag), CFixedVector2D(shape.x, shape.z) - fromBbHalfSize, CFixedVector2D(shape.x, shape.z) + fromBbHalfSize, CFixedVector2D(x, z) - toBbHalfSize, CFixedVector2D(x, z) + toBbHalfSize); shape.x = x; shape.z = z; shape.u = u; shape.v = v; MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the new shape region } } virtual void SetUnitMovingFlag(tag_t tag, bool moving) { ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag)); if (TAG_IS_UNIT(tag)) { UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; if (moving) shape.flags |= FLAG_MOVING; else shape.flags &= (flags_t)~FLAG_MOVING; MakeDirtyDebug(); } } virtual void SetUnitControlGroup(tag_t tag, entity_id_t group) { ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag)); if (TAG_IS_UNIT(tag)) { UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; shape.group = group; } } virtual void SetStaticControlGroup(tag_t tag, entity_id_t group, entity_id_t group2) { ENSURE(TAG_IS_VALID(tag) && TAG_IS_STATIC(tag)); if (TAG_IS_STATIC(tag)) { StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; shape.group = group; shape.group2 = group2; } } virtual void RemoveShape(tag_t tag) { ENSURE(TAG_IS_VALID(tag)); if (TAG_IS_UNIT(tag)) { UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; m_UnitSubdivision.Remove(TAG_TO_INDEX(tag), CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance), CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance)); MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); m_UnitShapes.erase(TAG_TO_INDEX(tag)); } else { StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; CFixedVector2D center(shape.x, shape.z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh)); m_StaticSubdivision.Remove(TAG_TO_INDEX(tag), center - bbHalfSize, center + bbHalfSize); MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); m_StaticShapes.erase(TAG_TO_INDEX(tag)); } } virtual ObstructionSquare GetObstruction(tag_t tag) { ENSURE(TAG_IS_VALID(tag)); if (TAG_IS_UNIT(tag)) { UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero()); CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1)); ObstructionSquare o = { shape.x, shape.z, u, v, shape.clearance, shape.clearance }; return o; } else { StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; ObstructionSquare o = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh }; return o; } } 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); 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); virtual bool TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, std::vector* out); virtual void Rasterize(Grid& grid, const std::vector& passClasses, bool fullUpdate); 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); 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); 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); - virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter); + virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict = false); virtual void SetPassabilityCircular(bool enabled) { m_PassabilityCircular = enabled; MakeDirtyAll(); CMessageObstructionMapShapeChanged msg; GetSimContext().GetComponentManager().BroadcastMessage(msg); } virtual bool GetPassabilityCircular() const { return m_PassabilityCircular; } virtual void SetDebugOverlay(bool enabled) { m_DebugOverlayEnabled = enabled; m_DebugOverlayDirty = true; if (!enabled) m_DebugOverlayLines.clear(); } void RenderSubmit(SceneCollector& collector); virtual void UpdateInformations(GridUpdateInformation& informations) { // If the pathfinder wants to perform a full update, don't change that. if (m_UpdateInformations.dirty && !informations.globalRecompute) informations = m_UpdateInformations; m_UpdateInformations.Clean(); } private: // Dynamic updates for the long-range pathfinder GridUpdateInformation m_UpdateInformations; // These vectors might contain shapes that were deleted std::vector m_DirtyStaticShapes; std::vector m_DirtyUnitShapes; /** * Mark all previous Rasterize()d grids as dirty, and the debug display. * Call this when the world bounds have changed. */ void MakeDirtyAll() { m_UpdateInformations.dirty = true; m_UpdateInformations.globallyDirty = true; m_UpdateInformations.globalRecompute = true; m_UpdateInformations.dirtinessGrid.reset(); m_DebugOverlayDirty = true; } /** * Mark the debug display as dirty. * Call this when nothing has changed except a unit's 'moving' flag. */ void MakeDirtyDebug() { m_DebugOverlayDirty = true; } inline void MarkDirtinessGrid(const entity_pos_t& x, const entity_pos_t& z, const entity_pos_t& r) { MarkDirtinessGrid(x, z, CFixedVector2D(r, r)); } inline void MarkDirtinessGrid(const entity_pos_t& x, const entity_pos_t& z, const CFixedVector2D& hbox) { ENSURE(m_UpdateInformations.dirtinessGrid.m_W == m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE && m_UpdateInformations.dirtinessGrid.m_H == m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE); if (m_TerrainTiles == 0) return; u16 j0, j1, i0, i1; Pathfinding::NearestNavcell(x - hbox.X, z - hbox.Y, i0, j0, m_UpdateInformations.dirtinessGrid.m_W, m_UpdateInformations.dirtinessGrid.m_H); Pathfinding::NearestNavcell(x + hbox.X, z + hbox.Y, i1, j1, m_UpdateInformations.dirtinessGrid.m_W, m_UpdateInformations.dirtinessGrid.m_H); for (int j = j0; j < j1; ++j) for (int i = i0; i < i1; ++i) m_UpdateInformations.dirtinessGrid.set(i, j, 1); } /** * Mark all previous Rasterize()d grids as dirty, if they depend on this shape. * Call this when a static shape has changed. */ void MakeDirtyStatic(flags_t flags, u32 index, const StaticShape& shape) { m_DebugOverlayDirty = true; if (flags & (FLAG_BLOCK_PATHFINDING | FLAG_BLOCK_FOUNDATION)) { m_UpdateInformations.dirty = true; if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), index) == m_DirtyStaticShapes.end()) m_DirtyStaticShapes.push_back(index); // All shapes overlapping the updated part of the grid should be dirtied too. // We are going to invalidate the region of the grid corresponding to the modified shape plus its clearance, // and we need to get the shapes whose clearance can overlap this area. So we need to extend the search area // by two times the maximum clearance. CFixedVector2D center(shape.x, shape.z); CFixedVector2D hbox = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh)); CFixedVector2D expand(m_MaxClearance, m_MaxClearance); std::vector staticsNear; m_StaticSubdivision.GetInRange(staticsNear, center - hbox - expand*2, center + hbox + expand*2); for (u32& staticId : staticsNear) if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end()) m_DirtyStaticShapes.push_back(staticId); std::vector unitsNear; m_UnitSubdivision.GetInRange(unitsNear, center - hbox - expand*2, center + hbox + expand*2); for (u32& unitId : unitsNear) if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end()) m_DirtyUnitShapes.push_back(unitId); MarkDirtinessGrid(shape.x, shape.z, hbox + expand); } } /** * Mark all previous Rasterize()d grids as dirty, if they depend on this shape. * Call this when a unit shape has changed. */ void MakeDirtyUnit(flags_t flags, u32 index, const UnitShape& shape) { m_DebugOverlayDirty = true; if (flags & (FLAG_BLOCK_PATHFINDING | FLAG_BLOCK_FOUNDATION)) { m_UpdateInformations.dirty = true; if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), index) == m_DirtyUnitShapes.end()) m_DirtyUnitShapes.push_back(index); // All shapes overlapping the updated part of the grid should be dirtied too. // We are going to invalidate the region of the grid corresponding to the modified shape plus its clearance, // and we need to get the shapes whose clearance can overlap this area. So we need to extend the search area // by two times the maximum clearance. CFixedVector2D center(shape.x, shape.z); std::vector staticsNear; m_StaticSubdivision.GetNear(staticsNear, center, shape.clearance + m_MaxClearance*2); for (u32& staticId : staticsNear) if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end()) m_DirtyStaticShapes.push_back(staticId); std::vector unitsNear; m_UnitSubdivision.GetNear(unitsNear, center, shape.clearance + m_MaxClearance*2); for (u32& unitId : unitsNear) if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end()) m_DirtyUnitShapes.push_back(unitId); MarkDirtinessGrid(shape.x, shape.z, shape.clearance + m_MaxClearance); } } /** * Return whether the given point is within the world bounds by at least r */ bool IsInWorld(entity_pos_t x, entity_pos_t z, entity_pos_t r) { return (m_WorldX0+r <= x && x <= m_WorldX1-r && m_WorldZ0+r <= z && z <= m_WorldZ1-r); } /** * Return whether the given point is within the world bounds */ bool IsInWorld(CFixedVector2D p) { return (m_WorldX0 <= p.X && p.X <= m_WorldX1 && m_WorldZ0 <= p.Y && p.Y <= m_WorldZ1); } void RasterizeHelper(Grid& grid, ICmpObstructionManager::flags_t requireMask, bool fullUpdate, pass_class_t appliedMask, entity_pos_t clearance = fixed::Zero()); }; REGISTER_COMPONENT_TYPE(ObstructionManager) 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) { PROFILE("TestLine"); // Check that both end points are within the world (which means the whole line must be) if (!IsInWorld(x0, z0, r) || !IsInWorld(x1, z1, r)) return true; 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; std::vector unitShapes; m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); for (size_t i = 0; i < unitShapes.size(); ++i) { std::map::iterator it = m_UnitShapes.find(unitShapes[i]); ENSURE(it != m_UnitShapes.end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; CFixedVector2D center(it->second.x, it->second.z); CFixedVector2D halfSize(it->second.clearance + unitUnitRadius, it->second.clearance + unitUnitRadius); if (Geometry::TestRayAASquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, halfSize)) return true; } std::vector staticShapes; m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); for (size_t i = 0; i < staticShapes.size(); ++i) { std::map::iterator it = m_StaticShapes.find(staticShapes[i]); 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; } bool CCmpObstructionManager::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) { PROFILE("TestStaticShape"); // TODO: should use the subdivision stuff here, if performance is non-negligible if (out) out->clear(); fixed s, c; sincos_approx(a, s, c); CFixedVector2D u(c, -s); CFixedVector2D v(s, c); CFixedVector2D center(x, z); CFixedVector2D halfSize(w/2, h/2); // Check that all corners are within the world (which means the whole shape must be) if (!IsInWorld(center + u.Multiply(halfSize.X) + v.Multiply(halfSize.Y)) || !IsInWorld(center + u.Multiply(halfSize.X) - v.Multiply(halfSize.Y)) || !IsInWorld(center - u.Multiply(halfSize.X) + v.Multiply(halfSize.Y)) || !IsInWorld(center - u.Multiply(halfSize.X) - v.Multiply(halfSize.Y))) { if (out) out->push_back(INVALID_ENTITY); // no entity ID, so just push an arbitrary marker else return true; } for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) { if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; CFixedVector2D center1(it->second.x, it->second.z); if (Geometry::PointIsInSquare(center1 - center, u, v, CFixedVector2D(halfSize.X + it->second.clearance, halfSize.Y + it->second.clearance))) { if (out) out->push_back(it->second.entity); else return true; } } for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) continue; CFixedVector2D center1(it->second.x, it->second.z); CFixedVector2D halfSize1(it->second.hw, it->second.hh); if (Geometry::TestSquareSquare(center, u, v, halfSize, center1, it->second.u, it->second.v, halfSize1)) { if (out) out->push_back(it->second.entity); else return true; } } if (out) return !out->empty(); // collided if the list isn't empty else return false; // didn't collide, if we got this far } bool CCmpObstructionManager::TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, std::vector* out) { PROFILE("TestUnitShape"); // TODO: should use the subdivision stuff here, if performance is non-negligible // Check that the shape is within the world if (!IsInWorld(x, z, clearance)) { if (out) out->push_back(INVALID_ENTITY); // no entity ID, so just push an arbitrary marker else return true; } CFixedVector2D center(x, z); for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) { if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; entity_pos_t c1 = it->second.clearance; if (!( it->second.x + c1 < x - clearance || it->second.x - c1 > x + clearance || it->second.z + c1 < z - clearance || it->second.z - c1 > z + clearance)) { if (out) out->push_back(it->second.entity); else return true; } } for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) continue; CFixedVector2D center1(it->second.x, it->second.z); if (Geometry::PointIsInSquare(center1 - center, it->second.u, it->second.v, CFixedVector2D(it->second.hw + clearance, it->second.hh + clearance))) { if (out) out->push_back(it->second.entity); else return true; } } if (out) return !out->empty(); // collided if the list isn't empty else return false; // didn't collide, if we got this far } void CCmpObstructionManager::Rasterize(Grid& grid, const std::vector& passClasses, bool fullUpdate) { PROFILE3("Rasterize"); // Cells are only marked as blocked if the whole cell is strictly inside the shape. // (That ensures the shape's geometric border is always reachable.) // Pass classes will get shapes rasterized on them depending on their Obstruction value. // Classes with another value than "pathfinding" should not use Clearance. std::map pathfindingMasks; u16 foundationMask = 0; for (const PathfinderPassability& passability : passClasses) { switch (passability.m_Obstructions) { case PathfinderPassability::PATHFINDING: { auto it = pathfindingMasks.find(passability.m_Clearance); if (it == pathfindingMasks.end()) pathfindingMasks[passability.m_Clearance] = passability.m_Mask; else it->second |= passability.m_Mask; break; } case PathfinderPassability::FOUNDATION: foundationMask |= passability.m_Mask; break; default: continue; } } // FLAG_BLOCK_PATHFINDING and FLAG_BLOCK_FOUNDATION are the only flags taken into account by MakeDirty* functions, // so they should be the only ones rasterized using with the help of m_Dirty*Shapes vectors. for (auto& maskPair : pathfindingMasks) RasterizeHelper(grid, FLAG_BLOCK_PATHFINDING, fullUpdate, maskPair.second, maskPair.first); RasterizeHelper(grid, FLAG_BLOCK_FOUNDATION, fullUpdate, foundationMask); m_DirtyStaticShapes.clear(); m_DirtyUnitShapes.clear(); } void CCmpObstructionManager::RasterizeHelper(Grid& grid, ICmpObstructionManager::flags_t requireMask, bool fullUpdate, pass_class_t appliedMask, entity_pos_t clearance) { for (auto& pair : m_StaticShapes) { const StaticShape& shape = pair.second; if (!(shape.flags & requireMask)) continue; if (!fullUpdate && std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), pair.first) == m_DirtyStaticShapes.end()) continue; // TODO: it might be nice to rasterize with rounded corners for large 'expand' values. ObstructionSquare square = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh }; SimRasterize::Spans spans; SimRasterize::RasterizeRectWithClearance(spans, square, clearance, Pathfinding::NAVCELL_SIZE); for (SimRasterize::Span& span : spans) { i16 j = Clamp(span.j, (i16)0, (i16)(grid.m_H-1)); i16 i0 = std::max(span.i0, (i16)0); i16 i1 = std::min(span.i1, (i16)grid.m_W); for (i16 i = i0; i < i1; ++i) grid.set(i, j, grid.get(i, j) | appliedMask); } } for (auto& pair : m_UnitShapes) { if (!(pair.second.flags & requireMask)) continue; if (!fullUpdate && std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), pair.first) == m_DirtyUnitShapes.end()) continue; CFixedVector2D center(pair.second.x, pair.second.z); entity_pos_t r = pair.second.clearance + clearance; u16 i0, j0, i1, j1; Pathfinding::NearestNavcell(center.X - r, center.Y - r, i0, j0, grid.m_W, grid.m_H); Pathfinding::NearestNavcell(center.X + r, center.Y + r, i1, j1, grid.m_W, grid.m_H); for (u16 j = j0+1; j < j1; ++j) for (u16 i = i0+1; i < i1; ++i) grid.set(i, j, grid.get(i, j) | appliedMask); } } void CCmpObstructionManager::GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) { GetUnitObstructionsInRange(filter, x0, z0, x1, z1, squares); GetStaticObstructionsInRange(filter, x0, z0, x1, z1, squares); } void CCmpObstructionManager::GetUnitObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) { PROFILE("GetObstructionsInRange"); ENSURE(x0 <= x1 && z0 <= z1); std::vector unitShapes; m_UnitSubdivision.GetInRange(unitShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); for (entity_id_t& unitShape : unitShapes) { auto it = m_UnitShapes.find(unitShape); ENSURE(it != m_UnitShapes.end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; entity_pos_t c = it->second.clearance; // Skip this object if it's completely outside the requested range if (it->second.x + c < x0 || it->second.x - c > x1 || it->second.z + c < z0 || it->second.z - c > z1) continue; CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero()); CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1)); squares.emplace_back(ObstructionSquare{ it->second.x, it->second.z, u, v, c, c }); } } void CCmpObstructionManager::GetStaticObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) { PROFILE("GetObstructionsInRange"); ENSURE(x0 <= x1 && z0 <= z1); std::vector staticShapes; m_StaticSubdivision.GetInRange(staticShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); for (entity_id_t& staticShape : staticShapes) { auto it = m_StaticShapes.find(staticShape); ENSURE(it != m_StaticShapes.end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) continue; entity_pos_t r = it->second.hw + it->second.hh; // overestimate the max dist of an edge from the center // Skip this object if its overestimated bounding box is completely outside the requested range if (it->second.x + r < x0 || it->second.x - r > x1 || it->second.z + r < z0 || it->second.z - r > z1) continue; // TODO: maybe we should use Geometry::GetHalfBoundingBox to be more precise? squares.emplace_back(ObstructionSquare{ it->second.x, it->second.z, it->second.u, it->second.v, it->second.hw, it->second.hh }); } } -void CCmpObstructionManager::GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) +void CCmpObstructionManager::GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict) { PROFILE3("GetUnitsOnObstruction"); // In order to avoid getting units on impassable cells, we want to find all // units s.t. the RasterizeRectWithClearance of the building's shape with the // unit's clearance covers the navcell the unit is on. std::vector unitShapes; CFixedVector2D center(square.x, square.z); CFixedVector2D expandedBox = Geometry::GetHalfBoundingBox(square.u, square.v, CFixedVector2D(square.hw, square.hh)) + CFixedVector2D(m_MaxClearance, m_MaxClearance); m_UnitSubdivision.GetInRange(unitShapes, center - expandedBox, center + expandedBox); std::map rasterizedRects; for (const u32& unitShape : unitShapes) { auto it = m_UnitShapes.find(unitShape); ENSURE(it != m_UnitShapes.end()); UnitShape& shape = it->second; if (!filter.TestShape(UNIT_INDEX_TO_TAG(unitShape), shape.flags, shape.group, INVALID_ENTITY)) continue; if (rasterizedRects.find(shape.clearance) == rasterizedRects.end()) { - // Wraitii 31/10/15: check out helpers/Rasterize.cpp for more info, but - // a change in the long-range pathfinder rasterization to fix stuck units - // requires the foundation code to be more restrictive, thus adding the substraction - // of Pathfinding::NAVCELL_SIZE. Remove it if the problem in Rasterize.cpp is ever fixed. + // The rasterization is an approximation of the real shapes. + // Depending on your use, you may want to be more or less strict on the rasterization, + // ie this may either return some units that aren't actually on the shape (if strict is set) + // or this may not return some units that are on the shape (if strict is not set). + // 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]; - SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance-Pathfinding::NAVCELL_SIZE, Pathfinding::NAVCELL_SIZE); + if (strict) + SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance, Pathfinding::NAVCELL_SIZE); + else + SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance-Pathfinding::NAVCELL_SIZE, Pathfinding::NAVCELL_SIZE); } SimRasterize::Spans& spans = rasterizedRects[shape.clearance]; // Check whether the unit's center is on a navcell that's in // any of the spans u16 i = (shape.x / Pathfinding::NAVCELL_SIZE).ToInt_RoundToNegInfinity(); u16 j = (shape.z / Pathfinding::NAVCELL_SIZE).ToInt_RoundToNegInfinity(); for (const SimRasterize::Span& span : spans) { if (j == span.j && span.i0 <= i && i < span.i1) { out.push_back(shape.entity); break; } } } } void CCmpObstructionManager::RenderSubmit(SceneCollector& collector) { if (!m_DebugOverlayEnabled) return; CColor defaultColor(0, 0, 1, 1); CColor movingColor(1, 0, 1, 1); CColor boundsColor(1, 1, 0, 1); // If the shapes have changed, then regenerate all the overlays if (m_DebugOverlayDirty) { m_DebugOverlayLines.clear(); m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = boundsColor; SimRender::ConstructSquareOnGround(GetSimContext(), (m_WorldX0+m_WorldX1).ToFloat()/2.f, (m_WorldZ0+m_WorldZ1).ToFloat()/2.f, (m_WorldX1-m_WorldX0).ToFloat(), (m_WorldZ1-m_WorldZ0).ToFloat(), 0, m_DebugOverlayLines.back(), true); for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = ((it->second.flags & FLAG_MOVING) ? movingColor : defaultColor); SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.clearance.ToFloat()*2, it->second.clearance.ToFloat()*2, 0, m_DebugOverlayLines.back(), true); } for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = defaultColor; float a = atan2f(it->second.v.X.ToFloat(), it->second.v.Y.ToFloat()); SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.hw.ToFloat()*2, it->second.hh.ToFloat()*2, a, m_DebugOverlayLines.back(), true); } m_DebugOverlayDirty = false; } for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i) collector.Submit(&m_DebugOverlayLines[i]); } Index: ps/trunk/source/simulation2/components/CCmpUnitMotion.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpUnitMotion.cpp (revision 17224) +++ ps/trunk/source/simulation2/components/CCmpUnitMotion.cpp (revision 17225) @@ -1,1830 +1,1830 @@ /* Copyright (C) 2015 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #include "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpUnitMotion.h" #include "simulation2/components/ICmpObstruction.h" #include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/components/ICmpOwnership.h" #include "simulation2/components/ICmpPosition.h" #include "simulation2/components/ICmpPathfinder.h" #include "simulation2/components/ICmpRangeManager.h" #include "simulation2/components/ICmpValueModificationManager.h" #include "simulation2/helpers/Geometry.h" #include "simulation2/helpers/Render.h" #include "simulation2/MessageTypes.h" #include "simulation2/serialization/SerializeTemplates.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "maths/FixedVector2D.h" #include "ps/CLogger.h" #include "ps/Profile.h" #include "renderer/Scene.h" // For debugging; units will start going straight to the target // instead of calling the pathfinder #define DISABLE_PATHFINDER 0 /** * When advancing along the long path, and picking a new waypoint to move * towards, we'll pick one that's up to this far from the unit's current * position (to minimise the effects of grid-constrained movement) */ static const entity_pos_t WAYPOINT_ADVANCE_MAX = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*8); /** * Maximum range to restrict short path queries to. (Larger ranges are slower, * smaller ranges might miss some legitimate routes around large obstacles.) */ static const entity_pos_t SHORT_PATH_SEARCH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*6); /** * When short-pathing, and the short-range pathfinder failed to return a path, * Assume we are at destination if we are closer than this distance to the target * And we have no target entity. * This is somewhat arbitrary, but setting a too big distance means units might lose sight of their end goal too much; */ static const entity_pos_t SHORT_PATH_GOAL_RADIUS = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*2); /** * If we are this close to our target entity/point, then think about heading * for it in a straight line instead of pathfinding. */ static const entity_pos_t DIRECT_PATH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*4); /** * If we're following a target entity, * we will recompute our path if the target has moved * more than this distance from where we last pathed to. */ static const entity_pos_t CHECK_TARGET_MOVEMENT_MIN_DELTA = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*4); /** * If we're following as part of a formation, * but can't move to our assigned target point in a straight line, * we will recompute our path if the target has moved * more than this distance from where we last pathed to. */ static const entity_pos_t CHECK_TARGET_MOVEMENT_MIN_DELTA_FORMATION = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*1); /** * If we're following something but it's more than this distance away along * our path, then don't bother trying to repath regardless of how much it has * moved, until we get this close to the end of our old path. */ static const entity_pos_t CHECK_TARGET_MOVEMENT_AT_MAX_DIST = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*16); /** * If we're following something and the angle between the (straight-line) directions to its previous target * position and its present target position is greater than a given angle, recompute the path even far away * (i.e. even if CHECK_TARGET_MOVEMENT_AT_MAX_DIST condition is not fulfilled). The actual check is done * on the cosine of this angle, with a PI/6 angle. */ static const fixed CHECK_TARGET_MOVEMENT_MIN_COS = fixed::FromInt(866)/1000; static const CColor OVERLAY_COLOR_LONG_PATH(1, 1, 1, 1); static const CColor OVERLAY_COLOR_SHORT_PATH(1, 0, 0, 1); struct SUnitMotionPlanning { WaypointPath nextStepShortPath; // if !nextStepClean, store a short path for the next step here u32 expectedPathTicket; bool nextStepClean; // is there any obstruction between the next two long waypoints? SUnitMotionPlanning() : expectedPathTicket(0), nextStepClean(true) {} }; /** * Serialization helper template for SUnitMotionPlanning */ struct SerializeUnitMotionPlanning { template void operator()(S& serialize, const char* UNUSED(name), SUnitMotionPlanning& value) { SerializeVector()(serialize, "next step short path", value.nextStepShortPath.m_Waypoints); serialize.NumberU32_Unbounded("expected path ticket", value.expectedPathTicket); serialize.Bool("next step clean", value.nextStepClean); } }; class CCmpUnitMotion : public ICmpUnitMotion { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_Update_MotionFormation); componentManager.SubscribeToMessageType(MT_Update_MotionUnit); componentManager.SubscribeToMessageType(MT_PathResult); componentManager.SubscribeToMessageType(MT_OwnershipChanged); componentManager.SubscribeToMessageType(MT_ValueModification); componentManager.SubscribeToMessageType(MT_Deserialized); } DEFAULT_COMPONENT_ALLOCATOR(UnitMotion) bool m_DebugOverlayEnabled; std::vector m_DebugOverlayLongPathLines; std::vector m_DebugOverlayShortPathLines; // Template state: bool m_FormationController; fixed m_WalkSpeed, m_OriginalWalkSpeed; // in metres per second fixed m_RunSpeed, m_OriginalRunSpeed; pass_class_t m_PassClass; std::string m_PassClassName; // Dynamic state: entity_pos_t m_Clearance; bool m_Moving; bool m_FacePointAfterMove; enum State { /* * Not moving at all. */ STATE_IDLE, /* * Not moving at all. Will go to IDLE next turn. * (This one-turn delay is a hack to fix animation timings.) */ STATE_STOPPING, /* * Member of a formation. * Pathing to the target (depending on m_PathState). * Target is m_TargetEntity plus m_TargetOffset. */ STATE_FORMATIONMEMBER_PATH, /* * Individual unit or formation controller. * Pathing to the target (depending on m_PathState). * Target is m_TargetPos, m_TargetMinRange, m_TargetMaxRange; * if m_TargetEntity is not INVALID_ENTITY then m_TargetPos is tracking it. */ STATE_INDIVIDUAL_PATH, STATE_MAX }; u8 m_State; enum PathState { /* * There is no path. * (This should only happen in IDLE and STOPPING.) */ PATHSTATE_NONE, /* * We have an outstanding long path request. * No paths are usable yet, so we can't move anywhere. */ PATHSTATE_WAITING_REQUESTING_LONG, /* * We have an outstanding short path request. * m_LongPath is valid. * m_ShortPath is not yet valid, so we can't move anywhere. */ PATHSTATE_WAITING_REQUESTING_SHORT, /* * We are following our path, and have no path requests. * m_LongPath and m_ShortPath are valid. */ PATHSTATE_FOLLOWING, /* * We are following our path, and have an outstanding long path request. * (This is because our target moved a long way and we need to recompute * the whole path). * m_LongPath and m_ShortPath are valid. */ PATHSTATE_FOLLOWING_REQUESTING_LONG, /* * We are following our path, and have an outstanding short path request. * (This is because our target moved and we've got a new long path * which we need to follow). * m_LongPath is valid; m_ShortPath is valid but obsolete. */ PATHSTATE_FOLLOWING_REQUESTING_SHORT, PATHSTATE_MAX }; u8 m_PathState; u32 m_ExpectedPathTicket; // asynchronous request ID we're waiting for, or 0 if none entity_id_t m_TargetEntity; CFixedVector2D m_TargetPos; CFixedVector2D m_TargetOffset; entity_pos_t m_TargetMinRange; entity_pos_t m_TargetMaxRange; fixed m_Speed; // Current mean speed (over the last turn). fixed m_CurSpeed; // Currently active paths (storing waypoints in reverse order). // The last item in each path is the point we're currently heading towards. WaypointPath m_LongPath; WaypointPath m_ShortPath; // Motion planning SUnitMotionPlanning m_Planning; PathGoal m_FinalGoal; static std::string GetSchema() { return "Provides the unit with the ability to move around the world by itself." "" "7.0" "default" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" ""; } /* * TODO: the running/charging thing needs to be designed and implemented */ virtual void Init(const CParamNode& paramNode) { m_FormationController = paramNode.GetChild("FormationController").ToBool(); m_Moving = false; m_FacePointAfterMove = true; m_WalkSpeed = m_OriginalWalkSpeed = paramNode.GetChild("WalkSpeed").ToFixed(); m_Speed = m_WalkSpeed; m_CurSpeed = fixed::Zero(); if (paramNode.GetChild("Run").IsOk()) m_RunSpeed = m_OriginalRunSpeed = paramNode.GetChild("Run").GetChild("Speed").ToFixed(); else m_RunSpeed = m_OriginalRunSpeed = m_WalkSpeed; CmpPtr cmpPathfinder(GetSystemEntity()); if (cmpPathfinder) { m_PassClassName = paramNode.GetChild("PassabilityClass").ToUTF8(); m_PassClass = cmpPathfinder->GetPassabilityClass(m_PassClassName); m_Clearance = cmpPathfinder->GetClearance(m_PassClass); CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetUnitClearance(m_Clearance); } m_State = STATE_IDLE; m_PathState = PATHSTATE_NONE; m_ExpectedPathTicket = 0; m_TargetEntity = INVALID_ENTITY; m_FinalGoal.type = PathGoal::POINT; m_DebugOverlayEnabled = false; } virtual void Deinit() { } template void SerializeCommon(S& serialize) { serialize.NumberU8("state", m_State, 0, STATE_MAX-1); serialize.NumberU8("path state", m_PathState, 0, PATHSTATE_MAX-1); serialize.StringASCII("pass class", m_PassClassName, 0, 64); serialize.NumberU32_Unbounded("ticket", m_ExpectedPathTicket); serialize.NumberU32_Unbounded("target entity", m_TargetEntity); serialize.NumberFixed_Unbounded("target pos x", m_TargetPos.X); serialize.NumberFixed_Unbounded("target pos y", m_TargetPos.Y); serialize.NumberFixed_Unbounded("target offset x", m_TargetOffset.X); serialize.NumberFixed_Unbounded("target offset y", m_TargetOffset.Y); serialize.NumberFixed_Unbounded("target min range", m_TargetMinRange); serialize.NumberFixed_Unbounded("target max range", m_TargetMaxRange); serialize.NumberFixed_Unbounded("speed", m_Speed); serialize.Bool("moving", m_Moving); serialize.Bool("facePointAfterMove", m_FacePointAfterMove); SerializeVector()(serialize, "long path", m_LongPath.m_Waypoints); SerializeVector()(serialize, "short path", m_ShortPath.m_Waypoints); SerializeUnitMotionPlanning()(serialize, "planning", m_Planning); SerializeGoal()(serialize, "goal", m_FinalGoal); } virtual void Serialize(ISerializer& serialize) { SerializeCommon(serialize); } virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) { Init(paramNode); SerializeCommon(deserialize); CmpPtr cmpPathfinder(GetSystemEntity()); if (cmpPathfinder) m_PassClass = cmpPathfinder->GetPassabilityClass(m_PassClassName); } virtual void HandleMessage(const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_Update_MotionFormation: { if (m_FormationController) { fixed dt = static_cast (msg).turnLength; Move(dt); } break; } case MT_Update_MotionUnit: { if (!m_FormationController) { fixed dt = static_cast (msg).turnLength; Move(dt); } break; } case MT_RenderSubmit: { PROFILE3("UnitMotion::RenderSubmit"); const CMessageRenderSubmit& msgData = static_cast (msg); RenderSubmit(msgData.collector); break; } case MT_PathResult: { const CMessagePathResult& msgData = static_cast (msg); PathResult(msgData.ticket, msgData.path); break; } case MT_ValueModification: { const CMessageValueModification& msgData = static_cast (msg); if (msgData.component != L"UnitMotion") break; } // fall-through case MT_OwnershipChanged: case MT_Deserialized: { CmpPtr cmpValueModificationManager(GetSystemEntity()); if (!cmpValueModificationManager) break; fixed newWalkSpeed = cmpValueModificationManager->ApplyModifications(L"UnitMotion/WalkSpeed", m_OriginalWalkSpeed, GetEntityId()); fixed newRunSpeed = cmpValueModificationManager->ApplyModifications(L"UnitMotion/Run/Speed", m_OriginalRunSpeed, GetEntityId()); // update m_Speed (the actual speed) if set to one of the variables if (m_Speed == m_WalkSpeed) m_Speed = newWalkSpeed; else if (m_Speed == m_RunSpeed) m_Speed = newRunSpeed; m_WalkSpeed = newWalkSpeed; m_RunSpeed = newRunSpeed; break; } } } void UpdateMessageSubscriptions() { bool needRender = m_DebugOverlayEnabled; GetSimContext().GetComponentManager().DynamicSubscriptionNonsync(MT_RenderSubmit, this, needRender); } virtual bool IsMoving() { return m_Moving; } virtual fixed GetWalkSpeed() { return m_WalkSpeed; } virtual fixed GetRunSpeed() { return m_RunSpeed; } virtual pass_class_t GetPassabilityClass() { return m_PassClass; } virtual std::string GetPassabilityClassName() { return m_PassClassName; } virtual void SetPassabilityClassName(std::string passClassName) { m_PassClassName = passClassName; CmpPtr cmpPathfinder(GetSystemEntity()); if (cmpPathfinder) m_PassClass = cmpPathfinder->GetPassabilityClass(passClassName); } virtual fixed GetCurrentSpeed() { return m_CurSpeed; } virtual void SetSpeed(fixed speed) { m_Speed = speed; } virtual void SetFacePointAfterMove(bool facePointAfterMove) { m_FacePointAfterMove = facePointAfterMove; } virtual void SetDebugOverlay(bool enabled) { m_DebugOverlayEnabled = enabled; UpdateMessageSubscriptions(); } virtual bool MoveToPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t minRange, entity_pos_t maxRange); virtual bool IsInPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t minRange, entity_pos_t maxRange); virtual bool MoveToTargetRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange); virtual bool IsInTargetRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange); virtual void MoveToFormationOffset(entity_id_t target, entity_pos_t x, entity_pos_t z); virtual void FaceTowardsPoint(entity_pos_t x, entity_pos_t z); virtual void StopMoving() { m_Moving = false; m_ExpectedPathTicket = 0; m_State = STATE_STOPPING; m_PathState = PATHSTATE_NONE; m_LongPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.clear(); } virtual entity_pos_t GetUnitClearance() { return m_Clearance; } private: bool ShouldAvoidMovingUnits() const { return !m_FormationController; } bool IsFormationMember() const { return m_State == STATE_FORMATIONMEMBER_PATH; } entity_id_t GetGroup() const { return IsFormationMember() ? m_TargetEntity : GetEntityId(); } bool HasValidPath() const { return m_PathState == PATHSTATE_FOLLOWING || m_PathState == PATHSTATE_FOLLOWING_REQUESTING_LONG || m_PathState == PATHSTATE_FOLLOWING_REQUESTING_SHORT; } void StartFailed() { StopMoving(); m_State = STATE_IDLE; // don't go through the STOPPING state since we never even started CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetMovingFlag(false); CMessageMotionChanged msg(true, true); GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); } void MoveFailed() { StopMoving(); CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetMovingFlag(false); CMessageMotionChanged msg(false, true); GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); } void StartSucceeded() { CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetMovingFlag(true); m_Moving = true; CMessageMotionChanged msg(true, false); GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); } void MoveSucceeded() { m_Moving = false; CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetMovingFlag(false); // No longer moving, so speed is 0. m_CurSpeed = fixed::Zero(); CMessageMotionChanged msg(false, false); GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); } bool MoveToPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t minRange, entity_pos_t maxRange, entity_id_t target); /** * Handle the result of an asynchronous path query. */ void PathResult(u32 ticket, const WaypointPath& path); /** * Do the per-turn movement and other updates. */ void Move(fixed dt); /** * Analyse the next long path step (if any) and precompute a short path if needed. * Then use the previous computed short path, if present, for the current step. */ void PlanNextStep(const CFixedVector2D& pos); /** * Decide whether to approximate the given range from a square target as a circle, * rather than as a square. */ bool ShouldTreatTargetAsCircle(entity_pos_t range, entity_pos_t circleRadius) const; /** * Computes the current location of our target entity (plus offset). * Returns false if no target entity or no valid position. */ bool ComputeTargetPosition(CFixedVector2D& out); /** * Attempts to replace the current path with a straight line to the goal, * if this goal is a point, is close enough and the route is not obstructed. */ bool TryGoingStraightToGoalPoint(const CFixedVector2D& from); /** * Attempts to replace the current path with a straight line to the target * entity, if it's close enough and the route is not obstructed. */ bool TryGoingStraightToTargetEntity(const CFixedVector2D& from); /** * Returns whether the target entity has moved more than minDelta since our * last path computations, and we're close enough to it to care. */ bool CheckTargetMovement(const CFixedVector2D& from, entity_pos_t minDelta); /** * Returns whether the length of the given path, plus the distance from * 'from' to the first waypoints, it shorter than minDistance. */ bool PathIsShort(const WaypointPath& path, const CFixedVector2D& from, entity_pos_t minDistance) const; /** * Rotate to face towards the target point, given the current pos */ void FaceTowardsPointFromPos(const CFixedVector2D& pos, entity_pos_t x, entity_pos_t z); /** * Returns an appropriate obstruction filter for use with path requests. * noTarget is true only when used inside tryGoingStraightToTargetEntity, * in which case we do not want the target obstruction otherwise it would always fail */ ControlGroupMovementObstructionFilter GetObstructionFilter(bool forceAvoidMovingUnits = false, bool noTarget = false) const; /** * Start moving to the given goal, from our current position 'from'. * Might go in a straight line immediately, or might start an asynchronous * path request. */ void BeginPathing(const CFixedVector2D& from, const PathGoal& goal); /** * Start an asynchronous long path query. */ void RequestLongPath(const CFixedVector2D& from, const PathGoal& goal); /** * Start an asynchronous short path query. */ void RequestShortPath(const CFixedVector2D& from, const PathGoal& goal, bool avoidMovingUnits); /** * Convert a path into a renderable list of lines */ void RenderPath(const WaypointPath& path, std::vector& lines, CColor color); void RenderSubmit(SceneCollector& collector); }; REGISTER_COMPONENT_TYPE(UnitMotion) void CCmpUnitMotion::PathResult(u32 ticket, const WaypointPath& path) { // reset our state for sanity. CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetMovingFlag(false); m_Moving = false; if (ticket == m_Planning.expectedPathTicket) { // If no path was found, better cancel the planning if (path.m_Waypoints.empty()) m_Planning = SUnitMotionPlanning(); m_Planning.nextStepShortPath = path; return; } // Ignore obsolete path requests if (ticket != m_ExpectedPathTicket) return; m_ExpectedPathTicket = 0; // we don't expect to get this result again // Check that we are still able to do something with that path CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) { if (m_PathState == PATHSTATE_WAITING_REQUESTING_LONG || m_PathState == PATHSTATE_WAITING_REQUESTING_SHORT) StartFailed(); else if (m_PathState == PATHSTATE_FOLLOWING_REQUESTING_LONG || m_PathState == PATHSTATE_FOLLOWING_REQUESTING_SHORT) StopMoving(); return; } if (m_PathState == PATHSTATE_WAITING_REQUESTING_LONG || m_PathState == PATHSTATE_FOLLOWING_REQUESTING_LONG) { m_LongPath = path; // If we are following a path, leave the old m_ShortPath so we can carry on following it // until a new short path has been computed if (m_PathState == PATHSTATE_WAITING_REQUESTING_LONG) m_ShortPath.m_Waypoints.clear(); // If there's no waypoints then we couldn't get near the target. // Sort of hack: Just try going directly to the goal point instead // (via the short pathfinder), so if we're stuck and the user clicks // close enough to the unit then we can probably get unstuck if (m_LongPath.m_Waypoints.empty()) m_LongPath.m_Waypoints.emplace_back(Waypoint{ m_FinalGoal.x, m_FinalGoal.z }); if (!HasValidPath()) StartSucceeded(); m_PathState = PATHSTATE_FOLLOWING; if (cmpObstruction) cmpObstruction->SetMovingFlag(true); m_Moving = true; } else if (m_PathState == PATHSTATE_WAITING_REQUESTING_SHORT || m_PathState == PATHSTATE_FOLLOWING_REQUESTING_SHORT) { m_ShortPath = path; // If there's no waypoints then we couldn't get near the target if (m_ShortPath.m_Waypoints.empty()) { // If we're globally following a long path, try to remove the next waypoint, it might be obstructed // If not, and we are not in a formation, retry // unless we are close to our target and we don't have a target entity. // This makes sure that units don't clump too much when they are not in a formation and tasked to move. if (m_LongPath.m_Waypoints.size() > 1) m_LongPath.m_Waypoints.pop_back(); else if (IsFormationMember()) { m_Moving = false; CMessageMotionChanged msg(true, true); GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); return; } CMessageMotionChanged msg(false, false); GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return; CFixedVector2D pos = cmpPosition->GetPosition2D(); if (m_TargetEntity == INVALID_ENTITY) { if (m_FinalGoal.DistanceToPoint(pos) <= SHORT_PATH_GOAL_RADIUS) { StopMoving(); MoveSucceeded(); if (m_FacePointAfterMove) FaceTowardsPointFromPos(pos, m_FinalGoal.x, m_FinalGoal.z); return; } } - m_LongPath.m_Waypoints.clear(); RequestLongPath(pos, m_FinalGoal); m_PathState = PATHSTATE_WAITING_REQUESTING_LONG; return; } // Now we've got a short path that we can follow if (!HasValidPath()) StartSucceeded(); m_PathState = PATHSTATE_FOLLOWING; if (cmpObstruction) cmpObstruction->SetMovingFlag(true); m_Moving = true; } else { LOGWARNING("unexpected PathResult (%u %d %d)", GetEntityId(), m_State, m_PathState); } } void CCmpUnitMotion::Move(fixed dt) { PROFILE("Move"); if (m_State == STATE_STOPPING) { m_State = STATE_IDLE; MoveSucceeded(); return; } if (m_State == STATE_IDLE) return; switch (m_PathState) { case PATHSTATE_NONE: { // If we're not pathing, do nothing return; } case PATHSTATE_WAITING_REQUESTING_LONG: case PATHSTATE_WAITING_REQUESTING_SHORT: { // If we're waiting for a path and don't have one yet, do nothing return; } case PATHSTATE_FOLLOWING: case PATHSTATE_FOLLOWING_REQUESTING_SHORT: case PATHSTATE_FOLLOWING_REQUESTING_LONG: { // TODO: there's some asymmetry here when units look at other // units' positions - the result will depend on the order of execution. // Maybe we should split the updates into multiple phases to minimise // that problem. CmpPtr cmpPathfinder(GetSystemEntity()); if (!cmpPathfinder) return; CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return; CFixedVector2D initialPos = cmpPosition->GetPosition2D(); // If we're chasing a potentially-moving unit and are currently close // enough to its current position, and we can head in a straight line // to it, then throw away our current path and go straight to it if (m_PathState == PATHSTATE_FOLLOWING) TryGoingStraightToTargetEntity(initialPos); // Keep track of the current unit's position during the update CFixedVector2D pos = initialPos; // If in formation, run to keep up; otherwise just walk // (TODO: support stamina, charging, etc) fixed basicSpeed; if (IsFormationMember()) basicSpeed = GetRunSpeed(); else basicSpeed = m_Speed; // (typically but not always WalkSpeed) // Find the speed factor of the underlying terrain // (We only care about the tile we start on - it doesn't matter if we're moving // partially onto a much slower/faster tile) // TODO: Terrain-dependent speeds are not currently supported fixed terrainSpeed = fixed::FromInt(1); fixed maxSpeed = basicSpeed.Multiply(terrainSpeed); bool wasObstructed = false; // We want to move (at most) maxSpeed*dt units from pos towards the next waypoint fixed timeLeft = dt; fixed zero = fixed::Zero(); while (timeLeft > zero) { // If we ran out of path, we have to stop if (m_ShortPath.m_Waypoints.empty() && m_LongPath.m_Waypoints.empty()) break; CFixedVector2D target; if (m_ShortPath.m_Waypoints.empty()) target = CFixedVector2D(m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z); else target = CFixedVector2D(m_ShortPath.m_Waypoints.back().x, m_ShortPath.m_Waypoints.back().z); CFixedVector2D offset = target - pos; // Work out how far we can travel in timeLeft fixed maxdist = maxSpeed.Multiply(timeLeft); // If the target is close, we can move there directly fixed offsetLength = offset.Length(); if (offsetLength <= maxdist) { if (cmpPathfinder->CheckMovement(GetObstructionFilter(), pos.X, pos.Y, target.X, target.Y, m_Clearance, m_PassClass)) { pos = target; // Spend the rest of the time heading towards the next waypoint timeLeft = timeLeft - (offsetLength / maxSpeed); if (m_ShortPath.m_Waypoints.empty()) { m_LongPath.m_Waypoints.pop_back(); PlanNextStep(pos); } else m_ShortPath.m_Waypoints.pop_back(); continue; } else { // Error - path was obstructed wasObstructed = true; break; } } else { // Not close enough, so just move in the right direction offset.Normalize(maxdist); target = pos + offset; if (cmpPathfinder->CheckMovement(GetObstructionFilter(), pos.X, pos.Y, target.X, target.Y, m_Clearance, m_PassClass)) { pos = target; break; } else { // Error - path was obstructed wasObstructed = true; break; } } } // Update the Position component after our movement (if we actually moved anywhere) if (pos != initialPos) { CFixedVector2D offset = pos - initialPos; // Face towards the target entity_angle_t angle = atan2_approx(offset.X, offset.Y); cmpPosition->MoveAndTurnTo(pos.X,pos.Y, angle); // Calculate the mean speed over this past turn. m_CurSpeed = cmpPosition->GetDistanceTravelled() / dt; } if (wasObstructed) { // Oops, we hit something (very likely another unit). // This is when we might easily get stuck wrongly. // If we still have long waypoints, try and compute a short path // This will get us around units, amongst others. // However in some cases a long waypoint will be in located in the obstruction of // an idle unit. In that case, we need to scrap that waypoint or we might never be able to reach it. // I am not sure why this happens but the following code seems to work. if (!m_LongPath.m_Waypoints.empty()) { CmpPtr cmpObstructionManager(GetSystemEntity()); if (cmpObstructionManager) { // create a fake obstruction to represent our waypoint. ICmpObstructionManager::ObstructionSquare square; square.hh = m_Clearance; square.hw = m_Clearance; square.u = CFixedVector2D(entity_pos_t::FromInt(1),entity_pos_t::FromInt(0)); square.v = CFixedVector2D(entity_pos_t::FromInt(0),entity_pos_t::FromInt(1)); square.x = m_LongPath.m_Waypoints.back().x; square.z = m_LongPath.m_Waypoints.back().z; std::vector unitOnGoal; - cmpObstructionManager->GetUnitsOnObstruction(square, unitOnGoal, GetObstructionFilter(true, false)); + // don't ignore moving units as those might be units like us, ie not really moving. + cmpObstructionManager->GetUnitsOnObstruction(square, unitOnGoal, GetObstructionFilter(false, false), true); if (!unitOnGoal.empty()) m_LongPath.m_Waypoints.pop_back(); } if (!m_LongPath.m_Waypoints.empty()) { PathGoal goal = { PathGoal::POINT, m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z }; RequestShortPath(pos, goal, true); m_PathState = PATHSTATE_WAITING_REQUESTING_SHORT; return; } } // Else, just entirely recompute BeginPathing(pos, m_FinalGoal); // potential TODO: We could switch the short-range pathfinder for something else entirely. return; } // We successfully moved along our path, until running out of // waypoints or time. if (m_PathState == PATHSTATE_FOLLOWING) { // If we're not currently computing any new paths: if (m_LongPath.m_Waypoints.empty() && m_ShortPath.m_Waypoints.empty()) { if (IsFormationMember()) { // We've reached our assigned position. If the controller // is idle, send a notification in case it should disband, // otherwise continue following the formation next turn. CmpPtr cmpUnitMotion(GetSimContext(), m_TargetEntity); if (cmpUnitMotion && !cmpUnitMotion->IsMoving()) { CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetMovingFlag(false); m_Moving = false; CMessageMotionChanged msg(false, false); GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); } } else { // check if target was reached in case of a moving target CmpPtr cmpUnitMotion(GetSimContext(), m_TargetEntity); if (cmpUnitMotion && cmpUnitMotion->IsMoving() && MoveToTargetRange(m_TargetEntity, m_TargetMinRange, m_TargetMaxRange)) return; // Not in formation, so just finish moving StopMoving(); m_State = STATE_IDLE; MoveSucceeded(); if (m_FacePointAfterMove) FaceTowardsPointFromPos(pos, m_FinalGoal.x, m_FinalGoal.z); // TODO: if the goal was a square building, we ought to point towards the // nearest point on the square, not towards its center } } // If we have a target entity, and we're not miles away from the end of // our current path, and the target moved enough, then recompute our // whole path if (IsFormationMember()) CheckTargetMovement(pos, CHECK_TARGET_MOVEMENT_MIN_DELTA_FORMATION); else CheckTargetMovement(pos, CHECK_TARGET_MOVEMENT_MIN_DELTA); } } } } void CCmpUnitMotion::PlanNextStep(const CFixedVector2D& pos) { if (m_LongPath.m_Waypoints.empty()) return; CmpPtr cmpPathfinder(GetSystemEntity()); if (!cmpPathfinder) return; const Waypoint& nextPoint = m_LongPath.m_Waypoints.back(); // The next step was obstructed the last time we checked; also check that // the step is still obstructed (maybe the units in our way moved in the meantime) if (!m_Planning.nextStepClean && !cmpPathfinder->CheckMovement(GetObstructionFilter(), pos.X, pos.Y, nextPoint.x, nextPoint.z, m_Clearance, m_PassClass)) { // If the short path computation is over, use it, else just forget about it if (!m_Planning.nextStepShortPath.m_Waypoints.empty()) { m_PathState = PATHSTATE_FOLLOWING; m_ShortPath = m_Planning.nextStepShortPath; } } m_Planning = SUnitMotionPlanning(); if (m_LongPath.m_Waypoints.size() == 1) return; const Waypoint& followingPoint = m_LongPath.m_Waypoints.rbegin()[1]; // penultimate element m_Planning.nextStepClean = cmpPathfinder->CheckMovement( GetObstructionFilter(), nextPoint.x, nextPoint.z, followingPoint.x, followingPoint.z, m_Clearance, m_PassClass); if (!m_Planning.nextStepClean) { PathGoal goal = { PathGoal::POINT, followingPoint.x, followingPoint.z }; m_Planning.expectedPathTicket = cmpPathfinder->ComputeShortPathAsync( nextPoint.x, nextPoint.z, m_Clearance, SHORT_PATH_SEARCH_RANGE, goal, m_PassClass, false, GetGroup(), GetEntityId()); } } bool CCmpUnitMotion::ComputeTargetPosition(CFixedVector2D& out) { if (m_TargetEntity == INVALID_ENTITY) return false; CmpPtr cmpPosition(GetSimContext(), m_TargetEntity); if (!cmpPosition || !cmpPosition->IsInWorld()) return false; if (m_TargetOffset.IsZero()) { // No offset, just return the position directly out = cmpPosition->GetPosition2D(); } else { // There is an offset, so compute it relative to orientation entity_angle_t angle = cmpPosition->GetRotation().Y; CFixedVector2D offset = m_TargetOffset.Rotate(angle); out = cmpPosition->GetPosition2D() + offset; } return true; } bool CCmpUnitMotion::TryGoingStraightToGoalPoint(const CFixedVector2D& from) { // Make sure the goal is a point (and not a point-like target like a formation controller) if (m_FinalGoal.type != PathGoal::POINT || m_TargetEntity != INVALID_ENTITY) return false; // Fail if the goal is too far away CFixedVector2D goalPos(m_FinalGoal.x, m_FinalGoal.z); if ((goalPos - from).CompareLength(DIRECT_PATH_RANGE) > 0) return false; CmpPtr cmpPathfinder(GetSystemEntity()); if (!cmpPathfinder) return false; // Check if there's any collisions on that route if (!cmpPathfinder->CheckMovement(GetObstructionFilter(), from.X, from.Y, goalPos.X, goalPos.Y, m_Clearance, m_PassClass)) return false; // That route is okay, so update our path m_LongPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.emplace_back(Waypoint{ goalPos.X, goalPos.Y }); return true; } bool CCmpUnitMotion::TryGoingStraightToTargetEntity(const CFixedVector2D& from) { CFixedVector2D targetPos; if (!ComputeTargetPosition(targetPos)) return false; // Fail if the target is too far away if ((targetPos - from).CompareLength(DIRECT_PATH_RANGE) > 0) return false; CmpPtr cmpPathfinder(GetSystemEntity()); if (!cmpPathfinder) return false; // Move the goal to match the target entity's new position PathGoal goal = m_FinalGoal; goal.x = targetPos.X; goal.z = targetPos.Y; // (we ignore changes to the target's rotation, since only buildings are // square and buildings don't move) // Find the point on the goal shape that we should head towards CFixedVector2D goalPos = goal.NearestPointOnGoal(from); // Check if there's any collisions on that route if (!cmpPathfinder->CheckMovement(GetObstructionFilter(false, true), from.X, from.Y, goalPos.X, goalPos.Y, m_Clearance, m_PassClass)) return false; // That route is okay, so update our path m_FinalGoal = goal; m_LongPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.emplace_back(Waypoint{ goalPos.X, goalPos.Y }); return true; } bool CCmpUnitMotion::CheckTargetMovement(const CFixedVector2D& from, entity_pos_t minDelta) { CFixedVector2D targetPos; if (!ComputeTargetPosition(targetPos)) return false; // Fail unless the target has moved enough CFixedVector2D oldTargetPos(m_FinalGoal.x, m_FinalGoal.z); if ((targetPos - oldTargetPos).CompareLength(minDelta) < 0) return false; CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return false; CFixedVector2D pos = cmpPosition->GetPosition2D(); CFixedVector2D oldDir = (oldTargetPos - pos); CFixedVector2D newDir = (targetPos - pos); oldDir.Normalize(); newDir.Normalize(); // Fail unless we're close enough to the target to care about its movement // and the angle between the (straight-line) directions of the previous and new target positions is small if (oldDir.Dot(newDir) > CHECK_TARGET_MOVEMENT_MIN_COS && !PathIsShort(m_LongPath, from, CHECK_TARGET_MOVEMENT_AT_MAX_DIST)) return false; // Fail if the target is no longer visible to this entity's owner // (in which case we'll continue moving to its last known location, // unless it comes back into view before we reach that location) CmpPtr cmpOwnership(GetEntityHandle()); if (cmpOwnership) { CmpPtr cmpRangeManager(GetSystemEntity()); if (cmpRangeManager) { if (cmpRangeManager->GetLosVisibility(m_TargetEntity, cmpOwnership->GetOwner()) == ICmpRangeManager::VIS_HIDDEN) return false; } } // The target moved and we need to update our current path; // change the goal here and expect our caller to start the path request m_FinalGoal.x = targetPos.X; m_FinalGoal.z = targetPos.Y; RequestLongPath(from, m_FinalGoal); m_PathState = PATHSTATE_FOLLOWING_REQUESTING_LONG; return true; } bool CCmpUnitMotion::PathIsShort(const WaypointPath& path, const CFixedVector2D& from, entity_pos_t minDistance) const { CFixedVector2D prev = from; entity_pos_t distLeft = minDistance; for (ssize_t i = (ssize_t)path.m_Waypoints.size()-1; i >= 0; --i) { // Check if the next path segment is longer than the requested minimum CFixedVector2D waypoint(path.m_Waypoints[i].x, path.m_Waypoints[i].z); CFixedVector2D delta = waypoint - prev; if (delta.CompareLength(distLeft) > 0) return false; // Still short enough - prepare to check the next segment distLeft -= delta.Length(); prev = waypoint; } // Reached the end of the path before exceeding minDistance return true; } void CCmpUnitMotion::FaceTowardsPoint(entity_pos_t x, entity_pos_t z) { CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return; CFixedVector2D pos = cmpPosition->GetPosition2D(); FaceTowardsPointFromPos(pos, x, z); } void CCmpUnitMotion::FaceTowardsPointFromPos(const CFixedVector2D& pos, entity_pos_t x, entity_pos_t z) { CFixedVector2D target(x, z); CFixedVector2D offset = target - pos; if (!offset.IsZero()) { entity_angle_t angle = atan2_approx(offset.X, offset.Y); CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition) return; cmpPosition->TurnTo(angle); } } ControlGroupMovementObstructionFilter CCmpUnitMotion::GetObstructionFilter(bool forceAvoidMovingUnits, bool noTarget) const { entity_id_t group = noTarget ? m_TargetEntity : GetGroup(); return ControlGroupMovementObstructionFilter(forceAvoidMovingUnits || ShouldAvoidMovingUnits(), group); } void CCmpUnitMotion::BeginPathing(const CFixedVector2D& from, const PathGoal& goal) { // reset our state for sanity. m_ExpectedPathTicket = 0; CmpPtr cmpObstruction(GetEntityHandle()); if (cmpObstruction) cmpObstruction->SetMovingFlag(false); m_Moving = false; m_PathState = PATHSTATE_NONE; #if DISABLE_PATHFINDER { CmpPtr cmpPathfinder (GetSimContext(), SYSTEM_ENTITY); CFixedVector2D goalPos = m_FinalGoal.NearestPointOnGoal(from); m_LongPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.emplace_back(Waypoint{ goalPos.X, goalPos.Y }); m_PathState = PATHSTATE_FOLLOWING; return; } #endif // If we're aiming at a target entity and it's close and we can reach // it in a straight line, then we'll just go along the straight line // instead of computing a path. if (TryGoingStraightToTargetEntity(from)) { if (!HasValidPath()) StartSucceeded(); m_PathState = PATHSTATE_FOLLOWING; return; } // Same thing applies to non-entity points if (TryGoingStraightToGoalPoint(from)) { if (!HasValidPath()) StartSucceeded(); m_PathState = PATHSTATE_FOLLOWING; return; } // Otherwise we need to compute a path. // If it's close then just do a short path, not a long path // TODO: If it's close on the opposite side of a river then we really // need a long path, so we shouldn't simply check linear distance if (goal.DistanceToPoint(from) < SHORT_PATH_SEARCH_RANGE) { // add our final goal as a long range waypoint so we don't forget // where we are going if the short-range pathfinder returns // an aborted path. m_LongPath.m_Waypoints.clear(); CFixedVector2D target = m_FinalGoal.NearestPointOnGoal(from); m_LongPath.m_Waypoints.emplace_back(Waypoint{ target.X, target.Y }); m_PathState = PATHSTATE_WAITING_REQUESTING_SHORT; RequestShortPath(from, goal, true); } else { m_PathState = PATHSTATE_WAITING_REQUESTING_LONG; RequestLongPath(from, goal); } } void CCmpUnitMotion::RequestLongPath(const CFixedVector2D& from, const PathGoal& goal) { CmpPtr cmpPathfinder(GetSystemEntity()); if (!cmpPathfinder) return; PathGoal improvedGoal = goal; improvedGoal.maxdist = SHORT_PATH_SEARCH_RANGE / 2; cmpPathfinder->SetDebugPath(from.X, from.Y, improvedGoal, m_PassClass); m_ExpectedPathTicket = cmpPathfinder->ComputePathAsync(from.X, from.Y, improvedGoal, m_PassClass, GetEntityId()); } void CCmpUnitMotion::RequestShortPath(const CFixedVector2D &from, const PathGoal& goal, bool avoidMovingUnits) { CmpPtr cmpPathfinder(GetSystemEntity()); if (!cmpPathfinder) return; m_ExpectedPathTicket = cmpPathfinder->ComputeShortPathAsync(from.X, from.Y, m_Clearance, SHORT_PATH_SEARCH_RANGE, goal, m_PassClass, avoidMovingUnits, GetGroup(), GetEntityId()); } bool CCmpUnitMotion::MoveToPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t minRange, entity_pos_t maxRange) { return MoveToPointRange(x, z, minRange, maxRange, INVALID_ENTITY); } bool CCmpUnitMotion::MoveToPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t minRange, entity_pos_t maxRange, entity_id_t target) { PROFILE("MoveToPointRange"); CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return false; CFixedVector2D pos = cmpPosition->GetPosition2D(); PathGoal goal; goal.x = x; goal.z = z; if (minRange.IsZero() && maxRange.IsZero()) { // Non-ranged movement: // Head directly for the goal goal.type = PathGoal::POINT; } else { // Ranged movement: entity_pos_t distance = (pos - CFixedVector2D(x, z)).Length(); if (distance < minRange) { // Too close to target - move outwards to a circle // that's slightly larger than the min range goal.type = PathGoal::INVERTED_CIRCLE; goal.hw = minRange + Pathfinding::GOAL_DELTA; } else if (maxRange >= entity_pos_t::Zero() && distance > maxRange) { // Too far from target - move inwards to a circle // that's slightly smaller than the max range goal.type = PathGoal::CIRCLE; goal.hw = maxRange - Pathfinding::GOAL_DELTA; // If maxRange was abnormally small, // collapse the circle into a point if (goal.hw <= entity_pos_t::Zero()) goal.type = PathGoal::POINT; } else { // We're already in range - no need to move anywhere if (m_FacePointAfterMove) FaceTowardsPointFromPos(pos, x, z); return false; } } m_State = STATE_INDIVIDUAL_PATH; m_TargetEntity = target; m_TargetOffset = CFixedVector2D(); m_TargetMinRange = minRange; m_TargetMaxRange = maxRange; m_FinalGoal = goal; BeginPathing(pos, goal); return true; } bool CCmpUnitMotion::IsInPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t minRange, entity_pos_t maxRange) { CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return false; CFixedVector2D pos = cmpPosition->GetPosition2D(); bool hasObstruction = false; CmpPtr cmpObstructionManager(GetSystemEntity()); ICmpObstructionManager::ObstructionSquare obstruction; //TODO if (cmpObstructionManager) // hasObstruction = cmpObstructionManager->FindMostImportantObstruction(GetObstructionFilter(true), x, z, m_Radius, obstruction); if (minRange.IsZero() && maxRange.IsZero() && hasObstruction) { // Handle the non-ranged mode: CFixedVector2D halfSize(obstruction.hw, obstruction.hh); entity_pos_t distance = Geometry::DistanceToSquare(pos - CFixedVector2D(obstruction.x, obstruction.z), obstruction.u, obstruction.v, halfSize); // See if we're too close to the target square if (distance < minRange) return false; // See if we're close enough to the target square if (maxRange < entity_pos_t::Zero() || distance <= maxRange) return true; return false; } else { entity_pos_t distance = (pos - CFixedVector2D(x, z)).Length(); if (distance < minRange) return false; else if (maxRange >= entity_pos_t::Zero() && distance > maxRange) return false; else return true; } } bool CCmpUnitMotion::ShouldTreatTargetAsCircle(entity_pos_t range, entity_pos_t circleRadius) const { // Given a square, plus a target range we should reach, the shape at that distance // is a round-cornered square which we can approximate as either a circle or as a square. // Previously, we used the shape that minimized the worst-case error. // However that is unsage in some situations. So let's be less clever and // just check if our range is at least three times bigger than the circleradius return (range > circleRadius*3); } bool CCmpUnitMotion::MoveToTargetRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) { PROFILE("MoveToTargetRange"); CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return false; CFixedVector2D pos = cmpPosition->GetPosition2D(); CmpPtr cmpObstructionManager(GetSystemEntity()); if (!cmpObstructionManager) return false; bool hasObstruction = false; ICmpObstructionManager::ObstructionSquare obstruction; CmpPtr cmpObstruction(GetSimContext(), target); if (cmpObstruction) hasObstruction = cmpObstruction->GetObstructionSquare(obstruction); if (!hasObstruction) { // The target didn't have an obstruction or obstruction shape, so treat it as a point instead CmpPtr cmpTargetPosition(GetSimContext(), target); if (!cmpTargetPosition || !cmpTargetPosition->IsInWorld()) return false; CFixedVector2D targetPos = cmpTargetPosition->GetPosition2D(); return MoveToPointRange(targetPos.X, targetPos.Y, minRange, maxRange); } /* * If we're starting outside the maxRange, we need to move closer in. * If we're starting inside the minRange, we need to move further out. * These ranges are measured from the center of this entity to the edge of the target; * we add the goal range onto the size of the target shape to get the goal shape. * (Then we extend it outwards/inwards by a little bit to be sure we'll end up * within the right range, in case of minor numerical inaccuracies.) * * There's a bit of a problem with large square targets: * the pathfinder only lets us move to goals that are squares, but the points an equal * distance from the target make a rounded square shape instead. * * When moving closer, we could shrink the goal radius to 1/sqrt(2) so the goal shape fits entirely * within the desired rounded square, but that gives an unfair advantage to attackers who approach * the target diagonally. * * If the target is small relative to the range (e.g. archers attacking anything), * then we cheat and pretend the target is actually a circle. * (TODO: that probably looks rubbish for things like walls?) * * If the target is large relative to the range (e.g. melee units attacking buildings), * then we multiply maxRange by approx 1/sqrt(2) to guarantee they'll always aim close enough. * (Those units should set minRange to 0 so they'll never be considered *too* close.) */ CFixedVector2D halfSize(obstruction.hw, obstruction.hh); PathGoal goal; goal.x = obstruction.x; goal.z = obstruction.z; entity_pos_t distance = Geometry::DistanceToSquare(pos - CFixedVector2D(obstruction.x, obstruction.z), obstruction.u, obstruction.v, halfSize); // Compare with previous obstruction ICmpObstructionManager::ObstructionSquare previousObstruction; cmpObstruction->GetPreviousObstructionSquare(previousObstruction); entity_pos_t previousDistance = Geometry::DistanceToSquare(pos - CFixedVector2D(previousObstruction.x, previousObstruction.z), obstruction.u, obstruction.v, halfSize); if (distance < minRange && previousDistance < minRange) { // Too close to the square - need to move away // Circumscribe the square entity_pos_t circleRadius = halfSize.Length(); entity_pos_t goalDistance = minRange + Pathfinding::GOAL_DELTA; if (ShouldTreatTargetAsCircle(minRange, circleRadius)) { // The target is small relative to our range, so pretend it's a circle goal.type = PathGoal::INVERTED_CIRCLE; goal.hw = circleRadius + goalDistance; } else { goal.type = PathGoal::INVERTED_SQUARE; goal.u = obstruction.u; goal.v = obstruction.v; goal.hw = obstruction.hw + goalDistance; goal.hh = obstruction.hh + goalDistance; } } else if (maxRange < entity_pos_t::Zero() || distance < maxRange || previousDistance < maxRange) { // We're already in range - no need to move anywhere FaceTowardsPointFromPos(pos, goal.x, goal.z); return false; } else { // We might need to move closer: // Circumscribe the square entity_pos_t circleRadius = halfSize.Length(); if (ShouldTreatTargetAsCircle(maxRange, circleRadius)) { // The target is small relative to our range, so pretend it's a circle // Note that the distance to the circle will always be less than // the distance to the square, so the previous "distance < maxRange" // check is still valid (though not sufficient) entity_pos_t circleDistance = (pos - CFixedVector2D(obstruction.x, obstruction.z)).Length() - circleRadius; entity_pos_t previousCircleDistance = (pos - CFixedVector2D(previousObstruction.x, previousObstruction.z)).Length() - circleRadius; if (circleDistance < maxRange || previousCircleDistance < maxRange) { // We're already in range - no need to move anywhere if (m_FacePointAfterMove) FaceTowardsPointFromPos(pos, goal.x, goal.z); return false; } entity_pos_t goalDistance = maxRange - Pathfinding::GOAL_DELTA; goal.type = PathGoal::CIRCLE; goal.hw = circleRadius + goalDistance; } else { // The target is large relative to our range, so treat it as a square and // get close enough that the diagonals come within range entity_pos_t goalDistance = (maxRange - Pathfinding::GOAL_DELTA)*2 / 3; // multiply by slightly less than 1/sqrt(2) goal.type = PathGoal::SQUARE; goal.u = obstruction.u; goal.v = obstruction.v; entity_pos_t delta = std::max(goalDistance, m_Clearance + entity_pos_t::FromInt(TERRAIN_TILE_SIZE)/16); // ensure it's far enough to not intersect the building itself goal.hw = obstruction.hw + delta; goal.hh = obstruction.hh + delta; } } m_State = STATE_INDIVIDUAL_PATH; m_TargetEntity = target; m_TargetOffset = CFixedVector2D(); m_TargetMinRange = minRange; m_TargetMaxRange = maxRange; m_FinalGoal = goal; BeginPathing(pos, goal); return true; } bool CCmpUnitMotion::IsInTargetRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) { // This function closely mirrors MoveToTargetRange - it needs to return true // after that Move has completed CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return false; CFixedVector2D pos = cmpPosition->GetPosition2D(); CmpPtr cmpObstructionManager(GetSystemEntity()); if (!cmpObstructionManager) return false; bool hasObstruction = false; ICmpObstructionManager::ObstructionSquare obstruction; CmpPtr cmpObstruction(GetSimContext(), target); if (cmpObstruction) hasObstruction = cmpObstruction->GetObstructionSquare(obstruction); if (hasObstruction) { CFixedVector2D halfSize(obstruction.hw, obstruction.hh); entity_pos_t distance = Geometry::DistanceToSquare(pos - CFixedVector2D(obstruction.x, obstruction.z), obstruction.u, obstruction.v, halfSize); // Compare with previous obstruction ICmpObstructionManager::ObstructionSquare previousObstruction; cmpObstruction->GetPreviousObstructionSquare(previousObstruction); entity_pos_t previousDistance = Geometry::DistanceToSquare(pos - CFixedVector2D(previousObstruction.x, previousObstruction.z), obstruction.u, obstruction.v, halfSize); // See if we're too close to the target square if (distance < minRange && previousDistance < minRange) return false; // See if we're close enough to the target square if (maxRange < entity_pos_t::Zero() || distance <= maxRange || previousDistance <= maxRange) return true; entity_pos_t circleRadius = halfSize.Length(); if (ShouldTreatTargetAsCircle(maxRange, circleRadius)) { // The target is small relative to our range, so pretend it's a circle // and see if we're close enough to that. // Also check circle around previous position. entity_pos_t circleDistance = (pos - CFixedVector2D(obstruction.x, obstruction.z)).Length() - circleRadius; entity_pos_t previousCircleDistance = (pos - CFixedVector2D(previousObstruction.x, previousObstruction.z)).Length() - circleRadius; return circleDistance <= maxRange || previousCircleDistance <= maxRange; } // take minimal clearance required in MoveToTargetRange into account, multiplying by 3/2 for diagonals entity_pos_t maxDist = std::max(maxRange, (m_Clearance + entity_pos_t::FromInt(TERRAIN_TILE_SIZE)/16)*3/2); return distance <= maxDist || distance <= maxDist; } else { CmpPtr cmpTargetPosition(GetSimContext(), target); if (!cmpTargetPosition || !cmpTargetPosition->IsInWorld()) return false; CFixedVector2D targetPos = cmpTargetPosition->GetPreviousPosition2D(); entity_pos_t distance = (pos - targetPos).Length(); return minRange <= distance && (maxRange < entity_pos_t::Zero() || distance <= maxRange); } } void CCmpUnitMotion::MoveToFormationOffset(entity_id_t target, entity_pos_t x, entity_pos_t z) { CmpPtr cmpPosition(GetSimContext(), target); if (!cmpPosition || !cmpPosition->IsInWorld()) return; CFixedVector2D pos = cmpPosition->GetPosition2D(); PathGoal goal; goal.type = PathGoal::POINT; goal.x = pos.X; goal.z = pos.Y; m_State = STATE_FORMATIONMEMBER_PATH; m_TargetEntity = target; m_TargetOffset = CFixedVector2D(x, z); m_TargetMinRange = entity_pos_t::Zero(); m_TargetMaxRange = entity_pos_t::Zero(); m_FinalGoal = goal; BeginPathing(pos, goal); } void CCmpUnitMotion::RenderPath(const WaypointPath& path, std::vector& lines, CColor color) { bool floating = false; CmpPtr cmpPosition(GetEntityHandle()); if (cmpPosition) floating = cmpPosition->IsFloating(); lines.clear(); std::vector waypointCoords; for (size_t i = 0; i < path.m_Waypoints.size(); ++i) { float x = path.m_Waypoints[i].x.ToFloat(); float z = path.m_Waypoints[i].z.ToFloat(); waypointCoords.push_back(x); waypointCoords.push_back(z); lines.push_back(SOverlayLine()); lines.back().m_Color = color; SimRender::ConstructSquareOnGround(GetSimContext(), x, z, 1.0f, 1.0f, 0.0f, lines.back(), floating); } lines.push_back(SOverlayLine()); lines.back().m_Color = color; SimRender::ConstructLineOnGround(GetSimContext(), waypointCoords, lines.back(), floating); } void CCmpUnitMotion::RenderSubmit(SceneCollector& collector) { if (!m_DebugOverlayEnabled) return; RenderPath(m_LongPath, m_DebugOverlayLongPathLines, OVERLAY_COLOR_LONG_PATH); RenderPath(m_ShortPath, m_DebugOverlayShortPathLines, OVERLAY_COLOR_SHORT_PATH); for (size_t i = 0; i < m_DebugOverlayLongPathLines.size(); ++i) collector.Submit(&m_DebugOverlayLongPathLines[i]); for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i) collector.Submit(&m_DebugOverlayShortPathLines[i]); } Index: ps/trunk/source/simulation2/components/ICmpObstructionManager.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpObstructionManager.h (revision 17224) +++ ps/trunk/source/simulation2/components/ICmpObstructionManager.h (revision 17225) @@ -1,485 +1,489 @@ /* Copyright (C) 2015 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. 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. * * 0 A.D. 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 0 A.D. If not, see . */ #ifndef INCLUDED_ICMPOBSTRUCTIONMANAGER #define INCLUDED_ICMPOBSTRUCTIONMANAGER #include "simulation2/system/Interface.h" #include "simulation2/helpers/Pathfinding.h" #include "maths/FixedVector2D.h" class IObstructionTestFilter; /** * Obstruction manager: provides efficient spatial queries over objects in the world. * * The class deals with two types of shape: * "static" shapes, typically representing buildings, which are rectangles with a given * width and height and angle; * and "unit" shapes, representing units that can move around the world, which have a * radius and no rotation. (Units sometimes act as axis-aligned squares, sometimes * as approximately circles, due to the algorithm used by the short pathfinder.) * * Other classes (particularly ICmpObstruction) register shapes with this interface * and keep them updated. * * The @c Test functions provide exact collision tests. * The edge of a shape counts as 'inside' the shape, for the purpose of collisions. * The functions accept an IObstructionTestFilter argument, which can restrict the * set of shapes that are counted as collisions. * * Units can be marked as either moving or stationary, which simply determines whether * certain filters include or exclude them. * * The @c Rasterize function approximates the current set of shapes onto a 2D grid, * for use with tile-based pathfinding. */ class ICmpObstructionManager : public IComponent { public: /** * External identifiers for shapes. * (This is a struct rather than a raw u32 for type-safety.) */ struct tag_t { tag_t() : n(0) {} explicit tag_t(u32 n) : n(n) {} bool valid() { return n != 0; } u32 n; }; /** * Boolean flags affecting the obstruction behaviour of a shape. */ enum EFlags { FLAG_BLOCK_MOVEMENT = (1 << 0), // prevents units moving through this shape FLAG_BLOCK_FOUNDATION = (1 << 1), // prevents foundations being placed on this shape FLAG_BLOCK_CONSTRUCTION = (1 << 2), // prevents buildings being constructed on this shape FLAG_BLOCK_PATHFINDING = (1 << 3), // prevents the tile pathfinder choosing paths through this shape FLAG_MOVING = (1 << 4) // indicates this unit is currently moving }; /** * Bitmask of EFlag values. */ typedef u8 flags_t; /** * Set the bounds of the world. * Any point outside the bounds is considered obstructed. * @param x0,z0,x1,z1 Coordinates of the corners of the world */ virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1) = 0; /** * Register a static shape. * * @param ent entity ID associated with this shape (or INVALID_ENTITY if none) * @param x,z coordinates of center, in world space * @param a angle of rotation (clockwise from +Z direction) * @param w width (size along X axis) * @param h height (size along Z axis) * @param flags a set of EFlags values * @param group primary control group of the shape. Must be a valid control group ID. * @param group2 Optional; secondary control group of the shape. Defaults to INVALID_ENTITY. * @return a valid tag for manipulating the shape * @see StaticShape */ virtual tag_t AddStaticShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h, flags_t flags, entity_id_t group, entity_id_t group2 = INVALID_ENTITY) = 0; /** * Register a unit shape. * * @param ent entity ID associated with this shape (or INVALID_ENTITY if none) * @param x,z coordinates of center, in world space * @param clearance pathfinding clearance of the unit (works as a radius) * @param flags a set of EFlags values * @param group control group (typically the owner entity, or a formation controller entity * - units ignore collisions with others in the same group) * @return a valid tag for manipulating the shape * @see UnitShape */ virtual tag_t AddUnitShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, flags_t flags, entity_id_t group) = 0; /** * Adjust the position and angle of an existing shape. * @param tag tag of shape (must be valid) * @param x X coordinate of center, in world space * @param z Z coordinate of center, in world space * @param a angle of rotation (clockwise from +Z direction); ignored for unit shapes */ virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a) = 0; /** * Set whether a unit shape is moving or stationary. * @param tag tag of shape (must be valid and a unit shape) * @param moving whether the unit is currently moving through the world or is stationary */ virtual void SetUnitMovingFlag(tag_t tag, bool moving) = 0; /** * Set the control group of a unit shape. * @param tag tag of shape (must be valid and a unit shape) * @param group control group entity ID */ virtual void SetUnitControlGroup(tag_t tag, entity_id_t group) = 0; /** * Sets the control group of a static shape. * @param tag Tag of the shape to set the control group for. Must be a valid and static shape tag. * @param group Control group entity ID. */ virtual void SetStaticControlGroup(tag_t tag, entity_id_t group, entity_id_t group2) = 0; /** * Remove an existing shape. The tag will be made invalid and must not be used after this. * @param tag tag of shape (must be valid) */ virtual void RemoveShape(tag_t tag) = 0; /** * Collision test a flat-ended thick line against the current set of shapes. * The line caps extend by @p r beyond the end points. * Only intersections going from outside to inside a shape are counted. * @param filter filter to restrict the shapes that are counted * @param x0 X coordinate of line's first point * @param z0 Z coordinate of line's first point * @param x1 X coordinate of line's second point * @param z1 Z coordinate of line's second point * @param r radius (half width) of line * @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) = 0; /** * Collision test a static square shape against the current set of shapes. * @param filter filter to restrict the shapes that are being tested against * @param x X coordinate of center * @param z Z coordinate of center * @param a angle of rotation (clockwise from +Z direction) * @param w width (size along X axis) * @param h height (size along Z axis) * @param out if non-NULL, all colliding shapes' entities will be added to this list * @return true if there is a collision */ 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) = 0; /** * Collision test a unit shape against the current set of registered shapes, and optionally writes a list of the colliding * shapes' entities to an output list. * * @param filter filter to restrict the shapes that are being tested against * @param x X coordinate of shape's center * @param z Z coordinate of shape's center * @param clearance clearance of the shape's unit * @param out if non-NULL, all colliding shapes' entities will be added to this list * * @return true if there is a collision */ virtual bool TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, std::vector* out) = 0; /** * Convert the current set of shapes onto a navcell grid, for all passability classes contained in @p passClasses. * If @p fullUpdate is false, the function will only go through dirty shapes. * Shapes are expanded by the @p passClasses clearances, by ORing their masks onto the @p grid. */ virtual void Rasterize(Grid& grid, const std::vector& passClasses, bool fullUpdate) = 0; /** * Gets dirtiness information and resets it afterwards. Then it's the role of CCmpPathfinder * to pass the information to other components if needed. (AIs, etc.) * The return value is false if an update is unnecessary. */ virtual void UpdateInformations(GridUpdateInformation& informations) = 0; /** * Standard representation for all types of shapes, for use with geometry processing code. */ struct ObstructionSquare { entity_pos_t x, z; // position of center CFixedVector2D u, v; // 'horizontal' and 'vertical' orthogonal unit vectors, representing orientation entity_pos_t hw, hh; // half width, half height of square }; /** * Find all the obstructions that are inside (or partially inside) the given range. * @param filter filter to restrict the shapes that are counted * @param x0 X coordinate of left edge of range * @param z0 Z coordinate of bottom edge of range * @param x1 X coordinate of right edge of range * @param z1 Z coordinate of top edge of range * @param squares output list of obstructions */ 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) = 0; 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) = 0; 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) = 0; /** * Returns the entity IDs of all unit shapes that intersect the given * obstruction square, filtering out using the given filter. + * @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) = 0; + virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict = false) = 0; /** * Get the obstruction square representing the given shape. * @param tag tag of shape (must be valid) */ virtual ObstructionSquare GetObstruction(tag_t tag) = 0; virtual ObstructionSquare GetUnitShapeObstruction(entity_pos_t x, entity_pos_t z, entity_pos_t clearance) = 0; virtual ObstructionSquare GetStaticShapeObstruction(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) = 0; /** * Set the passability to be restricted to a circular map. */ virtual void SetPassabilityCircular(bool enabled) = 0; virtual bool GetPassabilityCircular() const = 0; /** * Toggle the rendering of debug info. */ virtual void SetDebugOverlay(bool enabled) = 0; DECLARE_INTERFACE_TYPE(ObstructionManager) }; /** * Interface for ICmpObstructionManager @c Test functions to filter out unwanted shapes. */ class IObstructionTestFilter { public: typedef ICmpObstructionManager::tag_t tag_t; typedef ICmpObstructionManager::flags_t flags_t; virtual ~IObstructionTestFilter() {} /** * Return true if the shape with the specified parameters should be tested for collisions. * This is called for all shapes that would collide, and also for some that wouldn't. * * @param tag tag of shape being tested * @param flags set of EFlags for the shape * @param group the control group of the shape (typically the shape's unit, or the unit's formation controller, or 0) * @param group2 an optional secondary control group of the shape, or INVALID_ENTITY if none specified. Currently * exists only for static shapes. */ virtual bool TestShape(tag_t tag, flags_t flags, entity_id_t group, entity_id_t group2) const = 0; }; /** * Obstruction test filter that will test against all shapes. */ class NullObstructionFilter : public IObstructionTestFilter { public: virtual bool TestShape(tag_t UNUSED(tag), flags_t UNUSED(flags), entity_id_t UNUSED(group), entity_id_t UNUSED(group2)) const { return true; } }; /** * Obstruction test filter that will test only against stationary (i.e. non-moving) shapes. */ class StationaryOnlyObstructionFilter : public IObstructionTestFilter { public: virtual bool TestShape(tag_t UNUSED(tag), flags_t flags, entity_id_t UNUSED(group), entity_id_t UNUSED(group2)) const { return !(flags & ICmpObstructionManager::FLAG_MOVING); } }; /** * Obstruction test filter that reject shapes in a given control group, * and rejects shapes that don't block unit movement, and optionally rejects moving shapes. */ class ControlGroupMovementObstructionFilter : public IObstructionTestFilter { bool m_AvoidMoving; entity_id_t m_Group; public: ControlGroupMovementObstructionFilter(bool avoidMoving, entity_id_t group) : m_AvoidMoving(avoidMoving), m_Group(group) {} virtual bool TestShape(tag_t UNUSED(tag), flags_t flags, entity_id_t group, entity_id_t group2) const { if (group == m_Group || (group2 != INVALID_ENTITY && group2 == m_Group)) return false; if (!(flags & ICmpObstructionManager::FLAG_BLOCK_MOVEMENT)) return false; if ((flags & ICmpObstructionManager::FLAG_MOVING) && !m_AvoidMoving) return false; return true; } }; /** * Obstruction test filter that will test only against shapes that: * - are part of neither one of the specified control groups * - AND, depending on the value of the 'exclude' argument: * - have at least one of the specified flags set. * - OR have none of the specified flags set. * * The first (primary) control group to reject shapes from must be specified and valid. The secondary * control group to reject entities from may be set to INVALID_ENTITY to not use it. * * This filter is useful to e.g. allow foundations within the same control group to be placed and * constructed arbitrarily close together (e.g. for wall pieces that need to link up tightly). */ class SkipControlGroupsRequireFlagObstructionFilter : public IObstructionTestFilter { bool m_Exclude; entity_id_t m_Group; entity_id_t m_Group2; flags_t m_Mask; public: SkipControlGroupsRequireFlagObstructionFilter(bool exclude, entity_id_t group1, entity_id_t group2, flags_t mask) : m_Exclude(exclude), m_Group(group1), m_Group2(group2), m_Mask(mask) { Init(); } SkipControlGroupsRequireFlagObstructionFilter(entity_id_t group1, entity_id_t group2, flags_t mask) : m_Exclude(false), m_Group(group1), m_Group2(group2), m_Mask(mask) { Init(); } virtual bool TestShape(tag_t UNUSED(tag), flags_t flags, entity_id_t group, entity_id_t group2) const { // Don't test shapes that share one or more of our control groups. if (group == m_Group || group == m_Group2 || (group2 != INVALID_ENTITY && (group2 == m_Group || group2 == m_Group2))) return false; // If m_Exclude is true, don't test against shapes that have any of the // obstruction flags specified in m_Mask. if (m_Exclude) return (flags & m_Mask) == 0; // Otherwise, only include shapes that match at least one flag in m_Mask. return (flags & m_Mask) != 0; } private: void Init() { // the primary control group to filter out must be valid ENSURE(m_Group != INVALID_ENTITY); // for simplicity, if m_Group2 is INVALID_ENTITY (i.e. not used), then set it equal to m_Group // so that we have fewer special cases to consider in TestShape(). if (m_Group2 == INVALID_ENTITY) m_Group2 = m_Group; } }; /** * Obstruction test filter that will test only against shapes that: * - are part of both of the specified control groups * - AND have at least one of the specified flags set. * * The first (primary) control group to include shapes from must be specified and valid. * * This filter is useful for preventing entities with identical control groups * from colliding e.g. building a new wall segment on top of an existing wall) * * @todo This filter needs test cases. */ class SkipTagRequireControlGroupsAndFlagObstructionFilter : public IObstructionTestFilter { tag_t m_Tag; entity_id_t m_Group; entity_id_t m_Group2; flags_t m_Mask; public: SkipTagRequireControlGroupsAndFlagObstructionFilter(tag_t tag, entity_id_t group1, entity_id_t group2, flags_t mask) : m_Tag(tag), m_Group(group1), m_Group2(group2), m_Mask(mask) { ENSURE(m_Group != INVALID_ENTITY); } virtual bool TestShape(tag_t tag, flags_t flags, entity_id_t group, entity_id_t group2) const { // To be included in testing, a shape must not have the specified tag, and must // match at least one of the flags in m_Mask, as well as both control groups. return (tag.n != m_Tag.n && (flags & m_Mask) != 0 && ((group == m_Group && group2 == m_Group2) || (group2 == m_Group && group == m_Group2))); } }; /** * Obstruction test filter that will test only against shapes that do not have the specified tag set. */ class SkipTagObstructionFilter : public IObstructionTestFilter { tag_t m_Tag; public: SkipTagObstructionFilter(tag_t tag) : m_Tag(tag) { } virtual bool TestShape(tag_t tag, flags_t UNUSED(flags), entity_id_t UNUSED(group), entity_id_t UNUSED(group2)) const { return tag.n != m_Tag.n; } }; /** * Obstruction test filter that will test only against shapes that: * - do not have the specified tag * - AND have at least one of the specified flags set. */ class SkipTagRequireFlagsObstructionFilter : public IObstructionTestFilter { tag_t m_Tag; flags_t m_Mask; public: SkipTagRequireFlagsObstructionFilter(tag_t tag, flags_t mask) : m_Tag(tag), m_Mask(mask) { } virtual bool TestShape(tag_t tag, flags_t flags, entity_id_t UNUSED(group), entity_id_t UNUSED(group2)) const { return (tag.n != m_Tag.n && (flags & m_Mask) != 0); } }; #endif // INCLUDED_ICMPOBSTRUCTIONMANAGER