Skip to content

Instantly share code, notes, and snippets.

@flisboac
Created July 17, 2021 01:46
Show Gist options
  • Save flisboac/96c6b8d0f394dfdc4414e08443b3e765 to your computer and use it in GitHub Desktop.
Save flisboac/96c6b8d0f394dfdc4414e08443b3e765 to your computer and use it in GitHub Desktop.
Differences between OOP vs DOD approaches in software design (only examples here, actually)
// Working snippet at: https://glot.io/snippets/g0jhgoope4
// "DOD" stands for data-oriented design
#include <vector>
#include <cstddef>
#include <iostream>
#include <algorithm>
#include <queue>
#include <emmintrin.h>
#include <xmmintrin.h>
#include <cstdint>
static const std::size_t STEPS = 4;
// Some forward declarations here, just to get to the part of the implementation
// that really matters faster. Please, don't mind this!
class box;
static std::basic_ostream<char>& operator<<(std::basic_ostream<char>& os, box const& box);
static void print(std::vector<box> const& boxes, std::vector<bool> collisions);
static std::size_t nearest_multiple_of(std::size_t desired_size, std::size_t amount);
class box {
// This allows for the game engine to access all available instances and do
// global operations on all of them at the same time. Useful when rendering, or
// calculating the next game state.
//
// Component registry can be somewhere else, if needed (and most probably, it will be).
// TODO: state management (e.g. inclusion, deletion), free lists, etc.
static std::vector<std::string> _names;
static std::vector<float> _xs;
static std::vector<float> _ys;
static std::vector<float> _ws;
static std::vector<float> _hs;
std::size_t _id;
public:
static std::size_t total_instances() {
return _names.size();
}
// Obligatory rule of 5
// Please, ignore! Not relevant to the Data-oriented vs OOP debate!
box(): box("", 0, 0, 0, 0) {}
box(const box&) = default;
box(box&&) noexcept = default;
box& operator=(const box&) = default;
box& operator=(box&&) noexcept = default;
// "De-facto" constructors
explicit box(std::size_t id): _id(id) {}
box(std::string name, float x, float y, float w, float h) {
std::size_t reserve_size = nearest_multiple_of(_names.size() + 1, STEPS);
_names.reserve(reserve_size);
_xs.reserve(reserve_size);
_ys.reserve(reserve_size);
_ws.reserve(reserve_size);
_hs.reserve(reserve_size);
_names.emplace_back(std::move(name));
_xs.emplace_back(x);
_ys.emplace_back(y);
_ws.emplace_back(w);
_hs.emplace_back(h);
_id = _names.size() - 1;
}
// Properties
std::size_t id() const { return _id; }
std::string const& name() const { return _names.at(_id); }
float x() const { return _xs.at(_id); }
float y() const { return _ys.at(_id); }
float w() const { return _ws.at(_id); }
float h() const { return _hs.at(_id); }
float x_max() const { return this->x() + this->w(); }
float y_max() const { return this->y() + this->h(); }
std::vector<bool> calculate_collisions() {
std::vector<bool> results;
auto const& lhs = *this;
auto v_lhs_x = lhs.x();
auto v_lhs_y = lhs.y();
auto v_lhs_w = lhs.w();
auto v_lhs_h = lhs.h();
auto v_lhs_x_max = v_lhs_x + v_lhs_w;
auto v_lhs_y_max = v_lhs_y + v_lhs_h;
float c_lhs_x_min[] = { v_lhs_x, v_lhs_x, v_lhs_x, v_lhs_x };
float c_lhs_x_max[] = { v_lhs_x_max, v_lhs_x_max, v_lhs_x_max, v_lhs_x_max };
float c_lhs_y_min[] = { v_lhs_y, v_lhs_y, v_lhs_y, v_lhs_y };
float c_lhs_y_max[] = { v_lhs_y_max, v_lhs_y_max, v_lhs_y_max, v_lhs_y_max };
float c_lhs_w[] = { v_lhs_w, v_lhs_w, v_lhs_w, v_lhs_w };
float c_lhs_h[] = { v_lhs_w, v_lhs_w, v_lhs_w, v_lhs_w };
auto lhs_x_min = _mm_load_ps(c_lhs_x_min);
auto lhs_x_max = _mm_load_ps(c_lhs_x_max);
auto lhs_y_min = _mm_load_ps(c_lhs_y_min);
auto lhs_y_max = _mm_load_ps(c_lhs_y_max);
auto lhs_w = _mm_load_ps(c_lhs_w);
auto lhs_h = _mm_load_ps(c_lhs_h);
// Here, we process each component (property array) of box in steps of STEPS (4).
// i.e. load 4 X positions, compare groups of 4 positions, etc.
// This is only possible because
for (std::size_t id = 0; id < total_instances(); id += STEPS) {
auto const& rhs = box(id);
auto rhs_x_min = _mm_load_ps(&_xs.at(id));
auto rhs_y_min = _mm_load_ps(&_ys.at(id));
auto rhs_w = _mm_load_ps(&_ws.at(id));
auto rhs_h = _mm_load_ps(&_hs.at(id));
auto rhs_x_max = _mm_add_ps(rhs_x_min, rhs_w);
auto rhs_y_max = _mm_add_ps(rhs_y_min, rhs_h);
auto x_min = _mm_min_ps(lhs_x_min, rhs_x_min);
auto x_max = _mm_max_ps(lhs_x_max, rhs_x_max);
auto x_len = _mm_add_ps(lhs_w, rhs_w);
auto y_min = _mm_min_ps(lhs_y_min, rhs_y_min);
auto y_max = _mm_max_ps(lhs_y_max, rhs_y_max);
auto y_len = _mm_add_ps(lhs_h, rhs_h);
// Effectively, this is range comparison, in all coordinates
auto overlaps_x = _mm_cmplt_ps(_mm_sub_ps(x_max, x_min), x_len);
auto overlaps_y = _mm_cmplt_ps(_mm_sub_ps(y_max, y_min), y_len);
auto overlaps_all = _mm_and_ps(overlaps_x, overlaps_y);
alignas(__m128i) float overlaps_bools[STEPS];
_mm_store_ps(overlaps_bools, overlaps_all);
for (std::size_t j = 0; j < STEPS; j++) {
auto overlaps = overlaps_bools[j];
results.emplace_back(bool(overlaps));
}
}
return results;
}
static void print_collisions(box const& box, std::vector<bool> collisions) {
for (std::size_t i = 0; i < total_instances(); i++) {
auto const& box = ::box(i);
auto collides = collisions.at(i);
std::cout << box << ", collides? " << collides << std::endl;
}
}
};
int main(void) {
float W = 2.0f;
std::vector<box> test_boxes = {
{ "b0", 0.0f, 0.0f, W, W },
{ "b1", 3.0f, 0.0f, W, W },
{ "b2", 0.0f, 3.0f, W, W },
{ "b3", 3.0f, 3.0f, W, W }
};
box do_collide = { "do_collide", 1.0f, 1.0f, 3.0f, 3.0f };
box no_collide = { "no_collide", 6.0f, 6.0f, W, W };
std::cout << "with: " << do_collide << std::endl;
auto do_collisions = do_collide.calculate_collisions();
box::print_collisions(do_collide, do_collisions);
std::cout << std::endl << "with: " << no_collide << std::endl;
auto no_collisions = no_collide.calculate_collisions();
box::print_collisions(no_collide, no_collisions);
}
static std::basic_ostream<char>& operator<<(std::basic_ostream<char>& os, box const& box) {
os << '{'
<< box.name()
<< "(" << box.id() << ")"
<< ":" << box.x()
<< "," << box.y()
<< "," << box.w()
<< "," << box.h()
<< "}";
return os;
}
static std::size_t nearest_multiple_of(std::size_t desired_size, std::size_t amount) {
return desired_size + (amount - desired_size % amount);
}
std::vector<std::string> box::_names;
std::vector<float> box::_xs;
std::vector<float> box::_ys;
std::vector<float> box::_ws;
std::vector<float> box::_hs;
// Working snippet at: https://glot.io/snippets/g0jhh1n3ts
#include <vector>
#include <iostream>
#include <algorithm>
// Some forward declarations here, just to get to the part of the implementation
// that really matters faster. Please, don't mind this!
class box;
static std::basic_ostream<char>& operator<<(std::basic_ostream<char>& os, box const& box);
static void print(std::vector<box> const& boxes, std::vector<bool> collisions);
class box {
float _x = 0;
float _y = 0;
float _w = 0;
float _h = 0;
public:
// Obligatory rule of 5
// Please, ignore! Not relevant to the Data-oriented vs OOP debate!
box() = default;
box(const box&) = default;
box(box&&) noexcept = default;
box& operator=(const box&) = default;
box& operator=(box&&) noexcept = default;
// "De-facto" constructors
box(float x, float y, float w, float h): _x(x), _y(y), _w(w), _h(h) {}
// Accessors
float x() const { return _x; }
float y() const { return _y; }
float w() const { return _w; }
float h() const { return _h; }
float x_max() const { return _x + _w; }
float y_max() const { return _y + _h; }
bool collides_with(box const& rhs) {
auto const& lhs = *this;
auto x_min = std::min(lhs.x(), rhs.x());
auto x_max = std::max(lhs.x_max(), rhs.x_max());
auto x_len = lhs.w() + rhs.w();
auto y_min = std::min(lhs.y(), rhs.y());
auto y_max = std::max(lhs.y_max(), rhs.y_max());
auto y_len = lhs.h() + rhs.h();
// Effectively, this is range comparison, in all coordinates
auto overlaps_x = (x_max - x_min) < x_len;
auto overlaps_y = (y_max - y_min) < y_len;
auto overlaps = overlaps_x && overlaps_y;
return overlaps;
}
std::vector<bool> collides_with(std::vector<box> const& boxes) {
std::vector<bool> results;
for (std::size_t i = 0; i < boxes.size(); i++) {
auto const& rhs = boxes.at(i);
results.emplace_back(this->collides_with(rhs));
}
return results;
}
};
int main(void) {
float W = 2.0f;
std::vector<box> test_boxes = {
{ 0.0f, 0.0f, W, W },
{ 3.0f, 0.0f, W, W },
{ 0.0f, 3.0f, W, W },
{ 3.0f, 3.0f, W, W }
};
box do_collide = { 1.0f, 1.0f, 3.0f, 3.0f };
box no_collide = { 6.0f, 6.0f, W, W };
std::cout << "with: " << do_collide << std::endl;
auto do_collisions = do_collide.collides_with(test_boxes);
print(test_boxes, do_collisions);
std::cout << std::endl << "with: " << no_collide << std::endl;
auto no_collisions = no_collide.collides_with(test_boxes);
print(test_boxes, no_collisions);
}
static std::basic_ostream<char>& operator<<(std::basic_ostream<char>& os, box const& box) {
os << '{'
<< box.x() << ","
<< box.y() << ","
<< box.w() << ","
<< box.h() << "}";
return os;
}
static void print(std::vector<box> const& boxes, std::vector<bool> collisions) {
for (std::size_t i = 0; i < boxes.size(); i++) {
auto const& box = boxes.at(i);
auto collides = collisions.at(i);
std::cout << box << ", collides? " << collides << std::endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment