text: //
  // Copyright (c) 2008-2019 the Urho3D project.
  //
  // Permission is hereby granted, free of charge, to any person obtaining a copy
  // of this software and associated documentation files (the "Software"), to deal
  // in the Software without restriction, including without limitation the rights
  // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  // copies of the Software, and to permit persons to whom the Software is
  // furnished to do so, subject to the following conditions:
  //
  // The above copyright notice and this permission notice shall be included in
  // all copies or substantial portions of the Software.
  //
  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  // THE SOFTWARE.
  //
  
  #include "../Precompiled.h"
  
  #include "../Core/Context.h"
  #include "../Core/Profiler.h"
  #include "../Graphics/DebugRenderer.h"
  #include "../IO/Log.h"
  #include "../Navigation/CrowdAgent.h"
  #include "../Navigation/CrowdManager.h"
  #include "../Navigation/DynamicNavigationMesh.h"
  #include "../Navigation/NavigationEvents.h"
  #include "../Scene/Node.h"
  #include "../Scene/Scene.h"
  #include "../Scene/SceneEvents.h"
  
  #include <DetourCrowd/DetourCrowd.h>
  
  #include "../DebugNew.h"
  
  namespace Urho3D
  {
  
  extern const char* NAVIGATION_CATEGORY;
  
  static const unsigned DEFAULT_MAX_AGENTS = 512;
  static const float DEFAULT_MAX_AGENT_RADIUS = 0.f;
  
  static const StringVector filterTypesStructureElementNames =
  {
      "Query Filter Type Count",
      "   Include Flags",
      "   Exclude Flags",
      "   >AreaCost"
  };
  
  static const StringVector obstacleAvoidanceTypesStructureElementNames =
  {
      "Obstacle Avoid. Type Count",
      "   Velocity Bias",
      "   Desired Velocity Weight",
      "   Current Velocity Weight",
      "   Side Bias Weight",
      "   Time of Impact Weight",
      "   Time Horizon",
      "   Grid Size",
      "   Adaptive Divs",
      "   Adaptive Rings",
      "   Adaptive Depth"
  };
  
  void CrowdAgentUpdateCallback(dtCrowdAgent* ag, float dt)
  {
      static_cast<CrowdAgent*>(ag->params.userData)->OnCrowdUpdate(ag, dt);
  }
  
  CrowdManager::CrowdManager(Context* context) :
      Component(context),
      maxAgents_(DEFAULT_MAX_AGENTS),
      maxAgentRadius_(DEFAULT_MAX_AGENT_RADIUS)
  {
      // The actual buffer is allocated inside dtCrowd, we only track the number of "slots" being configured explicitly
      numAreas_.Reserve(DT_CROWD_MAX_QUERY_FILTER_TYPE);
      for (unsigned i = 0; i < DT_CROWD_MAX_QUERY_FILTER_TYPE; ++i)
          numAreas_.Push(0);
  }
  
  CrowdManager::~CrowdManager()
  {
      dtFreeCrowd(crowd_);
      crowd_ = nullptr;
  }
  
  void CrowdManager::RegisterObject(Context* context)
  {
      context->RegisterFactory<CrowdManager>(NAVIGATION_CATEGORY);
  
      URHO3D_ATTRIBUTE("Max Agents", unsigned, maxAgents_, DEFAULT_MAX_AGENTS, AM_DEFAULT);
      URHO3D_ATTRIBUTE("Max Agent Radius", float, maxAgentRadius_, DEFAULT_MAX_AGENT_RADIUS, AM_DEFAULT);
      URHO3D_ATTRIBUTE("Navigation Mesh", unsigned, navigationMeshId_, 0, AM_DEFAULT | AM_COMPONENTID);
      URHO3D_MIXED_ACCESSOR_ATTRIBUTE("Filter Types", GetQueryFilterTypesAttr, SetQueryFilterTypesAttr,
          VariantVector, Variant::emptyVariantVector, AM_DEFAULT)
          .SetMetadata(AttributeMetadata::P_VECTOR_STRUCT_ELEMENTS, filterTypesStructureElementNames);
      URHO3D_MIXED_ACCESSOR_ATTRIBUTE("Obstacle Avoidance Types", GetObstacleAvoidanceTypesAttr, SetObstacleAvoidanceTypesAttr,
          VariantVector, Variant::emptyVariantVector, AM_DEFAULT)
          .SetMetadata(AttributeMetadata::P_VECTOR_STRUCT_ELEMENTS, obstacleAvoidanceTypesStructureElementNames);
  }
  
  void CrowdManager::ApplyAttributes()
  {
      // Values from Editor, saved-file, or network must be checked before applying
      maxAgents_ = Max(1U, maxAgents_);
      maxAgentRadius_ = Max(0.f, maxAgentRadius_);
  
      bool navMeshChange = false;
      Scene* scene = GetScene();
      if (scene && navigationMeshId_)
      {
          auto* navMesh = dynamic_cast<NavigationMesh*>(scene->GetComponent(navigationMeshId_));
          if (navMesh && navMesh != navigationMesh_)
          {
              SetNavigationMesh(navMesh); // This will also CreateCrowd(), so the rest of the function is unnecessary
              return;
          }
      }
      // In case of receiving an invalid component id, revert it back to the existing navmesh component id (if any)
      navigationMeshId_ = navigationMesh_ ? navigationMesh_->GetID() : 0;
  
      // If the Detour crowd initialization parameters have changed then recreate it
      if (crowd_ && (navMeshChange || crowd_->getAgentCount() != maxAgents_ || crowd_->getMaxAgentRadius() != maxAgentRadius_))
          CreateCrowd();
  }
  
  void CrowdManager::DrawDebugGeometry(DebugRenderer* debug, bool depthTest)
  {
      if (debug && crowd_)
      {
          // Current position-to-target line
          for (int i = 0; i < crowd_->getAgentCount(); i++)
          {
              const dtCrowdAgent* ag = crowd_->getAgent(i);
              if (!ag->active)
                  continue;
  
              // Draw CrowdAgent shape (from its radius & height)
              auto* crowdAgent = static_cast<CrowdAgent*>(ag->params.userData);
              crowdAgent->DrawDebugGeometry(debug, depthTest);
  
              // Draw move target if any
              if (crowdAgent->GetTargetState() == CA_TARGET_NONE || crowdAgent->GetTargetState() == CA_TARGET_VELOCITY)
                  continue;
  
              Color color(0.6f, 0.2f, 0.2f, 1.0f);
  
              // Draw line to target
              Vector3 pos1(ag->npos[0], ag->npos[1], ag->npos[2]);
              Vector3 pos2;
              for (int i = 0; i < ag->ncorners; ++i)
              {
                  pos2.x_ = ag->cornerVerts[i * 3];
                  pos2.y_ = ag->cornerVerts[i * 3 + 1];
                  pos2.z_ = ag->cornerVerts[i * 3 + 2];
                  debug->AddLine(pos1, pos2, color, depthTest);
                  pos1 = pos2;
              }
              pos2.x_ = ag->targetPos[0];
              pos2.y_ = ag->targetPos[1];
              pos2.z_ = ag->targetPos[2];
              debug->AddLine(pos1, pos2, color, depthTest);
  
              // Draw target circle
              debug->AddSphere(Sphere(pos2, 0.5f), color, depthTest);
          }
      }
  }
  
  void CrowdManager::DrawDebugGeometry(bool depthTest)
  {
      Scene* scene = GetScene();
      if (scene)
      {
          auto* debug = scene->GetComponent<DebugRenderer>();
          if (debug)
              DrawDebugGeometry(debug, depthTest);
      }
  }
  
  void CrowdManager::SetCrowdTarget(const Vector3& position, Node* node)
  {
      if (!crowd_)
          return;
  
      PODVector<CrowdAgent*> agents = GetAgents(node, false);     // Get all crowd agent components
      Vector3 moveTarget(position);
      for (unsigned i = 0; i < agents.Size(); ++i)
      {
          // Give application a chance to determine the desired crowd formation when they reach the target position
          CrowdAgent* agent = agents[i];
  
          using namespace CrowdAgentFormation;
  
          VariantMap& map = GetEventDataMap();
          map[P_NODE] = agent->GetNode();
          map[P_CROWD_AGENT] = agent;
          map[P_INDEX] = i;
          map[P_SIZE] = agents.Size();
          map[P_POSITION] = moveTarget;   // Expect the event handler will modify this position accordingly
  
          SendEvent(E_CROWD_AGENT_FORMATION, map);
  
          moveTarget = map[P_POSITION].GetVector3();
          agent->SetTargetPosition(moveTarget);
      }
  }
  
  void CrowdManager::SetCrowdVelocity(const Vector3& velocity, Node* node)
  {
      if (!crowd_)
          return;
  
      PODVector<CrowdAgent*> agents = GetAgents(node, true);      // Get only crowd agent components already in the crowd
      for (unsigned i = 0; i < agents.Size(); ++i)
          agents[i]->SetTargetVelocity(velocity);
  }
  
  void CrowdManager::ResetCrowdTarget(Node* node)
  {
      if (!crowd_)
          return;
  
      PODVector<CrowdAgent*> agents = GetAgents(node, true);
      for (unsigned i = 0; i < agents.Size(); ++i)
          agents[i]->ResetTarget();
  }
  
  void CrowdManager::SetMaxAgents(unsigned maxAgents)
  {
      if (maxAgents != maxAgents_ && maxAgents > 0)
      {
          maxAgents_ = maxAgents;
          CreateCrowd();
          MarkNetworkUpdate();
      }
  }
  
  void CrowdManager::SetMaxAgentRadius(float maxAgentRadius)
  {
      if (maxAgentRadius != maxAgentRadius_ && maxAgentRadius > 0.f)
      {
          maxAgentRadius_ = maxAgentRadius;
          CreateCrowd();
          MarkNetworkUpdate();
      }
  }
  
  void CrowdManager::SetNavigationMesh(NavigationMesh* navMesh)
  {
      UnsubscribeFromEvent(E_COMPONENTADDED);
      UnsubscribeFromEvent(E_NAVIGATION_MESH_REBUILT);
      UnsubscribeFromEvent(E_COMPONENTREMOVED);
  
      if (navMesh != navigationMesh_)     // It is possible to reset navmesh pointer back to 0
      {
          Scene* scene = GetScene();
  
          navigationMesh_ = navMesh;
          navigationMeshId_ = navMesh ? navMesh->GetID() : 0;
  
          if (navMesh)
          {
              SubscribeToEvent(navMesh, E_NAVIGATION_MESH_REBUILT, URHO3D_HANDLER(CrowdManager, HandleNavMeshChanged));
              SubscribeToEvent(scene, E_COMPONENTREMOVED, URHO3D_HANDLER(CrowdManager, HandleNavMeshChanged));
          }
  
          CreateCrowd();
          MarkNetworkUpdate();
      }
  }
  
  void CrowdManager::SetQueryFilterTypesAttr(const VariantVector& value)
  {
      if (!crowd_)
          return;
  
      unsigned index = 0;
      unsigned queryFilterType = 0;
      numQueryFilterTypes_ = index < value.Size() ? Min(value[index++].GetUInt(), (unsigned)DT_CROWD_MAX_QUERY_FILTER_TYPE) : 0;
  
      while (queryFilterType < numQueryFilterTypes_)
      {
          if (index + 3 <= value.Size())
          {
              dtQueryFilter* filter = crowd_->getEditableFilter(queryFilterType);
              assert(filter);
              filter->setIncludeFlags((unsigned short)value[index++].GetUInt());
              filter->setExcludeFlags((unsigned short)value[index++].GetUInt());
              unsigned prevNumAreas = numAreas_[queryFilterType];
              numAreas_[queryFilterType] = Min(value[index++].GetUInt(), (unsigned)DT_MAX_AREAS);
  
              // Must loop through based on previous number of areas, the new area cost (if any) can only be set in the next attribute get/set iteration
              if (index + prevNumAreas <= value.Size())
              {
                  for (unsigned i = 0; i < prevNumAreas; ++i)
                      filter->setAreaCost(i, value[index++].GetFloat());
              }
          }
          ++queryFilterType;
      }
  }
  
  void CrowdManager::SetIncludeFlags(unsigned queryFilterType, unsigned short flags)
  {
      auto* filter = const_cast<dtQueryFilter*>(GetDetourQueryFilter(queryFilterType));
      if (filter)
      {
          filter->setIncludeFlags(flags);
          if (numQueryFilterTypes_ < queryFilterType + 1)
              numQueryFilterTypes_ = queryFilterType + 1;
          MarkNetworkUpdate();
      }
  }
  
  void CrowdManager::SetExcludeFlags(unsigned queryFilterType, unsigned short flags)
  {
      auto* filter = const_cast<dtQueryFilter*>(GetDetourQueryFilter(queryFilterType));
      if (filter)
      {
          filter->setExcludeFlags(flags);
          if (numQueryFilterTypes_ < queryFilterType + 1)
              numQueryFilterTypes_ = queryFilterType + 1;
          MarkNetworkUpdate();
      }
  }
  
  void CrowdManager::SetAreaCost(unsigned queryFilterType, unsigned areaID, float cost)
  {
      auto* filter = const_cast<dtQueryFilter*>(GetDetourQueryFilter(queryFilterType));
      if (filter && areaID < DT_MAX_AREAS)
      {
          filter->setAreaCost((int)areaID, cost);
          if (numQueryFilterTypes_ < queryFilterType + 1)
              numQueryFilterTypes_ = queryFilterType + 1;
          if (numAreas_[queryFilterType] < areaID + 1)
              numAreas_[queryFilterType] = areaID + 1;
          MarkNetworkUpdate();
      }
  }
  
  void CrowdManager::SetObstacleAvoidanceTypesAttr(const VariantVector& value)
  {
      if (!crowd_)
          return;
  
      unsigned index = 0;
      unsigned obstacleAvoidanceType = 0;
      numObstacleAvoidanceTypes_ = index < value.Size() ? Min(value[index++].GetUInt(), (unsigned)DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS) : 0;
  
      while (obstacleAvoidanceType < numObstacleAvoidanceTypes_)
      {
          if (index + 10 <= value.Size())
          {
              dtObstacleAvoidanceParams params;       // NOLINT(hicpp-member-init)
              params.velBias = value[index++].GetFloat();
              params.weightDesVel = value[index++].GetFloat();
              params.weightCurVel = value[index++].GetFloat();
              params.weightSide = value[index++].GetFloat();
              params.weightToi = value[index++].GetFloat();
              params.horizTime = value[index++].GetFloat();
              params.gridSize = (unsigned char)value[index++].GetUInt();
              params.adaptiveDivs = (unsigned char)value[index++].GetUInt();
              params.adaptiveRings = (unsigned char)value[index++].GetUInt();
              params.adaptiveDepth = (unsigned char)value[index++].GetUInt();
              crowd_->setObstacleAvoidanceParams(obstacleAvoidanceType, &params);
          }
          ++obstacleAvoidanceType;
      }
  }
  
  void CrowdManager::SetObstacleAvoidanceParams(unsigned obstacleAvoidanceType, const CrowdObstacleAvoidanceParams& params)
  {
      if (crowd_ && obstacleAvoidanceType < DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS)
      {
          crowd_->setObstacleAvoidanceParams(obstacleAvoidanceType, reinterpret_cast<const dtObstacleAvoidanceParams*>(&params));
          if (numObstacleAvoidanceTypes_ < obstacleAvoidanceType + 1)
              numObstacleAvoidanceTypes_ = obstacleAvoidanceType + 1;
          MarkNetworkUpdate();
      }
  }
  
  Vector3 CrowdManager::FindNearestPoint(const Vector3& point, int queryFilterType, dtPolyRef* nearestRef, dtStatus* status)
  {
      if (nearestRef)
          *nearestRef = 0;
      return crowd_ && navigationMesh_ ?
          navigationMesh_->FindNearestPoint(point, Vector3(crowd_->getQueryExtents()), crowd_->getFilter(queryFilterType), nearestRef, status) : point;
  }
  
  Vector3 CrowdManager::MoveAlongSurface(const Vector3& start, const Vector3& end, int queryFilterType, int maxVisited)
  {
      return crowd_ && navigationMesh_ ?
          navigationMesh_->MoveAlongSurface(start, end, Vector3(crowd_->getQueryExtents()), maxVisited, crowd_->getFilter(queryFilterType)) :
          end;
  }
  
  dtStatus CrowdManager::FindPath(PODVector<Vector3>& dest, const Vector3& start, const Vector3& end, int queryFilterType)
  {
      if (crowd_ && navigationMesh_)
          return navigationMesh_->FindPath(dest, start, end, Vector3(crowd_->getQueryExtents()), crowd_->getFilter(queryFilterType));
  }
  
  Vector3 CrowdManager::GetRandomPoint(int queryFilterType, dtPolyRef* randomRef)
  {
      if (randomRef)
          *randomRef = 0;
      return crowd_ && navigationMesh_ ? navigationMesh_->GetRandomPoint(crowd_->getFilter(queryFilterType), randomRef) :
          Vector3::ZERO;
  }
  
  Vector3 CrowdManager::GetRandomPointInCircle(const Vector3& center, float radius, int queryFilterType, dtPolyRef* randomRef)
  {
      if (randomRef)
          *randomRef = 0;
      return crowd_ && navigationMesh_ ?
          navigationMesh_->GetRandomPointInCircle(center, radius, Vector3(crowd_->getQueryExtents()),
              crowd_->getFilter(queryFilterType), randomRef) : center;
  }
  
  float CrowdManager::GetDistanceToWall(const Vector3& point, float radius, int queryFilterType, Vector3* hitPos, Vector3* hitNormal)
  {
      if (hitPos)
          *hitPos = Vector3::ZERO;
      if (hitNormal)
          *hitNormal = Vector3::DOWN;
      return crowd_ && navigationMesh_ ?
          navigationMesh_->GetDistanceToWall(point, radius, Vector3(crowd_->getQueryExtents()), crowd_->getFilter(queryFilterType),
              hitPos, hitNormal) : radius;
  }
  
  Vector3 CrowdManager::Raycast(const Vector3& start, const Vector3& end, int queryFilterType, Vector3* hitNormal)
  {
      if (hitNormal)
          *hitNormal = Vector3::DOWN;
      return crowd_ && navigationMesh_ ?
          navigationMesh_->Raycast(start, end, Vector3(crowd_->getQueryExtents()), crowd_->getFilter(queryFilterType), hitNormal)
              : end;
  }
  
  unsigned CrowdManager::GetNumAreas(unsigned queryFilterType) const
  {
      return queryFilterType < numQueryFilterTypes_ ? numAreas_[queryFilterType] : 0;
  }
  
  VariantVector CrowdManager::GetQueryFilterTypesAttr() const
  {
      VariantVector ret;
      if (crowd_)
      {
          unsigned totalNumAreas = 0;
          for (unsigned i = 0; i < numQueryFilterTypes_; ++i)
              totalNumAreas += numAreas_[i];
  
          ret.Reserve(numQueryFilterTypes_ * 3 + totalNumAreas + 1);
          ret.Push(numQueryFilterTypes_);
  
          for (unsigned i = 0; i < numQueryFilterTypes_; ++i)
          {
              const dtQueryFilter* filter = crowd_->getFilter(i);
              assert(filter);
              ret.Push(filter->getIncludeFlags());
              ret.Push(filter->getExcludeFlags());
              ret.Push(numAreas_[i]);
  
              for (unsigned j = 0; j < numAreas_[i]; ++j)
                  ret.Push(filter->getAreaCost(j));
          }
      }
      else
          ret.Push(0);
  
      return ret;
  }
  
  unsigned short CrowdManager::GetIncludeFlags(unsigned queryFilterType) const
  {
      if (queryFilterType >= numQueryFilterTypes_)
          URHO3D_LOGWARNINGF("Query filter type %d is not configured yet, returning the default include flags initialized by dtCrowd",
              queryFilterType);
      const dtQueryFilter* filter = GetDetourQueryFilter(queryFilterType);
      return (unsigned short)(filter ? filter->getIncludeFlags() : 0xffff);
  }
  
  unsigned short CrowdManager::GetExcludeFlags(unsigned queryFilterType) const
  {
      if (queryFilterType >= numQueryFilterTypes_)
          URHO3D_LOGWARNINGF("Query filter type %d is not configured yet, returning the default exclude flags initialized by dtCrowd",
              queryFilterType);
      const dtQueryFilter* filter = GetDetourQueryFilter(queryFilterType);
      return (unsigned short)(filter ? filter->getExcludeFlags() : 0);
  }
  
  float CrowdManager::GetAreaCost(unsigned queryFilterType, unsigned areaID) const
  {
      if (queryFilterType >= numQueryFilterTypes_ || areaID >= numAreas_[queryFilterType])
          URHO3D_LOGWARNINGF(
              "Query filter type %d and/or area id %d are not configured yet, returning the default area cost initialized by dtCrowd",
              queryFilterType, areaID);
      const dtQueryFilter* filter = GetDetourQueryFilter(queryFilterType);
      return filter ? filter->getAreaCost((int)areaID) : 1.f;
  }
  
  VariantVector CrowdManager::GetObstacleAvoidanceTypesAttr() const
  {
      VariantVector ret;
      if (crowd_)
      {
          ret.Reserve(numObstacleAvoidanceTypes_ * 10 + 1);
          ret.Push(numObstacleAvoidanceTypes_);
  
          for (unsigned i = 0; i < numObstacleAvoidanceTypes_; ++i)
          {
              const dtObstacleAvoidanceParams* params = crowd_->getObstacleAvoidanceParams(i);
              assert(params);
              ret.Push(params->velBias);
              ret.Push(params->weightDesVel);
              ret.Push(params->weightCurVel);
              ret.Push(params->weightSide);
              ret.Push(params->weightToi);
              ret.Push(params->horizTime);
              ret.Push(params->gridSize);
              ret.Push(params->adaptiveDivs);
              ret.Push(params->adaptiveRings);
              ret.Push(params->adaptiveDepth);
          }
      }
      else
          ret.Push(0);
  
      return ret;
  }
  
  const CrowdObstacleAvoidanceParams& CrowdManager::GetObstacleAvoidanceParams(unsigned obstacleAvoidanceType) const
  {
      static const CrowdObstacleAvoidanceParams EMPTY_PARAMS = CrowdObstacleAvoidanceParams();
      const dtObstacleAvoidanceParams* params = crowd_ ? crowd_->getObstacleAvoidanceParams(obstacleAvoidanceType) : nullptr;
      return params ? *reinterpret_cast<const CrowdObstacleAvoidanceParams*>(params) : EMPTY_PARAMS;
  }
  
  PODVector<CrowdAgent*> CrowdManager::GetAgents(Node* node, bool inCrowdFilter) const
  {
      if (!node)
          node = GetScene();
      PODVector<CrowdAgent*> agents;
      node->GetComponents<CrowdAgent>(agents, true);
      if (inCrowdFilter)
      {
          PODVector<CrowdAgent*>::Iterator i = agents.Begin();
          while (i != agents.End())
          {
              if ((*i)->IsInCrowd())
                  ++i;
              else
                  i = agents.Erase(i);
          }
      }
      return agents;
  }
  
  bool CrowdManager::CreateCrowd()
  {
      if (!navigationMesh_ || !navigationMesh_->InitializeQuery())
          return false;
  
      // Preserve the existing crowd configuration before recreating it
      VariantVector queryFilterTypeConfiguration, obstacleAvoidanceTypeConfiguration;
      bool recreate = crowd_ != nullptr;
      if (recreate)
      {
          queryFilterTypeConfiguration = GetQueryFilterTypesAttr();
          obstacleAvoidanceTypeConfiguration = GetObstacleAvoidanceTypesAttr();
          dtFreeCrowd(crowd_);
      }
      crowd_ = dtAllocCrowd();
  
      // Initialize the crowd
      if (maxAgentRadius_ == 0.f)
          maxAgentRadius_ = navigationMesh_->GetAgentRadius();
      if (!crowd_->init(maxAgents_, maxAgentRadius_, navigationMesh_->navMesh_, CrowdAgentUpdateCallback))
      {
          URHO3D_LOGERROR("Could not initialize DetourCrowd");
          return false;
      }
  
      if (recreate)
      {
          // Reconfigure the newly initialized crowd
          SetQueryFilterTypesAttr(queryFilterTypeConfiguration);
          SetObstacleAvoidanceTypesAttr(obstacleAvoidanceTypeConfiguration);
  
          // Re-add the existing crowd agents
          PODVector<CrowdAgent*> agents = GetAgents();
          for (unsigned i = 0; i < agents.Size(); ++i)
          {
              // Keep adding until the crowd cannot take it anymore
              if (agents[i]->AddAgentToCrowd(true) == -1)
              {
                  URHO3D_LOGWARNINGF("CrowdManager: %d crowd agents orphaned", agents.Size() - i);
                  break;
              }
          }
      }
  
      return true;
  }
  
  int CrowdManager::AddAgent(CrowdAgent* agent, const Vector3& pos)
  {
      if (!crowd_ || !navigationMesh_ || !agent)
          return -1;
      dtCrowdAgentParams params{};
      params.userData = agent;
      if (agent->radius_ == 0.f)
          agent->radius_ = navigationMesh_->GetAgentRadius();
      if (agent->height_ == 0.f)
          agent->height_ = navigationMesh_->GetAgentHeight();
      // dtCrowd::addAgent() requires the query filter type to find the nearest position on navmesh as the initial agent's position
      params.queryFilterType = (unsigned char)agent->GetQueryFilterType();
      return crowd_->addAgent(pos.Data(), &params);
  }
  
  void CrowdManager::RemoveAgent(CrowdAgent* agent)
  {
      if (!crowd_ || !agent)
          return;
      dtCrowdAgent* agt = crowd_->getEditableAgent(agent->GetAgentCrowdId());
      if (agt)
          agt->params.userData = nullptr;
      crowd_->removeAgent(agent->GetAgentCrowdId());
  }
  
  void CrowdManager::OnSceneSet(Scene* scene)
  {
      // Subscribe to the scene subsystem update, which will trigger the crowd update step, and grab a reference
      // to the scene's NavigationMesh
      if (scene)
      {
          if (scene != node_)
          {
              URHO3D_LOGERROR("CrowdManager is a scene component and should only be attached to the scene node");
              return;
          }
  
          SubscribeToEvent(scene, E_SCENESUBSYSTEMUPDATE, URHO3D_HANDLER(CrowdManager, HandleSceneSubsystemUpdate));
  
          // Attempt to auto discover a NavigationMesh component (or its derivative) under the scene node
          if (navigationMeshId_ == 0)
          {
              auto* navMesh = scene->GetDerivedComponent<NavigationMesh>(true);
              if (navMesh)
                  SetNavigationMesh(navMesh);
              else
              {
                  // If not found, attempt to find in a delayed manner
                  SubscribeToEvent(scene, E_COMPONENTADDED, URHO3D_HANDLER(CrowdManager, HandleComponentAdded));
              }
          }
      }
      else
      {
          UnsubscribeFromEvent(E_SCENESUBSYSTEMUPDATE);
          UnsubscribeFromEvent(E_NAVIGATION_MESH_REBUILT);
          UnsubscribeFromEvent(E_COMPONENTADDED);
          UnsubscribeFromEvent(E_COMPONENTREMOVED);
  
          navigationMesh_ = nullptr;
      }
  }
  
  void CrowdManager::Update(float delta)
  {
      assert(crowd_ && navigationMesh_);
      URHO3D_PROFILE(UpdateCrowd);
      crowd_->update(delta, nullptr);
  }
  
  const dtCrowdAgent* CrowdManager::GetDetourCrowdAgent(int agent) const
  {
      return crowd_ ? crowd_->getAgent(agent) : nullptr;
  }
  
  const dtQueryFilter* CrowdManager::GetDetourQueryFilter(unsigned queryFilterType) const
  {
      return crowd_ ? crowd_->getFilter(queryFilterType) : nullptr;
  }
  
  void CrowdManager::HandleSceneSubsystemUpdate(StringHash eventType, VariantMap& eventData)
  {
      // Perform update tick as long as the crowd is initialized and the associated navmesh has not been removed
      if (crowd_ && navigationMesh_)
      {
          using namespace SceneSubsystemUpdate;
  
          if (IsEnabledEffective())
              Update(eventData[P_TIMESTEP].GetFloat());
      }
  }
  
  void CrowdManager::HandleNavMeshChanged(StringHash eventType, VariantMap& eventData)
  {
      NavigationMesh* navMesh;
      if (eventType == E_NAVIGATION_MESH_REBUILT)
      {
          navMesh = static_cast<NavigationMesh*>(eventData[NavigationMeshRebuilt::P_MESH].GetPtr());
          // Reset internal pointer so that the same navmesh can be reassigned and the crowd creation be reattempted
          if (navMesh == navigationMesh_)
              navigationMesh_.Reset();
      }
      else
      {
          // eventType == E_COMPONENTREMOVED
          navMesh = static_cast<NavigationMesh*>(eventData[ComponentRemoved::P_COMPONENT].GetPtr());
          // Only interested in navmesh component being used to initialized the crowd
          if (navMesh != navigationMesh_)
              return;
          // Since this is a component removed event, reset our own navmesh pointer
          navMesh = nullptr;
      }
  
      SetNavigationMesh(navMesh);
  }
  
  void CrowdManager::HandleComponentAdded(StringHash eventType, VariantMap& eventData)
  {
      Scene* scene = GetScene();
      if (scene)
      {
          auto* navMesh = scene->GetDerivedComponent<NavigationMesh>(true);
          if (navMesh)
              SetNavigationMesh(navMesh);
      }
  }
  
  }
  