XNA how to write a good collision algorithm?

Question

I'm currently working on a new game in XNA and I'm just setting basic stuff up like sprites/animations, input, game objects etc.

Meanwhile I'm trying to think of a good way to detect collisions for all the game objects, but I can't really think of a fast algorithm, which limits the game to very few objects. This is what I did in my last project that was a school assignment

    public static void UpdateCollisions()
{
    //Empty the list
    AllCollisions.Clear();

    //Find all intersections between collision rectangles in the game
    for (int a = 0; a < AllGameObjectsWithCollision.Count; a++)
    {
        GameObject obja = AllGameObjectsWithCollision[a];
        for (int b = a; b < AllGameObjectsWithCollision.Count; b++)
        {
            GameObject objb = AllGameObjectsWithCollision[b];

            if (obja.Mask != null & objb.Mask!= null && obja != objb && !Exclude(new Collision(obja, objb)))
            {
                if (obja.Mask.CollisionRectangle.Intersects(objb.Mask.CollisionRectangle))
                    AllCollisions.Add(new Collision(obja, objb));
            }
        }
    }
}

So it checks for all collisions between all objects, but excludes adding collisions I found unnecessary.

To then inform my objects that they are colliding, I used a virtual method OnCollision that I called like this

//Look for collisions for this entity and if a collision is found, call the OnCollision method in this entity
        var entityCol = FindCollision(entity);

        if (entityCol != null)
        {
            if (entityCol.Other == entity)
                entityCol = new Collision(entity, entityCol.Obj1);
            entity.OnCollision(entityCol);
        }

Collision FindCollision(GameObject obj)
{
    Collision collision = AllCollisions.Find(delegate (Collision col) { return (GameObject)col.Obj1 == obj || (GameObject)col.Other == obj; });
    return collision;
}

This made my game run slower fairly quickly when the amount of gameobjects increased.

The first thing that pop ups in my head is to create new threads, would that be a good idea & how would I do that in a good way?

I have studied algorithms a little bit so I know basic concepts and how ordo works.

I'm fairly new to c# and programming overall, so don't go too advanced without explaining it. I learn quick though.

Nico Schertler · Accepted Answer · 2017-06-18 17:00:31Z

There are quite a few things you can do:

The nested for loops produce a quadratic running time, which grows rather quickly as the number of objects increase. Instead, you could use some acceleration data structures (e.g. grids, kd-trees, BVHs). These allow you to reduce the intersection checks to only the entities that can potentially intersect.

If you can order your entities, you can reduce the collision checks by half by just checking entity pairs, where the second is "greater" (with respect to the order) than the first. I.e. you do not need to check b-a if you already checked a-b.

This part can be potentially slow:

!Exclude(new Collision(obja, objb)))

If Collision is a class, then this will always allocate new memory on the heap and recycle it eventually. So it might be better to make Collision a struct (if it is not already) or pass obja and objb directly to Exclude(). This also applies to your other uses of Collision. You haven't shown the implementation of Exclude() but if it is a simple linear search, this can be improved (e.g. if you search linearly in a list that contains an entry for every object, you already have a cubic running time for just the loops).

The implementation of FindCollision() is most likely a linear search (depending on what AllCollisions is) and it can get quite slow. Why are you storing the collisions anyway? Couldn't you just call OnCollision() as soon as you found the collision? A different data structure (e.g. a hash map) would be more appropriate if you want to check if a collision is associated with a specific entity efficiently.

Finally, parallelizing things is surely a viable option. However, this is somewhat involved and I would advice to focus on the basics first. If done correctly, you can reduce your cubic running time to n log n or even n.

Collectives™ on Stack Overflow

XNA how to write a good collision algorithm?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related