Observations from porting Kran a few times

[VincentToups]

Hi, paldepind, I thought I'd post a few observations about the library that I've developed from porting/modifying it a few times.

First: it seems like the most likely place for bugs to crop up is when the every function side effects in such a way as to modify the linked list of entities in the current system. As far as I can tell there isn't any obvious way to make sure that a given execution of every over all entities in a system actually covers all entities that may be added during the activation. This was a particularly clear problem in Cljan, but I only noticed it clearly in Scran. Scran's approach is to detect if the current entity has been removed from the current system, and if so, to iterate backwards over the already visited entities, looking for one still in the system, and restarting iteration from there.

This covers most cases but obviously an intrepid user can produce pathological every functions which, for instance, delete and add nodes in a complex way so as to cause some nodes to be visited twice and others not at all. I believe I encountered some strange behavior in Kran where some iterations mysteriously terminated early that may be related.

Second: I have come to understand entity component systems, and Kran and its derivatives, as performance optimized object oriented systems of a kind where dispatch is optimized by recognizing that membership in particular systems (the analog of classes) changes relatively infrequently and is easy to calculate. That is, Kran-like systems spend a lot of time calculating what systems entities belong to and moving them into and out of systems so that the most common case: executing particular behaviors on these entities, can be done with very little overhead: simply traverse the linked list.

However, we can generalize and empower this model considerably by abstracting the membership and application steps. Imagine if, during system creation, instead of providing a list of components, we provide a function which takes the component array of an entity and returns whether the entity belongs in the associated system. In this way we can generalize system membership beyond just the test whether the intersection of the system's components and the entities components is empty. Since membership changes infrequently and at known times, we can get away with this, performance wise.

What remains is to instruct Kran how to call the every function on the elements of the system. Another function can be provided which transforms the entity into a list of values to which every is then applied. Again, we don't disrupt the performance benefits of the system as long as this function is simple, for instance, it extracts and enlists certain components.

With these two changes, Kran, though, becomes significantly more powerful: it would be possible, for instance, to define a system as including entities which have components X, Y but NOT component Z, which is currently impossible. Other tricks are probably also possible!

I'm considering adding this functionality Scran and Cljan. What do you think?

Finally, I've personally found it useful to the iteration primitives of Kran directly to the client code, in the form of map-system, reduce-system, and for-each-system, which have the obvious functionality. This sort of makes every of less central importance: it just serves as the default behavior of the system. I think that is all!

[paldepind]

Hello Vincent, thanks for sharing your observations.

I actually don't think I put much thought into how every functions might modify the list of entities they're iterating over. I implemented the forEach on the linked list in a way so that the callback function could potentially remove the currently processed entity from the system without problems. That, I think, covers most cases.

But, from the top of my mind, I think a possible bulletproof solution would be to delay/batch all changes to the systems entity list until after the every has finished. Thus conceptually the every function is called for all members of the system at the time before the iteration through the system is initiated. You'd be able to change the systems members all you wanted but theses changes would only be visible after the last call to the every callback. How would that cover your use case? Do you have a need to have the changes applied while in iteration over the system members?

I have come to understand entity component systems, and Kran and its derivatives, as performance optimized object oriented systems of a kind where dispatch is optimized by recognizing that membership in particular systems (the analog of classes) changes relatively infrequently and is easy to calculate.

I'm not sure. If I fully understand what you mean by this. I consider traditional objects in OOP as a mean of encapsulating data and the functions that operates on the data (properties and methods). Class hierarchies then makes it possible to add further data and function to already existing objects. In other words data and functions is tightly bound! Breaking this tight coupling is one of the biggest advantages to entity systems.

That is, Kran-like systems spend a lot of time calculating what systems entities belong to and moving them into and out of systems so that the most common case: executing particular behaviors on these entities, can be done with very little overhead: simply traverse the linked list.

Yes. Absolutely. This is something that every entity system has to do. Optimize system execution in favor of adding and removal of components to entities. This is one of the things I spent the most time on getting right when I wrote Kran.

However, we can generalize and empower this model considerably by abstracting the membership and application steps. Imagine if, during system creation, instead of providing a list of components, we provide a function which takes the component array of an entity and returns whether the entity belongs in the associated system. In this way we can generalize system membership beyond just the test whether the intersection of the system's components and the entities components is empty. Since membership changes infrequently and at known times, we can get away with this, performance wise.

This is a very interesting idea. Actually Kran tests whether or not a sysem's set of components is a subset of an entity's set of components. Can you give an example of when this test is too limiting? Doing what you suggest would hurt performance. Currently when adding a component to an entity the components collectionsRequieringComp property is used to improve the performance of the add. This makes adding components quite a bit more efficient.