Nuck Physics Engine

features

• slotmap storage
• broadphase and narrowphase collision detection
• AABB: axis aligned bounding box
• separating axis theorem
• spatial partitioning (spatial hashing)
• linear dynamics
• different object types
• sleep optimization
• collision detection with callback API

This is a basic introduction on how to write a physics engine. I personally love using ECS for writing games, so this physics engine will be written in a way that makes it compatible with basically any game making architecture out there.

Slotmap

Motivation

While making a physics engine, one of the big issues will be storage and access of physical objects. A naive solution to this problem would be to just make an array and store the pointers to the elements in that array. But, here are the big issues with that:

• lets say you delete the object from array with index 4, all the objects after that index will have their index shifted by one in order to accomodate for the missing element in the array, so no if you have some code that points to element with index 10 in the array, it would now be pointing to the element that previously had the index of 11, and in order to fix that, you have to write code to manually update the referring index of your code or instead of erasing, just mark the deleted element as null, but that would also cause performance issues as your project grows
• you have to write additional code to ensure the consistency of creationg/deletion of objects which can result in performance sacrifices
• this method is extremely prone to dangling pointers and memory leaks as you will be giving direct pointer of objects from the array to your code
• this approach will not work with ECS as if you want to write a physics component, it is not possible unless the memebers of that component are all safe to copy and move around freely

In order to fix all of these issues, we will utilize the same approach as done by Box2D.

We will use something called a "slotmap", you can think of it as a more efficient version of a vector from cpp

Explanation

To put it simply, we will still have a vector say “objects”, it will contain all the objects but we will have one 2 other vectors alongside it, “free_indexes” and “generations” both of type uint32_t.

• “objects”: contains all the actual physical objects, this vector will only be updated with two actions, replacing the object in an index, and adding an object, we won’t do anything else, we will not be deleting anything from this
• “generations”: tracks the generation of object in a specific index, basically this ensures proper deletion of objects, lets say we have an empty world with no objects, when you create an object, it will get index_0 and generation_0, so basically, we will just put that object at index 0 in the “objects” vector and add 0 to the same index 0 in the “generations” vector, now say we delete that object, what will happen is that we will just take the the object’s generation and index, make sure the object matches the generation value in that index in “generations” vector, then add 1 to that index in “generations” vector, and then just push that index of the object(in our case 0) to the “free_indexes” vector because that index is now free, we will not be doing anything to do the objects vector.
• “free_indexes”: tracks all the indexes that are free in the “objects” vector, after deleting an object in the previous step, we will have now 0 added to the free_indexes vector, now if we try to create an object, instead of just pushing that object to the “objects” vector, what it will do is get the last index value from “free_indexes”, pop the “free_indexes” vector from the back, now the index we will have is the index from where an object was deleted previously(the previous object is still there but not in our record anymore, the index of that object is basically free), and then we will just place the new object at that index, we will get the generation value of that index from “generation” vector and set the generation for that object equal to that value.

In order to properly access the objects, we will utilize “ObjectID”s. They are basically plain old data types (POD) that just contain the index and generation of an object, and using those two values alone, we can get any object from our world without having to store the pointer to that object. Because they are PODs, we can easily treat them as components in an ECS architecture.

So, when we create an object, instead of getting that object, we will get the ObjectID which we can use to get that object, and while deleting an object, we will just need to provide the ObjectID.

Implementation

Now that we have a somewhat intuitive understanding of how this system works, we can move onto writing code for it.

We will start by defining our basic data structure. Currently, the Object is just an empty struct but we will populate it later on as we progress.

struct Object {};
 
struct ObjectID {
    uint32_t index;
    uint32_t generation;
};
 
class World {
  private:
    std::vector<Object> m_objects;
    std::vector<uint32_t> m_generations;
    std::vector<uint32_t> m_free_indexes;
  public:
    auto create_object() -> ObjectID;
    auto get_object(ObjectID object_id) -> Object *;
    auto destroy_object(ObjectID object_id) -> void;
}

As you can see we have added the required vectors and methods to our World class.

create_object

