This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.
Though the previous solution will work well in new designs, we couldn't use it as it was in our engine -- the reason being, as always, backward compatibility. We have to address the last bullets we neglected in the previous section.
For historic reasons, such as J2ME, the engine still works in fixed-point arithmetic -- and supports "non-integer" and negative Z-orders. In addition, the range of possible Z-orders spans the entire integer space - way too many for a single array. Moreover, every object created gets the default maximal Z-order possible (231-1).
Unfortunately, we couldn't come up with a solution to this problem in O(1) runtime complexity and reasonable memory complexity, and had to settle for best-effort approach.
We allow negative an non-integer Z-levels, as well as very high or low values - but these aren't as optimal as natural bounded Z-orders. We also provide a special-case optimization for the default Z-order.
First thing we did was to replace the buckets array with another linked-list. This will allow us to open new buckets for non-integer Z-levels in between "optimized" buckets, or add new large/small buckets on-demand.
We also allocate at the end of the list the last Z-order, for the maximal default entry. Every item in the buckets list holds a list of sortables, and the Z-order it represents.
Initially, the buckets list is initialized with a bucket for each optimized natural Z-order, plus the maximal level. Then, the links of the buckets list holding the buckets themselves are put in an array (the "quick-access" array). As before, we cache the internal structure the linked-list uses:
Buckets in linked-list with quick-access array
This ensures we can always access optimized Z-orders buckets quickly, even when new Z-order buckets are inserted in-between.
When we need to add a new object, we first check if its Z-order is the default order. If so, it is appended to that bucket, which we hold direct reference to. Otherwise, we'll test whether it's an optimized Z-order. If it is, we can simply append it to the proper bucket after looking it up in the quick-access array.
If this is an un-optimized Z-order, we'll fall back to an O(n) search method that will look for an existing bucket with the new Z-order. We simply traverse all the buckets in order, starting from the nearest optimized one, and try to find a bucket with that Z-order. If we can't find one, we'll insert a new bucket between links in the appropriate location in the buckets list:
Opening a new bucket between existing buckets
Support for negative Z-order is similar, except we cannot use the quick-access array, and traversal is done from zero downwards.
One little issue we still need to resolve is discarding empty non-optimized buckets. This can be done while traversing the collection. For instance, a counter could be kept for each non-optimized bucket holding how many times the bucket was empty when traversed. If during traversal the counter is over a threshold, the bucket can be removed.
This allows us to support old games, but give new games that follow the guidelines better performance.
You can find the complete implementation of this collection at https://github.com/mominis/zorder in the FixedPointZCollection class.
First, there's a common conception among game developers that performance bottlenecks are the result of the render process, neglecting the CPU aspect of executing the game's logic. When we first started working the Jelly Jump problem, we were given speculations from the content developers' experiments, and tried finding the problem with the rendering process before we even proved the problem was there.
It took us several hours of finding nothing to stop for a second, ignore the initial testing results we got and start working methodically, finding quickly that graphics had nothing to do with the problem. As developers working a bug, we need focus the bug reporter on what happens, not why it happens. Finding the "why?" is our job.
As a young self-taught programmer, I had a period where I didn't believe in Computer Sciences studies, thinking that in today's world every language already has all the basic data structures and algorithms implemented for you, and there's little need for this kind of knowledge "in the real world". I know some experienced programmers that still think so. But after having my share of problems to solve over the years, I see it more as a 20-80 rule. Looking at our initial optimization attempts, we were able to improve performance by using what Java had to offer. The simple solution took us 80 percent of the way -- which in most cases is good enough.
But as game engine developers, we can't be "good enough" programmers; we need to be the best programmers. We develop applications that should run as smoothly as possible on a wide variety of devices, squeezing our every last bit of available CPU, GPU and memory resources (except when we've got battery issues on mobile devices, but that's beside the point). For most applications, 80 percent is enough, but as game engine developers we must be able to do better -- and for that we must have that extra edge over "non-believers".
In this case, the extra 20 percent made us adopt a different approach altogether, and employ methods from OS-kernel scheduler technology to achieve a better solution. In the end, we're sorting a collection without using any sorting algorithm! Employing "traditional" methods would never have gotten use there. Never underestimate knowledge you acquire, no matter how unrelated to your field it may seem -- that's what makes brilliant moments.