Allow sprites to be renumbered

[stevesims]

Sprites are always drawn in numerical order, low to high, so higher number sprites always get drawn on top of lower numbered sprites. The nature of how hardware sprites work is that they will all always be above software sprites.

There is no mechanism provided to renumber sprites, or to shuffle their order.

Currently if a program wishes to adjust the drawing order of sprites, they need to redefine the sprites affected. As sprites with no frames defined or those marked as hidden, users can make gaps in their sprite lists, which can help with this.

To better aid programs adjust the drawing order of sprites we could consider adding APIs to help with sprite renumbering.

The sprites list in agon-vdp is currently a plain C array of Sprites objects. To aid shuffling of sprites, this could be an array of pointers instead.

Possible APIs to add would be ones to "swap" two sprites, "delete" a sprite from the list, and "insert" a sprite into the list. Inserting or deleting would effectively renumber sprites. Deleting a sprite would need to move all sprites after that one down a slot and insert a new sprite at the end of the list. Inserting a sprite would need to move all sprites from the selected slot up one, deleting the last in the list, and inserting a new sprite at the selection spot.

A question that would need to be thought about here is whether inserting or deleting a sprite should affect the number of active sprites. For efficiency, a case to be made to leave the number of active sprites the same, however deleting a visible software sprite would need the sprites to be hidden to ensure that they get properly erased. Inserting a sprite may also push a software sprite outside of the active range too, so if the final sprite in the list is a software sprite that would also need to get erased.

Swapping sprites would have similar problems, as if a visible software sprite is swapped to be outside of the range of active sprites that would also need to be hidden.

Changing the number of active sprites always forces all sprites to be hidden before the number of active sprites changes which, when software sprites are being used, is a fairly costly operation.

[HeathenUK]

Can I suggest that rather than introducing the concept of re-ordering the sprite ID (and via this, altering the z-order), we instead introduce the concept of the "layer number" for each sprite, defaulting to the same as the sprite id (if nothing else for backward compatibility) with layer number capping at 255 just as sprite id is. Equal layer numbers would offer no guarantee of z-ordering.

This has the advantage of allowing you to group sprites of a similar nature together in one layer, and of not needing to worry too much about theorising about swaps and inserts.

What do you reckon?

[stevesims]

@HeathenUK this is an interesting idea, and I can see the appeal. The proposed approach of setting a "layer number" for a sprite is, essentially, very similar to how the z-index property in CSS works for elements on web pages, where elements with higher values get positioned over those with lower numbers. It would be pretty easy to understand.

I must admit that my initial reaction was one of resistance - but now that I've thought through the problem more thoroughly I've come around to the idea and think this is probably the way to go. 😁

Something that is important to understand is that with sprites drawing performance is important, especially for hardware sprites.

Currently the VDP has a simple sprites array of 256 Sprite objects, and we have a number that indicates how many of those should be considered "active". There are also effectively two ways in which individual sprites can also be hidden. Drawing sprites, whether software or hardware, is a matter of iterating over the "active" sprites, checking whether the sprite should be drawn, and if so drawing the sprite.

Performance is most important for hardware sprites. For every row of the screen, the scan-out code iterates over the active sprites array. If the sprite is a hardware sprite that is visible on the current row it will draw the corresponding row of the sprite into the scan-out buffer at the appropriate X offset. As this happens on every row, it needs to be pretty efficient.

Drawing software sprites uses a very similar approach, but only needs one iteration over the active sprites array, and uses a simpler check for visibility.

No matter how we allow the drawing order of sprites to be changed, we need to ensure that our hardware sprite drawing loop can stay as efficient as it currently is, and ideally the software sprites drawing loop too. This essentially means the list of sprites used by the sprite drawing routines needs to stay in drawing order, as working out a different order at drawing time would be expensive.

Currently the underlying sprite handling in vdp-gl is currently written to expect the sprites it is given to be a single block of memory. This would need to change to be an array of pointers to allow the sprites to be re-ordered. This won't be hard - the routines inside vdp-gl that work with individual sprites call a getSprite(int index) function to get a pointer a sprite, so the implementation of that function would just need to change to be a pointer lookup instead of a pointer calculation.

A "layer number" approach would just mean that when the layer number in an individual sprite is changed, the list of sprite pointers would need to be updated to reflect the new drawing order. This wouldn't be a super-cheap thing to do, but overall is relatively inexpensive, and as it doesn't need to be performed at draw time would be an acceptable cost.
Using only a "layer number" approach has the advantage of removing concerns about the impacts and implications of swap/insert/delete.

Software sprites would still need to be hidden and re-shown when a layer number is changed, owing to how they get drawn - as each sprite is drawn individually, the copy of the background they keep to restore when they are hidden can actually include pixels from other software sprites.

As for defaulting the layer number to be the same as the sprite ID, that I'm not quite so sure about. My inclination is to default them to zero. The sprite pointer list could be sorted based on both the layer number and ID, ensuring that we always have a guaranteed drawing order.

(In writing this, I've just realised that the nature of our sprites API is that as the maximum number of "active" sprites is 255, our sprites array is one larger than it needs to be, as the sprite at index 255 can't actually be shown. :D )

[HeathenUK]

Agree that defaulting to layer 0 and then sorting the array first by layer and then ID both solves backward compatibility AND gives you more clarity on what order same-layer sprites will draw in.