Shuffling meta sprites

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Shuffling meta sprites

Post by DRW »

What would you say is the best way to shuffle the order in which meta sprites are displayed on the screen?

If it was just about the "more than eight sprites per scanline" issue, then it would be enough to simply shift the start index every frame.
For example, with five meta sprites, in the first frame you output them in the order of 12345. Then 23451. Then 34512 etc.

But when it's also about meta sprites overlapping each other and you don't want a definite z axis, but you want two meta sprites to constantly switch between which one is at the front and which at the back, then a simple index shift would not be enough since two specific meta sprites would mostly keep the z position relative to each other.

So, without using a randomizer, what would you say is the best way to shuffle meta sprites at every frame, so that every meta sprites equally gets to each "slot" in the row and so that all of them equally switch the z position relative to each other when they overlap?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Shuffling meta sprites

Post by FrankenGraphics »

On priority, for those moments that are about the scanline limit, i believe there are several axes(?) of importance. Some of them are more or less universal, others more circumstantial.

What objects on screen are important to the player?
Where is the player most likely to focus vision?
What objects are moving? You want to track those better than stationaries. Just like when you're drivning a car, you want to track moving objects.
What objects are moving the fastest? The same reason, but you need to evaluate if this is the right time for a high-precision sorting job.
What objects are layered for additional colours? you might want to flicker those first since you still get to keep silhouette and possibly light/dark intact if you've pushed pixels appropriately.
EDIT: What are the extremities of a larger meta-sprite? Those may be more important since that might signify a collision. Like the tip of the whip in castlevania (haven't actually studied it that close, it may or may not be prioritized - but serves as an example).

Best case scenario is when as many of the axes the user spontaneously finds important/convenient overlap at the point(s) your priority is intersecting.

There are probably more.
Last edited by FrankenGraphics on Wed Jun 14, 2017 11:20 am, edited 3 times in total.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Shuffling meta sprites

Post by tepples »

Haunted: Halloween '85 always fills the display list from 0 (frontmost) through 63 (rearmost), and it always draws an entire metasprite at a time, with individual sprites in the order that they appear in the sprite record. It draws the player first and then draws each other actor in an order that's perturbed by the current frame count. Pseudocode follows:

Code: Select all

player_index = 0
size_of_actor_table = 6

frontmost = player_index
draw_actor(frontmost)
for x from 7 down through 0:
    actor_to_draw = (x XOR nmis) & 0x07
    if actor_to_draw != frontmost and actor_to_draw < size_of_actor_table:
        draw_actor(actor_to_draw)
The chance for each enemy to appear in each frame isn't exactly even, but it's close enough.

The Curse of Possum Hollow modifies this slightly in that select objects near the player can appear in front of the player by replacing the player in frontmost. This can be a solid priority-trick rectangle for a phone pole or a slime pool, or it can be a hand rising from the floor.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Shuffling meta sprites

Post by tokumaru »

I run through my list of objects twice, once for A.I. and then again for drawing (i.e. generating OAM entries). The drawing order is randomized by picking the first object to draw randomly and then incrementing the slot index by a prime number (say, 7) each time until all objects have been drawn. I support some basic layering by filling the OAM from both ends (0 up and 63 down) and letting each object select which end to use. High priority sprites must be kept to a minimum, so they don't constantly steal the spot of regular sprites. Layering between objects is accomplished through the use of "slave" objects, whose draw routine is called by the draw routine of a parent object, so the the layering between child and parent objects is maintained.

I wonder why you specifically ruled out the use of a randomizer, since there's little to no overhead in using one if your only doing it for the first object.
na_th_an
Posts: 558
Joined: Mon May 27, 2013 9:40 am

Re: Shuffling meta sprites

Post by na_th_an »

I draw the main character first, on top of everything, and always. Then I draw the baddies, in a different order each frame, iterating N times with N = number of baddies, but cycling using a prime to N as increment, mod N. If the game has bullets I draw them first, but if they tend to be a lot and I see lots of interference with baddies, and bullets are not very far, I only draw half of the bullets each frame, starting with 0 or 1 alternatively, incrementing 2.

Pretty custom as per game. But my games tend to be simple, so this works.
User avatar
Dwedit
Posts: 4922
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Shuffling meta sprites

Post by Dwedit »

The stupid easy way to do OAM cycling is to advance 9 sprites (add 36 to the pointer) each time you write data for a sprite. When you reach 0, you've hit the 64 sprite limit.
Then you put the sprites in there in a shuffled order, probably having each sprite take turns being first.
This tends to have artifacts like flicking half sprites when too many sprites are on the scanline.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shuffling meta sprites

Post by DRW »

FrankenGraphics wrote:On priority, for those moments that are about the scanline limit, i believe there are several axes(?) of importance.
That's a different topic though.
That is more general game design: In what groups do I place my meta sprites, so that the important ones are rendered first?
I guess each programmer has to decide that on a situational basis.

But I'm simply talking about a good shuffling algorithm of meta sprites that are of equal importance, so that the absolute priority within the group and the priority between two meta sprites is distributed evenly during the various frames.
tepples wrote:

Code: Select all

player_index = 0
size_of_actor_table = 6

frontmost = player_index
draw_actor(frontmost)
for x from 7 down through 0:
    actor_to_draw = (x XOR nmis) & 0x07
    if actor_to_draw != frontmost and actor_to_draw < size_of_actor_table:
        draw_actor(actor_to_draw)
If I change the value size_of_actor_table from 6 to another value, like 10 or 15, how do I have to adjust the values 7 (start value of x counter) and 0x07, so that it still works?
Can this be formulated in a way so that it works with every number of actors?
tokumaru wrote:The drawing order is randomized by picking the first object to draw randomly and then incrementing the slot index by a prime number (say, 7) each time until all objects have been drawn. I support some basic layering by filling the OAM from both ends (0 up and 63 down) and letting each object select which end to use. High priority sprites must be kept to a minimum, so they don't constantly steal the spot of regular sprites. Layering between objects is accomplished through the use of "slave" objects, whose draw routine is called by the draw routine of a parent object, so the the layering between child and parent objects is maintained.
I don't really understand the whole slave object thing.

In my case, I would have an array of actors that are all equal to each other.
Then the algorithm would simply pick each of them and perform the drawing routine until none are left.
tokumaru wrote:I wonder why you specifically ruled out the use of a randomizer, since there's little to no overhead in using one if your only doing it for the first object.
I ruled it out because using a randomizer is nothing where I would need help with.
Well, at least when the randomizer is about picking slots from the array until all have been drawn.
But yeah, if you combine the randomizer with a specific algorithm, I'd like to see how this is done.


I'll try out the other algorithms and any further suggestions in the next days.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Shuffling meta sprites

Post by FrankenGraphics »

That's a different topic though.
You're right. But in order to answer this...
So, without using a randomizer, what would you say is the best way to shuffle meta sprites at every frame (...)
...in the fullest sense, you also need to answer what meta-sprites (or just sprites) should be shuffled, if not all. So the topics are interlinked, the way i see it. You don't need a clear design to pick a technique, but the technique will most likely work best for the product when it fullfils the goal of the design / the goal of the design will be most fullfilled when choosing the right technique, accordingly.

I'm sorry i can't help with the specific technical side of your query. It's not my primary (or even secondary) field.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Shuffling meta sprites

Post by tepples »

DRW wrote:[In the Haunted,] If I change the value size_of_actor_table from 6 to another value, like 10 or 15, how do I have to adjust the values 7 (start value of x counter) and 0x07, so that it still works?
1. Round up the actor table's size to the next power of 2, then subtract 1.
2. Use that value instead of each 7.

For 5 to 8 actors, use 7. For 9 to 16 actors, use 15.
DRW wrote:Can this be formulated in a way so that it works with every number of actors?
Yes.

Code: Select all

def round_up_to_power_of_2(value):
    return 1 << int(ceil(log2(value)))

player_index = 0
size_of_actor_table = 6
actor_table_mask = round_up_to_power_of_2(size_of_actor_table) - 1

frontmost = player_index
draw_actor(frontmost)
for x from actor_table_mask down through 0:
    actor_to_draw = (x XOR nmis) & actor_table_mask
    if actor_to_draw != frontmost and actor_to_draw < size_of_actor_table:
        draw_actor(actor_to_draw)
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Shuffling meta sprites

Post by Bregalad »

I simply write my sprites forward, then backwards next frame (sprite index is -4 each time instead of +4), then forwards again, etc... For me meta-sprite order is important (top-down graphics) (but not sprite order within the metasprite), so I sort them by Y position and also make the sort with a reversed direction each frame.

In a game where sprite order is unimportant I'd use a completely different technique, probably more randomized, I think Konami handled sprite cycling the best.

Besides, I'm pretty sure sprite cycling has already been discussed to death on those forums.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shuffling meta sprites

Post by DRW »

Bregalad wrote:Besides, I'm pretty sure sprite cycling has already been discussed to death on those forums.
That's the second time now. The third if you count this.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Shuffling meta sprites

Post by Bregalad »

The post you linked to do not talk about sprite cycling. However, a lot of existing threads already does. Such as this or this.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shuffling meta sprites

Post by DRW »

Bregalad wrote:The post you linked to do not talk about sprite cycling.
The statement "That's the second time now" was referring to your recent habit of criticising and belittling my posts.
Last time when I asked about the color palette and now your side note in this thread.

Plus the whole "half your post is off-topic" thing from the thread I linked.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Shuffling meta sprites

Post by Bregalad »

So you are taking personal grudges against me, just because I point out some lack of research of your side ? Doesn't sound like the most constructive behaviour.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Shuffling meta sprites

Post by DRW »

It seems more like you take grudges against me.

I mean, you complain about off-topicness on this forum? Seriously?

And your complaint when it came to my question about the color palette was not even correct: Apparently, it's unanswerable and yet, a lot of people wrote something.

And now the current thread: Maybe I could have done research. But after eight follow-up posts, you really felt the need to still point out that the thread shouldn't have existed to begin with?

So, yeah, I'm starting to get sick of this. It's always you, it's always against me and it's always the same thing: Criticising that my post was made at all.
(Or can you point me to, let's say, five of your recent posts where you wrote to complain about certain posts, so that I see that it's your general behavior towards everybody and not just me?)
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Post Reply