By	Casey Muratori

Many of you wrote in to describe the first part of this Lister Panel series as, and I quote, “A lot like the first book of Lord of the Rings: there’s a hobbit and a wizard, which is cool, but mostly everyone just walks around talking about stuff instead of actually fighting.” And many of you added, “I hope the next installment is more like The Two Towers, where there’s tons of armies and shit.” Well, I never read Lord of the Rings. Frankly, as soon as a book starts putting apostrophes in the middle of proper names, I’m out. But in the interest of pleasing all the people all the time, I will absolutely do my best to make sure this article has all the epic battle scenes that you have come to expect from my Witness Wednesday series while still retaining the hobbit/wizard dynamic that made the previous article so approachable for young audiences. So, Karl the Hobbit looked out across the battlefield of… D’ar-gar’ith, let’s say… which had a lot of important historical significance which I won’t go into it right now but trust me it’s wicked intricate, and anyway he saw lots of clashing armies that were totally doing all these badass moves and it was amazing and everyone was casting spells but the good army was losing so Karl said to his wizard friend Gary, “I must implement the update function for The Lister Panel, or the battle will be lost!” And lo did he then open upeth his Emacs window and starteth typing.

The Lister Panel lists entities. That’s what it does. So naturally, since I generally try to work from basic implementation upwards as much as possible, the first thing I actually started typing was the function that picks the entities shown in the list. I wasn’t sure how many entities would be involved in The Witness by the time it shipped, so it seemed plausible to me that, in an extreme scenario, just filtering the entities might take some time  —  probably not on the order of seconds, but possibly on the order of hundreds of milliseconds, which would drag down the framerate if it was done every frame. So I wanted to make sure that updating the list of entities wasn’t something that had to be done every frame. At the same time, I had some features I wanted to implement that would actually be much cooler if they did update every frame, so I also wanted to make sure that it could update every frame if you wanted it to and it wasn’t too much of a performance hog. So I started off by writing a very simple update function:

As you can see, it is a very straightforward function. If the panel is set to update automatically, then it updates by looping over all the entities and seeing which ones “pass the filter”. The results are placed into viewing_ids, a permanently stored array that uses The Witness’s standard array storage template. Much like I mentioned before regarding the naming of variables and structures, I try to use the utilities that are standard in whatever codebase I’m in unless there is a clear reason not to. That is also why you see that unusual “Foreach” construct: it is how Jon writes his for loops. It is basically a macro that is designed to automatically loop over the contents of his standard array template, which is also used for the “all_entities” array. I figure, since Jon et al has to maintain this code, using constructs familiar to him makes it a little easier, and that’s always a good thing. One thing that does warrant comment here, though, which has nothing to do with Jon’s coding conventions, is the “current_settings” bit. Since the Lister_Panel is a class, as per The Witness’s editor architecture (there is one class per panel), I could just shove everything in that class. But instead of doing that, I instead did this:

Now, I know what you’re thinking. You think I’m so totally crazily against object-oriented programming that I can’t even bring myself to store data in something called “class”, so I have to make my own “struct” outside it to hold the data. But I swear it’s not that. What I was actually doing was starting to “bank” my data. This is not that common of a thing for me to do in general code, but in editor code, I actually do it fairly frequently. The idea is that if you have a bunch of variables that determines how a piece of code behaves, sometimes it is useful to be able to switch them around en masse. In editors this is particularly common because editors often have lots of modal options that are designed to save users time by switching something into one mode, doing a bunch of operations that can be done in that mode quickly, then switching into another mode, and so on. So, since I know that the Lister_Panel is going to be the kind of thing that will have lots of modality to it, I just put all the state variables for user-controlled behavior into the Lister_Panel_Settings struct. Normally, if I wasn’t sure about that, I’d just put them directly in the class, and move them out later when it became clear that modality was necessary. But since I knew it was going to be necessary, I just saved myself some typing and put them in there to begin with. Now, if you look back at the update() code, you may be wondering what “passes_filter” does. So was I at the time I wrote it. Since I knew the Lister Panel needed to have a variety of ways it could pick which entities it was going to list, I knew there would have to be some concept of filtering, but when I wrote the update function I didn’t actually have any idea what that would look like. So in classic top-down C coding fashion, I just typed “passes_filter” and figured I’d pass the setting and the entity and get back a boolean that said whether it should be included. So the next step, to get things working, was to write passes_filter():

