Game Programming

ECS Concepts – Part 5: Entity Filtering

by Cory on November 10, 2017 12:35 AM

Ok so this might seem like a weird topic to start talking about systems in depth, but filtering entities is one of the first things you’re gonna want to do in a system and it’s probably the only system related topic that I can talk about in complete isolation. Trust me I got this.

Systems have to operate on entities, but before they do that they need to figure out which entities to modify. At first glance, this is an easy thing to do. Given my previous Entity/Component implementation, all one needs to do is to take a reference to a given Entity, and use the get() method to retrieve the relevant components and check whether or not the returned component pointers are null. Easy peasy right? I bet that’s what you were thinking about how to do it. Too bad, I DON’T DO THINGS THE EASY WAY. Can we do better???? (Yes.) I believe that with slightly more advanced techniques, we can speed up the performance (I think? I haven’t actually checked) and make it syntactically more user friendly. The second one is the big win in my opinion, since it reduces the amount of repetitive code you would have to write and makes the user facing portion of the code easier to read.

Entity Filter User Interface

Let’s imagine that we are inside a system and need to tell it which kinds of entities it needs to keep track of. We need to figure out a way to give it a list of data types representing components so that it can do some sort of computation on them. Well, wait a minute, this doesn’t seem so simple anymore does it? You could go with some kludge-y solution like mapping data types to strings (DON’T DO THIS), or a slightly better solution like converting the types to std::type_index and supplying those to whatever is doing the entity filtering. Neither of these options sound too good to me because it’s messy, it’s possible to receive many kinds of invalid and unwanted input, and most of all it requires the user to somehow be aware of implicit assumptions in the user interface (having to do type_index conversions or creating and memorizing a ComponentType to string mapping for example).

Fortunately, you can do “meta computations” of data types very nicely in C++ using template functions. And more specifically, when you want to use multiple template arguments and you don’t know how many there are, you can use a C++ feature called variadic templates. (This link is a pretty nice article about how to use variadic templates by Eli Bendersky, a dude who’s really really good at C++ and stuff).

The syntax for this would look something like:

EntityFilter e;
// call function all_of() supplying 3 template arguments to it
e.all_of<Physics, Velocity, Position>();

I made a class to encapsulate this filtering functionality called EntityFilter. This class can filter() entities, returning a boolean that is true if the provided entity satisfies all the filter requirements or false otherwise. I can also add member functions to configure this filter to select entities. In the above code snippet, I use all_of(), which tells the entity filter to look for entities with Physics AND Velocity AND Position components. In other words, this describes a logical AND expression that operates on class types provided as the template parameters.

I made some other functions called one_of() and none_of(), which correspond to logical OR and logical NOT expressions, respectively. You can add multiple expressions to the same filter to create relatively complex filters:

EntityFilter e;
e.all_of<Velocity, Position>();
e.one_of<Sprite, Circle, VertexList>();
e.none_of<TileMap>();

In this example, we configure an entity filter that looks for entities that have Position and Velocity components; has at least one of Sprite, Circle, or VertexList components; and does not have a TileMap component. (The AND, OR, and NOT expressions themselves are logically AND’d together to get the final result.)

Before I go any further, let me say that I got the concept and syntax from Artemis-odb. In this ECS framework, they have something called “Aspects” (using the same connotation as in Aspect Oriented Programming) which is roughly equivalent to my EntityFilter shit.

Entity Filter Usage

In the scheme of the overall ECS framework, the entity filter object would be a class member of the System class. In the last post, I reference this in a code snippet of the System class definition. It’s actually inside another component called EntitySubscription that I have yet to talk about.

But for simplicity, let’s assume that there’s no EntitySubscription yet and EntityFilter is just a member of System. The entity filter should be configured before the system starts updating, but it can be changed at any time. My recommended usage is to configure the filter in the system init() method of a child class that you inherit from System. This way, you can setup stuff in the constructor and at the top of the init() method and then use that information to configure the filter if necessary. You can also make changes to the filter during run time after update is being called should the need arise. Like so:

void ChildSystem::on_init(Game& game) {
// configure entity filter
this->entity_filter_->all_of<Velocity, Position>();
this->entity_filter_->one_of<Sprite, Circle, VertexList>();
this->entity_filter_->none_of<TileMap>();
}

That’s it! The entity filter is used automatically in the parent System class during update. (This will change a little when I introduce EntitySubscrpitions later). Here is some pseudo-code for how the System class would use the entity filter:

void System::update(Game& game) {
if (!this->is_enabled()) {
return;
}

assert(this->world_ != nullptr);

// handle any queued up messages
this->mailbox_.process_queue();

std::vector<Entity*>::const_iterator it;
std::vector<Entity*> entities = this->world_->get_active_entities();
for (it = entities.begin(); it != entities.end(); ++it) {
if (!this->entity_filter().filter(*it)) {
// if this fails to pass through the filter, ignore it
continue;
}

this->on_update(game, *it); // send passing entity to update hook
}
}

Recall that the ChildSystem class defines on_update() to customize update behavior. And note that the entity filter can be used directly if you ever need to do that for some reason. Use filter() and supply it an entity pointer just like in the above code snippet.

A Quick Digression about Variadic Templates

Before I delve into the implementation of the EntityFilter, let me talk a little bit about variadic templates and some pure programming stuff. So how do you use a template class that can have potentially any number of template arguments you must be wondering??? Well, you need to use recursion and induction. Remember intro to comp sci? Well I hope so and if not tough shit here we go.

The idea is to create at least 2 overloads of the template method that will be accepting variable template parameters:

template <typename arg>
void my_func();

template <typename arg, typename ...args>
void my_func();

The first overload is just a regular template function that takes exactly 1 template argument and it serves as your base case. The second overload is your induction case, that is actually utilizing the variadic template feature. The second overload is matched when you provide this function with two or more template arguments. It peels the first argument off into arg and then has the rest of the arguments in the args list. For this function, you code in whatever you might need to do with the first variable, and then recursively call the function with args. This is the list of template arguments with one less argument than you started with. This will cause the code to recurse until you reach the base case overload which should be written to terminate the call chain and complete the computation as it returns into each previous function call that was made. By the way, this is roughly the process you go through when you write any kind of recursive algorithm or function.

Well that was a bit abstract, so here’s an example take directly from Bendersky’s page that I linked above:

template <typename arg>
arg adder(arg a) {
return a;
}

template <typename arg, typename ...args>
arg adder(arg first, args… rest) {
return first + adder(rest);
}

This example uses variadic templates to create a function to add an arbitrary number of elements together. The aptly named ‘adder’ function’s base case is to just return the single argument when there is only one provided. This should be obvious right? Then the induction overload peels the first argument off and uses the plus operator to add it to a representation of the completed addition of all arguments excluding first. This representation, the adder(rest) call, is the inductive step. When args is two or more, this recursive call matches the second template overload except now it supplies this second function call with one less argument than the current function call. When args is only one element, that function call will match with the first overload and break the chain.

The Expression Class and What it Does

Ok so back to filtering entities. As you’ve seen previously, the entity filter needs to be able to contain many boolean expressions. I’ve created a subclass in the entity filter called Expression to encapsulate a single boolean expression. We want to do what that example just did with the adder, but for template types. For instance, if we want to create an all_of expression (doing a logical AND), we want to iterate through all the types specified in the template, somehow convert them into boolean values, and then combine them into one final value.

I made a class called ExpressionTuple that is a template class and inherits from Expression. (I’ll tell you why I did that in the next section). I’m going to try and go over how ExpressionTuple works piece by piece because this class is where all the heavy lifting happens and it’s really dense and hard to understand when you’re seeing it for the first time, imo. The class definition signature is this:

template <typename ...Tokens>
class ExpressionTuple : public Expression {
// stuff
};

Notice that the variadic argument I’m using is called Tokens. This class has a recursive variadic template method called traverse_tuple() that peels off the arguments one by one. Here’s where it gets a little hairy:

template <size_t N>
using TokenType = typename std::tuple_element<N, std::tuple<Tokens...>>::type;

template <size_t N, typename std::enable_if<(N > 1)>::type* = nullptr>
bool traverse_tuple(Entity& e, bool in_result) {
return this->traverse_tuple<N - 1>(e, evaluate(e.get<TokenType<N - 1>>() != nullptr, in_result));
}

template <size_t N, typename std::enable_if<(N == 1)>::type* = nullptr>
bool traverse_tuple(Entity& e, bool in_result) {
return evaluate(e.get<TokenType<N - 1>>() != nullptr, in_result);
}

Let me start with the TokenType alias. The TokenType alias lets me concisely access members of the class template parameters tuple. Remember that Tokens... is just short hand for whatever the template arguments are from inside the angle brackets. So in ExpressionTuple<Physics, Velocity, Position>, Tokens... expands to Physics, Velocity, and Position. I use this fact to create an std::tuple class that has the same template parameters as the ExpressionTuple class itself. And then I access elements from this tuple using std::tuple_element by supplying an element position, N, and then take the type of the element at this position of the tuple.

// the tuple for ExpressionTuple<Physics, Velocity, Position>
TokenType<0> // gives you Physics type
TokenType<1> // gives you Velocity type
TokenType<2> // gives you Position type

Now on to traverse_tuple. The base case overload is the bottom one, where I use enable_if to match this template member function if N (the number of template arguments in the variadic template) is one. I convert the TokenType to a boolean by calling the get<ComponentType>() (remember this?) from the entity class and checking if it’s not null. Then, I call evaluate(), which is another member function in ExpressionTuple takes 2 parameters—an input boolean from all the previous template parameters you’ve evaluated, and a boolean from the current template parameter. I encapsulated evaluate() into it’s own method because the logical expression is different for the AND, OR, and NOT expressions.

// child interface
virtual bool evaluate(bool has_token, bool in_result) = 0;

So if we want to write an AND expression, the body of this function looks like this:

virtual bool evaluate(bool has_token, bool in_result) {
return has_token && in_result;
}

Relax, it’s one line and it’s just the logical AND. :)

The inductive overload of traverse_tuple() is almost exactly the same except it’s enable_if expression matches if the number of template arguments is greater than one. It also has a recursive function call wrapping the same evaluation step as in the base case. Which overload is called again depends on the number of template parameters that haven’t been peeled off yet. Here’s the full code for ExpressionTuple:

template <typename ...Tokens>
class ExpressionTuple : public Expression {
public:
ExpressionTuple<Tokens...>(bool in_result) : Expression(in_result) {}
virtual ~ExpressionTuple<Tokens...>() {}

virtual bool filter(Entity& e) {
return this->traverse_tuple<std::tuple_size<std::tuple<Tokens...>>::value>(e, this->in_result());
}

private:
// child interface
virtual bool evaluate(bool has_token, bool in_result) = 0;

// private helper methods for folding tuples
template <size_t N>
using TokenType = typename std::tuple_element<N, std::tuple<Tokens...>>::type;

template <size_t N, typename std::enable_if<(N > 1)>::type* = nullptr>
bool traverse_tuple(Entity& e, bool in_result) {
return this->traverse_tuple<N - 1>(e, evaluate(e.get<TokenType<N - 1>>() != nullptr, in_result));
}

template <size_t N, typename std::enable_if<(N == 1)>::type* = nullptr>
bool traverse_tuple(Entity& e, bool in_result) {
return evaluate(e.get<TokenType<N - 1>>() != nullptr, in_result);
}
};

There’s two last things I want to mention here.

The constructor for this class takes a boolean in_result. When you create an AND expression, you need to feed in true as the in_result. For an OR expression, it needs to be false. Basic digital logic stuff. Having a parameter to supply in_result also lets me chain tuples together.

ExpressionTuple has a function called filter() that acts as the public facing interface. When you want to compute the result of some expression, call filter() and it will do traverse_tuple() and calculate the result of running this expression on the Entity and return it as a boolean.

Good god I hope this section was coherent. I was learning about this stuff while I was writing this, so it’s still really cool to me! Out of all the stuff I’ve talked about so far, this uses the most C++ tricks stuffed into the smallest space. And I don’t want this to be some horrible abomination of code that only I can read so I hope this helps anyone who tries to read it. Yes that’s right I’m talking about YOU.

Storing Expressions in the Entity Filter

We’re almost there, but not done yet. ExpressionTuple is a templated class, so that means each ExpressionTuple with a different order, number or type of template parameters is its own distinct type! This means you can’t store them in the same array without finagling it a little. Doesn’t that sound familiar? That’s right, we need to use type erasure again!

That’s why I had a parent class called Expression that ExpressionTuple inherits from. Expression allows me to store these expression tuples polymorphically. The Expression class is where you can find the definition of in_result and it also exposes the filter() interface method. This has no references to template classes at all. The filter method in this class is a pure virtual function that is overridden by the filter method in the ExpressionTuple class. Now I can store all different kinds of ExpressionTuples (and it’s child classes) in a single polymorphic array of Expression pointers. When filtering, I don’t need to know the types of each expression as long as I just need the output of filter().

Additionally, I have child instances of the ExpressionTuple class to define the AND, OR, and NOT expressions. These classes are really simple and are only responsible for feeding in the appropriate in_result and defining the evaluate function.

template <typename ...Tokens>
class And : public ExpressionTuple<Tokens...> {
public:
And() : ExpressionTuple<Tokens...>(true) {}

virtual bool evaluate(bool has_token, bool in_result) {
return has_token && in_result;
}
};

This is the entirety of the AND class. It’s very simple. If down the line, you discover a new type of logical relationship you want to add to filter computations, you can inherit from ExpressionTuple and modify evaluate to do whatever you want.

The Entity Filter, Complete

Let me bring this back full circle. We got ExpressionTuples to evaluate entities using boolean expressions involving component types and a parent Expression class to store all these types polymorphically in a single array for easy processing.

The last thing to do is to pretty things up a bit for the end user. To match the syntax I was describing at the beginning of the post, I made 3 convenience factory methods in EntityFilter to construct AND, OR, and NOT expressions:

template <typename ...Components>
EntityFilter& all_of() {
this->filter_expressions_.insert(new And<Components...>());
}

template <typename ...Components>
EntityFilter& one_of() {
this->filter_expressions_.insert(new Or<Components...>());
}

template <typename ...Components>
EntityFilter& none_of() {
this->filter_expressions_.insert(new Not<Components...>());
}

These push expressions onto the vector inside the EntityFilter. And then we also have the filter() user interface here too, that loops through all the expressions in filter_expressions_ and calls THEIR filter expressions, folds over in_result, and returns whether or not the Entity in question passes all the criteria. And that’s pretty much everything that’s in the EntityFilter class. The rest of the guts is in the nested expression tuple stuff.

Oh and one more thing, there’s a boolean member in the EntityFilter called allow_all. This is used when the EntityFilter is not configured at all and thus has no expressions with which to filter. When filter() is called on an empty EntityFilter, it will return the value of allow_all. This lets the user configure a restrictive filter that doesn’t allow any entities through or a permissive filter that lets everything through when not given any expressions.

Jesus christ, there you have it. I took something really easy and made it incredibly complicated. What I really care about most though is that the user interface is easy and intuitive, which I think I achieved. Right? ...right????? Anyway, I highly recommend looking at this file in it’s entirety on github. You can find it at /engine/ECS/System/EntitySubscription/EntityFilter.h.



This Thought is part of Game Programming

Game programming general topic. I eventually hope to split this into separate ideas exclusively about specific games that I make.

back to the

top