public void TestAllCollisions()
{
#if DEBUG
collisionTests = 0;
#endif
depth = 0;
TestAllCollisions(quadtree_Root);
}
private void TestAllCollisions(Node_Quadtree node)
{
depth = 0;
// Check collision between all objects on this level and all acestor objects
// The current level is included as its own ancestor so all necessary pairwise tests are done
ancestorStack[depth] = node;
++depth;
for (int i = 0; i < depth; ++i)
{
IQuadtree_Object a;
IQuadtree_Object b;
for (int ii = 0; ii < ancestorStack.objects.Count; ++ii)
{
for (int iii = 0; iii < node.objects.Count; ++iii)
{
a = ancestorStack.objects[ii];
b = node.objects[iii];
bool bothSame = a == b;
bool bothStatic = a.Body.Type == RigidBody2D_Type.Static && b.Body.Type == RigidBody2D_Type.Static;
// If the two objects are the same object or any of the above conditions are true
if (bothSame || bothStatic)
// Do NOT use the "break" keyword as other objects in the list will not be tested!
continue;
}
// Collision detection
Detection2D.DetectCollision(a, b);
#if DEBUG
collisionTests++;
#endif
}
}
}
[C#] How can I avoid duplicate tests in this loop?
Author
I have a loop that is resursive and will go through all the nodes in the quadtree and test their contained objects against each other:
The problem is that if I only have two objects (a and b) then a vs b will be tested as well as b vs a.
How can I avoid testing the same two objects twice?
Test all actual ancestors against the current depth (BTW, I really don't think you mean to set depth = 0 at the beginning of the function; and where is your recursive call?), then test the current depth against itself with two nested loops. Set the inner loop to start just after the outer loop's current value. Only add the current node to the stack after you've done all that testing.
If a node at the current depth can also be in the ancestor stack (i.e. before the commented part where you add the current node to the stack), you're probably SOL.
By the way, why aren't you using foreach-style looping?
If a node at the current depth can also be in the ancestor stack (i.e. before the commented part where you add the current node to the stack), you're probably SOL.
By the way, why aren't you using foreach-style looping?
Author
The original code looks like the following:
I deleted some important lines in the process of cleaning it up to put a less cluttered version on the boards, sorry.
EDIT: There's some kind of forum bug that will not let me post the complete code?! It cut off the recursive part when there was line between that part and the rest of the code.
Is this not what I have done?
Does this mean that this looping method will not work?
EDIT:
This will prevent pairs from being tested twice, but I would miss testing all objects:
[Edited by - Spa8nky on March 21, 2010 6:19:56 AM]
public void TestAllCollisions() {#if DEBUG collisionTests = 0;#endif depth = 0; TestAllCollisions(quadtree_Root); } private void TestAllCollisions(Node_Quadtree node) { // Check collision between all objects on this level and all acestor objects // The current level is included as its own ancestor so all necessary pairwise tests are done ancestorStack[depth++] = node; for (int i = 0; i < depth; ++i) { IQuadtree_Object a; IQuadtree_Object b; //for (int ii = 0; ii < ancestorStack.objects.Count; ++ii) //{ // for (int iii = ii; iii < node.objects.Count; ++iii) for (int ii = 0; ii < ancestorStack.objects.Count; ++ii) { for (int iii = 0; iii < node.objects.Count; ++iii) { a = ancestorStack.objects[ii]; b = node.objects[iii]; // Test conditions // Using "is" keyword is faster than using either enums or GetType() = typeof() bool bothSame = a == b; bool bothBullet = a is Entity2D_Bullet && b is Entity2D_Bullet; bool bothEnemy = a is Entity2D_Enemy && b is Entity2D_Enemy; bool bothStatic = a.Body.Type == RigidBody2D_Type.Static && b.Body.Type == RigidBody2D_Type.Static; // If the two objects are the same object or any of the above conditions are true if (bothSame || bothStatic || bothBullet || bothEnemy) { // Don't perform any collision test with these two objects // Do NOT use the "break" keyword as other objects in the list will not be tested! continue; } // Now perform the collision test between A and B in some manner Detection2D.DetectCollision(a, b); } } } // Recursively visit all existing children for (int i = 0; i < 4; ++i) { if (node.child != null) { TestAllCollisions(node.child); } } // Remove current node from ancestor stack before returning depth--; }I deleted some important lines in the process of cleaning it up to put a less cluttered version on the boards, sorry.
EDIT: There's some kind of forum bug that will not let me post the complete code?! It cut off the recursive part when there was line between that part and the rest of the code.
Quote:
Set the inner loop to start just after the outer loop's current value. Only add the current node to the stack after you've done all that testing.
Is this not what I have done?
Quote:
If a node at the current depth can also be in the ancestor stack (i.e. before the commented part where you add the current node to the stack), you're probably SOL.
Does this mean that this looping method will not work?
EDIT:
This will prevent pairs from being tested twice, but I would miss testing all objects:
for (int ii = 0; ii < ancestorStack.objects.Count; ++ii) { for (int iii = ii; iii < node.objects.Count; ++iii) { a = ancestorStack.objects[ii]; b = node.objects[iii];[Edited by - Spa8nky on March 21, 2010 6:19:56 AM]
Author
My code has now reached a stage where it should be working. I've made sure no object pairs are tested twice and each child node is tested against itself and its ancestors:
With a depth of 3 however, the quadtree is still missing collision tests with some objects that straddle.
To me it seems that all nodes are tested correctly using the method above, can anyone see any obvious discrepancies?
public void TestAllCollisions() {#if DEBUG collisionTests = 0;#endif depth = 0; TestAllCollisions(quadtree_Root); } private void TestAllCollisions(Node_Quadtree node) { // Check collision between all objects on this level and all ancestor objects // The current level is included as its own ancestor so all necessary pairwise tests are done ancestorStack[depth++] = node; for (int i = 0; i < depth; ++i) { IQuadtree_Object a; IQuadtree_Object b; int iiiStart; int iiiEnd = node.objects.Count; for (int ii = 0; ii < ancestorStack.objects.Count; ++ii) { iiiStart = ii < iiiEnd ? ii : 0; for (int iii = iiiStart; iii < iiiEnd; ++iii) { a = ancestorStack.objects[ii]; b = node.objects[iii]; // Test conditions // Using "is" keyword is faster than using either enums or GetType() = typeof() bool bothSame = a == b; bool bothBullet = a is Entity2D_Bullet && b is Entity2D_Bullet; bool bothEnemy = a is Entity2D_Enemy && b is Entity2D_Enemy; bool bothStatic = a.Body.Type == RigidBody2D_Type.Static && b.Body.Type == RigidBody2D_Type.Static; // If the two objects are the same object or any of the above conditions are true if (bothSame || bothStatic || bothBullet || bothEnemy) { // Don't perform any collision test with these two objects // Do NOT use the "break" keyword as other objects in the list will not be tested! continue; } // Now perform the collision test between A and B in some manner Detection2D.DetectCollision(a, b);#if DEBUG collisionTests++;#endif } } } // Recursively visit all existing children for (int i = 0; i < 4; ++i) { if (node.child != null) { TestAllCollisions(node.child); } } // Remove current node from ancestor stack before returning --depth; }With a depth of 3 however, the quadtree is still missing collision tests with some objects that straddle.
To me it seems that all nodes are tested correctly using the method above, can anyone see any obvious discrepancies?
This is a n-body problem. As long as you go with quad tree, the extra cost of double collision test should be negligible.
QT: n log n
Naive: n^2
QuadTree reduces number of tests so much that saving half of total comparisons is negligible vs. logarithmic reduction.
Assign each object a strongly ordered ID (unique ints). For collision between a and b, report the one with smaller ID first. So (a,b) and (b,a) always fall under a. (a,a) can be trivially ignored.
Or, after testing each object, remove it from quad tree. Since if a collides with b, then b collides with a. So if object didn't collide with anything when it was tested, subsequent queries will not collide with anything either.
This method might be slower, since modifying quad trees comes with high constant factor cost, and likely isn't worth it. Especially if objects are not points.
Or, after object is tested, mark it as such, and ignore it subsequent queries. Something like:
QT: n log n
Naive: n^2
QuadTree reduces number of tests so much that saving half of total comparisons is negligible vs. logarithmic reduction.
Assign each object a strongly ordered ID (unique ints). For collision between a and b, report the one with smaller ID first. So (a,b) and (b,a) always fall under a. (a,a) can be trivially ignored.
Or, after testing each object, remove it from quad tree. Since if a collides with b, then b collides with a. So if object didn't collide with anything when it was tested, subsequent queries will not collide with anything either.
This method might be slower, since modifying quad trees comes with high constant factor cost, and likely isn't worth it. Especially if objects are not points.
Or, after object is tested, mark it as such, and ignore it subsequent queries. Something like:
foreach (Object o in objects) { test(o, qt); o.markAsTested();}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
