25 KiB
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, with some minor modifications and updates as well as translating it to be C++ rather than C.
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.
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.
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:
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
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;
};
CollidableNodes on their own cannot collide with anything. They need one or more shapes as their children to function. CollisionShapes 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.
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:
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
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.
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:
/*! 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:
/* 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:
class CollidableNode : public Node2D {
...
public:
Signal<CollisionShape*, CollidableNode*, CollisionShape*> overlap_enter{};
...
};
and listened to like this:
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.
/*! 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 InputEffects. 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.
/*! 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:
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.
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 to check my math.
So so so much cppreference.com (though i downloaded it so i could check it on the train).