ECS Survivors Part IV: Collisions

In the last instalment of this blog series, we created a rendering pipeline to allow for drawing multiple objects according to their priority, and we also created a GUI anchoring system allowing us to create dynamic and scalable GUI elements.

This time around, I wanted to work on something a bit more interesting: Collisions. Now this took much more time than anticipated. What started as a simple collision detection and resolution system quickly escalated to a full-blown scientific paper comparing five different collision systems. In this blog, I will give an overview of three methods implemented with "pure" ECS as well as share some of the results from the paper I wrote.

Before we dive into the collision systems, we need to have collision bodies! Let's create a new system in a new Gameplay module that will spawn enemies at the edge of the screen ever so often. For that, we create a Spawner component which contains the name of the prefab it will instantiate. Then the spawner system will determine first if the enemy will be spawned on the X axis or Y axis of the screen, and alternate for every enemy. Next, we determine how far along that axis the entity will be spawned, as which axis, Left or Right, or Top or Bottom. This gives us a nice semi-random distribution of enemy spawns around the screen, and just like that, we can now have hundreds of bodies to collide with.

// game.cpp
...
m_world.entity("enemy_spawner")
            .set<gameplay::Spawner>({"enemy"});
...
// gameplay/components.h
...
struct Spawner {
        std::string enemy_prefab_name;
    };
...
// gameplay/gameplay_module.cpp
...
bool spawn_on_x_axis = false;

void GameplayModule::register_systems(flecs::world world) {
        world.system<const Spawner, const core::GameSettings>("Spawn Enemies")
                .tick_source(m_spawner_tick)
                .term_at(1).singleton()
                .each([&,world](flecs::entity self, const Spawner &spawner, const core::GameSettings &settings) {
                    const flecs::entity e = world.lookup(spawner.enemy_prefab_name.c_str());

                    if (0 == e) return; // check if the prefab exists

                    float factor = rand() % 2; // 0 or 1
                    float randX = spawn_on_x_axis
                                      ? factor * settings.windowWidth // left or right of screen
                                      : rand() % settings.windowWidth; any pixel of the screen witdth
                    float randY = spawn_on_x_axis
                                      ? rand() % settings.windowHeight // any pixel of the screen height
                                      : factor * settings.windowHeight; // top or bottom of the screen

                    world.entity().is_a(e).child_of(self)
                            .set<core::Position2D>({randX, randY});

                    spawn_on_x_axis = !spawn_on_x_axis;
                });
...

If you have a keen eye, you have probably noticed that our player and enemies now have cute little textures! We will implement that a bit later. There are two reasons why we use textures instead of drawing colored circles. The first is we are making a game and it has to look somewhat good. Thanks to KenneyNL and their assets, we can do just that.  The second reason, and the most important one, is that Raylib does some optimisations to drawing textures rather than circles. From what I gather, textures are drawn in batches automatically while circles are drawn one by one, increasing the overhead from the CPU to GPU communication.

We have entities, a lot of them. Let's make them collide with each other. Let's first go over the basics for each collision method. We will separate the collision process into two phases, collision detection and resolution, where we first identify collisions, then fix them. Since our colliders are exclusively circles, it simplifies the detection process. Below is the general detection implementation. We first filter all the duplicate collision checks by comparing the entity IDS. Afterwards, we validate that the two colliders can collide with each other by performing a bitwise operator with the filters. For now, this feature is not useful, but I can anticipate that flying enemies later on wouldn't collide with walking enemies; in that case, filters would come in handy. Finally, we can check if the two entities overlap; if so, we identify the collision by some means.

if (self.id() >= other.id()) return;
if ((collider.collision_filter & other_collider.collision_type) == none) return;

float rad = collider.radius + other_collider.radius;
if (Vector2DistanceSqr(pos.value, other_pos.value) < rad * rad) {
	// add logic here
}

In the resolution phase, we iterate over the identified collisions and fix the overlaps.

Vector2 mypos = self.get<core::Position2D>()->value;
Vector2 otherPos = other.get<core::Position2D>()->value;
float combinedRadius = self.get<Collider>()->radius +
                                               other.get<Collider>()->radius;

// Find the distance and adjust to resolve the overlap
Vector2 direction = otherPos - mypos;
Vector2 moveDirection = Vector2Normalize(direction);
float overlap = combinedRadius - Vector2Length(direction);

// Move the entities apart by the amount of overlap
Vector2 move = moveDirection * overlap * 0.5f;

self.set<Velocity2D>({self.get<Velocity2D>()->value - move});
other.set<Velocity2D>({other.get<Velocity2D>()->value + move});

// Resolve by adjusting positions
self.set<core::Position2D>({mypos - move / 2.f}); // Move the current entity
other.set<core::Position2D>({otherPos + move / 2.f}); // Move the other entity

Often, the collision methods require an additional cleanup at the end of the frame so that the collisions don't carry over to the next one. This cleanup depends solely on the specific method.

Speaking of methods, let's first look at the first three, which are implemented with "pure" ECS and feature an O(n^2) time complexity. The first uses ECS relationships, the second creates new entities for each collision record, and the third stores the collisions in a central list inside a singleton component.

...
if (Vector2DistanceSqr(pos.value, other_pos.value) < rad * rad) {
    self.add<CollidedWith>(other);
    other.add<CollidedWith>(self);
}

The relationship method performs the worst out of the three methods. The main reason for this is the fragmentation of archetypes. A relationship is a subtype of component that is uniquely identifiable by the relationship and target it hold. So one entity might have (CollidedWith, a) (CollidedWith, b) and another (Collided, a) (CollidedWith, c), and Flecs will create three new archetypes (tables) for the entities  (CollidedWith, a) (CollidedWith, b)  (CollidedWith, c). The thing is that the tables will only contain a few entities. Now, imagine we have 1000 entities collided with each other. Flecs will create new archetypes for many of the relationships, leading to many small tables, resulting in fragmentation, and joining these tables together is where the performance costs the most.

...
if (Vector2DistanceSqr(pos.value, other_pos.value) < rad * rad) {
    world.entity().set<CollisionRecord>({self, other});
}

To avoid the heavy performance cost of relationship, I then considered creating a new entity representing a collision record. While this was about twice as good as the relationship implementation, I believe there is still some overhead associated to creating thousands of entities in a frame just to delete them right after. In fact, I imagine that Flecs would create a new table for the Collision records and delete it after the frame.

...
if (Vector2DistanceSqr(pos.value, other_pos.value) < rad * rad) {
    holder.records.push_back({self, other});
}

To reduce the overhead of creating and deleting thousands of entities every frame, I then thought of storing the collision records in a global list stored in a singleton component. This more than doubled the performance of collision detection and resolutions in the game, and is the method I eventually settled on. There's no way I need more than 4800 entities on screen at the same time, right? (Don't quote me on this)

