1
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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: enter image description here

\$\endgroup\$
  • \$\begingroup\$ Thanks for the reply. Are there any books that delve into tree structures and their game development applications somewhere inside? Game Programming Patterns mentions spatial partitioning in it's last chapter, though it doesn't really go into it in depth. However it does keep things simple enough that I can easily understand. The reason I ask is that I learn better when reading off of dead trees than on my screen. \$\endgroup\$ – Douglas Gaskell Apr 5 '15 at 22:50
  • \$\begingroup\$ Follow up on this, if I have a quad tree for lets say fighter units, and a quad tree for regular ships that fighters can fly over. How do I identify when a fighter is close to a ship? \$\endgroup\$ – Douglas Gaskell Apr 6 '15 at 18:56
  • \$\begingroup\$ You don't need multiple trees. A tree is just a node that contains nodes, each of which contains nodes, etc., etc. At the very bottom (leaf nodes) you just have more than one bucket/vector/list. \$\endgroup\$ – Jon Apr 7 '15 at 1:32
  • \$\begingroup\$ Added some rough code as example; the nodes encapsulate the logical divisions. When queried, each node returns the requested bucket from either itself, or one of it children. If the node currently being queried satisfies the filter conditions, it returns it's own bucket, otherwise it recursively queries its' children. After recursion, if the tree has not found a match, the tree always returns its' own bucket. \$\endgroup\$ – Jon Apr 7 '15 at 1:45
  • \$\begingroup\$ Using the new information, you would just query the node(s) that the ship is in for air units :) The granularity specified by the filter determines "how far away" returned units will be. A 5th level node containing the jet can arbitrarily limit the outward branching to level 4, thus returning objects within a small "radius" of that node. \$\endgroup\$ – Jon Apr 7 '15 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.