This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Changing order of meta sprites per frame

Changing order of meta sprites per frame
by on (#159533)
What is the best way to render the meta sprites in my game in a different order in every frame?

In the moment, all my characters data is stored in an array:
Index 0: Player character
Index 1: Opponent 1
Index 2: Opponent 2
Index 3: Projectile
Index 4: Flying object

Then I iterate through this array and call the RenderSprites function for each of these characters which takes the X and Y coordinate as well as the index to an array where all possible meta sprites are stored and then puts the necessary sprites on screen.

This way, the player character is always drawn on top.
Which, in general, is not bad, but unfortunately, some of my characters can move outside the platforms and are therefore sometimes in front of the house wall. And it looks strange if the player stands on the roof while the feet of the opponent are in front of the house wall, but the opponent's head is behind the player character.

So, what can I do to change the order every frame without having to waste too much CPU time for it?

By the way, I always want to change the order of whole meta sprites, not single hardware sprites. So, when you pause the emulator while two characters are overlapping, then one whole character shall stand in front of the other one. I don't want a scene where in the same frame, 50 % of a specific character stands in front of another character while 50 % of it stands behind the other one. (Unless this would require too much work and the other method is much faster.)
Re: Changing order of meta sprites per frame
by on (#159534)
What I do is process the object slots in sequential order when running their A.I., but in random order when calling their drawing routines. Each object outputs its sprites sequentially, so it has full control over the priorities of the individual sprites.

The only kind of global priority control I have is that each object can pick which end of the OAM it'll use. This makes it possible to have 2 sprite layers, although the high-priority layer should be used sparingly, or else they'd quickly obfuscate the low-priority ones.
Re: Changing order of meta sprites per frame
by on (#159535)
tokumaru wrote:
What I do is process the object slots in sequential order when running their A.I., but in random order when calling their drawing routines.

But what is a good routine to do this? How do I implement randomizing the characters?

They are not part of a dynamic list, so something like this is out of the question:
Code:
while (list.Length > 0)
{
    index = random(0, list.Length - 1);

    Draw(list[index]);

    list.Remove(index);
}


Similarly, I cannot do this:
Code:
remaining = array.Length;

while (remaining > 0)
{
    index = random(0, array.Lenth - 1);

    if (!array[index].WasDrawn)
    {
        Draw(array[index]);
        array[index].WasDrawn = true;
        --remaining;
    }
}

Because that one would mean that the loop runs many more times than necessary.

Not to mention that every number that cannot be represented by cutting off certain bits of the random number isn't useful for randomizing anyway.

tokumaru wrote:
The only kind of global priority control I have is that each object can pick which end of the OAM it'll use. This makes it possible to have 2 sprite layers, although the high-priority layer should be used sparingly, or else they'd quickly obfuscate the low-priority ones.

Do I understand it correctly? You just let the sprites decide whether they start drawing at the beginning or the end of the 256 bytes of the 64 sprites?

This could make the rendering a bit more complicated than necessary:
Until now, when drawing a hardware sprite, I simply increment a counter for the current byte. In your version, I always have to make an if check whether we're at the beginning or the end and update the index correspondingly.
Also, in this case, it would mean that, for example, the player character is always either the very first or the very last displayed character while the ones in the middle are always somewhere in the middle. I'd rather have a version where every character has the chance to be in every spot, i.e. the player character than be in the front, in the back or somewhere in between. Same for everything else.
Re: Changing order of meta sprites per frame
by on (#159536)
Quote:
Which, in general, is not bad, but unfortunately, some of my characters can move outside the platforms and are therefore sometimes in front of the house wall. And it looks strange if the player stands on the roof while the feet of the opponent are in front of the house wall, but the opponent's head is behind the player character.

I guess you'll have to decide whenever you sort sprites appearance so that they will always look in the correct priority in such cases, or just put them in a random order and don't care if it sometimes appear wrong. If your game is a purely 2D platformer, then go for the latter option. Having a system that detects whenever metasprites are overlaping, and sort them only if they do is theoretically possible, but a bit complex for the NES.

Drawing your metasprites alternating between increasing and then decreasing order would be good enough. Even better would be to alternate between increasing and decreasing *and* alternate the starting point. For example if your game engine supports 6 objects, you could do:
0 -> 5
5 -> 0
1 -> 5, 0
4 -> 0, 5
2 -> 5, 0 -> 1
3 -> 0, 5 -> 4
3 -> 5, 0 -> 2

(etc...)
Re: Changing order of meta sprites per frame
by on (#159538)
Bregalad wrote:
I guess you'll have to decide whenever you sort sprites appearance so that they will always look in the correct priority in such cases, or just put them in a random order and don't care if it sometimes appear wrong.

I want to put them into random order (since the game is purely 2D, not even isometric). Of course I don't have a system that detects whether they are overlapping since, whenever they don't, everything is correct anyway.

I have one little problem with your method: Doesn't this mean that two characters that are next to each other mostly appear next to each other? For example, character 1 almost never appears between character 4 and character 5. Only either in front of both or behind both. Or am I completely mistaken here?
But I'd rather have a method where the output is random enough so that you don't recognize a pattern based of the position of the characters in the array.

What method did commercial games use where enemy characters can overlap and where they change their z order in every frame?
Re: Changing order of meta sprites per frame
by on (#159540)
I like to randomize order by cycling through, incrementing modulo the number of objects by some number that is relatively prime to the number of objects.

Example with 8 objects:
Code:
// fixed order
for (int i=0; i<8; ++i) update_object(i);

// pseudo-random order
static int random_index;
static const int random_p[4] = { 1, 5, 7, 3 };

random_index = (random_index + 1) % 4; // change order each frame
int p = random_p[random_index]; // this is the number to increment with

int i = 0;
do
{
    update_object(i);
    i = (i+p) % 8;
} while (i != 0);

// each frame you get one of four orderings:
// p = 1 --> 0,1,2,3,4,5,6,7
// p = 3 --> 0,3,6,1,4,7,2,5
// p = 5 --> 0,5,2,7,4,1,6,3
// p = 7 --> 0,7,6,5,4,3,2,1

As long as p is relatively prime to the modulo, it will visit all of the objects correctly.
Re: Changing order of meta sprites per frame
by on (#159547)
Yeah, I do that with 24 object slots. Well, not exactly that because I start at a random position and increment the same amount every frame, but if you want the player to always be the first to be drawn, starting at 0 and changing the increment each frame sounds like an interesting idea.
Re: Changing order of meta sprites per frame
by on (#159611)
@rainwarrior: I'm not sure whether I have understood this.
Will it work if I have five characters? Because isn't something with modulo that isn't 2, 4, 8, 16 etc. slow to calculate?

tokumaru wrote:
but if you want the player to always be the first to be drawn

I myself do not want the player to be drawn first. He shall change positions like every other sprite as well. Because it would look strange when I attack an opponent and the player's hand is in front of the opponent. But when the opponent jumps down the roof, his whole body is in front of the house while the player, who is on the roof, is still drawn in front of the opponent.
Re: Changing order of meta sprites per frame
by on (#159613)
Any modulo will work, the key word is relatively prime. Any number relatively prime to the modulo can be used for the increment. For 5 that is: 1,2,3,4.

Powers of 2 are convenient for modulo, but non-power of 2 can work OK:
Code:
i += p;
if (i >= 5) i-= 5;


Though, if it's really just 5 items, you might do just as well to create a table of permutations of the order and just use that, or you could even use a collection of unrolled update loops, e.g.:
Code:
loop_0:
    ldx #0
    jsr object_update
    ldx #1
    jsr object_update
    ...
    rts

loop_1:
    ldx #4
    jsr object_update
    ldx #2
    jst object_update
    ...
    rts
Re: Changing order of meta sprites per frame
by on (#159616)
I've found in my own engine that drawing all meta sprites by iterating forwards and then backwards through the list of meta sprites, alternating the iteration direction each frame, to produce nice results (starting at the beginning of the sprite page, every frame, except for the hero and up to 2 entities sorted against her). It is an improvement over what I did in Nomolos, anyway, which was to just let the current address in my sprite page keep wrapping each frame. For particularly large meta sprites, I export a special version of the animations for these sprites to draw the same picture but with its sprites in a different order, so no sprites permanently drop out from a boss, for example. I, too, have my hero always on top, sorted with at most two other entities: her owl and maybe an NPC. In all other cases she's either in front of something, or getting hit by something, so this works out even with the pseudo perspective visuals we have in place.
Re: Changing order of meta sprites per frame
by on (#159619)
Or you could do what Haunted: Halloween '85 does: loop from 0 to one less than the smallest power of 2 not smaller than the size of the object table, XOR the loop index with a number that increases every frame, and if the result is within the object table, draw that object. For example, with six slots in the object table, you'd loop from 0 to 7 because 7 is one less than 8, which is the smallest power of 2 not smaller than the size of the object table.
Code:
for i in range(8):
    objid = i ^ nmis
    if objid >= 6: continue
    objects[objid].draw()
Re: Changing order of meta sprites per frame
by on (#160021)
I have 16 object slots in Brony Blaster. What I do is that on one frame, I draw them from 00 to 0F, then on the other frame, I draw them from 0F to 00. I can understand the appeal of randomization, but this is simple and doesn't take too much frame time nor does it take too much space in the code, since the actual drawing routine is JSRed each frame as it always was, and that it's only a difference of INXes, DEXes and CPXes in the routine that selects which object to draw.
Re: Changing order of meta sprites per frame
by on (#160022)
The main problem with simply inverting the order is that the sprites in the middle of the list are always disfavored, never having a chance to be at the top of OAM, meaning they'll flicker more than the others, or even disappear completely, if more than 16 sprites are lined up.
Re: Changing order of meta sprites per frame
by on (#160035)
O.k., I did some other things in my game in the last weeks, but now it is at the point where I finally need to implement this feature here.

So, I learned various methods in this thread:

Bregalad's idea:
Switching the direction that the array is gone through in every frame (start to end or end to start) and, additionally, shifting the starting point of the array every second frame.


rainwarrior's method where the gap between the array entries is calculated with pseudo-random values.
The problem though in this case is: The index increment uses a modulo. But this is only fast if you have 2, 4, 8, 16 etc. items, right?
But this isn't necessarily a given in my case. What if I have five characters?
i = (i+p) % 5
This doesn't work as smooth as modulo of 8.
Yes, I know it generally works, but I'd rather want to avoid it.


With tepples' method, I see this as the problem:
if objid >= 6: continue
This means that the loop might go longer than necessary, doing steps where nothing is processed at all.


So, I guess Bregalad's method is the most straightforward one and the one that can be applied best for arrays with a number that doesn't necessarily have to be 2, 4, 8, 16 etc.

But the question is: Would you say it's elegant? Are the characters drawn in a different enough order so that overlapping sprites flicker differently enough?

Or can somebody confirm that the other two methods are faster even though one uses a modulo of an arbitrary number and the other uses a continue when the value is out of the array size?

Is there one that gives the best results and is also the fastest? Or do I have to do a comrpomise between speed and equal distribution of the sprite entries in the various frames?
Re: Changing order of meta sprites per frame
by on (#160037)
To deal with the non-power-of-two slots thing (my engine has 24 object slots), I use a lookup table to wrap the index around. For example, if you have 6 slots, the table is $00, $01, $02, $03, $04, $05, $00, $01, $02, $03, $04, $05. To get the next index you add the increment value to the current index and use the result to fetch the actual value from this table, which handles the wrapping around, so you don't need to explicitly check for overflows. I don't know if something like this is feasible in C.
Re: Changing order of meta sprites per frame
by on (#160040)
tokumaru wrote:
The main problem with simply inverting the order is that the sprites in the middle of the list are always disfavored, never having a chance to be at the top of OAM, meaning they'll flicker more than the others, or even disappear completely, if more than 16 sprites are lined up.


That's exactly why I mentioned the "appeal" of RNG-based flickering, but there aren't many cases where there are more than 16 sprites per scanline in the game I'm doing. I don't think those happen in other games either, except maybe games that can have huge or long sprites (Like Godzilla and Adventure Island)
Re: Changing order of meta sprites per frame
by on (#160041)
DRW wrote:
With tepples' method, I see this as the problem:
if objid >= 6: continue
This means that the loop might go longer than necessary, doing steps where nothing is processed at all.

But those steps should complete much faster than steps where something is drawn. So yes, there's some overhead but not too much.

Quote:
Is there one that gives the best results and is also the fastest? Or do I have to do a comrpomise between speed and equal distribution of the sprite entries in the various frames?

Premature optimization is a root cause of all kinds of evil. Make it work, then make it fast.
Re: Changing order of meta sprites per frame
by on (#160042)
DRW wrote:
The problem though in this case is: The index increment uses a modulo. But this is only fast if you have 2, 4, 8, 16 etc. items, right?
But this isn't necessarily a given in my case. What if I have five characters?
i = (i+p) % 5

I did address this exact case in my earlier post:
rainwarrior wrote:
Any modulo will work, the key word is relatively prime. Any number relatively prime to the modulo can be used for the increment. For 5 that is: 1,2,3,4.

Powers of 2 are convenient for modulo, but non-power of 2 can work OK:
Code:
i += p;
if (i >= 5) i-= 5;

This only takes 3-6 more cycles than a bitwise AND, probably not a deal-breaker.
Re: Changing order of meta sprites per frame
by on (#160080)
rainwarrior wrote:
I did address this exact case in my earlier post:

Oops. Sorry, I've overlooked this. Yeah, you're right. This one would work.

Alright, thanks for your help. I guess I'll try it all out a bit and then I decide which version I take for my game.