The create_object method works as follows: currently it does not take any arguments, but when we add more properties to the Object, it will accept those properties,

• we innitialize an curr_index and curr_gen variables
• check if there are any free indexes available
• if NO
  • we set the curr_index equal to the total number of elements in the “m_objects” vector, this is because we will pushing a new element onto the “objects” vector, the index of current last element in the vector will be m_objects.size() - 1 so after pushing an element, the index of that element will be equal to the size of the vector when that element was not added to the vector
  • we push the new object into the “m_objects” vector
  • since its a new element into the objects vector, it will belong to the 0th generation and hence we set the curr_gen equal to zero, then we push curr_gen into the generations vector, the index of this curr_gen in the generations vector and the index of newly added object in the objects vector would automatically be equal
• if YES
  • get the last value of free index from the free_indexes vector and pop that element, and then set the curr_index equal to that free index
  • set the object at the curr_index in the objects vector equal to the new object, so basically we are replacing the older object with the newer one
  • now since we had a free index, the generation of that index in the generations vector would have already been updated, so we just need to get the current generation of that index from the generations vector and set curr_gen equal to that generation
• now we just return the “ObjectID” with corresponding index and generation

auto create_object(std::string input) -> ObjectID {
    uint32_t curr_index;
    uint32_t curr_gen;
 
    if (m_free_indexes.empty()) {
        curr_index = m_objects.size();
        m_objects.push_back(Object{ .input = input });
        curr_gen = 0;
        m_generations.push_back(curr_gen);
    } else {
        curr_index = m_free_indexes.back();
        m_free_indexes.pop_back();
        m_objects[curr_index] = Object{ .input = input };
        curr_gen = m_generations[curr_index];
    }
    return ObjectID{ .index = curr_index, .generation = curr_gen };
};

get_object

The get_object method works as follows:

• it takes in the ObjectD as an input
• checks if the index of that id is less than the size of objects vector and generation in generations vector at that index matches the generation of the ID, this ensure that the input ID is valid
• if the id is valid, then we just return the pointer to the object at that index in the objects vector
• if the id is not valid, we just return nullptr

auto get_object(ObjectID object_id) -> Object * {
    if (object_id.index < m_objects.size()
        && m_generations[object_id.index] == object_id.generation) {
        return &m_objects[object_id.index];
    }
    return nullptr;
};

destroy_object

the destroy_object works as follows:

• it takes in the ObjectID as input
• checks whether the id is still valid the same way we did in the create_object method
• if the id is valid, then we just increment the generation at that index in the generations vector by 1 and push that index onto the free_indexes vector to indicate that the object at that index has been deleted from the world

auto destroy_object(ObjectID object_id) -> void {
    if (object_id.index < m_objects.size()
        && m_generations[object_id.index] == object_id.generation) {
        m_generations[object_id.index] += 1;
        m_free_indexes.push_back(object_id.index);
    }
};

Iterator

In the following guide, we will be adding functionality that applies to all of the objects a given world, in order to make that simpler and easier to do, we will implement a custom iterator for the World class. It can be done by adding the following code to the World class:

NOTE: I will not be explaining this section because it is strictly C++ specfic and you can figure this out from other C++ sources

class World {
  // .. private section
  public:
    struct Iterator {
      private:
        World *m_world;
        size_t m_index;
 
        void advance_to_next_valid() {
            while (m_index < m_world->m_objects.size()
                   && std::ranges::find(m_world->m_free_indexes, m_index)
                       != m_world->m_free_indexes.end()) {
                m_index = m_index + 1;
            }
        }
 
      public:
        Iterator(World *world, size_t start) : m_world(world), m_index(start) {
            advance_to_next_valid();
        }
 
        bool operator!=(const Iterator &other) const {
            return m_index != other.m_index;
        }
        auto operator++() -> Iterator & {
            ++m_index;
            advance_to_next_valid();
            return *this;
        }
 
        auto operator*() -> std::pair<ObjectID, Object &> {
            return { ObjectID{ static_cast<uint32_t>(m_index), m_world->m_generations[m_index] },
                     m_world->m_objects[m_index] };
        }
    };
 
