Stop the Lazy Updates

While this could certainly apply to my update schedule on the blog, that’s not what’s on my mind at the moment.

In the engine I’m working on in my free time, have no been bitten twice by middleware that use a lazy approach to positional updates. In my case it was the underlying rendering engine that I used as a starting point (Horde3D) and an otherwise excellent UI system (libRocket).

In both cases the systems had structures of deep hierarchical relationships between elements, which I’ll uniformly refer to as “Nodes” here as that applies well enough. Additionally I’ll refer to positions as being in “Local” and “World” space which is nomenclature more common to 3D transforms, but applies just as well to 2d offsets as in the case of libRocket’s UI elements.

In order to calculate the world position of any element, you must first know the world position of all of its ancestors in order starting from the farthest back.

The “Lazy Update” approach I’ve referred to works by flagging any node that has its position changed and its ancestors as dirty, i.e. needing to have its world position calculated, and sets the local position. The trick employed is that those calculations are done when the world position is requested. This is convenient in that it doesn’t require any management from the end user and “Just works”, but at the cost of deferring processing to an unknown point in time. Sporadically, seemingly harmless readings of the world position of an element could carry with it the processing time associated with traversing and updating large portions if not the entire hierarchy. This might not sound like much, but you can easily end up with pathological cases where your game entities are reading and writing to those positions frequently enough that you create a significant amount of work for essentially no benefit (especially if you are attempting to maintain a high and consistant frame rate).

UI systems seem fairly innocuous, but they’re just not really. Regardless of whether or not an HTML/CSS or similar system is employed for decorating various elements, you still have a lot of elements to display. Even merely calculating the positions of objects while factoring in padding, borders, etc. can lead to a non-trivial amount of work. A word of advice; don’t think about what’s happening to your cache in these cases… there’s no way it can not be just very, very sad. Sad, sad cache…

Dealing with dependencies of this nature inherently requires management of some sort. Hitting it with a hammer by updating anytime a position is read is not an option if you’re looking for reliable processing times.

Some other approaches are: 1. Calculating the number of dependencies each entity has and then processing those groups in descending order 2. Using a set number of update groups which elements put themselves into, reading data from already updated groups as needed 3. Neither of these approaches solves the problem 100% for every usage case, but you should be managing this based on the needs of your program and not anyone else’s. The temptation is to get tricky and as user friendly as possible, but the key to it all is reliability. In some cases you may be able to simplify the transform representation and simply do away with the ability to arbitrarily parent nodes. That can sound drastic, but in many game object structures you’ll find that parenting occurs rarely if at all. I will concede however that that is way more likely in more traditional arcade-esque games.

At the very core of it all, there is this reality: You’ll never be as angry as you are when you realize that the spike in your profiling is because you read the position of an object.

-r