Index by base classes in GameObjectManager::m_objects_by_type_index

mstoeckl commented 3 months ago

Previously, the m_objects_by_type_index map only listed the objects by their (main) class. Finding all objects inheriting a given base class (like BadGuy, Portable, or PathObject) required scanning through the entire list of objects and trying a dynamic_cast on each. This PR changes the map to, for a given GameObject, record it in m_objects_by_type_index for all its notable intermediate base classes. Thus, for example, a Lantern is registered in the m_objects_by_type_index map for the lists for type indexes corresponding to Lantern, Rock, Portable, MovingSprite, and MovingObject. Now, one can efficiently look up all e.g. Portable objects by querying m_objects_by_type_index[std::type_index(typeid(Portable))], and this will be fast even if the level has 10000 unrelated objects.

In practice, this PR significantly speeds up processing for the Player and Crusher classes, which no longer need to search through many unrelated objects when looking for e.g. other players, Bullets, Portables, Bricks, etc. (A test level that I made with many crushers and about 1000 coins, which used to lag, now runs quickly.)

The awkward part of this approach is identifying the various base classes of an object when it is time to register them in GameObjectManager::this_before_object_add(). This is done by adding a new virtual function to GameObject, which when called provides all the classes under which to record an object. Every class inheriting GameObject must then implement the method to add itself to its own list. (This is admittedly tedious, but the method body is only a very formulaic line.)

This supersedes but does not conflict with https://github.com/SuperTux/supertux/pull/2986 .

HybridDog commented 3 months ago

I have tried the change on the level from #1682. In flame graphs generated with hotspot, GameObjectManager::update looks a lot faster now.

`GameObjectManager::update` flame graphs

master: gameobjectmanager_update_master

this PR: gameobjectmanager_update_pr

Main game loop flame graphs

master: screenmanager_run_master

this PR: screenmanager_run_pr

#

The return value of get_class_types depends only on the type of the object it is called on dynamically. Is it possible to somehow change get_class_types, e.g. with constexpr, such that it does not need to call the parent class get_class_types method during runtime? Or does the compiler optimise this away automatically?

Is there a way to avoid adding get_class_types manually to all GameObjects with compile-time programming?

mstoeckl commented 3 months ago

The return value of get_class_types depends only on the type of the object it is called on dynamically. Is it possible to somehow change get_class_types, e.g. with constexpr, such that it does not need to call the parent class get_class_types method during runtime?

It should be possible, instead of a std::vector, to return some type of list constructable at compile time using constexpr. However, I could not find any simple solutions. As get_class_types is called at most twice per created object, I do not think the cost is significant.

Is there a way to avoid adding get_class_types manually to all GameObjects with compile-time programming?

Yes, but I wouldn't recommend them.

It may be possible to define a macro to handle class definitions which both defines the class and automatically adds get_class_types.
Code generation always works, but can complicate the build.
If one has a (template parameter) list of all types that could be tracked, std::is_base_of might be usable to filter that list at compile time. However, 1) constructing that list requires including headers for all types 2) one ultimately trades a single line defining get_class_types for two (an #include and an entry in a list of template parameters), 3) I haven't actually tried this, so it may not even work -- there could be recursion depth issues.

HybridDog commented 3 months ago

Thanks for the information. The changes look fine to me.

mstoeckl commented 2 months ago

I've rebased this to fix merge conflicts. (In files src/objects/floating_image.hpp, src/objects/moving_sprite.hpp, and src/supertux/game_object.hpp)

tobbi commented 2 months ago

Thank you 👍

weluvgoatz commented 2 months ago

Sorry, but please re-open this, as this breaks every object that has a path attached to it by making them disappear.

mstoeckl commented 2 months ago

Sorry, but please re-open this, as this breaks every object that has a path attached to it by making them disappear.

Thank you for letting me know. Github doesn't seem to have a way to reopen merged&reverted PRs, so I've made a new PR that should fix the issue.

SuperTux / supertux