    auto begin() -> Iterator {
        return Iterator(this, 0);
    }
 
    auto end() -> Iterator {
        return Iterator(this, m_objects.size());
    }
    // ... rest of the methods
};

Linear Dynamics

It is all about calculating the new position of objects based on their velocity and acceleration.

We can do this by utilizing the Newton’s equations of motion and Newton’s laws of motion. Further instead of using acceleration dirctory we will represent it in Force and Mass (using Newton’s second law $F=ma$) in order to simplify the calculations and give use more control.

$v=u+\frac{F}{m}t$ $\Delta x=ut+\frac{1}{2}\frac{F}{m}{t}^2$ $v^2-u^2=2\frac{F}{m}\Delta x$

On the base of it, an object just needs to store three properties: Velocity, Mass, and Net Force. There are two ways to represent net force, either as a list or as a single 2d/3d vector.
In school you used the list method (summing up all the forcing acting on an object), but in computation, it would get extremely annoying to deal with as you grow your project.

So, we will be using the single 2d/3d vector method. We can calculate all the forces acting on an object into a single net vector and then create that vector after each frame update, this allows the user to apply a force and then automatically clear it.

struct Object {
    Maths::Vector2 position;
    Maths::Vector2 velocity;
    Maths:Vector2 force;
    float mass;
};

NOTE: Here the position member points to the top-left corner of any object, this is because it is kind of an industry standard for 2D games. Also this project assumes that your project follows the stadard graphical plane in games, i.e x coordinate increases in the right direction, and y coordinate increases in the down direction.

We will be utilizing struct instead of a class because we don’t need to add functionality to the object itself, the world will handle it.

Now that we have setup our object, it is time to create our world. Our world will be responsible for storing all the objects(using a list) and stepping(updating) the states of all those stored objects. A basic implementaion of our world would look like this:

class World {
  private:
    std::vector<Object *> m_objects; // list of objects
 
  public:
    Vector2 gravity; // (optional for the user) gravity vector for simulating gravity
    auto add_object(Object *object) -> void; // method for adding objects to the list
    auto remove_object(Object *object) -> void; // method for removing objects from the list
    auto step(float delta_time) -> void; // method for stepping the world state
};

The step function accepts a “delta_time” variable which is a fundamental part of working with video game physics or basically any visual simulation. Delta time basically allows us to make sure the functionality of our physics engine stays consistent across all values of FPS. It ensures that our physics simulation does not break on very high or very low FPS.

Different Object Types

There are total 3 types of basic object types in physics engines:

• dynamic → they are affected by forces and can be moved by other objects (your player perhaps)
• static → they are not affected by forces and cannot be moved (stationary tiles or platforms)
• kinematic → they are affected by forces and cannoto be moved (moving platforms)

Sleep Optimization

When objects are not moving, they need to be put to sleep, so that we don’t apply motion calculations to them even though they are sleeping.

It works in a very simple way, if an object’s velocity is below the “Threshold velocity”, then we add delta time to the “sleep_timer”, it keeps happening untill the objects’ velocity stays below the threshold, if at any point the object’s sleep_timer exceedes the “Threshold time” then we consider the object to be asleep.

Then at any time we want a sleeping object to start moving again, we just reset the timer and set “is_sleeping” to false. (This can be at times when the movement of a physical object is triggered)

struct Object {
    // ...
    bool is_sleeping = false;
    float sleep_timer = 0.0F;
};

void World::step(float delta_time) {
    for (ObjectID object_id : *this) {
        Object* object = this->get_object(object_id);
        // skip a null pointer or a sleeping object
        if (object == nullptr || object->is_sleeping == true) {
            continue;
        }
 
        // .....
 
        // if an objects's velocity is below the sleep threshold, then we put the object to sleep
        if (pow(Maths::Vector2Length(object->velocity), 2) < SLEEP_LINEAR_THRESHOLD) {
            object->sleep_timer += delta_time;
            if (object->sleep_timer > SLEEP_TIME_THRESHOLD) {
                object->is_sleeping = true;
                object->velocity = Maths::Vector2(0, 0); // Ensure no drift
            }
        } else {
            object->sleep_timer = 0.0f;
        }
    }
};

