Blog
Bio
The Technician
No Imperfections Noted
The Jeff and Casey Show
Jeff and Casey Time
Casey Muratori
Seattle, WA
Working on The Witness, Part 15
Special Filters
Suppose that you are the star of a 1980s-era murder mystery show. You have just spent the last forty-five minutes, minus commercials, unraveling the murderous plot of a certain language architect. In the ensuing climactic scene, with a grand flourish, you emphatically point your finger at a certain bearded fellow and yell, “So, ladies and gentleman, the person who killed the productivity of modern programmers is in fact BJARNE STROUSTRUP!”
A hush befalls the crowd. All eyes are on Stroustrup. He knows he is guilty. He knows you know he is guilty. What is he going to do? Will he try to deflect blame toward Andrew Koenig? Will he attempt to flee to Mexico, where the authorities do not come down very hard on coding abuses?
For our purposes, it doesn’t matter, because that is not the important part of the story. As the keen readers among you have already detected, the important thing here isn’t Stroustrup’s murderous trail of language modifications, but the pointing.
And pointing, as it turns out, was also critical to the next piece of code I wrote for The Witness’s Lister Panel.
Special Filters
In The Witness, there are entities called “groups” which are just collections of other entities. Normally, groups can be nested inside other groups, and can exist for all sorts of purposes. But in special circumstances, a group is designated as a “layer”.
In the implementation, this is almost meaningless. It is simply a boolean that is set on the group which says “hey, by the way, I am a layer”. But in the UI, these layers are important because they are things which are supposed to show up in a special, easy-to-access view in the lister panel where they can be quickly hidden, shown, and selected.
Last week, I showed how to get the lister to a point where it was listing entities with a type filter, but that doesn’t help when the criteria for filtering is based on data inside the actual entities, as opposed to their type. So I needed to add something different.
As always, the first thing I did was to take a look at the sorts of things I actually wanted to do when filtering. I wrote the code I’d need to use to filter an entity “e” by whether or not it was a layer:
if(e->portable_type == &ptype_Group)
{
Entity_Group *group = (Entity_Group *)e;
result = group->is_a_layer;
}
The code checks to see if the entity is a group, and if it is, it casts down to the actual type and looks at its data. This is generally the kind of place where object-oriented peoples would be very uncomfortable, and would instead want to introduce a virtual function call like “is_layer()” that no entities respond to except for the group entity. In The Witness codebase, that is not generally the way things are implemented, but even if it were, I would probably still use this method and not the virtual function call method.
The reason is because the Lister Panel is a place that is all about intrusively looking at things and making decisions about them, and it is clear and understandable to put the code that does this determination all in one place. If instead these tests are scattered throughout the entity classes as a suite of virtual functions, suddenly it becomes very complicated for someone reading the code to know, say, what constitutes a layer, or even how they would go about modifying what that meant if they needed to.
Moving on, I didn’t want just one test case for filtering, I wanted a few. So I looked for some other things that one might to filter on, like whether or not an entity was “animated” using The Witness’s animation system:
result = (e->animator && e->mesh && e->mesh->name);
I also tried another specific-to-only-one-type-of-entity filter, which was whether or not something was a door that “slid” open, as opposed to “swung” open:
if(e->portable_type == &ptype_Door)
{
Entity_Door *door = (Entity_Door *)e;
result = (door->slides_open != 0);
}
All three of these tests looked nice and straightforward and only involved an entity pointer, so it seemed to me that I should be able to treat them all the same way. The only question was, do I do that with a switch statement, or with a table?
Switch statement vs. table is always a milquetoast decision, because the two are extremely similar and most of the time it’s not clear that there’s a right answer. One looks like this:
switch(the_test_to_do)
{
case test_id:
{
// perform the test
} break;

...
}
and the other looks like this:
void test_function()
{
// perform the test
}

test_array_entry test_table[] =
{
{test_function},
};
In this particular case, I decided to go with the table-based approach, largely because I felt like I might be iterating over the table and dispatching to it in more than one way and in more than one place. While you can still do that with switch statements, it tends to be more difficult to keep the code clean because there isn’t really a place to “attach” data to the various cases of the switch — such as what the name of the test is — whereas the table gives you a convenient place to do that.
But, really, it’s a six of one, half-dozen of the other kind of a scenario and either option is fine.
So, I began implementing the table scheme by writing the code that would use it, but I quickly noticed something important about the way the filter results needed to be processed. Since each filter typically handles only a small subset of entity types, such as “doors” in the case of “doors that slide open”, presumably you don’t really want them to apply to things that aren’t doors. There’s already a type filtering system, so if the user wanted to filter out things that weren’t doors, they could just do that directly. So really, this special filtering system has to be able to deal with three types of results: passes, doesn’t pass, and not applicable. In the case where the filter isn’t applicable, it should just be ignored, rather than treating that case as if the entity should be filtered out, which is what would happen in a straight boolean system.
So, it turns out that the code that calls these special filters is more intricate than you might otherwise assume:
switch(filter_mode)
{
case LISTER_FILTER_MODE_OFF:
{
// NOTE(casey): Ignored
} break;

case LISTER_FILTER_MODE_POSITIVE:
{
int handler_result = NOT_APPLICABLE;
special.handler(e, &handler_result);
if(handler_result != NOT_APPLICABLE)
{
passes_special = (handler_result != 0);
}
} break;

case LISTER_FILTER_MODE_NEGATIVE:
{
int handler_result = NOT_APPLICABLE;
special.handler(e, &handler_result);
if(handler_result != NOT_APPLICABLE)
{
passes_special = (handler_result == 0);
}
} break;

default:
assert(!"Unrecognized special filter mode");
} break;
}
Basically, each filter can have two modes where it is active: filtering for a positive match (“this door slides open”), and filtering for a negative match (“this door does not slide open”). Each of those cases then needs to make sure that it only affects the result if the filter itself reported an actual true or false value, not a NOT_APPLICABLE value. This leads directly to a usable prototype for special filters:
static void filter_door_slides_open(Entity *e, int *result)
{
if(e->portable_type == &ptype_Door)
{
Entity_Door *door = (Entity_Door *)e;
*result = (door->slides_open != 0);
}
}
This way, the filter is a nice, isolated routine, and it only touches the result when it actually pertains to the entity in question. If the checks for the filter don’t pass, the result is never touched and the default NOT_APPLICABLE is passed through.
Now, there is a bit of a snafu here, however, which is that there needs to be some value for NOT_APPLICABLE that makes sense. I used
#define NOT_APPLICABLE -1
but really this is not the safest thing to do. The reason is because the result value that the filters return is an integer, which is often set to the result of a comparison, as with (door->slides_open != 0) above. While most of the time there is no risk of these operations producing -1, thus appearing to report NOT_APPLICABLE when really they were trying to report “true”, it is not entirely out of the question that someone working with the code might do this by accident. For example, the line:
*result = flags;
might plausibly be written by someone trying to filter for “are there any flags set on an entity”, which will work fine right up until all flags are set, at which point perhaps its value actually could be -1, etc., etc. But this was not an eventuality I was particularly concerned about, and since this was a quick-and-dirty piece of editor code, I did not spend a lot of time worrying about how to prevent something like that.
Filter Tables
Constructing a table of these is straightforward:
typedef void Special_Filter(Entity *e, int *result);
struct Special_Filter_Entry
{
char *positive_name;
char *negated_name;
Special_Filter *handler;
};

Special_Filter_Entry special_filters[] =
{
{"group is layer", "group is not layer", filter_groups_must_be_layers},
{"door slides open", "door swings open", filter_door_slides_open},
};
And then using them is a simple matter of looping over all the filters, once during passes_filter() to combine it with the type filtering and produce the actual entity list, and once during the UI display, to actually show all the filters that are available and allow the user to click on them.
Before adding a bunch of special filters, however, there’s something I always like to do in these scenarios that often saves a lot of typing later on. It’s a trivial macro construction that I use whenever i know I’m going to be defining a bunch of functions with the same function signature:
#define SPECIAL_FILTER(name) void name(Entity *e, int *result)
This is one of my favorite types of macros, because it saves a ton of typing while not really costing much in terms of legibility or debugging clarity. With this macro, you can do this:
typedef SPECIAL_FILTER(Special_Filter);
to replace the function pointer typedef, so it will always be properly synchronized with the prototype, and then you can do this:
static SPECIAL_FILTER(filter_groups_must_be_layers)
{
...
}
for every actual filter. This is really convenient, because it allows you to define the function prototype in one place and one place only, and automatically have all your functions and the function pointer type automatically conform with no fussing.
Parametric Filters
With the table-driven system in place, it was easy to implement new filters. But eventually I implemented an entity flags filter that really wasn’t working the way I wanted:
static SPECIAL_FILTER(filter_entity_flag_xxx)
{
*result = (e->entity_flags & xxx);
}
The “xxx”, in this case, might be any entity flag, and in order to support all the entity flags, I would have to keep writing new functions, one for each flag that needed testing. That seemed unnecessarily verbose, so I decided to add a parameter to the filter call that could be set per entry in the table:
#define SPECIAL_FILTER(name) void name(int param, Entity *e, int *result)

struct Special_Filter_Entry
{
char *positive_name;
char *negated_name;
Special_Filter *handler;
int param;
};
By adding it last, I wouldn’t have to do any typing to ignore it on filters that didn’t need it. But now, I could write a generic version of the flag tester:
static SPECIAL_FILTER(filter_entity_flag)
{
*result = (e->entity_flags & param);
}
and all I had to do was append the actual flag I wanted to test to the end of the table entry for the flag testing filter:
{"doesn't collide", "collides", filter_entity_flag, ENTITY_DO_NOT_COLLIDE},
{"doesn't cluster", "clusters", filter_entity_flag, ENTITY_DO_NOT_CLUSTER},
{"doesn't reflect", "reflects", filter_entity_flag, ENTITY_DO_NOT_REFLECT},
...
Technically, the parameter could be used for anything, and I could even expand it to a union if I wanted to support passing an arbitrarily typed parameter. But in practice I did not end up needing anything other than a spare int for all the filters I ended up implementing.
Filter-based Editing
After I had special filters implemented, it occurred to me that it would be quite easy to add the ability to generically edit the properties that were being filtered. In addition to turning a filter on for positive and negative cases, there could also be another filter option which would be “allow me to edit this directly from the entity list”. This is easy to add in the UI, obviously, but to actually implement the editing I needed to add something to the special filters themselves.
It turned out to be very easy to piggy-back editing on top of filtering, just by passing more arguments to the filters. Since the filter code knows how to deal with whatever it is filtering, it is usually quite easy to add code for changing whatever it is filtering when necessary:
static SPECIAL_FILTER(filter_entity_flag)
{
if(op)
{
if(new_value)
{
e->entity_flags |= param;
}
else
{
e->entity_flags &= ~param;
}
note_change(e);
}

*result = (e->entity_flags & param);
}
As you can see, the result is still produced the same way as it was before, but now there is an if() that checks whether the value should be operated on. If so, then it uses the boolean new_value to determine whether it should switch to a positive or negative value relative to the filter. The note_change() call is just something that The Witness editor uses to mark entities that have changed for more optimal undo processing (ie., to prevent diffing all the entities every frame).
Similarly, filters like the one for whether or not a group is a layer can use the operation to toggle that as well, even though it is a different type of modification:
static SPECIAL_FILTER(filter_groups_must_be_layers)
{
if(e->portable_type == &ptype_Group)
{
Entity_Group *group = (Entity_Group *)e;

if(op)
{
group->is_a_layer = new_value;
note_change(e);
}

*result = group->is_a_layer;
}
}
Both are nice and concise, and have the added benefit of reusing the checks for entity type if they were already necessary for performing the filtering.
Since the filters still work exactly the same way, the code that runs the filters doesn’t need to be touched, other than to pass “false” as the new op parameter. In the interface code, editing can then be enabled trivially like this:
{for(int special_index = 0;
special_index < NV_ARRAY_SIZE(special_filters);
++special_index)
{
if(current_settings.special_button[special_index])
{
Special_Filter_Entry &entry = special_filters[special_index];

int handler_result = NOT_APPLICABLE;
entry.handler(entry.param, e, false, false, &handler_result);

if(handler_result == NOT_APPLICABLE)
{
layout.nub(entry.positive_name);
}
else
{
if(layout.push_button(entry.positive_name, handler_result)
{
note_operation_name(handler_result ? entry.negated_name : entry.positive_name);

int ignored;
entry.handler(entry.param, e, true, !handler_result, &ignored);
}
}
}
}}
I first called the filter without asking to perform any operation so that it can retrieve the result of the filter for the entity being listed. I couldn’t assume that it was positive (or negative, in the case of a negative filter), because I wanted to allow you to configure the Lister Panel so that it could optionally use a different set of filters for picking the entities to list vs. the “filters” that would be used to perform operations.
Once I had the existing value of the entity for the filter, I checked to see whether or not it was a filter applicable to the entity. If it wasn’t, I drew a “nub” in the interface, which is basically a little thing that shows you that you cannot click on it because it is not relevant. But if the filter was relevant, I drew an actual push_button, which the user could press to toggle the state of that entity. If they did, I would re-call the filter, asking it to perform its operation using the opposite value as what it has just returned as the current one.
So, with very little code, I now had an entity list with configurable filters and configurable buttons for editing any of the filterable parameters where that made sense. But, it seemed logical that the user might also want to edit these values en masse for everything listed. This combines the filtering with the editing in a nice way, so that you can trivially do an operation like “find all the doors that slide open and mark them all as invisible”. So I added another row of buttons, before the listing, that were basically column headers, but if you clicked on them, it would edit the value for all of the entities:
{for(int special_index = 0;
special_index < NV_ARRAY_SIZE(special_filters);
++special_index)
{
if(current_settings.special_button[special_index])
{
Special_Filter_Entry &entry = special_filters[special_index];

bool current_state = xxx;
if(layout.push_button(entry.positive_name, current_state))
{
note_operation_name(current_state ? entry.negated_name : entry.positive_name);
Foreach(int id, viewing_ids)
{
Entity *e = manager->find(id);
if(e)
{
int ignored;
entry.handler(entry.param, e, true, !current_state, &ignored);
}
}
}
}
}}
Typing in the code, it was very straightforward except for the xxx part. I wanted to know what the state of the global edit button should be, but how could I determine that? It seemed like it wanted to be some amalgam of the state of all the entities with respect to that filter, where if any of them were positive, it the button would appear as if it were on, and if none of them were, then it would appear off.
Since there didn’t seem to be any particularly clever solution to this problem, I just did the obvious thing and actually used the filter results from iterating over the entities that were being listed, and stored that in an array, one for each filter:
int handler_result = NOT_APPLICABLE;
entry.handler(entry.param, e, 0, false, &handler_result);

if(handler_result != NOT_APPLICABLE)
{
special_states[special_index] |= (handler_result ? 2 : 1);
}
Basically, for each entity, I stored a bit field where bit 1 was set if the filter was negative, and bit 2 was set if the filter was positive, so that anyone in the future could check for any combination of the two and act accordingly. The xxx code above now has a proper way to get the value it wants:
bool current_state = special_states[special_index];
And that completes the implementation of quick and easy editing of filter-based values in the Lister Panel.
Corrections
One of the things I pride myself on in this Witness Wednesdays series is the relentless fact-checking that I do before publication. Each article is fact checked for several months, if not more, before it is finally considered ready for publication. Therefore it is my extreme displeasure to report that there was, for the very first time, a slight factual inaccuracy in last week’s article: technically, Tolkien does not use apostrophes in his names. He actually uses dashes and accents.
In my defense, accents are sort of like apostrophes. If you didn’t know what an accent was, for example, you might say, “hey look, Tolkien puts apostrophes on top of his words for some reason” or “why do these French people put backwards apostrophes on top of their words” and so on. Of course, you shouldn’t say that last one because it’s vaguely racist, because it implies that all French people put backwards apostrophes on things, whereas really, when you get to know them, a lot of French people are actually very capable of using apostrophes correctly. I am not racist, of course, even though I said it, because it was hypothetical, and besides, some of my best friends are French.
Anyway, racism and factual errors aside, tune in next week for another error-free Witness Wednedsay where I will continue the construction of the Lister Panel with copious, excruciatingly detailed commentary for your extreme reading pleasure!
- Casey Muratori
2014 June 25
Site design and technology © Copyright 2005-2014 by Molly Rocket, Inc., All Rights Reserved.
Contents are assumed to be copyright by their individual authors.
Do not duplicate without their express permission.
casey muratori
casey's blog - post 23
prev
next
mollyrocket.com