4
\$\begingroup\$

I'm pretty new when it comes to the whole Entity Component System structure and I got some questions I just can't wrap my head around.

I know that for example collisions, you'd have a CollisionComponent and a CollisionSystem for handeling collisions. But what if I'd like to use a quadtree for collisions? Where do I put that quadtree? What do I store in that quadtree? Both the PositionComponent and CollisionComponent?

A quadtree is just an example, it could be any abstract container really. If somebody who has more experience with ECS could give me a primer on this, I'd be very grateful.

\$\endgroup\$
4
\$\begingroup\$

Update

I have wrote Theraot.ECS inspired by Fastest way to look up an entity with a set of components?.

However this answer motivated me to allow to specify custom containers for particular types. It would be necesary to provide an adapter to the interface IIntKeyCollection<TValue> exposed in the project. Which would in theory allow the ECS to use a quadtree internally, just for some types of componets, for example some third party Vector2.

The project is free and open source software, feel free to study it, use it, whatever. MIT license.


Original Answer

But what if I'd like to use a quadtree for collisions?

You have a physics system that has access to the quadtree.

Addendum: On the server both the physics (for collisions) and the network (to know what things are near the players, so it can send them only notification about their surrounding) would need the quadtree. On the client, both physics and rendering (to have a quick approximation of what is in camera to send to the GPU) would need the quadtree.


Where do I put that quadtree?

It can be part of the physics system or shared (by means other than ECS) among various systems (you can pass it on system creation, see dependency injection).


Fancy commercial game engines can have the luxury of making a ECS that spatially aware. On one hand it has performance benefits. On the other it couples the ECS to a particular geometry, and a particular geometry library... which makes it very hard to reuse separete from the game engine.

Addendum: I believe it is possible to develop an ECS solution that allows to specify custom containers. Either for the whole or just for particular component types. We could tell such ECS to use (an adapter around) a quadtree that would be alike to the deeply woven one in the fancy ECS, except it was injected.


What do I store in that quadtree?

Ern...

There are two ways that I can think of to go about this (besides the fancy spatially aware ECS):

  • You have a system that synchronizes the quadtree with the ECS. This system will query every object that has a position component (and is not marked static or sleeping) and update the quadtree based on that.

    This means your quadtree needs to have entity ids, and perhaps copies of relevant components that the systems that use the quadtree need.

    The drawback is that you have a system busy synchronizing components, which would have some impact of performance.

  • You have components that actually reference to the quadtree.

    If we go for encapsulation, we would have a type – with value semantics – that has the means to get the position of an entity from the quadtree and to set the position updating the quadtree, and then you store that in your component.

    If you want – or need – pure data, it would be a reference to the quadtree and some id for the position inside the quadtree (those could still be entity ids), such that the system that uses it will access the position associated with that component and not the others.

    The drawback is, of course, that you have a reference to a big datastructure - which lies outside of the ECS - stored in your component. You must be aware of that when it comes to serialize the components for a save state, for example.

Addendum

  • Have smart position components, such that systems can subscribe to changes of these components. Then the system that updates the quadtree can subscribe.

    This is similar to the idea above, except the quadtree is not directly referenced in the component.

    The ECS are not meant to have notification for changed components (and I do not mean events for added and removed components, but events for modified values), and having them is detrimental for performance※.

    If the ECS does not have the means to subscribe to changes of a component - and I do not think they should have it, at least not out of the box※※ - we can make a not very pure component that has this ability.

    Perhaps having each component handle its own events does not sound as a great idea, then we could consider to centrilize these notification in a... wait, I'm adding a dependency to the components. We could just make that dependency the quadtree and we are back at idea above.


※: On one hand, we can have only entities that move have a velocity component, or alternatively we can add a component to mark entities that do not move. In either case, the systems would be able to iterate over and only over the entities that move, being sure that all of them moved since last tick. On the other hand, ECS often optimize for cache locality and fast access and iteration, in fact, a tighly managed ECS could even provide - temporary - direct references to components allowing to modify them quickly but with no means to rise an event to notify that they were (well, we could assume they were modified if the developer took the references).

※※: If the ECS allows to specify a custom container, in particular for specific component types, we could tell the ECS to use one that has events for value changed. However, if that is possible, we could just use the quadtree.

\$\endgroup\$
  • \$\begingroup\$ I wonder why the quadtree needs to sit external to the ECS, or else be woven so deeply that the whole ECS is spatially aware. Couldn't it just be another system? I could envision making a QuadtreeNode component that I associate with each entity that needs to show up in spatial queries, representing it as a leaf node in the tree. Then I'd add intermediate nodes in the tree as their own entities with only a QuadtreeNode component. The Quadtree system could be responsible for updating these nodes based on movement of objects with both a QuadtreeNode and Position, after the movement systems run. \$\endgroup\$ – DMGregory Aug 28 at 11:40
  • \$\begingroup\$ @DMGregory so you have a system that reads the positions and moves the nodes. I mentioned the option of a system keeping them in sync, I think you call it "quadtree system". The QuadtreeNode leaf would only have the entity id. That is how you can get entities by traversing the quadtree. \$\endgroup\$ – Theraot Aug 28 at 11:52
  • \$\begingroup\$ I will give you my 2 cents here. What if those behaviours could be split? We could have a system that registers change of position and quadtree system that would be able to subscribe to events of change. While keeping quadtree separate from reading the position change and from tightly coupling it to other systems that would notify the change in position. I haven't used ECS, so my words could be nonsense, I would be grateful if you corrected me. \$\endgroup\$ – Candid Moon _Max_ Aug 31 at 12:00
  • \$\begingroup\$ @CandidMoon_Max_ Expanded answer. \$\endgroup\$ – Theraot Aug 31 at 14:15
4
\$\begingroup\$

Just like with any software architecture question, the short answer is "It depends..."

Where do I put that quadtree?

Any auxiliary data structures needed by one system only should be part of that system. So if that quadtree is only used by the CollisionSystem, then you can make it part of the system.

But if that quadtree is used by many different systems, then it might make sense to extract it into an own system which does nothing but keep that quadtree up to date and also offers public interfaces for other systems to query the quadtree.

But on the other hand, if you have a dedicated MovementSystem in your architecture which is the only system allowed to move entities, then there could be potential efficiency gains to also have it manage the QuadTree. This is because the MovementSystem knows exactly which PositionComponents moved in the current tick, which allows it to decide if a branch of the quadtree needs to be updated or not.

What do I store in that quadtree?

That depends on how you are using it and how expensive it is in your particular ECS architecture to navigate between components of the same entity. If retrieving components from entity IDs is fast, then the QuadTreeSystem might only store coordinate tuples and EntityIDs (if your PositionComponent is exactly that, it might store the PositionComponent).

But if navigating between components is expensive in your architecture, you might also store any other components in the tree nodes which are frequently required by the users of your QuadTreeSystem.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.