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
The project is free and open source software, feel free to study it, use it, whatever. MIT license.
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?
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.
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.