Entity filter

[linonetwo]

There are too many trees in my game, and the system not related to trees wasted too much time on them. O(SxE)

What do you think is the most performant way to implement an entity filter?

Maybe use another object to track '@type' -> id mapping? (I'm using '@type' instead of 'type' in my entity) So we can only iterate through entities of some type, or with arbitrary components. So time reduced to nearly O(S).

What do you think the new API will be?

[linonetwo]

Interesting thing is, most ECS framework is "component centered", systems can only iterate through component of some type.

)

While you actually iterate through entities.

[mattblackdev]

Definitely want to implement this. Two ways I can think of:

1. Allow systems to specify keys
2. Allow systems to specify a filter fn
   Either way the ecs hook should be able to keep track of which entities to pass to each system.

The filter could be initialized as an effect of initialEntities. During each frame systems can call createEntity or destroyEntity as needed. After all systems execute and either method has been called, the filter could be updated. That covers invalidation due to changes in existence of entities.

Problem is as you mentioned, there’s no component manager. In order to know if components have been added or removed, I think there would need to be an addComponent and removeComponent api for the systems as well. Then the filter could be re-evaluated.

There’s also the question of how systems should specify their own filters. I was thinking a filter property on the functions themselves.

What are your thoughts on any of the above?

[linonetwo]

I think it is ok to just pass the whole entity map to param, just like it is doing now. Just like in redux, we also get the whole state in mapStateToProps.

What we want in ECS is a reverse index for entities.

There is a function groupBy in the lodash, who can group objects (entities) by a key in the object (component).

for example:

const entities = [
{ '@type': 'a', component1: 'c1' }, { '@type': 'b', component1: 'c1' }, { '@type': 'a', component2: 'c2' }
]

const componentNames = [ '@type', 'component1', 'component2' ];
const entitiesMap = zipObject(componentNames, componentNames.map(componentName => groupBy(entities, componentName)))

so we can get:

expect(entitiesMap).toBe({
 '@type': [
	{ '@type': 'a', component1: 'c1' }, { '@type': 'b', component1: 'c1' }, { '@type': 'a', component2: 'c2' }
	],
  'component1': [{ '@type': 'a', component1: 'c1' }, { '@type': 'b', component1: 'c1' }],
  'component2': [{ '@type': 'a', component2: 'c2' }],
});

But doing this every tick is resource consuming, if we can use the proxy (just like immer) to know what new component is inserted into the entity, this can be done more efficiently.

[mattblackdev]

Hey I didn’t do what you said but I did what I said. I couldn’t really understand what the ‘@type’ key was for but I made a ‘Filters’ story example. Could you take a look at that and/or the latest commits? Would like to hear your thoughts.

[linonetwo]

I'm just using @type as a "Flag Component" for filtering. If using your latest comment I think I can do something like:

function treeUnderCursorSystem({ filteredEntities: { trees, cursor }}) {
  // do things with tree and cursor position
}

treeUnderCursorSystem.filter = entities =>
  ({ trees: entities.filter(entity => entity['@type'] === 'tree'),
     cursor: entities.find(entity => entity['@type'] === 'cursor'),
   })

This is ok, I barely forget we can add properties to JS function.

But this way seems not saving too much calculation. If we can do some memorization, and let two system share filter, it will be better.

Just like redux connect, it has https://github.com/reduxjs/reselect

Selectors can compute derived data, allowing Redux to store the minimal possible state.
Selectors are efficient. A selector is not recomputed unless one of its arguments changes.
Selectors are composable. They can be used as input to other selectors.

Immer objects are comparable, just like redux, so reselect will work too, maybe we can reselect for the filter. So if two systems share the same filter function , the calculation will be memorized.

But draft.entities is too flat, and every single entity change will make draft change and invalidate the cache...

[linonetwo]

a9120ed#diff-09a97399442da33c8c8ee0de3e669346R132-R141

I see you invalidate filters if add/remove entity/component, this is fair enough I think.

This is in a coarse granular because currently, filters are imperative. If there can be a declarative filter, only affected filters will be invalidated, instead of invalidating all filters.

---

I have another idea for reusing filter:

Currently, the imperative filter's result is stored corresponded to the system. If there were the declarative filter, I think it can be like this:

// get trees list and the first cursor
function treeUnderCursorSystem({ filteredEntities: { trees, cursor: [cursor], movable }}) {
  // do things with tree and cursor position
}

treeUnderCursorSystem.filter = {
  // filter entity with key '@type' and its value is 'tree'
  trees: ['@type', 'tree'],
  cursor: ['@type', 'cursor'],
  // filter entity with key 'position'
  movable: ['position'],
}

Then inside the ecs hook:

function createFilterFunction(keyValueForFilter) {
	return entities => entities.filter(entity => keyValueForFilter[0] in entity && entity[keyValueForFilter[0]] === keyValueForFilter[1])
}

so the filters will be a map:

{  trees: [id, id, id], cursor: [id], ...}

instead of currently a list:

[[id, id, id], [id, id, id], ...]

So when adding a component { 'position': [0, 0] } to an entity, the update to filters can be fine-grained.

Sometimes, a message-passing between two systems is using a new empty component, so adding/deleting component may be a frequent operation in every tick, that's why fine-grained filter memorization is critical.

This is what comes into my mind.

[mattblackdev]

Okay awesome! That makes a lot of sense. I'll work on this when I can. It sounds like a few hours at least. Thanks for the code examples!

[mattblackdev]

Just a heads up, I've been working on this, getting a little distracted by the discovery of this state lib from the author of react-three-fiber: https://github.com/react-spring/zustand.

[linonetwo]

I've seen that before. But I still love @rematch/core , since it supports plugin better. And there are also https://github.com/davidkpiano/xstate providing an interesting mental model different from the redux.

I think the difference between ECS and them is that ECS encourage a looser couple. And provides more caching since it executes at a faster pace. They are similar, but I didn't find many articles about the comparison between redux and ECS.

---

You remind me of xstate, I think I will try combine state machine with ECS in my game.

[mattblackdev]

@linonetwo Hey it's been a while! I hope this finds you well. There have been so many exciting developments in the react-three-fiber ecosystem. There is a cool new ECS lib on the scene as well: https://github.com/hmans/miniplex