Querying for multiple components at once

[pmrv]

EntityManager.{components_for_entity,pairs_for_type} now take a variable
amount of component types. When only one type is given they should behave
exactly as the old version and if not the single component instance is
replaced by a tuple of component instances in the order of the types given.

Since I have some free time at hand at the moment, I just went ahead and implemented this one.

[seanfisk]

This feature is pretty awesome, and I can definitely see it being useful. I like it a lot. However, I'm not convinced that the API is totally there.

A main concern with ecs is speed: the framework needs to be fast. That's why benchmarks are so important (and why we need to write them!). Adding a branch into a function that's going to be called every frame will probably be significant. I think I'd rather have another API call, maybe the plurals of both of those functions. As I said, I can't back any of this up until we have benchmarks.

I'm sorry I haven't been as responsive as I should. I'm finishing up my Master's degree right now and it's coming down to the wire. I want to do some more work on ecs including benchmarks, etc. after I graduate in about three weeks.

To summarize: Without benchmarks to confirm, I would be more comfortable merging in these features as separate functions. This would allow users to avoid the branch penalty and possibly result in a cleaner API (totally subjective, of course).

[pmrv]

The branching could be avoided, at the cost of always returning tuples even when only one component type is given. The code I added in the len (…) > 1: branches also works when only one component type is given. This would break the current API, but would make it feel more consistent to me. But I see your point in having to benchmark all of this and actually like the idea of being able to clearly distinguish between these two cases. Guess I'll just add another branch for this the next couple of days and then try to get some benchmarks going. Though the semester just started here and I'll be a little bit shorter on time, too. And don't worry about being unresponsive, a Master's thesis is obviously more important.

[seanfisk]

OK, yes, I see what you are saying. I'd have to get back into the code a bit more, but I think that always returning tuples might clutter the API a bit.

I don't mind introducing API-breaking changes right now, though. I'd like to follow Semantic Versioning, and that allows for making API changes up until 1.0.0. It's going to be a while before 1.0.0 is released, I would think.

Thanks for your work and suggestions. I'll be getting back into it soon. Good luck with your semester!

[pmrv]

Toying a bit with the timeit module, things look bleak for this patch, honestly. My pairs_for_types seems a factor 100 slower than the original version, components_for_entity is at about two. So for now I just opened another branch for a version which has your original functions plus mine. But I actually like the code less and less the more I look at it, so I'll try to come up with something nicer and faster in the next couple of days.

[tivek]

I've experimented a bit with the Artemis way of bookkeeping: every entity has a bitmask which keeps track of its component types, each bit corresponding to a particular component type. This bitmask is an integer stored within the entity (alternatively, it lives in a separate dict within the EntityManager, but I found that to be slower). Then the multiple component query function becomes

class EntityManager(object):
    ...
    def pairs_for_types(self, *component_types):
        try:
            mask = self._build_mask(*component_types)
            storage = tuple(self._database[ct] for ct in component_types)
            shortest = min(storage, key = len)

            return [(entity, tuple(comp_by_type[entity] for comp_by_type in storage))
                    for entity in shortest if entity._bits & mask == mask]
        except KeyError:
            return []

Depending on the number of entities, for one component type this function is "only" an order of magnitude slower than the original one. It also scales quite reasonably with the number of component types in a search. However, my test makeup might be different than yours @ponderstibbons , since my own set intersection implementation was in the same ballpark. The set intersection starts to fall behind for anything more than 100 entities, in my case with a random composition of 20 component types. Also, did you take care to make a list from the iterator returned by the original EntityManager.pairs_for_type()?

Downsides: It is a somewhat intrusive solution. It requires updating of bitmasks at the point of adding and removal of components.

On a different note, one could argue that within a typical game frame likely no components are added or swapped out. (Depends on the type of game of course: in an action-packed platformer maybe every tenth frame sees entities/components get created/removed, but in a move-based game the state is changed after every move.) This means that multiple-component queries could be cached, which should speed up the update loop. A removal or addition of a particular component type can invalidate all involved queries, at which point those should be either run again from scratch or "fixed up" in place. I'll see what I can whip up.

[pmrv]

I like this approach a lot better than my version and would very much like to see the code you got on that so far.

For the benchmarks I used something like for _ in entity_manager.pairs_for_type(...): pass, which should be equivalent to making a list of it. But I don't have much experience in such things so it's likely I made an error somewhere (or your set intersection is just better than mine).

[tivek]

Sure, I've just uploaded the branch with multiple component query: https://github.com/tivek/ecs/tree/multiple_component_query. Please take a look. If you and @seanfisk find it useful, hopefully it can be merged.

I've decided to keep component bitmasks of entities in the EntityManager and not within the Entities themselves. This is because I saw a performance increase when the Entity class is abandoned in favor of simple integer IDs. You can see that branch here: https://github.com/tivek/ecs/tree/integer-entity

[pmrv]

Cool, I like it. I just added a pull request to your repo which contains the other change I made in this request.

Also could you add the benchmarks you used, just so we have something we can use as a starting point or reference in the future?

The integer IDs also look good to me, but again that's up to @seanfisk.

[tivek]

Thanks, merged!

My benchmarks are currently a mess, but hopefully this weekend I will find some time and make them nicer for a commit!