   [C#] Proximity detection and quadtrees.
  I'm currently working on some simple AI for an enemy which is based on proximity detection.The enemy has 5 surrounding circles that it uses to detect what is in the environment.To speed up the detection process I can use a quadtree and only detect objects in the same node, parent nodes and child nodes.I'm currently trying to figure out how best to implement the detection process for the circles.Should I insert all 5 circles into the quadtree separately and return all possible colliding objects once per frame?  The objects can then be tested separately with the ai responding accordingly.ORShould I test all objects in the quadtree, including the 5 circles, at the same time?  This would only require one test method per frame.  However, this would require me to determine if the current quadtree pairwise test includes one of the 5 circles and which of the objects the 5 circles belonged to.  The objects would then need to be passed to a separate list which would have to be dealt with when the ai is next updated.Which of the above two would you be inclined to use, or perhaps someone could suggest a more elegant solution?   
  The algorithm for option 1 is a follows:   public List<IQuadtree_Object> InsertShape(Shape2D shape)   {  // Create list to store all nodes affected by this shape  List<Node_Quadtree> nodes = new List<Node_Quadtree>(100);    InsertShape(quadtree_Root, shape, ref nodes);  // Get all child nodes for the node in which the shape finally resides  GetChildNodes(nodes[nodes.Count - 1], ref nodes);  // Create a list of possible colliding objects from nodes affected  List<IQuadtree_Object> objects = new List<IQuadtree_Object>();    for (int i = 0; i < nodes.Count; ++i)  { objects.AddRange(nodes.objects);  }  return objects;   }   private void GetChildNodes(Node_Quadtree node, ref List<Node_Quadtree> nodes)   {  for (int i = 0; i < 4; ++i)  { if (node.child != null) {nodes.Add(node.child);GetChildNodes(node.child, ref nodes); }  }   }   private void InsertShape(Node_Quadtree node, Shape2D o, ref List<Node_Quadtree> nodes)   {  float delta;  int index = 0;  Vector2 position = o.Centroid;// Shape's centre  float radius = o.Radius; // Shape's radius (minimum bounding circle of all vertices)  bool straddle = false;  // Compute the quadrant number [0..3] in which the quadtree_Object sphere centre is located  // If straddling any of the dividing x or y planes, flag as straddled  delta = position.X - node.centre.X;  if (Math.Abs(delta) <= radius)  { straddle = true;  }  else if (delta > 0.0f)  { index |= (1 << 0); // YX bitmask  }  delta = position.Y - node.centre.Y;  if (Math.Abs(delta) <= radius)  { straddle = true;  }  else if (delta > 0.0f)  { index |= (1 << 1); // YX bitmask  }  if (!straddle && node.child[index] != null)  { // Fully contained in existing child node.  Insert in that subtree (based on index) nodes.Add(node); InsertShape(node.child[index], o, ref nodes);  }  else  { // Straddling, or no child node to descend into nodes.Add(node);  }   }This process would be called for each of the 5 circles, once per frame.   The advantage being that it returns all objects to be handled in the ai routine and not in the quadtree routine like option 2 would entail.Opinions and thoughts are welcome.[Edited by - Spa8nky on May 17, 2010 6:32:23 AM];  Hmm I'm trying to understand the two methods. Is this correct?Method 1: Begin with an empty quad tree. Then, for each circle insert it into the quad tree and immediately collide it with other objects in the tree node.Method 2:  Begin with an empty quad tree. Then, for each circle insert it into the quad tree. Then, for each node in the quad tree collide all circles within that node.If that is the case option 2 would likely result in many fewer unnecessary collision checks since at the beginning the quad tree nodes are quite large. Not sure interpret your the 2 methods correctly though...   ;  Are the circles concentric? If so, you should just put the largest circle into the quadtree, get what it collides with, and then iterate over that subset with the smaller circles. No sense going through the entire tree for each circle.If the circles aren't concentric, one possible solution would be to only do one of the five circles on each frame. That means there's up to a four frame delay before the creature would notice that one of its circles has been hit, but this is unlikely to be noticeable to the player in practice, and it'd be considerably less effort on a per-frame basis.   ;Quote:Original post by DerakonAre the circles concentric? If so, you should just put the largest circle into the quadtree, get what it collides with, and then iterate over that subset with the smaller circles. No sense going through the entire tree for each circle.Good thinking.  The circles are concentric and I will update the routine to only check for one large circle per frame.Thank you for helping. :)Quote:Original post by EJHMethod 1: Begin with an empty quad tree. Then, for each circle insert it into the quad tree and immediately collide it with other objects in the tree node.Method 2: Begin with an empty quad tree. Then, for each circle insert it into the quad tree. Then, for each node in the quad tree collide all circles within that node.The fundamental difference between the 2 methods:Method1: Doesn't insert the object directly into the quadtree but instead returns all the quadtree nodes which contain objects that could collide with the object.Method2: Inserts the object directly into the quadtree where it is updated along with all other objects.  All possible colliding objects are determined in one pairwise test routine.  The reaction to a collision would then be called from the collision resolution method.I'm still undecided.  Method1 works great for objects such as decals which only require the surrounding geometry once to be created and do not need to reside in a bounding volume hierarchy.  Method2 means that all objects regardless of type can be pairwise tested in one routine.;  My quadtrees have an explicit method for "get me everything that intersects this rectangle". They come in handy fairly often. Using one here would take the same amount of computing time as would be required for inserting the circle into the tree and running it through standard collision (modulo overhead from extra function calls), but the design is a lot simpler. Until you know you need to optimize this, go with the simpler design.   ;  Good point, well made.  I shall stick with option 1 for A.I. then! :)   