Since I knew that I was going to have to emulate the original Lister Panel behavior, the one thing I definitely knew I would have was filtering by type. I also figured I would want to extend that behavior by allowing filtering by more than one type at a time. So instead of just having a single selected type, I decided to make an array of booleans, one for each type, so I could just set any arbitrary mask. If I were concerned about space, or if there had been an existing utility for it in The Witness code base, I could have made this a bitfield, but I wasn’t, and there wasn’t, so I didn’t. Conveniently, The Witness has a unique ID for every type in the system, and more convenient still, they are sequential. This means that mapping from a type to an element in an array of booleans is trivial, hence the direct usage of serial_number_in_memory as an index into the include_type array. What is not quite as convenient is the fact that the maximum value of serial_number_in_memory isn’t known at compile time. So in defining the array, I had two options: use a flexibly-sized array that grows to encompass the largest number, and use a fixed-size array and assert if I’m ever out-of-bounds. All things being equal, I would usually choose the former. While I don’t love flexibly-sized things in game code, because I find they are usually unnecessary and lead to less predictable behavior, in editors I feel like they are often required because, by definition, when you are editing things, a lot of sizes are in flux and bounds cannot usually be estimated or guaranteed. That said, in this case I actually didn’t choose a flexibly-sized array, I chose a fixed-size array:

with an assert:

As you can see from the TODO I put in the code, I wasn’t super happy with this decision, but I went with it anyway. Why? The reason is because, frankly, I’m not super comfortable in The Witness codebase. A lot of the stuff is foreign to me, and I don’t have total confidence in my ability to predict what is going to happen with various utility classes and so on. In my own codebase, I know I have options for flexibly-sized array things that can be copied around in predictable ways that will be fast in the ways I need them to be, not leak memory, and will clean themselves up at times I understand and in the ways I want them to. But in a foreign codebase, where I’m not so well versed, I don’t always know what all the assumptions are. Since this the Lister Panel rewrite was done in a very short amount of time (less than three days, I think), I did not want to be introducing any unknowns. So I opted for the fixed array size. Fixed arrays have the wonderful benefit that, as long as you know you never write off the end, they are totally foolproof and there are no surprises. It’s just like any other variable. And, as a bonus, unlike dynamic arrays, it clears to zero with everything else when you do a = {0}, so you don’t even have to know about codebase conventions like whether or not the C runtime library will be available or whether memset() is a good idea, etc. Yes, this is just me being overly cautious, and I’d be totally fine if someone came through and replaced it with one of the utility templates if they were sure it had all the init, copy and shutdown semantics right. But I didn’t really want to be the person to do that, because like I covered in previous articles, I have been surprised by the way The Witness codebase did things in the past. Unlike the viewing_id array, I knew this array might be copied around, stored to disk, created and destroyed often, and other sorts of things that were more subtle than just a single array that never really needed to be cleaned up or copied at all (panels exist for the lifetime of the app). With the fixed array in place, and the update function filtering entities by type, I needed a good way to manipulate it. Compression-oriented programming is always easy when you have a large set of compression options that you’ve mastered, and a bunch of code that does what you want. But often times during development, even if you have the former, you don’t necessarily have the latter. A lot of programmers  —  including myself, more times than I care to admit  —  end up plowing through these situations by just guessing at what the interface should be and then moving on. The much smarter thing to do is to take the time to actually write usage code if you don’t have it available. It’s not as good as actually having a completely working system you can compress, but it’s the next best thing, and much better than guessing. So one thing I often do is just type out what I want it to look like when I do a bunch of things that I might plausibly want to do:

Nowadays, I actually do this sort of thing very often. When I get to a point in the code when I am working on something and I’m breaking it into functions but it’s a little too early to really be sure, I just stop and make a bunch of usage code first. It doesn’t take very long, and it forces you to actually think through exactly what you want to do and how you want to do it. The right thing to do usually just pops right out at you once you take the time to do this. So, I was pretty sure all I really needed was something that quickly sets all the types to one value or another, and from that I could build all the operations I needed trivially. I went ahead and made this a general function:

Very simple, but it’s exactly the right thing for me to do everything I might need to do with one or two lines of code. Looking at that usage code, it’s also worth noting that you might want to do this:

or alternatively

These are both just ways of wrapping direct access to the type array. There’s no real point in doing this except for debug checking: if type was negative or greater than the array size, there’d be memory overwrite problems, so wrapping the access in various ways allows for a conveniently-placed assertion that will catch it. In this case, I opted not to do that because I knew the chance that I would make that mistake was essentially zero, and this wasn’t even code that was shipping in the actual game. But in cases where I was more concerned about mistakes in ranges, I would definitely have wrapped it in an inline function of some kind that would check to make sure the array accesses were safe. Yes, it is unlikely, but it is usually better to be safe than sorry when you’re talking about code that ships to an end user. So it’s definitely something to consider. And again, in my own codebase, where I am more comfortable with the utilities available, I probably would be using a dynamic thing here that was range-checked automatically anyway.

At this point, I wrote the UI portion of the code, but for the most part I’m going to skip over UI in this part of the series, because I already showed you how that code works in the previous articles. Listing all the types so that the user could select which ones to include and exclude was a simple matter of making a bank of boolean toggle buttons  —  just like the previous articles did  —  one for each type in the system. There was also a row of “quick” buttons for doing allow-all or allow-none. This was all just a few lines of simple code, since the UI system had already been nicely compressed to handle it. Here is literally all of the UI code for the type filtering:

Now, if you remember from last week, there’s still one more mode I need to implement: LISTER_TYPE_MODE_ENTITY_PANEL. In LISTER_TYPE_MODE_LIST, I’m listing types based on user-configured types. But in LISTER_TYPE_MODE_ENTITY_PANEL, I’m supposed to list types based on what is selected in another piece of UI, the Entity Panel. So, how to support that? Well, since I already have everything written, all I really need to do is, in the update() function, I just make sure I sync the include_type array to whatever the Entity Panel has selected as its current type:

And that’s all there is to it.

OK, so, even though we’re only a few lines of code in, the Lister Panel is already half way to doing what it used to do, and it has gained some new features along the way. Next week, I’ll continue building out the system to support the other thing the original system did: layer listing. At this point, I feel like I speak for everyone when I say that this was, as the preamble implied, an epic battle featuring thousands of orcs and demons and elves and shit. Anyone who was not satisfied with the level of pure adrenaline present in the previous article will surely have been satisfied by this week’s riveting, fast-paced action scenes that really brought the visceral combat of Middle Earth to life. Of course, one thing that I’ve always been a little confused by is why it’s called “Middle Earth”. I suppose that’s the kind of thing you actually have to read the books to know. In my mind, “Middle Earth” suggests that it is inside the Earth somewhere, but I don’t know how that’s possible because they have a sky and sun and things like this, don’t they? You can’t see the sun from inside the Earth, that’s just obvious, and I don’t know why the book series is so famous if the author couldn’t even figure that out. You know what? To hell with Lord of the Rings. It’s obviously not quality fiction. Next week I will use The Chronicles of Narnia as a metaphor instead, since they at least understand the basics. Everyone knows you can still see the sun from inside a wardrobe as long as you leave the doors open.