Hey Piotr!
It's been about a year since I started using becsy
and it's still working wonderfully for my use case; thanks again for your sustained effort on this awesome library ๐ I hope for my app to go public soon enough so we can share it with you!
I've come with yet another odd use case, but one I'm hoping you'd have suggestions on ๐
I've been trying to build a VisibilitySystem
which marks specific elements which are in or out of view as visible using a VisibleComponent
. To determine visibility performantly, my system is making use of an external data structure to implement a map of tiles (leveraging tiling as the algorithm), and we're also considering a quadtree for spatial queries later onwards.
My question is: I'm struggling to find a fast way to lookup entities after I query for which ones are visible in my data structure. The problem is exacerbated by our world having a huge number of entities (sometimes upwards of 10000).
The system I'm trying to build is roughly like:
class VisibilitySystem extends System {
entities = this.query((q) => q.addedOrChangedOrRemoved.with(IdComponent, PositionComponent, SizeComponent));
camera = this.query((q) => q.addedOrChanged.with(CameraComponent).trackWrites);
initialize() {
this.tileMap = new TileMap();
}
execute() {
for (const entity of this.entities.addedOrChangedOrRemoved) {
const id = entity.read(IdComponent).id;
const visible = this.tileMap.addElement(
id,
entity.read(PositionComponent),
entity.read(SizeComponent)
);
// Works great for mutating a single entity when it changes
if (visible) {
entity.add(VisibleComponent);
}
}
if (this.camera.addedOrChanged.length) {
const camera = this.entities.addedOrChanged[0];
const visibleElementIds = this.tileMap.visibleElements(camera);
// Question: I want to avoid traversing through all ~10000 elements I have here to save on performance cost
// and add a `VisibleComponent` to those things which have become visible (and do a lookup to see which
// elements are no longer visible to remove the component, etc).
}
}
}
In such a situation I would typically err for a lookup table of sorts to easily lookup an entity by the id
you see above, but I can appreciate that building threading primitives for that may be tricky.
One idea I had whilst thinking through my use case is adding an indexed
query flavour to queries. It felt like it'd fit well into the way we're currently interpreting the API in our project, whilst also aligning with becsy
's thread-safe vision. One way I could see that playing out is as below - supporting hashed lookup of entities based on user-defined components:
class MySystem {
entities = this.query(
(q) =>
q
.addedOrChangedOrRemoved
.with(IdComponent, PositionComponent, SizeComponent))
.indexed('entitiesById', e => e.read(IdComponent).id)
);
execute() {
// later on, we are able to do a quick lookup & add the `VisibleComponent` to entities
for (const entities of entitiesWhichAreNowVisible) {
// O(1) lookup vs O(n) for thousands of elements
const entity = this.entities.fromIndex('entitiesById', entity);
entity.add(VisibleComponent);
}
}
}
In this way, we'd keep the API surface change pretty small, whilst also fitting into the pre-existing concept of query flavours.
Another pattern distinct to above may be to allow entities in a system to mark themselves as being indexed:
const entity = this.someQuery.current[0];
const entityId = entity.read(IdComponent).id;
entity.index(entityId);
// in another tick of the game loop
const entityId = someListOfIds[0];
const entity = this.queryIndex(entityId);
In either case: Just wanted to share those ideas as I've been thinking about this a little bit in the context of my project ๐ Keen for any and all suggestions from your side independent of these of course, including if we're not wielding the existing API surface of becsy
well enough / missing something which would suit the above use case.
In short: We need a way to refer to performantly refer to entities by identifiers stored in a specialised data structure.
Thanks in advance for all your help!