Sprite cycling for objects processed in a constant order

[tokumaru]

As I see it, the main reason to update objects in a specific order is to have them interact with each other properly. Objects that can affect the position of others, for example, should be updated first, so their final position is known when the objects affected by those are updated.

As an optimization, it may be desirable to draw the objects as soon as they're finished updating, specially if there's a significant overhead in the process of calling each object, which might require bankswitching, jump tables, and so on. The problem with this approach is that sprites are always output in the same order.

I guess that one of the most basic forms of sprite cycling still works in this case, which is starting from a random OAM position and advancing a prime number of positions each time. The main problems with this approach are:

- no priority control within the same object;
- no priority control between different objects;
- no way to reserve sprite 0 for raster effects;
- poor handling of the case when more than 64 sprites are needed (the last objects to be processed will get dropped every time);

Can anyone think of better sprite cycling techniques that will handle at least part of those problems better than this basic technique? To me, personally, the most important things are priority control within the same object and decent handling of more than 64 sprites, but I'd love to hear other people's thoughts on this.

[dougeff]

I was looking at game code a while back...maybe it was Zelda, that used a table of pseudo-random offsets for sprite cycling.

[rainwarrior]

As an optimization, it may be desirable to draw the objects as soon as they're finished updating, specially if there's a significant overhead in the process of calling each object, which might require bankswitching, jump tables, and so on. The problem with this approach is that sprites are always output in the same order.

Personally I would drop this requirement and proceed from there.

You can put your metasprites and drawing code in its own bank, if bankswitching is a problem. The object's state should already be in RAM after its update, you can read that state from any bank; the update and drawing code need not be side-by-side in banks. (A segment switch could put them side-by-side in your code, though.)

A jump table lookup per-object should be relatively minor compared to a metasprite draw, I would expect?

If you have a lot of objects (e.g. bullet hell), you'll need something more specialized anyway, and I think you're really just asking about something generic here for a moderate number of objects.

You could also impose simple requirements to make the process more streamlined, if appropriate for your game. e.g. Exactly 1 metasprite per object would eliminate the need for per-object drawing code (or you could handle a small number of special cases, if not many need extra sprites).

[Dwedit]

It's not really all that much of an optimization to do the drawing code in the object handling code, you save a load to X and that's basically it.

[tokumaru]

Personally I would drop this requirement and proceed from there.

I was actually expecting you to say this, because of a conversation we had about bankswitching a while back.

I was set on having a bank entirely dedicated to object logic and another to meta-sprites, but I did the math and I'm pretty sure that I'll need more than one bank for the logic. Meta-sprites MAY all fit in a bank, but I figured I'd try the more flexible approach instead of creating a possibly unnecessary limitation.

You can put your metasprites and drawing code in its own bank, if bankswitching is a problem. The object's state should already be in RAM after its update, you can read that state from any bank;

Yes, if all meta-sprites were in a single bank I'd only have to switch banks 1 more time, not for every object.

the update and drawing code need not be side-by-side in banks. (A segment switch could put them side-by-side in your code, though.)

Well, that depends on how other things are designed... My objects have pointers to the animation scripts they're using, and the meta-sprites are inlined in the scripts, so that I can point to both (script and meta-sprite) using a single pointer (don't have the RAM to store the meta-sprite pointer separately, which would be necessary if they were in another bank), and since the logic needs the script data, the meta-sprite data also needs to be there, kinda forcing everything to be together, which actually doesn't sound bad.

It's not really all that much of an optimization to do the drawing code in the object handling code, you save a load to X and that's basically it.

That's quite the understatement... For the simplest possible case, you'd need a new loop, which would involve loading X, incrementing it, testing for the end condition, and checking if the object slots are occupied before attempting to use the data in them. But to make things flexible you'd need to do more, like randomizing the order in which the slots are read, looking up the address of each object's specialized drawing routine, and possibly switching banks. That could pile up fast!

[tokumaru]

So far, I've thought of the following approach:

Before processing the objects, pick 2 consecutive OAM positions at random. These 2 variables delimit the block of used OAM slots, which at this time is empty.

Then, when each object is about to draw itself, it randomly picks one end of this block, causing it to grow up or down.