On whichever event we want an object to start moving after being stationary, we would just add the following lines of code:

object->is_sleeping = false;
object->sleep_timer = 0.0f;

Broadhphase and Narrowphase

firstly we do broadphase, then narrowphase

• Broadphase → narrowing the objects down to a smaller number, like using spatial partitioning(spatial hashing in our case) to eliminate objects that are far away from a certain object of interest
• Narrowphase → precice collision detection to check if two objects are colliding or not

AABB

This is just a simple data structure that stores the total “reach” or “span” of a physical object, it is extremely useful for optimizing collision detection code. You can easily implement AABB using following code:

struct AABB {
    Maths::Vector2 max;
    Maths::Vector2 min;
};
AABB compute_AABB(const Object& object) {
    AABB box;
    box.max = object.position;
    box.min = Maths::Vector2{ object.position.x + object.size.x,
                              object.position.y + object.size.y };
    return box;
}
bool AABB_overlap(const AABB& a, const AABB& b) {
    return (
        a.min.x < b.max.x && a.max.x > b.min.x && a.min.y < b.max.y
        && a.max.y > b.min.y
    );
}

Spatial Partitioning (Broadphase)

A better way to iterate over objects in the world than just running simple loops.
What we do is that we convert the whole 2d plane into a grid of fixed sized cells, so in this example each of the grid cells would have a 128x128 pixel region. Most commonly used in 2d games is 64x64 or 128x128. We can the size by using the following code:

constexpr int CELL_SIZE = 128;

We will firstly have to convert the normal coordinates of objects into grid cell coordinates:

struct CellPosition {
    int x, y;
    bool operator==(const CellPosition& other) const {
        return x == other.x && y == other.y;
    }
};
CellPosition get_cell_position(float x, float y);

What we will be doing is that each of this cell will point to a vector containing all the object_ids of objects in that cell itself, we will do this by utilizing a hashmap. We need a hasher to allow CellPosition to become a key in a hashmap:

struct CellHasher {
    std::size_t operator()(const CellPosition& cell) const {
        return std::hash<int>()(cell.x) ^ (std::hash<int>()(cell.y) << 1);
    }
};

Now we just have to add the following code to the world class:

class World {
  private:
    // ...
    std::unordered_map<CellPosition, std::vector<ObjectID>, CellHasher> m_spatial_grid;
    void update_spatial_grid();
    std::vector<ObjectID> query_region(const AABB& bounds);
    // ....
};

The m_spatial_grid represents the grid cell coordinate system. The update_spatial_grid is a function that updates all the grid cells according the positions of various objects after all the objects have completed their motion for a particular frame. The query_region function takes in an input of AABB of a specific object or region, and it them calculates all the objects which are in the same grid cells as that particular AABB, so basically it ouputs all the objects that might collide with that provided AABB so we can only test those specific objects instead of just going over all the objects in the world.
This makes our collision detection system extremely performant as it reduces the number of checks we have to perform, !exponentially!

void World::update_spatial_grid() {
    m_spatial_grid.clear();
 
    for (ObjectID object_id : *this) {
        Object* object = get_object(object_id);
        if (object == nullptr) {
            continue;
        }
 
        AABB box = compute_AABB(*object);
        int minX = static_cast<int>(floor(box.min.x / CELL_SIZE));
        int maxX = static_cast<int>(floor(box.max.x / CELL_SIZE));
        int minY = static_cast<int>(floor(box.min.y / CELL_SIZE));
        int maxY = static_cast<int>(floor(box.max.y / CELL_SIZE));
 
        for (int x = minX; x <= maxX; ++x) {
            for (int y = minY; y <= maxY; ++y) {
                m_spatial_grid[{ x, y }].push_back(object_id);
            }
        }
    }
}

