Proper Collision handling with lots of objects.

1

I am working on a Shmup and wanted to know if this was a good way to handle lots of enemies and bullets. I have all the player and his bullets in entityGroup1 and the enemies and their bullets in entityGroup2 and then I call CollidesWith. If a collision is found the entities Collided function is called. When I want to remove an entity I set it’s variable remove = true. In another file I have the enemies and bullets in their own list to draw them.

Gameplay

public class EntityGroup
    {
        public List<Entity> entities = new List<Entity>();

        public void Update(float dt)
        {
            for (int i = 0; i < entities.Count; i++)
            {
                entities[i].Update(dt);
            }

            for (int i = entities.Count - 1; i >= 0; i--)
            {
                if (entities[i].remove)
                {
                    entities.RemoveAt(i);
                }
            }
        }

        public void CollidesWith(EntityGroup entityGroup)
        {
            for (int i = entities.Count - 1; i >= 0; i--)
            {
                Entity entity1 = entities[i];
                if (entity1.remove) continue;

                for (int j = entityGroup.entities.Count - 1; j >= 0; j--)
                {
                    Entity entity2 = entityGroup.entities[j];
                    if (entity2.remove) continue;

                    if (RectCollision(entity1, entity2))
                    {
                        entity1.Collided(entity2);
                        entity2.Collided(entity1);
                    }
                }
            }
        }

        public void Add(Entity entity)
        {
            entity.group = this;
            entities.Add(entity);
        }

        public bool RectCollision(Entity a, Entity b)
        {
            float a_left = a.position.X;
            float a_top = a.position.Y;
            float a_right = a.position.X + a.width;
            float a_bottom = a.position.Y + a.height;

            float b_left = b.position.X;
            float b_top = b.position.Y;
            float b_right = b.position.X + b.width;
            float b_bottom = b.position.Y + b.height;

            if (a_top > b_bottom) return false;
            if (b_top > a_bottom) return false;
            if (a_left > b_right) return false;
            if (b_left > a_right) return false;

            return true;
        }
    }
2

Unless you need those entities present in whatever Entity.Update(dt) is for future entities (doesn’t appear so since in your CollidesWith method you skip if their remove value is set anyway), you can update and remove them in the same loop.

I.e.

for (int i = 0; i < entities.Count; i++)
{
	entities[i].Update(dt);
	if (entities[i].remove)
	{
		entities.RemoveAt(i);
		i -= 1;
	}
}

Or better yet, just have Update return a boolean if it should be removed or not and forgo the remove variable entirely.

At any rate, since we only see code for EntityGroup and not Entity, hard to say.

1 Like
3

This should work fine. Code could perhaps be simplified a little, as TheKelsam noted.

But since you did specify “lots”, it’s worth noting that this is an O(n*m) implementation. Performance is proportional to the number of bullets multiplied by the number of enemies.

It might be overkill for your game, but there are much better options: this video does an excellent job explaining the theory behind spatial hashing, (even if the code is javascript and thus not entirely translatable to monogame).

Again, if your game has the same scale as the gif you shared, this is 100% overkill even on mobile hardware. Still interesting and fun to mess around with, though. And necessary if you end up expanding into something with a bit more open-world or bullet-hell influences.

2 Likes
4

Yea I just wanted to know if I was doing something completely wrong thanks for the help.