From e4f03880d49bdbe0c7269be0f40f23b197bcea77 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Wed, 7 Dec 2022 12:02:59 +0200 Subject: [PATCH] Schedule systems based on their declared dependencies --- source/game/stage.cpp | 32 ++++--- source/game/stage.h | 12 ++- source/game/system.h | 11 ++- source/game/systemscheduler.cpp | 154 ++++++++++++++++++++++++++++++++ source/game/systemscheduler.h | 54 +++++++++++ 5 files changed, 249 insertions(+), 14 deletions(-) create mode 100644 source/game/systemscheduler.cpp create mode 100644 source/game/systemscheduler.h diff --git a/source/game/stage.cpp b/source/game/stage.cpp index 7cad5bc..3888410 100644 --- a/source/game/stage.cpp +++ b/source/game/stage.cpp @@ -15,7 +15,8 @@ Stage::Stage(Reflection::Reflector &f, DataFile::Collection &r): resources(r), event_source(event_bus), event_observer(event_bus), - root(std::make_unique(*this)) + root(std::make_unique(*this)), + scheduler(reflector) { event_observer.observe([this](auto &e){ if(!active_camera) @@ -30,7 +31,9 @@ Stage::~Stage() void Stage::remove_system(System &s) { + scheduler.remove_system(s); erase_if(systems, [&s](auto &p){ return p.get()==&s; }); + pending_reschedule = true; } void Stage::set_active_camera(Handle c) @@ -57,22 +60,29 @@ void Stage::synthesize_initial_events(Handle entity, EventObserver &targ void Stage::tick(Time::TimeDelta dt) { + if(pending_reschedule) + { + scheduler.schedule(); + pending_reschedule = false; + } + { #ifdef DEBUG AccessGuard::BlockForScope _block; #endif - for(const auto &s: systems) - { - System::Activator act(*s); - try - { - s->tick(dt); - } - catch(const invalid_access &exc) + for(const SystemScheduler::Group &g: scheduler.get_groups()) + for(System *s: g.systems) { - throw invalid_access(format("%s by %s", exc.what(), Debug::demangle(typeid(*s).name()))); + System::Activator act(*s); + try + { + s->tick(dt); + } + catch(const invalid_access &exc) + { + throw invalid_access(format("%s by %s", exc.what(), Debug::demangle(typeid(*s).name()))); + } } - } } for(const auto &s: systems) diff --git a/source/game/stage.h b/source/game/stage.h index 283dc81..0c2219b 100644 --- a/source/game/stage.h +++ b/source/game/stage.h @@ -9,6 +9,7 @@ #include "eventsource.h" #include "handle.h" #include "reflection.h" +#include "systemscheduler.h" namespace Msp::Game { @@ -33,7 +34,9 @@ private: to put it in a pool. */ std::unique_ptr root; std::vector> systems; + SystemScheduler scheduler; Handle active_camera; + bool pending_reschedule = false; public: Stage(Reflection::Reflector &, DataFile::Collection &); @@ -78,8 +81,13 @@ inline void Stage::iterate_objects(const F &func) template inline T &Stage::add_system(Args &&... args) { - systems.emplace_back(std::make_unique(*this, std::forward(args)...)); - return static_cast(*systems.back()); + // Ensure that a reflected class exists for scheduling + reflector.get_or_create_class(); + + auto &sys = systems.emplace_back(std::make_unique(*this, std::forward(args)...)); + scheduler.add_system(*sys); + pending_reschedule = true; + return static_cast(*sys); } template diff --git a/source/game/system.h b/source/game/system.h index 8c9c8b1..09ee157 100644 --- a/source/game/system.h +++ b/source/game/system.h @@ -27,8 +27,11 @@ public: ORDER_MASK = 24 }; - struct Dependency + class Dependency { + friend class System; + + private: DependencyFlags flags = NO_DEPENDENCY; const Reflection::ClassBase &type; void (*prepare)(Stage &) = nullptr; @@ -36,7 +39,11 @@ public: void (*unblock)(DependencyFlags) = nullptr; void (*block)(DependencyFlags) = nullptr; + public: Dependency(const Reflection::ClassBase &t): type(t) { } + + DependencyFlags get_flags() const { return flags; } + const Reflection::ClassBase &get_type() const { return type; } }; class Activator: public NonCopyable @@ -67,6 +74,8 @@ protected: void declare_dependency(DependencyFlags); public: + const std::vector &get_dependencies() const { return dependencies; } + void begin_tick(); virtual void tick(Time::TimeDelta) = 0; void end_tick(); diff --git a/source/game/systemscheduler.cpp b/source/game/systemscheduler.cpp new file mode 100644 index 0000000..d6fb9a5 --- /dev/null +++ b/source/game/systemscheduler.cpp @@ -0,0 +1,154 @@ +#include "systemscheduler.h" +#include +#include +#include +#include "system.h" + +using namespace std; + +namespace Msp::Game { + +SystemScheduler::SystemScheduler(Reflection::Reflector &r): + reflector(r) +{ } + +void SystemScheduler::add_system(System &s) +{ + nodes.emplace_back(&s, reflector.find_class(typeid(s))); +} + +void SystemScheduler::remove_system(System &s) +{ + erase_if(nodes, [&s](const GraphNode &n){ return n.system==&s; }); + for(auto i=groups.begin(); i!=groups.end(); ) + { + erase_if(i->systems, [&s](System *gs){ return gs==&s; }); + if(i->systems.empty()) + i = groups.erase(i); + else + ++i; + } +} + +void SystemScheduler::schedule() +{ + for(GraphNode &n: nodes) + { + n.scheduled_order = ~0U; + n.predecessors.clear(); + } + + for(auto i=nodes.begin(); i!=nodes.end(); ++i) + for(auto j=i; ++j!=nodes.end(); ) + { + int order = get_order(*i, *j); + if(order<0) + j->predecessors.push_back(&*i); + else if(order>0) + i->predecessors.push_back(&*j); + } + + groups.clear(); + unsigned unscheduled_count = nodes.size(); + while(unscheduled_count) + { + unsigned order = groups.size(); + Group &group = groups.emplace_back(); + for(GraphNode &n: nodes) + if(!~n.scheduled_order && ranges::all_of(n.predecessors, [order](GraphNode *p){ return p->scheduled_order &deps1 = node1.system->get_dependencies(); + const vector &deps2 = node2.system->get_dependencies(); + + auto get_dep_type = [](const System::Dependency &d){ return &d.get_type(); }; + auto i = ranges::find(deps1, node2.type, get_dep_type); + int flags1 = (i!=deps1.end() ? i->get_flags()&System::ORDER_MASK : 0); + i = ranges::find(deps2, node1.type, get_dep_type); + int flags2 = (i!=deps2.end() ? i->get_flags()&System::ORDER_MASK : 0); + if(flags1&flags2) + throw scheduling_error(format("Conflicting ordering between %s and %s", node1.type->get_name(), node2.type->get_name())); + else if(flags1==System::RUN_BEFORE || flags2==System::RUN_AFTER) + return -1; + else if(flags1==System::RUN_AFTER || flags2==System::RUN_BEFORE) + return 1; + else + return 0; +} + +int SystemScheduler::get_data_order(const GraphNode &node1, const GraphNode &node2) +{ + int data_order = 0; + const Reflection::ClassBase *ordered_data = nullptr; + const Reflection::ClassBase *unordered_data = nullptr; + for(const System::Dependency &d1: node1.system->get_dependencies()) + { + int flags1 = d1.get_flags()&System::DATA_MASK; + if(!flags1) + continue; + + for(const System::Dependency &d2: node2.system->get_dependencies()) + { + int flags2 = d2.get_flags()&System::DATA_MASK; + if(!flags2) + continue; + + const Reflection::ClassBase *common_type = nullptr; + if(&d1.get_type()==&d2.get_type() || d1.get_type().is_base_of(d2.get_type())) + common_type = &d1.get_type(); + else if(d2.get_type().is_base_of(d1.get_type())) + common_type = &d2.get_type(); + else + continue; + + int order = 0; + // Read-only access to old data always comes first + if(flags1==System::READ_OLD) + order = -1; + else if(flags2==System::READ_OLD) + order = 1; + // Read-only access to fresh data always comes last + else if(flags1==System::READ_FRESH) + order = 1; + else if(flags2==System::READ_FRESH) + order = -1; + // Chained updates always come after non-chained writes + else if(flags1==System::CHAINED_UPDATE && (flags2==System::WRITE || flags2==System::UPDATE)) + order = 1; + else if(flags2==System::CHAINED_UPDATE && (flags1==System::WRITE || flags1==System::UPDATE)) + order = -1; + else + unordered_data = common_type; + + if(order && data_order && order!=data_order) + throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s and %s", + node1.type->get_name(), node2.type->get_name(), ordered_data->get_name(), common_type->get_name())); + + data_order = order; + ordered_data = common_type; + } + } + + if(!data_order && unordered_data) + throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s", + node1.type->get_name(), node2.type->get_name(), unordered_data->get_name())); + + return data_order; +} + +} // namespace Msp::Game diff --git a/source/game/systemscheduler.h b/source/game/systemscheduler.h new file mode 100644 index 0000000..2ab4804 --- /dev/null +++ b/source/game/systemscheduler.h @@ -0,0 +1,54 @@ +#ifndef MSP_GAME_SYSTEMSCHEDULER_H_ +#define MSP_GAME_SYSTEMSCHEDULER_H_ + +#include +#include "reflection.h" + +namespace Msp::Game { + +class System; + +class scheduling_error: public std::logic_error +{ +public: + scheduling_error(const std::string &w): logic_error(w) { } +}; + +class SystemScheduler +{ +public: + struct Group + { + std::vector systems; + }; + +private: + struct GraphNode + { + System *system = nullptr; + Reflection::ClassBase *type = nullptr; + std::vector predecessors; + unsigned scheduled_order = 0; + }; + + Reflection::Reflector &reflector; + std::vector nodes; + std::vector groups; + +public: + SystemScheduler(Reflection::Reflector &); + + void add_system(System &); + void remove_system(System &); + void schedule(); +private: + static int get_order(const GraphNode &, const GraphNode &); + static int get_explicit_order(const GraphNode &, const GraphNode &); + static int get_data_order(const GraphNode &, const GraphNode &); +public: + const std::vector &get_groups() const { return groups; } +}; + +} // namespace Msp::Game + +#endif -- 2.45.2