To me it sounds simple enough and objects would end up in reasonably random positions each time. I'd also have control over priorities within the same object, which is a step up from the basic "prime increment" technique.

There is one big problem though: what to do when the block reaches the edges of OAM? Wrapping around would mean breaking the priorities within the same object. Not wrapping around would mean wasting sprites on both ends.

Then there's also the problem of needing more than 64 sprites, in which case the last objects to be processed would always be at a disadvantage. I considered remembering whether each object got renderedor or not, and having objects that did get rendered last time to "sacrifice themselves" this time in favour of the ones that didn't, but that's sounding way too complicated!

[rainwarrior]

if all meta-sprites were in a single bank I'd only have to switch banks 1 more time, not for every object.

Even if they were only mostly in the same bank it could still be efficient enough. e.g. You can try to group things so objects that will appear together in the game are in the same bank, or when there are multi-bank combinations just make sure the CPU load in that area of the game doesn't break your performance budget.

Like, you don't need the "most efficient" implementation all the time. Optimization is wasted unless you would go over-budget without it.

...to make things flexible you'd need to do more, like randomizing the order in which the slots are read, looking up the address of each object's specialized drawing routine, and possibly switching banks. That could pile up fast!

Everything contributes, of course, but we should only be talking about a handful of extra scanlines each frame. It's overhead, sure, but the bulk of computation should still be drawing the sprite itself. In the end, performance budget control will really be about number of objects. If the extra overhead makes them 10% less efficient, it just means you can have 9 objects at once instead of 10. (Overhead should be measured against the whole object update, too, not just the draw portion.)

So far, I've thought of the following approach: ... (description of approach and various limitations of it)

So the question I'd ask is, how much do you want to sacrifice convenience and ease of use to reduce the overhead? How many extra objects does it buy you? Would you rather have something easy to work with instead?

My usual approach is to make it work the way you'd like it to be, first, without worrying whether it is the most efficient thing (as long as it's reasonable). Test its performance and see if it's good enough before considering sacrifices.

You know more about what your game is going to need than anyone else; there are always things that would normally look like a sacrifice that don't actually matter for a specific game. I'm not a huge fan of generic solutions to these kinds of problems, and it's hard to give commentary/advice from this distance. If you've got a different way you think will work better with your situation, give it a whirl.

[tokumaru]

So the question I'd ask is, how much do you want to sacrifice convenience and ease of use to reduce the overhead? How many extra objects does it buy you? Would you rather have something easy to work with instead?

I won't lie, the idea of having everything about each object stored in the same place is very appealing to me. Editing them will be easier if everything is nearby. Having everything together also means less address lookup tables and less indirection. The whole thing seems simpler and easier to work with than if the object handling was split in two parts, EXCEPT for the sprite cycling.

I don't think that my current idea for cycling sprites is particularly complicated though, it's about as complex as the solution I had when drawing was completely isolated from the logic, it just has a couple of drawbacks I wish I could think of simple solutions for.

My usual approach is to make it work the way you'd like it to be, first, without worrying whether it is the most efficient thing (as long as it's reasonable). Test its performance and see if it's good enough before considering sacrifices.

That is good advice, and I've been trying to follow it. Right now it feels to me like isolating objects is the most organized, straightforward and versatile thing to do. The only drawback being the sprite cycling, which I actually consider to be a minor thing. By definition, it's a workaround to minimize the effects of a prominent hardware limitation, and by default it looks like a glitch. It seem silly to me to sacrifice anything about the engine to make the sprite flicker look slightly better.

[Sogona]

- no way to reserve sprite 0 for raster effects;

Is there really not a way to just advance another prime number when you get to 0?

Haven't tested, but something simple like

Code: Select all

        lda oam_index
        clc
        adc #76        ;76 / 4 = 19
        bne SkipSprite0
        adc #76
SkipSprite0:
        sta oam_index

wouldn't work?

[tokumaru]

Is there really not a way to just advance another prime number when you get to 0?

This is actually a pretty good idea! Don't know why I didn't think of that...! I'll not be using this technique in my game, but this is still a good suggestion for anyone that does use it.