There are two more methods which I won't elaborate upon in this blog: Spatial hashing and Box2d. A great way to speed up collision detection is to only query areas that are of interest. Spatial hashing can split up the space into small subsections, reducing the overall checks on average to O(n/m). Otherwise, Box2d is a popular physics library and is surprisingly easy to integrate with ECS. Box2d uses a dynamic AABB tree to partition the space, which averages queries of O(log(n)), quite an improvement from our current O(n^2). As mentioned previously, we don't even need that much performance, even Vampire Survivors can only spawn up to 300 entities at a time.

So it's settled, we will use the collision record list. However now another problem arises. Once we detect a collision, how do the colliding entities react to it? Say I have two entities with a Health component and a Damage component, I want them to deal damage to each other. Well, for now we will use relationship to notify entities they have collided with another. I don't like this that much because of the same issue I raised previously. However, we can reduce the performance cost by only adding the CollidedWith relationship on collision layers different to one another; An enemy colliding with an enemy will not trigger the collision reaction, but an enemy colliding with the player, or vice versa, will.

if (Vector2DistanceSqr(pos.value, other_pos.value) < rad * rad) {
    holder.records.push_back({self, other});
    if ((collider.collision_type & other_collider.collision_type) == none) {
        self.add<CollidedWith>(other);
        other.add<CollidedWith>(self);
    }
}

Like I said, I don't love this so much because it is quite slow, but it becomes so intuitive to perform the collision reactions that it outweighs the negatives. Let me show you.

world.system<core::Damage>("collision detected, deal damage to target")
    .with<physics::CollidedWith>(flecs::Wildcard)
    .write<TakeDamage>()
    .each([](flecs::iter &it, size_t i, core::Damage &dmg) {
        flecs::entity other = it.pair(1).second();
        if (other.has<TakeDamage>() || !other.has<core::Health>()) return;
            other.set<TakeDamage>({dmg.value});
});

world.system<core::Health, TakeDamage>("take damage")
    .each([](flecs::entity e, core::Health &health, TakeDamage &dmg) {
        health.value -= dmg.damage;
        if (health.value <= 0)
            e.destruct();
        e.remove<TakeDamage>();
});

Firstly, for all entities that have a CollidedWith relationship as well as a Damage component, we will add a TakeDamage component to the target of the relationship. In a second system, all entities with a TakeDamage and Health component will subtract the damage amount from their health.

Edit from the future: While trying to optimize the fragmentation from the method above I found that it is possible to force flecs to delete the empty tables in the world. Moreover, the Flecs devs are currently working on a feature that allows to force components to avoid fragmentation. The only problem is that this feature is far from complete and as it currently stands, is not able to accomplish what I want. For now, deleting the unused tables is the best option, maybe the relationship method becomes viable because of this, but I wouldn't count on it.  

 world.system("Remove empty tables to avoid fragmentation in collision (CHANGE TO DONTFRAGMENT WHEN FEATURE IS OUT)")
            .interval(5.0f)
            .kind(flecs::PostFrame)
            .run([world](flecs::iter& it) {
                ecs_delete_empty_tables_desc_t desc;
                desc.delete_generation = true;
                ecs_delete_empty_tables(world.c_ptr(), &desc);
                std::printf("Removing empty tables to avoid fragmentation in collision\n");
});

Finally since last time I made a few changes to the rendering as mentioned previously. I have replaced all of the instances of the Circle component and Color component and instead created a Renderable component and updated all of the rendering systems.

struct Renderable {
    Texture2D texture;
    Vector2 draw_offset;
    float rotation;
    float scale;
    Color tint;
};

world.system<const Renderable, const core::Position2D>("Draw Entities with Textures")
    .kind<Render>()
    .with<Visible>()
    .group_by<Priority>()
    .each([](const Renderable &renderable, const core::Position2D &position) {
        DrawTextureEx(
            renderable.texture,
            position.value - Vector2(renderable.texture.width, renderable.texture.height) - renderable.draw_offset * renderable.scale,
            renderable.rotation,
            renderable.scale,
            renderable.tint
        );
});

I haven't been too explicit about all of the new changes, so if you have some questions, I would direct you first to the git repo to fill in the blanks. The playable version on Itch.io has been updated with the latest collision features and now also can use game assets such as textures. You can play here.

Now I think we have a really solid foundation and we can start to implement actual game mechanics. For the next blog, you can expect just that. Afterwards, I would like to make the camera follow the player, if it isn't too long,g I will surely combine it with some gameplay elements. Once we have a few attacks and some different enemies, I would like to have a world, or at least a nice background to look at. That is it for now, though. I am super excited to get going on some actual gameplay. See you then!