Collision, triggering, and range detection in an RTS. What are the optimal solutions for unit spatial awareness?

Question

I've finally ran into the problem of multiple triggers and collisions within my 2D RTS. Up till now I've been using unities sphere colliders as a way of simulating spatial awareness. To trigger when objects have entered and exited a specific area around a unit or building so that they can be appropriately targeted.

This became a performance problem when I started having hundreds of colldiers overlapping each other. Since the units are aware of projectiles as well as other units/buildings, this becomes very expensive very fast. I've found that I can only manage to have a couple hundred projectiles and about 100 colliders within close proximity of each other before the game slows to a crawl just from PhysX. (hundreds of projectiles entering and exiting 100 collliders all the time)

I did some research and found spatial partitioning mentioned all over the place. Is this a solution to the problem I am currently presented with? Are there other solutions for objects to have spatial awareness of potentially hundreds of other objects at a time without bringing my CPU to it's knees?

Answer 1

You will probably need a hybrid between a btree, and quad-tree. (to get you Googling)

A few things to consider when partitioning:
-Surface-to-air missiles do not need to test against ground units
-Likewise with air-to-surface and air-to-air
-Buildings don't move and shouldn't test against other objects; other objects should test against buildings
-Projectiles only move forward (even when following a curved path); no need to test objects behind and/or too far left/right

The logical divisions like air/ground will be separate buckets within the leaf-nodes of the tree you make. With said tree, any projectile can quickly query for nodes that are in range and within a FOV of it's "forward" direction. The node can return all of its contained objects, or any individual bucket. For example, air-to-air missiles will query only the air buckets out of the nodes in front of them. Likewise, tanks only need to consider the ground-unit and building buckets.

Very quickly/roughly (more or less C#, apparently):

class TreeNode
{
   void AddAirUnit(AirUnit unit) {...}
   void AddUnit(UnitTypes unitType, Unit unit)
   {
      m_allUnits.Add(unit);
      foreach (TreeNode child in m_nodes)
      {
         //Parent can test whether each child should own unit
         //Or each child can ignore units that don't actually belong to it
         child.AddUnit(unitType, unit);
      }
   }
   virtual AirUnit[] GetAirUnits() {...}
   virtual LandUnit[] GetLandUnits() {...}
   virtual Unit[] GetUnits(UnitTypes unitType) {...}
   virtual Unit[] GetAllUnits() {...}
   TreeNode[4/8] m_nodes; //Quad/Oct
   List<AirUnit> m_airUnits;
   List<LandUnit> m_landUnits;
   List<Unit> m_allUnits;
   //Vector3 m_centerPoint; //Things we might need?
   BoundingBox m_boundingBox; //Things we might need?
}
class Tree : TreeNode
{
   //If not obvious, the tree should contain only references, not copies.
   //One reference may be deposited into more than one bucket through recursion.
   //If the children should be tested (according to query), but return 0 items,
   //the parent should/would also return 0 items, so just return the empty bucket.
}

Tree usage:

void UseTree(Ray mouseRay)
{
   Tree tree = Tree();
   //populate tree

   tree.GetAllUnits(); 
   //GetXXX functions already provide logical sorting, how will you spatially sort?
   s_filter = mouseRay; //Presumably, a filter/query would be either set(static)
   tree.GetAirUnits();
   tree.GetAirUnits(mouseRay); //or passed as a parameter.
   //m_nodes should be private, but for explanation:
   tree.m_nodes[0].m_nodes[0].m_nodes[0].m_nodes[0].m_nodes[0].GetAirUnits();
}

Additional implementation details may be extrapolated from this example: