By	Casey Muratori

The problem with the internet is that everyone thinks they’re an expert. That would be fine, if everyone actually was an expert, but the truth is that only I am an expert, so it’s just frustrating. To give a simple example, someone wrote in to say that they were “promised” references to the Chronicles of Narnia in Part 14 of this series, and that Part 15 failed to deliver on that “promise”. Nothing could be further from the truth. This is a perfect example of someone thinking they know what they’re talking about when they clearly don’t. If you go back and read Part 15, you will plainly see that the entire article is all one giant Chronicles of Narnia reference, but because I am actually an expert on the series (unlike the erroneous commenter), I chose to reference something subtle that only other experts would understand. As devotees of the Chronicles know, one of the primary villains in the later books is the snail-mage Shellius Grubb, who often uses his magical powers to entrap the minds of his enemies into long daydreams about things that are completely unrelated to Narnia. This was precisely how I constructed Part 15 of Witness Wednesday, and if you were a true fan of the Narnia books  —  not those horrific movie adaptations  —  you would have seen this immediately. But in addition to being an expert, I am also a professional, so I do not let amateur comments like this deter me from the important task of making subtle long-form references to outdated World War II allegories. So without further ado, here is one of the many famous speeches Prince Caspian used to address his people during the myriad national holidays celebrated in Narnia:

The original Lister Panel didn’t actually display groups of things at all. It was strictly a flat, linear list of entities. So when I updated the Lister Panel to have scrolling displays and filtering options and other fancinesses, it seemed like a good time to add basic hierarchical listing support to bring it more in line with what artists use in packages like 3DSMAX and Maya. The Witness’s entity model already included hierarchically nested groups, there just wasn’t any way to ever see them in a standard “tree view”-style list. To show items in a tree view, obviously you have to traverse them depth-first, because for each item at a certain level of the tree, you don’t list the next item at its level until you’ve listed all of its “children”, and all of its children’s children, and so on. This is the classic case for a simple recursive function, assuming you know that the depth of the tree and the size of the stack aren’t onerous:

Of course, it is always worth taking a moment to think about the assumptions. Every time you call a function, all of its locals get pushed onto the program’s stack. So a recursive call acts like a multiplier on the stack space required to execute the function. If the stack space required for the function is 1k, and the maximum depth of recursion if 100, then you can ballpark 100k of stack space, which probably isn’t an issue on any modern platform. On the otherhand, if the function did something like this:

Now you have a problem. Each invocation of the function requires over 64k of stack space, so a recursion depth of 100 now requires over 6 megabytes of stack space just for the buffer variable alone. This can get out of hand quickly:

Now we’re up to over 65536*1024 = 64 megabytes of stack space per invocation, or over 6 gigabytes for a 100-deep recursion. That’s a (hopefully) absurd example, but serves to illustrate the point that the multipliers all cascade, and you should always be aware of how otherwise harmless counts can quickly combine to yield unwieldy combinations. And, as an aside, it’s worth noting that sometimes your code can end up being used in more extreme circumstances than what you consider appropriate. In The Witness, there was a piece of code I wrote that used a recursive function to traverse some collision data. I did the mental check at the time and knew that it would be safe for all the cases that could happen in the shipping product. But I did not consider what might happen when it was used in other scenarios. And it just so happened that when that code was called in debug mode, where you can fly around and do a bunch of things you cannot do in the release build, the amount of traversal it would have to do could grow considerably and the stack could overflow. The stack, even on PC, is often set to a smaller size than you would think. I ended up having to change the code from recursion to a loop with explicit storage. So really, it can often be better to be safe than sorry with this kind of thing. For the hierarchical entity listing, I was confident that recursion was OK, primarily because the depth of recursion is guaranteed to be very low. Artists generally cannot deal with groups that are nested inside other groups hundreds of times deep, so the maximum nesting level tends to be in the 10s at the very most, nowhere near the 100s, and the stack space per invocation in this case was negligible.

I knew the first step to making the hierarchical entity listing actually behave like a normal tree view was to add conditional expansion of the children, since the only thing that really makes tree views more usable than straight lists is their convenient collapsibility. So I needed to write something like this:

But the problem is, whether or not a group entity is expanded in the Lister Panel isn’t really something that should be stored on the entity itself. First, it would prevent ever having more than one Lister Panel, because the group would expand and collapse in all the lists at once if there was just one notion of “expanded” state. Second, as a policy, it invites disaster by suggesting that everyone who ever needs to do anything with entities should just dump that data into the entity itself, which bloats the class and takes up a lot of space unnecessarily, not to mention making it very hard to read and understand what an entity class contains. So I chose the more localized approach of having the Lister Panel store the set of entities that were expanded in its listing:

When I say “set”, I actually mean the logical notion of a set, and not the STL set class. In the case of The Witness codebase, it actually has very few fundamental algorithm utilities, and so there isn’t a notion of a “set”. But there is a hash table, and a hash table can obviously be used to store a set by just using the key part of the hash and ignoring the data part: if the key is found, then the entity is expanded in the Lister Panel, if it is not found, then it is collapsed. Nice and simple. As an aside, if you’re looking at this code and wondering why the return value for expansion_button() wasn’t designed to be something that could be used cleanly in this case, I can elaborate a bit on that. First, the common case for expansion_button() is actually the case where there is just a boolean that stores the expansion state:

So the code is squeaky-clean in that case. In the case with the hash table, different work needs to be done depending on whether expansion or collapse happened, and, more crucially, work only happens when the state changes. In order to write this cleanly, you would have to return whether or not the state was toggled:

Unfortunately, this makes the common case a little uglier:

So I preferred the prior way. It’s conceivable that you might introduce a second function so you can have it both ways, but that seems like overkill unless you anticipate having a lot of both cases in the code, which isn’t the case with The Witness.

I now had a Lister Panel that could list things hierarchically, but it couldn’t actually perform its filtering when things were listed hierarchically, since I had not yet put in any code to call the filter. It may seem like an easy addition of just calling the old “passes_filter” call at each step of the hierarchy, but doing filtering that way has a drawback: if you want to, you can’t actually display the parent groups of things that are included in the filter unless the parent groups are also included in the filter. In other words, say you want to see all grass entities in the world, but you want to see them in a view that shows the complete hierarchy leading up to each grass entity. Ie., if a grass entity was inside a group, you want to see that group expanded and the grass entity inside it, but you don’t want to see any other groups or any of the non-grass entities inside the group. This is a pretty common operation to want to do, since often times you want to manipulate the groups that things are in, but the only way to find those groups is by talking about the things that are in them. So filters are usually best written on non-groups even if you want to manipulate the groups themselves. Filtering like this is not something that can readily be performed during a depth-first walk of the hierarchy, and even if it was, it’s not clear that the code should work that way, since part of the idea behind the Lister Panel was that the rendering code wouldn’t iterate over all the entities all the time, it would only iterate over the filtered entities as found by the update() function, to ensure that it could still be used if the total entity count got too large. So what I needed to do was write a prepass that went through the filtered entities and figured out what groups should be “pulled in” by the filtered entities if the Lister Panel was set to a mode where the hierarchy was always supposed to be shown. There is a very easy way to write code like this in a structure where it is easy to ask what the “parent” of something in a hierarchy is. It is related to (but simpler than) the “disjoint set forest” data structure, which I highly recommend reading about if it’s not already in your wheelhouse of programming tools. The idea is simple: iterate over all the entities that you want to display. For each one, check to see if you’ve processed it already. If you haven’t, walk its pointer up to the root of the hierarchy, processing each entity along the way. This ensures that you visit each entity only once, that you never visit any entity other than the filtered entities and their ancestors, and that you always visit all ancestors of the filtered entities:

During this iteration, I also keep track of a “top_level” array, which stores any entity at the root of the hierarchy. It checks the Lister Panel setting to see whether or not entities are supposed to be listed hierarchically, and if they aren’t, it just adds everything so it will be listed flat. Otherwise, it only adds things at the root. Now, the Lister Panel also allows you to set whether or not you wanted to “pull in” all the groups of the filtered entities, as I mentioned before. You can see in the loop above that it only continues looking for the parent if that setting is set. If groups aren’t being pulled in, you have a situation where the loop above doesn’t actually add everything to the top_level that might need to be when the Lister is set to a hierarchical display. A secondary loop makes sure that entities whose parents aren’t included in the listing get added to top_level:

Now, this seems rather inefficient to me, because I should think you could cleverly fold this logic in to the previous loop and avoid a second iteration. Present Me suspects that Past Me was writing this code in a hurry (which I was) and either didn’t realize the loops could fold together, or more probably, didn’t want to spend the extra time to do so. I will refrain from criticizing past me for the moment, but I would definitely suggest casting a slightly disapproving look in the direction of this code. I am casting just such a look right now, in fact.

And so, fair citizens of Narnia, with the possible exception of the Lion, because we are not on speaking terms at the moment, I would like to thank you  —  on behalf of myself and the King of Narnia, whom I assume exists, but, much like Lord of the Rings, I did not read this series either so I’m not entirely sure  —  for attending this glorious Witness Wendesday event! Return, fair subjects, to the wardrobe area next week for another invigoratingly verbose excursion into The Lister Panel.