# Hymn mini-devlog (Part 1)

This series is a long rant of me about how I made my first complete game and contains some nerdy technical details. Bare with me please.

**Game link:** [Hymn](https://labg.itch.io/hymn)
**Other parts:** [Part 2](https://hackmd.io/@4bNcOyqaSZ-TSF0OdM7r2Q/H18T_amB2)


## I. About Hymn

One hot summer morning, I made up my mind to participate in my very first game jam, which also named [My First Game Jam Summer 2022](https://itch.io/jam/my-first-game-jam-summer-2022). I teamed up with my senior from high school, and together, we set our goal to make a complete game. With our limited experience in game development, we joined forces with an aspiring composer and a professional artist from a different side of the earth (thanks to the jam's matching event). Filled with enthusiasm, we went on our journey to create a unique well-crafted game that would showcase all our talents.

## II. Planning

I took the lead in brainstorming the game mechanics. Initially, I planned a combination of platforming, puzzles, and action elements. The main character would possess a set of limited skills and powers that players could strategically use before each stage.


However, we soon realized that this idea wasn't practical. Our game designer, Hel, made a nice take. Generally, enemies and obstacles were not meant to be added for the sole purpose of challenging players' skills and abilities. Instead, players's skillsets come after enemies and obstacles design.

> *"Enemies and obstacles aren't meant to showcase players' skills. It's the other way around – players are given powers to survive and conquer those challenges." - **Hel, the game designer***

We decided to hand over the design work to Hel, while I focused on preparing for the early stages of development. So my coding adventure kinda started from there.

## III. Back-end preparation

### 1. Hello window

At that time I was not smart enough to reuse my old code, so I started over. For the graphics and sounds I used **SFML** - a fast C++ multimedia library. I started with the main game loop. It was something like this:

void App::run()
{
    // Maximize the window
    resizeView();

    sf::Time tick, dt;
    sf::Clock clock;
    tick = clock.restart();

    while(mWin.isOpen())
    {
        dt = clock.restart();
        tick += dt;
        // Update game world at constant interval: mTPF
        while(tick > mTPF)
        {
            input(mTPF);
            update(mTPF);
            tick -= mTPF;
        }
        render();
    }
}

The application would run and draw a black window, so nothing much to see. The next step would be adding some physics!

### 2. Hello ECS

#### a. Overview
Talking about the architecture of game development, many modern titles have moved beyond solely relying on the Object-Oriented Programming (OOP) approach when building games from scratch. OOP, if not designed properly, can lead to problems such as diamond inheritance, performance bottlenecks, inflexibility, and limited code reuse. Numerous articles delve into this topic in detail. Designing proper OOP system is nowhere near simple. That's why I opted for a safer alternative: **Entity-Component-System** (ECS).

If you're familiar with the Unity3D game engine, ECS should ring a bell. There are plenty of resources available, and if you're interested, I can suggest [this article](https://austinmorlan.com/posts/entity_component_system/) as a starting point. In a nutshell, an ECS-based architecture revolves around composition, where each game object is composed of various components. Adding or modifying a character type becomes as simple as adding or modifying relevant components. As a data-oriented approach, ECS significantly enhances performance by packing data into contiguous memory regions.

#### b. Sparse Set and Archetype
There are two primary methods for implementing an ECS system: **Sparse Set** and **Archetypes**.

* **Sparse Set:** In this method, each component type has an array that holds a fixed number of components. Systems effiiently update the component data. Let's say we have a `RenderSystem` that cares about `Transform` and `Texture` components. During each game loop, the system checks entities with these two component types (they may have additional components which does not matter), retrieves data from the arrays, and performs meaningful processing (for e.g rendering the texture based on transform information like position, rotation, scale, etc.). By touching only the arrays it requires, a system benefits from CPU caching, which leads to improved performance.
* **Archetype:** In contrast to the sparse set method, the archetype approach packs all components of entities with the same component set into a single location. Let's consider three entities: A with `health`, `texture`, and `transform` components; B and C with `texture` and `transform` components. In this case, we have two archetypes: `[health-texture-transform]={A}` and `[texture-transform]={B; C}`. The advantage of the archetype model lies in its efficiency when components don't undergo frequent removal/addition. Memory locality will lift performance dramatically.

I was noob at that time so I went the easy route and followed a tutorial on how to implement sparse set. Tp be honest, it was not until recently that I knew about archetype model.

After boring back-end works, I could create a box this way:

ECS ecs;
Entity box = ecs.createEntity();
ecs.addComponent<Transform>(box, Transform{
    vector2(100.f, 500.f), // position
    0.f,                   // rotation
    1.f                    // scale
});
ecs.addComponent<Texture>(box, Texture{
    &myTexture // pass the address of the texture
});

The syntax is nice and later on the custom engine performed well so I am quite proud of this part.

This is me having some fun with ECS's processing power, there were 5000 colorful boxes falling from the sky, notice the FPS gain when there were less boxes on the screen (my specs were AMD Ryzen 5600H, NVIDIA RTX 3060 Mobile):


### 3. Hello Physics

The next part was to implement collision detection and resolution. From a player's perspective, collision is pretty straight forwards: the character touches obstacles and stops/bounces back. However, getting the collision right is a little bit tricky. Since our game only featured at most a few moving objects and others were static, I used swept AABB algorithm.

#### a. Swept Axis-Aligned Bounding Box algorithm (Swept AABB)

You may ask why did I use swept AABB instead of vanilla AABB. Well, the answer is AABB simply does not deal with speedy objects. It is easy for an object moving very fast (for eg. a bullet) to penetrate a wall and fool the naive algorithm. That's when our AABB+ algorithm comes into play. The main idea is that whenever an object move, it will cast a displacement vector and we will use that vector to calculate if it did touch any obstacle. This way it is nearly impossible for objects to penetrate each other even though they have really high speed.


Note that swept AABB is however not a golden hammer. Firstly, it only deals with static v.s dynamic collision. So for example when your scene has something like hundreds moving objects (that collide with each other, of course) this algorithm is not a good idea. Secondly, swept AABB only alters the velocity of objects, which means overlap can happen due to floating points inaccuracy. To prevent this one can introduce some sort of impulse or just use pure AABB afterwards.

First thing first, I defined the collision component:

struct Collision
{
    // Is the object static?
    bool fixed; 
    // Collision bounding box
    sf::FloatRect box;
};

Okay, how swept AABB actually works?

There are normally 2 stages when a collision happens:
* Collision detection: In this stage, we are tasked to determine if two objects are colliding and collision information.
* In this specific context, we assume that only dynamic and static objects collide, i.e. the player and every other platform tiles.
* Time of collision (TOC) is a float between 0.0 and 1.0. Imagine that in every frame, we advance the world in a constant amount of time. If 2 objects collide at the start of the frame, TOC will be 0.0, if they collide at the middle of the frame, TOC will be 0.5, and so on.
* Ideally, we will compute both TOC and the normal of collision surface.
* Collision resolve: Once we have got data of the collision, we can resolve them appropriately. For example, the colliding object can slide on the surface of the static object. We can achieve that by projecting the later part of the displacement vector on the surface.

The implementation is pretty cliche, the hardest part is to find the intersection of the displacement vector and the obstacle:

// Find the collision point of a ray and a rect
// root: begin position of the ray
// path: direction of the ray
// target: the rect
// time: collision point's position to the ray relatively 
// (between 0 and 1)
// normal: direction of the normal. Since we use swept AABB, 
// it's either parallel or perpendicular to the x-axis
bool vectorAndRect(sf::Vector2f root, sf::Vector2f path,
    const sf::FloatRect& target, float& time, sf::Vector2f& normal)
{
    // Calculate the time for the extended ray to intersect with
    // 4 lines which form the rectangle
    sf::Vector2f near, far;
    
    // Deal with special cases where the ray is parallel to x or y-axis
    if (path.x == 0.f)
    {
        near.x = -std::numeric_limits<float>::infinity();
        far.x = std::numeric_limits<float>::infinity();
    }
    else
    {
        near.x = (target.left - root.x) / path.x;
        far.x = (target.left + target.width - root.x) / path.x;

        if (near.x > far.x)
            std::swap(near.x, far.x);
    }

    if (path.y == 0.f)
    {
        near.y = -std::numeric_limits<float>::infinity();
        far.y = std::numeric_limits<float>::infinity();
    }
    else
    {
        near.y = (target.top - root.y) / path.y;
        far.y = (target.top + target.height - root.y) / path.y;

        if (near.y > far.y)
            std::swap(near.y, far.y);
    }

    // Calculate default cases
    if (far.x <= 0.f && far.y <= 0.f)
        return false;
    if (near.x >= 1.f && near.y >= 1.f)
        return false;
    if (near.x >= far.y || near.y >= far.x)
        return false;

    // Whichever side is closer is the first side to touch the ray
    if (near.x >= near.y)
    {
        time = near.x;
        if (path.x < 0)
            normal = RIGHT;
        else
            normal = LEFT;
    }
    else
    {
        time = near.y;
        if (path.y < 0)
            normal = DOWN;
        else
            normal = UP;
    }
    
    return true;
}

#### Are we done?

Yey, we are done with the physics! Well... not so fast. Now a new problem is introduced. If you like game development, you must be familiar with this:

// 1
velocity += acceleration * deltaTime;
// 2
position += velocity * deltaTime;
// 3

The question is: where do we alter velocity to make objects not slam into each other? Is it 1, 2, or 3?

* First position is just off because then we alter the velocity again which introduces potential collisions.
* Third position is also out of our interest because the whole point of altering the velocity is to get the correct position at the end of the frame.

So of course we should alter the velocity between velocity and position update. But the process was not what you expected.

Remember that this game was based on ECS. So initially, I had a `RigidBody` system updating velocity and position of entities. Its update function was like this:

void RigidSystem::update(sf::Time dt)
{
    // Process every entity that match this system
    for(auto& e : m_entities)
    {
        // Get the component from ECS
        Transform& tf = m_ecs->get_component<Transform>(e);
        Rigid& rg = m_ecs->get_component<Rigid>(e);
    
        // Update data
        rg.vel += rg.acc * dt.asSeconds();
        tf.pos += rg.vel * dt.asSeconds();
    }
}

As you can see, the `RigidSystem` was not aware of the collisions, yet it is responsible for updating position right after velocity. So we need a way to insert the collision resolution part inside those two parts. It is hard, because good ECS design does not involve system's communications. What I did was a bit janky. I chose to separate those two updating lines into two different systems. Instead of only one system responsible for updating physics of our engine, we will have three.

// RigidSystem is responsible for updating velocity only
void RigidSystem::update(sf::Time dt)
{
    for(auto& e : m_entities)
    {
        // Get the component from ECS
        Rigid& rg = m_ecs->get_component<Rigid>(e);
    
        // Update data
        rg.vel += rg.acc * dt.asSeconds();
    }
}

// CollisionSystem is responsible for resolving the collisions
void CollisionSystem::update(sf::Time dt)
{
    for(auto& mover : m_entities)
    for(auto& target : m_entities)
        if(mover != target)
        {
            // Get collision components
            Collision& colm = m_ecs->get_component<Collision>(mover);
            Collision& colt = m_ecs->get_component<Collision>(target);
            
            // Only process if mover is dynamic and target is static
            if(colm.fixed == true || colt.fixed == false)
                continue;

            // Get mover's rigidbody component
            Rigid& rg1 = m_ecs->get_component<Rigid>(mover);

            float time = 1.0f;
            sf::Vector2f normal = sf::Vector2f();
            // The swept AABB function
            if(collideEntity_entity(colm.box, rg1, colt.box, dt, normal, time))
            {
                // Project the later part of displacement 
                // vector perpendicularly to normal
                resolveAABB(rg1, normal, time);
            }
        }
}

// Position system is only responsible for updating the final position
void PositionSystem::update(sf::Time dt)
{
    for(auto& e : m_entities)    
    {
        Transform& tf = m_ecs->get_component<Transform>(e);
        Rigid& rg = m_ecs->get_component<Rigid>(e);
        
    	tf.box.left += rg.vel.x * dt.asSeconds();
    	tf.box.top += rg.vel.y * dt.asSeconds();
    }
}

Then, in our world's update function, we can do this:

void World::update(sf::Time dt)
{
    // Other stuffs...
    
    m_rigidBody->update(dt);
    m_collisionSolver->update(dt);
    m_positioner->update(dt);

    // Other stuffs...
}

This way we can inject the collision solving part between natural velocity update and position update. That also means we are done with the barebone collision.

A liltle bit testing:


ANDDDD that's it for now. I will write about interesting parts later too.