Hello everyone,

For my studies, I have to create a game with a team of novice programmers, like myself. One of the tasks we have to complete is improving collision performance to a point such that 2000 entities can be in the game, while it runs smoothly. At the moment I got it to run smoothly with 1000 entities, if i disable effects and other visual things. To do this, I divided the game into areas of around 400 pixels and let every game entitiy that needs to be checked for collisions calculate in which area(s) it is in right now, using the four corners of their respective collision boxes. Then, the code only checks collisions for entities in the same areas. The code I was using before, checks every pair of entities twice, because i'm using a double foreach loop.

Now, I tried implementing some changes, such that this won't happen, but now the effects of the collision is only seen on one of the entities or not at all.

This is the code for checking collisions, which resides in the BaseLevel class:

        protected void CheckCollision()
        {
            if (checkCollision)
            {
                HashSet<GameObject> checkedCollisions = new HashSet<GameObject>();
                foreach (HashSet<GameObject> objectList in areas.Values)
                {
                    HashSet<GameObject> ObjectList = new HashSet<GameObject>(objectList);
                    foreach (GameObject thing in ObjectList)
                    {
                        if (thing is GameEntity || thing is Item || thing is Rock)
                        {
                            checkedCollisions.Add(thing);
                            foreach (GameObject other in ObjectList)
                                if (!checkedCollisions.Contains(other) && other != thing)
                                    if (other is GameEntity || other is Item || other is Rock)
                                        thing.fireCollisionEvent(other);

                            foreach (Island island in islands)
                                if (island.isColliding(thing))
                                    thing.fireCollisionEvent(island);
                        }
                    }
                }
            }
        }

And this is the code for invoking the collision event, which resides in the GameObject class:

        internal void fireCollisionEvent(GameObject other)
        {
            if (other.ID != this.ID && this.getBoundingBox().Intersects(other.getBoundingBox()))
            {
                this.onCollisionDetected?.Invoke(this, other);
                other.onCollisionDetected?.Invoke(other, this);
            }
        }

In the previous version, every object invoked their own collision event, but then in that scenario, the collision would also need to be checked twice.

Should this code work? Or did I make a mistake that I overlooked?

Dexterdy said:
The code I was using before, checks every pair of entities twice, because i'm using a double foreach loop.

Which is necessary also because of this:

All 4 corners of the bounding box of the red object fall into the same cell, so it won't detect collision with the green object.
Only the green object detects the collision at all. Maybe this causes some logic error in your new attempt.

Dexterdy said:
HashSet checkedCollisions = new HashSet();

…..

if (!checkedCollisions.Contains(other)

It's maybe more expensive to build and resolve indirection on the hash map (cache misses, dynamic allocation), than it is to calculate the collision (simple bounding box checks).

One old trick is to store in each object a link to the last one it was checked against. This avoids double checks, but is not compatible with multi threading, if you plan to use this.

Another option to avoid double checks is using a method that guarantees each object finds all collisions of itself with any other. Then you can simple skip over potential pairs if current memory address (or index, id, etc.) is larger than that that of the other one.
This is quite easy: Each object has to check a neighborhood of 3x3 grid cells to ensure this. After this works, you can often optimize it down to just 2x2 (object is top left from cell center? Then check top left neighbors, but ignore bottom right ones. Depends on grid and object size ratio if this trick works.)

There are a lot of articles about spatial tree data structures, first and foremost the good old Quad Tree. This scales an area down to regions that contain regions and so on up to a defined grid size which then holds up all the objects that are located in such a region. It can be very effective if you don't change the size of your area that much and can for sure be made multithreading ready. A drawback however is that it isn't meant to work in more than 2 dimensions but you could write a data-cell object which easily checks the 3rd dimension as well. Then there is another one I like to use for some dynamic area positioning, especially if UI is involved, the R-Tree. It is more expensive if things change frequently because in opposite to the Quad Tree, it dynamically resizes the overall area if things change but the iteration time is slightly above the Quad Tree.

However, in physics engines, your objects are separated into trees of meshes, submeshes and vertices and collision is calculated along those trees. So you sheald definitely consider to use at least one of those spatial trees instead