Sign in to follow this  
Spa8nky

[C#] Automatically assigning UIDs to classes that inherit an interface.

Recommended Posts

Spa8nky    230
If I define my interface as follows:
    public interface IQuadtree_Object
    {
        RigidBody2D Body { get; }           // Body used in physics simulation (Quadtree will reallocate node this frame if the body is awake)
        int ID { get; }                     // Unique ID

        void Draw();
        void Update(float dt);
    }

and I can assign a unique ID to an object like so:
    static class QuadtreeUID
    {
        static int uID = 0;

        public static int GetUID()
        {
            return ++uID;
        }
    }

Is there any way I can automatically assign a unique ID to any class that inherits from IQuadtree_Object without having to type the following: int iD = QuadtreeUID.GetUID(); for each and every class that iherits from IQuadtree_Object? Thanks

Share this post


Link to post
Share on other sites
jpetrie    13104
Put that functionality in a (possibly abstract) base class and inherit from that.

You could also employ one of several AOP or reflection-based techniques to help automate the process, but those will be extremely heavyweight.

Why is your object assigning it's own ID anyhow? It feels like that should be something the quad tree itself does. That way you wouldn't need the QuadTreeID class at all.

You could even support the idea of an object being in multiple quad trees by putting the ID in the tree and not the object. For example, if the quad tree had a list of all the objects in it, the ID is implicitly the index in the list, or something.

Share this post


Link to post
Share on other sites
Spa8nky    230
Quote:

Why is your object assigning it's own ID anyhow? class at all.


I need to prevent the quadtree from testing collision pairs twice.

Quote:

It feels like that should be something the quad tree itself does. That way you wouldn't need the QuadTreeID


How could I assign a unique ID to each object and still only test pairs belonging to relevant nodes?

Share this post


Link to post
Share on other sites
jpetrie    13104
Quote:

How could I assign a unique ID to each object and still only test pairs belonging to relevant nodes?

Based on the code you've provided so far, having the tree generate the object ID when the object is added to the tree is exactly the same as having some external code assign that ID via the QuadTreeUID class. What are you confused about, or is there some aspect of this problem you haven't shown yet?

You could do:

// this is a method of the quad tree:
int nextId = 0;
AddToTree( IQuadtree_Object o ) {
o = nextId;
nextId++;
}

if you were okay with making the ID field settable (I'm terribly fond of this approach, but it would work). You could also create a dictionary mapping from the object to the ID. Depending on how you've implemented the tree itself there may be other, better places to store the ID.

The only real difference -- which I don't think should matter if the rest of your system is sanely designed -- is that the IDs for a given quad tree will generally always be contiguous in this implementation; in your original plan, if you have more than one quad tree you're more likely to get holes in the spread of IDs if you generate IDs for both trees simultaneously.

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
Original post by Spa8nky

I need to prevent the quadtree from testing collision pairs twice.


if (a.Body == b.Body) // same pair

Share this post


Link to post
Share on other sites
Spa8nky    230
Quote:

if (a.Body == b.Body) // same pair


That will stop identical objects from being tested but not different objects from being tested if they have been already.

For example:

A = Wall
B = Player

A vs B should not be tested if B vs A has already been tested.

EDIT:

Quote:

You could do:

// this is a method of the quad tree:
int nextId = 0;
AddToTree( IQuadtree_Object o ) {
o = nextId;
nextId++;
}


Would this make things difficult when reinserting objects into the quadtree? If an object moves then its iD will be incremented and if 1000s of objects are moving each frame then the IDs will soon overwrite themselves.

I'm probably not thinking about this the right way though.

Share this post


Link to post
Share on other sites
jpetrie    13104
Quote:

That will stop identical objects from being tested but not different objects from being tested if they have been already.

For example:

A = Wall
B = Player

A vs B should not be tested if B vs A has already been tested.

How do unique IDs help in any way? Do you just store pairs of IDs that have been tested, and then skip that pair if you see it again during the same phase?

Are you sure you cannot structure the algorithm so that it is not possible to see a pair more than once?

Even if not, you can store pairs of objects since just as easily as pairs of integers -- the objects are, I assume, reference types and so storing the references in a pair is likely just as cheap as storing two IDs. Then you won't need this ID system at all.

Quote:

Would this make things difficult when reinserting objects into the quadtree? If an object moves then its iD will be incremented and if 1000s of objects are moving each frame then the IDs will soon overwrite themselves.

I'm probably not thinking about this the right way though.

Why are you reinserting the objects? And how? You can probably prevent them from getting new IDs if that's really necessary. It's going to depend on how you need to use the ID and how the tree class is structured and used, though.

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
Original post by Spa8nky

That will stop identical objects from being tested but not different objects from being tested if they have been already.

IDs don't solve that problem either.

for (RigidBody o : objects) {
test(qt, o);
o.markAsTested();
}

...
if (a.wasTested() || b.wasTested() || a.Body == b.Body) // don't test


When o is tested, it will report all possible collisions between o and everything else. The reverse holds true as well, so o will never need to be tested again.

Quote:
If an object moves then its iD will be incremented and if 1000s of objects are moving each frame then the IDs will soon overwrite themselves.


A pointer to object is a unique ID. There is no need for another ID.

Share this post


Link to post
Share on other sites
Spa8nky    230
Quote:

Why are you reinserting the objects?


If an object changes size, rotates or moves, it might have to be reassigned to a new node as it could no longer be contained inside its current node.

Quote:

And how?



private void ReinsertObject(IQuadtree_Object o)
{
#if DEBUG
objectsUpdated++;
#endif
// Remove the object from the current node
RemoveObject(quadtree_Root, o);

// Reinsert the object along with its updated parameters that affect node placement (position, size, etc.)
InsertObject(quadtree_Root, o);
}




Is this not the norm for quadtrees, or am I making this process too complicated?

Quote:

When o is tested, it will report all possible collisions between o and everything else. The reverse holds true as well, so o will never need to be tested again.


What if o is overlapping 2 objects and both overlaps need to be resolved?

If I flag o as tested then o will only be tested against one object?

EDIT:

Quote:

When o is tested, it will report all possible collisions between o and everything else.


How can I test against all other objects in the quadtree for one object when I need to traverse the parent nodes in a logical order?

Eg:

If the object is in a child node then it must be tested against parent/ancestor nodes. It makes no sense to me to test each object individually when I can test all objects stored at the current node depth against parent/ancestors.

Wouldn't your method require traversing through all ancestors for every object in the tree?

I'm lost on your logic, could you help me out please?

[Edited by - Spa8nky on March 31, 2010 11:32:46 AM]

Share this post


Link to post
Share on other sites
Spa8nky    230
Ok guys, I think I've finally solved this once and for all!


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 = 0;
int iiiEnd = node.objects.Count;

for (int ii = 0; ii < ancestorStack[i].objects.Count; ++ii)
{
// If the ancestor node is the same as the current node
// I.E. I'm testing all the objects in the same node against each other
if (ancestorStack[i] == node)
{
// Adjust the index so that the same objects pairs are not tested twice
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;
}



I had to change the index for when the current node being tested is the same as the ancestor node so the same two pairs aren't tested twice. Otherwise the index increments as normal.

If you can see any problems please shout, otherwise I'm a happy bunny.

Thanks again.

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