# Game Math/C++/Calculating The Future

Sara Gerretsen

https://git.saragerretsen.nl/Sara/kernmodule-cpp

# Game Style

Speed racer (with full 2d motion).

# Math

Other than all the basic binary vector operations, my `Vecf` 2d vector class implements the following:

Only thing particularly of-note is the SDL_FPoint conversion operator. Used to simplify interaction with the `SDL_Render` API. Most of this was copied from my [previous 2d vector implementation]([cutes/vmath.h at main - cutes - Sara's Gitea](https://git.saragerretsen.nl/Sara/cutes/src/branch/main/vmath.h), with some minor modifications and updates as well as translating it to be C++ rather than C.

```cpp
struct Vecf {
    float x{0.f}, y{0.f};

    operator SDL_FPoint();
    //! squared distance between two vectors as points. Use for comparing distances efficiently.
    static float sqr_distance(Vecf const &from, Vecf const &to);
    //! distance between two vectors as points
    static float distance(Vecf const &from, Vecf const &to);
    //! compare within an epsilon
    static bool equals_approximate(Vecf const &lhs, Vecf const &rhs);
    //! scalar member-wise multiplication product
    static float dot(Vecf const &lhs, Vecf const &rhs);
    //! unsigned angle difference in radians between lhs and rhs
    static float angle_between(Vecf const &lhs, Vecf const &rhs);
    //! interpolate linearly between two points
    static Vecf lerp(Vecf const &from, Vecf const &to, float t);
    //! move towards a point by a set unit distance
    static Vecf move_towards(Vecf const &from, Vecf const &to, float delta);
    //! calculate the outgoing velocity of an object reflecting against a surface
    static Vecf reflect(Vecf const &in, Vecf const &normal);
    //! magnitude (a.k.a length or absolute) of this vector
    float magnitude() const;
    //! square of the magnitude, use for comparing lengths of vectors efficiently
    float sqr_magnitude() const;
    //! vector perpendicular to this one
    Vecf perpendicular() const;
    //! rotate vector by t Radians
    Vecf rotated(float t) const;
    //! vector pointing in the same direction with a length of 1. Or, vector divided by it's magnitude
    Vecf normalized() const;
    //! reverse scale of vector
    Vecf reciprocal() const;
    //! returns true if either the x or y element is NaN
    bool is_nan() const;

    Vecf clamp_magnitude(float max) const;
    //! scale vector member-wise
    void scale(float x, float y);
    //! scale vector member-wise
    void scale(Vecf const &factors);
    Vecf scaled(Vecf const &factor) const;

    static Vecf const RIGHT;
    static Vecf const UP;
    static Vecf const ONE;
    static Vecf const POSITIVE_INFINITY;
    static Vecf const ZERO;
};

```

# General Structure:

The core systems of the project make extensive use of C++ smart pointers for memory management. There are no *owning* raw pointers. Though many raw pointers are used to access smart-pointer-managed memory. Basically everything in the `core/` directory will be part of the `ce` namespace, short for `CanvasEngine`.

I decided to try writing purely C++20 as standardised. (Hence no `#pragma`, oops)

## CanvasEngine

Named after the (now-discontinued) "engine" used for teaching C# basics at GLU.

Represents the main application state and provides an interface to the engine subsystems.

```cpp
void CanvasEngine::run(std::unique_ptr<Level> &level) {
    if(!stay_open)
        return;
    assert(CanvasEngine::singleton_instance == nullptr && "Engine singleton instance already assigned, starting another instance is invalid");
    // register as singleton
    CanvasEngine::singleton_instance = this;
    // take ownership of and instantiate level
    this->level = std::move(level);
    if(!this->level->is_instantiated())
        this->level->instantiate();
    // start tracking time
    this->frame_start_time = this->last_frame_start_time = SDL_GetTicks64();
    SDL_LogInfo(SDL_LOG_CATEGORY_APPLICATION, "CANVAS: starting");
    // main application loop
    while(stay_open) {
        // track frame time
        this->frame_start_time = SDL_GetTicks64();
        this->delta_time = double(this->frame_start_time - this->last_frame_start_time) / 1000.f;
        // process events
        this->process_events();
        // update application implementation
        if(this->delta_time > this->target_delta_time) {
            this->tick(this->delta_time);
            this->last_frame_start_time = this->frame_start_time;
            this->draw(render);
            SDL_RenderPresent(this->render);
        } else {
            SDL_Delay(2);
        }
        if(this->next_level) {
            this->level = std::move(this->next_level);
            this->level->instantiate();
        }
    }
    assert(CanvasEngine::singleton_instance == this && "Engine singleton instance changed while game was running");
    CanvasEngine::singleton_instance = nullptr;
}

```



## Hierarchy

The world is made up of instances of, or inheriting from, `Node`. `Node` defines the interface required for gameplay functionality and rendering, without implementing it.

The majority of actual functionality in `Node` is in the `propagate_` functions. As they're responsible for pushing notifications like _tick and _added to child objects.

```cpp
class Node {
public:
friend class Level;
typedef std::unique_ptr<Node> OwnedPtr;
typedef std::vector<std::pair<std::string, Node::OwnedPtr>> ChildrenVector;
private:
    Node *parent{nullptr};
    bool inside_tree{false};
    bool request_deletion{false};
    bool has_ticked{false};
    std::string name{};
    ChildrenVector children{};
    bool visible{true};
    bool tick{true};
    ce::Level *level{nullptr};
public:
    Signal<> destroyed{}; //!< Signal invoked by the destructor
    Signal<Node*> child_removed{}; //!< Signal invoked when a child is removed.
    Signal<Node*> child_added{}; //!< Signal invoked when a child is added.
public:
    Node(std::string name);
    virtual ~Node();
public:
    virtual void _added() {} //!< called the moment after the object is added as a child to another node
    virtual void _first_tick() {} //!< called the first frame this object is active
    virtual void _tick(double delta_time [[maybe_unused]]) {} //!< called every frame
    virtual void _removed() {} //!< called the moment before the object is removed as a child to another node
    virtual void _draw(SDL_Renderer *render [[maybe_unused]], ce::Transform const &view_transform [[maybe_unused]]) {}
    virtual void _draw_ui(SDL_Renderer *render [[maybe_unused]], ce::Transform const &ui_transform [[maybe_unused]]) {}
    virtual void _update_transform() {}
public:
    template <class TNode> TNode *get_child(std::string const &name); //!< get a non-owning pointer to a child
    template <class TNode, typename... Args> TNode *create_child(Args... cargs);
    void add_child(Node::OwnedPtr &child); //!< add a child, the caller must own the pointer
    void set_parent(Node *new_parent);
    Node *get_parent() const; //!< get the parent.
    std::string const &get_name() const; //!< get the name of this node.
    void set_name(std::string const &name); //!< change the name of this node.
    void flag_for_deletion(); //!< request deletion at the end of the frame.
    bool requests_deletion() const; //!< returns whether or not the node is flagged for deletion.
    void set_visible(bool value); //!< enable or disable _draw for this object and all children
    bool is_visible() const;
    void set_tick(bool value);
    bool is_ticking() const;
    ce::Level *get_level() const;
    bool is_inside_tree() const;
    ChildrenVector &get_children();
private:
    void set_level(ce::Level *level);
    void set_is_inside_tree(bool value);
    std::optional<Node::OwnedPtr> remove_child(Node *child); //!< remove a child, the caller now owns the pointer
    void propagate_tick(double delta_time);
    void propagate_post_tick();
    void propagate_added();
    void propagate_removed();
    void propagate_draw(SDL_Renderer *render, ce::Transform const &view_transform);
    void propagate_draw_ui(SDL_Renderer *renderer, ce::Transform const &ui_transform);
    bool rename_child(std::string const &old_name, std::string const &new_name);
};
```

 `Node2D` provides transformation and transform hierarchy through `Transform`. `Transform` is a simple struct with a `position`, `rotation` and `scale`. As SDL_render (the media library i used instead of SFML) doesn't support using matrix transformations.

core/node2d.cpp:

```cpp
void Node2D::_update_transform() {
    if(this->parent_node2d != nullptr)
        this->global_transform = this->transform * this->parent_node2d->get_global_transform();
    else
        this->global_transform = this->transform;
    for(ChildrenVector::value_type &pair : this->get_children())
        pair.second->_update_transform();
}

void Node2D::set_transform(Transform const &transform) {
    this->transform = transform;
    this->_update_transform();
}

...

void Node2D::set_global_transform(Transform transform) {
    this->global_transform = transform;
    if(this->parent_node2d) {
        Transform parent = this->parent_node2d->get_global_transform();
        transform.position -= parent.position.rotated(-parent.rotation);
        transform.scale_by(parent.scale.reciprocal());
        assert(transform.scale.x != 0.f || transform.scale.y != 0.f);
        transform.rotation -= parent.rotation;
    }
    this->transform = transform;
    this->_update_transform();
}

```

## Collision Subsystem

Accessed through the `CollisionWorld` object, available on the `CanvasEngine` singleton through `ce::CanvasEngine::get_singleton()->get_collision_world()`. The collision world is a simple list of all currently active `CollidableNodes`. It loops over every pair, every tick. And notifies them if they overlapped. `RigidBody` inherits from `CollidableNode` and implements very rudimentary collision solving. As well as velocity, forces, and drag.

core/colldiable_node.hpp

```cpp
class CollidableNode : public Node2D {
    CollisionMask mask{~0x0u /* all layers by default */};
    CollisionMask layers{0x1u /* only the first layer is enabled by default */};
public:
    Signal<CollisionShape*, CollidableNode*, CollisionShape*> overlap_enter{};
public:
    CollidableNode(std::string const &name, CollisionMask layers, CollisionMask mask);
    void add_overlap(CollisionShape *shape, CollisionShape *other);

    void set_mask(CollisionMask mask);
    CollisionMask get_mask() const;
    void set_layers(CollisionMask layers);
    CollisionMask get_layers() const;
};
```

`CollidableNode`s on their own cannot collide with anything. They need one or more shapes as their children to function. `CollisionShape`s are also nodes that will automatically register as part of a parent `CollidableNode`. `CollisionShape` is just a circle with a transform. Of the transform, only position applies, as rotation doesn't matter, and scaling would require implementing actually complicated overlap and escape vector detection.

```cpp
class CollisionShape : public Node2D {
    CollidableNode *owner{nullptr};
    float radius;
    CollisionWorld &world;
    bool is_registered{false};
    float bounce{0.5f};
public:
    CollisionShape(std::string const &name, float radius, float bounce);

    virtual void _added() override;
    virtual void _removed() override;
    virtual void _draw(SDL_Renderer *render, ce::Transform const &view_transform) override;

    // return true if either of these objects could receive a notification for colliding with the other
    static bool can_collide(CollisionShape const *lhs, CollisionShape const *rhs);
    static bool shapes_overlap(CollisionShape const *lhs, CollisionShape const *rhs);

    // get the motion lhs will have to make to fully disconnect from rhs.
    static Vecf get_escape_vector(CollisionShape const *lhs, CollisionShape const *rhs);


    CollidableNode *get_owner() const;
    float get_radius() const;
    CollisionMask get_layers() const;
    CollisionMask get_mask() const;
    float get_bounce() const;
private:
    void register_with_world();
    void deregister_with_world();
};

```

core/rigidbody.cpp:

```cpp
void RigidBody::_tick(double delta) {
    Vecf next_velocity{
        this->linear_velocity * (1.f - drag * delta)
        + this->acceleration * delta
        + this->impulse
    };
    this->set_global_transform(this->get_global_transform()
        .translated((next_velocity + this->linear_velocity) * 0.5f * delta + this->motion)
    );
    this->linear_velocity = next_velocity;
    this->motion = this->acceleration = this->impulse = Vecf::ZERO;
}

void RigidBody::on_collision(CollisionShape *shape, CollidableNode *other, CollisionShape *other_shape) {
    Transform const shape_transform{shape->get_global_transform()};
    Transform const other_transform{other_shape->get_global_transform()};
    Vecf escape_vector{CollisionShape::get_escape_vector(shape, other_shape)};
    // we do this because there's no collision object to maintain a static physics state for different body's resolution steps.
    // (if we were to directly modify the transform here, the escape vector for the other body would be completely off)
    this->motion = escape_vector;
    float const bounce{shape->get_bounce() * other_shape->get_bounce()};
    if(RigidBody *other_rb{dynamic_cast<RigidBody*>(other)}) {
        Vecf const relative_velocity{other_rb->linear_velocity - this->linear_velocity};
        float const relative_mass{other_rb->mass / (other_rb->mass + this->mass)};
        this->add_impulse(escape_vector.normalized() * relative_velocity.magnitude() * bounce * relative_mass);
    } else {
        this->add_impulse(Vecf::reflect(this->linear_velocity, escape_vector.normalized()) * bounce);
    }
}
```

core/collision.hpp

```cpp
void CollisionWorld::check_collisions() {
    for(int i{0}; i < this->shapes.size(); ++i) {
        CollisionShape *shape{this->shapes[i]};
        this->check_collisions_for(shape, i);
    }
}

void CollisionWorld::check_collisions_for(CollisionShape *shape, size_t begin) {
    // check all shapes *after* this one in the shapes list.
    // (As the shapes *before* have already been checked, guaranteeing that each pair will only be checked once)
    for(size_t i{begin+1}; i < this->shapes.size(); ++i) {
        CollisionShape *other{this->shapes[i]};
        if(other != shape && other->get_owner() != shape->get_owner() && CollisionShape::shapes_overlap(shape, other)) {
            if((shape->get_mask() & other->get_layers()) != 0x0u)
                shape->get_owner()->add_overlap(shape, other);
            if((shape->get_layers() & other->get_mask()) != 0x0u)
                other->get_owner()->add_overlap(other, shape);
        }
    }
}

```

Collision detection uses masks to minimize checks. Though I didn't end up using those in the final version. It uses sqr_magnitude instead of magnitude to avoid a sqrt. Though it's a minor optimization that isn't really needed for a project this size.

```cpp
bool CollisionShape::can_collide(CollisionShape const *lhs, CollisionShape const *rhs) {
    return lhs->owner != nullptr && rhs->owner != nullptr
        && lhs->owner != rhs->owner
        && ((lhs->get_mask() & rhs->get_layers()) != 0x0u
            || (rhs->get_mask() & lhs->get_layers()) != 0x0u);
}

bool CollisionShape::shapes_overlap(CollisionShape const *lhs, CollisionShape const *rhs) {
    float const rad_sum{lhs->radius + rhs->radius};
    return (lhs->get_global_transform().position - rhs->get_global_transform().position).sqr_magnitude() < rad_sum * rad_sum;
}

Vecf CollisionShape::get_escape_vector(CollisionShape const *lhs, CollisionShape const *rhs) {
    Vecf const difference{lhs->get_global_transform().position - rhs->get_global_transform().position};
    float const diff_mag{difference.magnitude()};
    return diff_mag < (lhs->radius + rhs->radius)
        ? (difference / diff_mag) * (lhs->radius + rhs->radius - diff_mag)
        : Vecf::ZERO;
}
```

# Signals

Notifications are carried between objects using Signals. An implementation of the Observer pattern intended to provide generic, typesafe, anonymous callbacks.

core/signal.hpp:

```cpp

/*! Observer-listener implementation
 */
template <class... Args>
class Signal {
    std::vector<Callable<void, Args...>> listeners{};
public:
    void connect(Callable<void, Args...> callable);
    void disconnect(Callable<void, Args...> callable);
    void invoke(Args...);
};

template <class... Args> void Signal<Args...>::connect(Callable<void, Args...> callable) {
    this->listeners.push_back(callable);
}

template <class... Args> void Signal<Args...>::disconnect(Callable<void, Args...> callable) {
    std::erase_if(this->listeners,
    [&callable](Callable<void, Args...> &listener) -> bool {
        return listener == callable;
    });
}

template <class... Args> void Signal<Args...>::invoke(Args... args) {
    for(Callable<void, Args...> &listener : this->listeners) {
        listener.call(args...);
    }
}

#ifdef DEBUG
static inline
void TEST_signals() {
    struct A {inline void f(int val) {
        std::printf("A: %d\n", val);
    }};
    struct B { inline void f(int val) {
        std::printf("B: %d\n", val);
    }};

    A a_object;
    B b_object;

    Signal<int> signal;

    Callable<void, int> a_callable{Callable<void, int>::make(&a_object, &A::f)};
    Callable<void, int> b_callable{Callable<void, int>::make(&b_object, &B::f)};

    signal.connect(a_callable);
    signal.invoke(5);
    signal.connect(b_callable);
    signal.invoke(12);
    signal.disconnect(a_callable);
    signal.invoke(10);
}
#endif
```

This is achieved using the custom Callable template class. It's made up of an end-programmer-facing `Callable` wrapper. And a `HiddenCallable` to enable the end-programmer to use a very simple stack-allocated interface, while behind the scenes it can do polymorphism as required to make `Callable` anonymous (so not requiring the caller to know the type of the target).

core/callable.hpp:

```cpp
/* Base interface template for a member function pointer object
 */
template <class Return, class... Args>
struct HiddenCallableBase {
    virtual ~HiddenCallableBase() = default;
    virtual Return call(Args... args) const = 0;
    virtual bool equals(HiddenCallableBase<Return, Args...> const &other) const;
};

template <class Return, class... Args> bool HiddenCallableBase<Return, Args...>::equals(HiddenCallableBase<Return, Args...> const &other) const {
    return &other == this;
}

/* Hidden component of a Callable, specialized for a specific target object
 */
template <class Target, class Return, class... Args>
struct HiddenCallable : public HiddenCallableBase<Return, Args...> {
typedef Return (Target::*Signature)(Args...);
    HiddenCallable(Target *target, Signature function);
    Target *target{nullptr};
    Signature function{nullptr};
    virtual void call(Args...) const override;
    virtual bool equals(HiddenCallableBase<Return, Args...> const &other) const override;
};

template <class Target, class Return, class... Args> bool HiddenCallable<Target, Return, Args...>::equals(HiddenCallableBase<Return, Args...> const &other) const {
    HiddenCallable<Target, Return, Args...> const *cast{dynamic_cast<HiddenCallable<Target, Return, Args...> const *>(&other)};
    return cast != nullptr && &other == this && cast->target == this->target && cast->function == this->function;
}

template <class Target, class Return, class... Args> HiddenCallable<Target, Return, Args...>::HiddenCallable(Target *target, Signature function) : target{target}, function{function} {}
template <class Target, class Return, class... Args> void HiddenCallable<Target, Return, Args...>::call(Args... args) const {
    std::invoke(this->function, this->target, args...);
}

/* Class for referring to a callable pointer to a member function.
 */
template <class Return, class... Args>
class Callable {
public:
    std::shared_ptr<HiddenCallableBase<Return, Args...> const> hidden;
    template <class Target> static Callable<Return, Args...> make(Target *target, Return (Target::*function)(Args...));
    Return call(Args... args);
};

template <class Return, class... Args> template <class Target> Callable<Return, Args...>
Callable<Return, Args...>::make(Target *target, Return (Target::*function)(Args...)) {
    Callable<Return, Args...> callable;
    callable.hidden = std::make_unique<HiddenCallable<Target, Return, Args...>>(target, function);
    return callable;
};

template <class Return, class... Args> Return Callable<Return, Args...>::call(Args... args) {
    return this->hidden->call(args...);
}

template <class Return, class... Args> bool operator==(Callable<Return, Args...> const &lhs, Callable<Return, Args...> const &rhs) {
    return lhs.hidden->equals(*rhs.hidden.get());
}
```

The general concept of this is based on Godot's concepts of the same names (the exposed/hidden layers and function pointers). Though heavily modified, as I don't need to support a custom scripting language. Which then allowed me to use compile-time type checking. Rather than having to do that using a variant type at runtime. It also lets me avoid `void*` sorcery. However much I may love myself a `void*`, it's best to avoid them where needed.

These are then exposed in classes as such:

core/collidable_node.hpp:

```cpp
class CollidableNode : public Node2D {
...
public:
    Signal<CollisionShape*, CollidableNode*, CollisionShape*> overlap_enter{};
...
};
```

and listened to like this:

```cpp
Player::Player()
...
    this->overlap_enter.connect(ce::Callable<void, ce::CollisionShape *, ce::CollidableNode *, ce::CollisionShape *>::make(
        this, &Player::_on_overlap_enter
    ));
...
}
```

# Input

The input subsystem is rather simple to use. It has three concepts. The `InputMap` being the simplest.

```cpp
/*! Map input bindings to functions.
 */
class InputMap {
    std::map<std::string, InputAction> bindings{};
public:
    InputAction &bind_input(std::string const &name, std::vector<InputEffect*> &&binds);
    InputAction &get_action(std::string const &action_id);
    void process_event(SDL_Event const &evt);
};
```

The input map can be acquired from the `CanvasEngine`. Input actions are then registered. Which expose a `changed` `Signal`. That can be listened for as described in the relevant section.

An input Action is built of `InputEffect`s. Which are objects that receive SDL events, filter them, and transform them, to produce a signal whenever they want. Containing whatever data they want.

For example a `KeyboardKey` effect will wait for a specific key to be pressed. And mark itself as changed. So that the `InputAction` will notify it's listeners.

More complex effects are also possible. For example a `ButtonAxis` combines two `InputEffects` and maps one to -1 and one to +1. Giving an easy 2-directional axis.

```cpp
/*! Represents a collection of bindings.
 */
class InputAction {
private:
    std::vector<InputEffect::Ptr> effects{}; //!< list of all effects used to produce final result
public:
    Signal<InputValue> changed{};
    InputAction() = default;
    InputAction(InputEffect::Ptr &effect);
    InputAction(std::vector<InputEffect*> &effects);

    void process_event(SDL_Event const &evt); //!< process an incoming OS event

    template <class Effect> Effect *get_effect_of_type(); //!< get the first effect from the effects list that is of type Effect
};

```

The part of the `Player` constructor that sets up input looks like this:

```cpp
    ce::InputMap &map{ce::CanvasEngine::get_singleton()->get_input_map()};
    map.bind_input("horizontal", {
        new ce::ButtonAxis(
            new ce::KeyboardScancode(SDL_SCANCODE_A),
            new ce::KeyboardScancode(SDL_SCANCODE_D)
        )
    }).changed.connect(ce::Callable<void, ce::InputValue>::make(
        this, &Player::_input_horizontal_movement)
    );
    map.bind_input("vertical", {
        new ce::ButtonAxis(
            new ce::KeyboardScancode(SDL_SCANCODE_W),
            new ce::KeyboardScancode(SDL_SCANCODE_S)
        )
    }).changed.connect(ce::Callable<void, ce::InputValue>::make(
        this, &Player::_input_vertical_movement)
    );

```

It uses a `ButtonAxis` to combine two scancodes into an axis with a range of `-1` to `1`. Making input tracking slightly easier.

# Levels

Levels are relatively tiny objects. Only really existing to have somewhere to construct the node hierarchy. Though also useful for storing level-local data.

```cpp
class Level1 : public ce::Level {
public:
    unsigned score{0};
    unsigned lives{3};
    ce::Signal<unsigned> score_added{};
    ce::Signal<unsigned> life_lost{};
public:
    void add_score();
    void lose_life();
    virtual ce::Node::OwnedPtr construct() override;
};
```

Although they can be constructed anywhere. Only the `CanvasEngine` should call `instantiate` to actually construct and instantiate the scene when the level becomes the new primary level.

# External resources used:

Game Engine Architecture by Jason Gregory

Game Physics by David H. Eberly

Many hours on [Desmos.com](desmos.com) to check my math.

So so so much [cppreference.com](cppreference.com) (though i downloaded it so i could check it on the train).