Sign in to follow this  
Spa8nky

[C#] How can I avoid duplicate tests in this loop?

Recommended Posts

Spa8nky    230
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:
        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[i].objects.Count; ++ii)
                {
                    for (int iii = 0; iii < node.objects.Count; ++iii)
                    {
                        a = ancestorStack[i].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
                    }
                }
            }

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?

Share this post


Link to post
Share on other sites
Zahlman    1682
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?

Share this post


Link to post
Share on other sites
Spa8nky    230
The original code looks like the following:


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[i].objects.Count; ++ii)
//{
// for (int iii = ii; iii < node.objects.Count; ++iii)
for (int ii = 0; ii < ancestorStack[i].objects.Count; ++ii)
{
for (int iii = 0; iii < node.objects.Count; ++iii)
{
a = ancestorStack[i].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[i] != null)
{
TestAllCollisions(node.child[i]);
}
}

// 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[i].objects.Count; ++ii)
{
for (int iii = ii; iii < node.objects.Count; ++iii)
{
a = ancestorStack[i].objects[ii];
b = node.objects[iii];


[Edited by - Spa8nky on March 21, 2010 6:19:56 AM]

Share this post


Link to post
Share on other sites
Spa8nky    230
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:


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[i].objects.Count; ++ii)
{
iiiStart = ii < iiiEnd ? ii : 0;

for (int iii = iiiStart; iii < iiiEnd; ++iii)
{
a = ancestorStack[i].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[i] != null)
{
TestAllCollisions(node.child[i]);
}
}

// 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?

Share this post


Link to post
Share on other sites
Antheus    2409
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:
foreach (Object o in objects) {
test(o, qt);
o.markAsTested();
}
This may have some benefits if the cost of test is high.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this