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

Shuffling meta sprites

Shuffling meta sprites
by on (#198172)
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?
Re: Shuffling meta sprites
by on (#198173)
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.
Re: Shuffling meta sprites
by on (#198174)
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:
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.
Re: Shuffling meta sprites
by on (#198175)
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.
Re: Shuffling meta sprites
by on (#198178)
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.
Re: Shuffling meta sprites
by on (#198184)
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.
Re: Shuffling meta sprites
by on (#198187)
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:
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.
Re: Shuffling meta sprites
by on (#198190)
Quote:
That's a different topic though.

You're right. But in order to answer this...
Quote:
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.
Re: Shuffling meta sprites
by on (#198223)
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:
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)
Re: Shuffling meta sprites
by on (#198243)
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.
Re: Shuffling meta sprites
by on (#198245)
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.
Re: Shuffling meta sprites
by on (#198253)
The post you linked to do not talk about sprite cycling. However, a lot of existing threads already does. Such as this or this.
Re: Shuffling meta sprites
by on (#198254)
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.
Re: Shuffling meta sprites
by on (#198255)
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.
Re: Shuffling meta sprites
by on (#198256)
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?)
Re: Shuffling meta sprites
by on (#198260)
Well, I have zero grudge against you or anyone else - I just find it's a shame you didn't use the "search" function in those specific cases - but if you don't want to use it I guess I can't force you to. It would save you a lot of time as you'd immediately see the existing answers appearing.
Re: Shuffling meta sprites
by on (#198261)
Even on a purely factual level your complaint was not entirely justified:

The first thread that you linked only talked about logical organization of sprite order, not the ever changing, evenly distributed algorithm I'm looking for.

The second very short thread had maybe one single post where one possibility was explained a bit. The rest was mostly about slightly different stuff again. Hardly a full solution to my problem.

Besides, what am I supposed to do? Do you expect me to necrobump a seven or five year old thread?
Re: Shuffling meta sprites
by on (#198264)
DRW wrote:
Do you expect me to necrobump a seven or five year old thread?

In the past, the preference here appears to have been necro over dupe. That's consistent with the worldview set forth in the classic Flash animation "Posting and You".
Re: Shuffling meta sprites
by on (#198268)
Isn't the sentiment against necroing that the content of the thread is no longer relevant/the original participants are no longer active? In which case, each thread can be individually judged based on its content and knowledge of the users.

Restricting dupes on the other hand seems most important in forums plagued by questions like "when will raspberry pi 4 be released" / "gee, i wish the next raspberry will have x gigs of ram or other features that goes against the foundation's principle to make 35 dollar educational computers widely available" and such? Especially on bostad with active users in the ten to hundred thousands?
Re: Shuffling meta sprites
by on (#198316)
DRW wrote:
Besides, what am I supposed to do? Do you expect me to necrobump a seven or five year old thread?

Indeed - you are "supposed" (that means really "encouraged") to look at existing info, and ask about things that remains unclear to you, including possibly necrobump something.

Quote:
Isn't the sentiment against necroing that the content of the thread is no longer relevant/the original participants are no longer active?

Many active people back then are still active today - many of us had been active here for the last 15 years.
Re: Shuffling meta sprites
by on (#198320)
Precisely - so necroing doesn't seem to cause the same dilemma other boards may experience.
Re: Shuffling meta sprites
by on (#198329)
(Necro posts vs new similar post)

My opinion is "you should start a new thread". You get more [new] comments on a new post than a necro one, especially if the same people already commented in the necro post that are still here today.

Another thing...if you are new and have MANY questions, don't start 15 new threads, just continue on one thread.

Edit - added a word, in brackets
Re: Shuffling meta sprites
by on (#198331)
Back on topic.

I've tried...
"pick a random starting point each frame" and start filling from there, wrapping around. But not really random, nor just adding 9 each time (I think someone suggested something like that). But step through a list of start points that are preshuffled...0, $80, $20, $a0, $40, $c0, $60, $e0 or similar.

Or,
4 alternative lists of object ordering, for drawing metasprites...
(1,2,3,4,5,6,7,8)
(8,7,6,5,4,3,2,1)
(1,3,5,7,2,4,6,8)
(8,6,4,2,7,5,3,1)

Both were simple and seemed to work.
Re: Shuffling meta sprites
by on (#198509)
I don't have a huge number of metasprites, and I don't usually need Z-order, so

1.- The index of the first metasprite to be processed is incremented each frame, modulus the total number N of sprites, by a prime of N. That way each metasprite in the list gets to be the first in a cycle of N frames.
2.- Then I iterate N times adding M to the current index modulus the total number N of sprites, with M a (different) prime of N. That way the whole list gets processed (i.e. sent incrementally to the OAM copy) in the current frame.

That way the order of metasprites is different enough from frame to frame without having to resort to lookup tables or random numbers.

This method proved useful in systems with a harshed limit of sprites per scanline such the SEGA SG-1000, which only supports 4 monochrome sprites per scanline.
Re: Shuffling meta sprites
by on (#198513)
na_th_an wrote:
This method proved useful in systems with a harshed limit of sprites per scanline such the SEGA SG-1000, which only supports 4 monochrome sprites per scanline.

Too bad we can't see the actual effect in the video, since YouTube doesn't offer 60Hz playback for resolutions 480p and lower.
Re: Shuffling meta sprites
by on (#198554)
It is not 100% perfect but it does the job. Of course, with that number of sprites, the game is a blink fest :) You watch it yourself in any SEGA 8-bit emulator (for example Kega Fusion) as the game is free to download from our site or clicky, so no need for crappy youtube videos.
Re: Shuffling meta sprites
by on (#198556)
tokumaru wrote:
na_th_an wrote:
This method proved useful in systems with a harshed limit of sprites per scanline such the SEGA SG-1000, which only supports 4 monochrome sprites per scanline.

Too bad we can't see the actual effect in the video, since YouTube doesn't offer 60Hz playback for resolutions 480p and lower.

We don't see the entire flicker sequence, but at least this is a flicker sequence that is long enough and varied enough that it still works when you drop every second frame, so it still looks effective at 30 Hz. (As opposed to various simple techniques with only 2-frame sequences where you end up only seeing half the picture.)