std::vector<ObjectID> World::query_region(const AABB& bounds) {
    std::vector<ObjectID> result;
    std::unordered_set<uint64_t> seen;
 
    int minX = static_cast<int>(floor(bounds.min.x / CELL_SIZE));
    int maxX = static_cast<int>(floor(bounds.max.x / CELL_SIZE));
    int minY = static_cast<int>(floor(bounds.min.y / CELL_SIZE));
    int maxY = static_cast<int>(floor(bounds.max.y / CELL_SIZE));
 
    for (int x = minX; x <= maxX; ++x) {
        for (int y = minY; y <= maxY; ++y) {
            CellPosition key{ x, y };
            auto it = m_spatial_grid.find(key);
            if (it != m_spatial_grid.end()) {
                for (ObjectID id : it->second) {
                    uint64_t combined_unique_id = ((uint64_t)id.index << 32) | id.generation;
                    if (seen.insert(combined_unique_id).second) { // this code only runs if the current object with the unique id is not in the seen vector
                        result.push_back(id);
                    }
                }
            }
        }
    }
 
    return result;
}

Collision Detection and Callbacks/API

Currently we have only setup AABB based collision detection but this is pretty much enough for a simple 2D game

What we do is that we have a collision structure that (currently) stores the objects which have collided, so whenever a collision happens, what we do is that we create the collision structure and add it to the collisions vector present on the physical world.

struct Collision {
    ObjectID a;
    ObjectID b;
};

After that, we just need the following functions:

• get_collisions → provides the user with a constant reference to the m_collisions vector so the user can iterate over all the collisions that have happened
• is_colliding → check if an object is colliding with literally any other object
• are_colliding → check if two objects are colliding with each other
• get_collisions_for → get a vector of objects that are colliding with a specific object

class World {
  private:
    // ...
    std::vector<Collision> m_collisions;
    // ...
  public:
    // ...
    const std::vector<Collision>& get_collisions() const;
    bool is_colliding(ObjectID id) const;
    bool are_colliding(ObjectID a, ObjectID b) const;
    std::vector<Collision> get_collisions_for(ObjectID id) const;
    // ...
};

We can easily implement them using following:

const std::vector<Collision>& World::get_collisions() const {
    return m_collisions;
}
bool World::is_colliding(ObjectID id) const {
    for (const auto& col : m_collisions) {
        if (col.a == id || col.b == id)
            return true;
    }
    return false;
}
bool World::are_colliding(ObjectID a, ObjectID b) const {
    for (const auto& col : m_collisions) {
        if ((col.a == a && col.b == b) || (col.a == b && col.b == a))
            return true;
    }
    return false;
}
std::vector<Collision> World::get_collisions_for(ObjectID id) const {
    std::vector<Collision> result;
    for (const auto& col : m_collisions) {
        if (col.a == id || col.b == id)
            result.push_back(col);
    }
    return result;
}

After that we just handle the collision detection in the World::step() function after updating the spatial grid

NOTE: you can see how the spatial hashing system (grid cells method) helps us optimize the number of objects that we are checking against

void World::step(float delta_time) {
    this->update_spatial_grid();
 
    m_collisions.clear();
    std::unordered_set<uint64_t> checked_pairs;
    for (ObjectID a_id : *this) {
        Object* a = get_object(a_id);
        if (a == nullptr) {
            continue;
        }
 
        AABB a_box = compute_AABB(*a);
        std::vector<ObjectID> nearby_objects = query_region(a_box);
        for (ObjectID b_id : nearby_objects) {
            if (a_id == b_id) {
                continue;
            }
            Object* b = get_object(b_id);
            if (!b)
                continue;
 
            // avoid duplicate pairs
            uint64_t smaller = std::min(a_id.index, b_id.index);
            uint64_t larger = std::max(a_id.index, b_id.index);
            uint64_t pair_key = (smaller << 32) | larger;
            if (!checked_pairs.insert(pair_key).second) {
                continue;
            }
 
            AABB b_box = compute_AABB(*b);
            if (AABB_overlap(a_box, b_box)) {
                m_collisions.push_back(Collision{ a_id, b_id });
            }
        }
    }
};