Gameboy Development Forum

martendo · 2020-03-30 11:00:54

Hi everyone,

I'm working on a GBC game, similar to the Zelda games, and I'm at the point where I'm making some entity/object handlers. I'm a bit stuck.

Let's say I want to add a new object to (S)OAM, and I want it to be placed at the top of OAM (I want it to be drawn on top of other sprites), but there are already some sprites there.

I'm thinking I do something like call the routine that writes to SOAM with already ordered sprites, but I still don't really know how to get this order. I think somehow I've got to compare Y coordinates of the sprites and possibly write to a temporary table, but once I find a new top sprite, I'll have to compare again, and that would just take a long time. Again, I don't really know what I should do.

I'm working is ASM.
Any help would be greatly appreciated.

toxa · 2020-03-30 13:41:23

i'm not an expert, but i'd rather do this: allocate sprites from the end (you call - bottom) of oam. if there's no more space, call reallocation procedure to remove "holes". it might be a rare call. do you need exact order for the new sprites (like the new one must appear below the three first ones), or simplier (like the newest above all)? you may also move into two directions from the center of oam: above all and below all.

martendo · 2020-03-30 14:00:53

Thanks toxa.

Interesting approach, but I was thinking of changing the order of sprites based on their Y position. This is because the game is played in top-down 2D, like the Zelda or Pokemon games. Whenever a sprite is "behind" another, for example the player walks down the screen and is now "behind" an NPC (onscreen, it's really drawn slightly above), I want the sprite with the lower Y coord (NPC) to be drawn on top of the one with the higher Y (the player). Does this make sense?

I've been looking at Oracle of Ages as an example for a while now. This game does exactly what I want to do myself. Move a sprite up the list if it's to be drawn on top of others. I've looked through the code and the disassembly here, but I can't find any routine that does what I'm seeing in OAM.

I guess if it's absolutely necessary, I could shift each entry in OAM to the next, but I'm not sure if that's very practical. There's got to be another way to do it.

toxa · 2020-03-30 14:53:56

ah, i see! i never played zelda, so did not understand. you are trying to make 2,5d? move sprites, then sort them. because everything is mostly sorted and you know, what you are moving, you may optimize sorting to reduce complexity. calculate the list of objects to be exchanged, then commit it to oam at the proper moment.

Last edited by toxa (2020-03-30 14:54:47)

martendo · 2020-03-30 15:04:40

I guess I'll try to shift the necessary OAM entries for now and see how that turns out. Any other suggestions are still welcome. (And if moving entries doesn't work out, then they're very welcome!)
Thanks.

toxa · 2020-03-30 15:33:17

anyway, you better have inner structures to calculate and modify, and then set the calculated result to oam. it allows to make the calculations not very time critical.

nitro2k01 · 2020-03-30 18:00:44

Perhaps keep the sprite table sorted by Y position at all times? If you know about algorithm complexity, you might know that insertion sort is O(n^2) complexity. (The time is proportional to the number of objects times the number of objects.) However, this is for the worst case. For an almost sorted list, the complexity is close to O(n). (The time is proportional to the number of objects.) Or if objects move seldom, update the position in the table on the fly when moving. You should hopefully never have to move it more than one step per frame.

Tauwasser · 2020-03-31 16:17:51

Most games also keep a meta-table of the "objects" in RAM anyway and then fill the region that is transferred to OAM on every frame based on that. They keep the objects sorted and then generate OAM sprites (usually 2x2 Tiles) from these objects. So that improves performance already.

toxa · 2020-04-02 07:23:06

one more consideration: this method (sorting by y) works only if all your characters have equal height, consist of one sprite by height, and all of them standing on the ground. e.g. your characters can not "jump", because it is equally as "going away" from the player. if you have a game character, that is two sprites high, then another character standing just behind will cut the first one in two. that's why it is better to have in-memory structutes, that describe the scene in 3-d, and then all your sprites should be sorted by z-order according to this representation, no matter what y coordinate do they have.

ISSOtm · 2020-04-25 06:07:27

Sorry, I'm late to the party.

The way I would implement it would walk a first time through the objects, generating the order objects should be rendered in. (Either by adding a "next to draw" pointer in each actor struct, if feasible; otherwise using an array of pointers to actors)
Then I would walk through the objects again, but this time in the draw order, and that's when I would write to OAM.

This means that any logic can be applied to the first pass (including subtracting some height variable from the stored Y coord if characters can jump), and that objects are grouped per actor instead of being sorted by themselves, which only works if actors are at most 1 object tall (= 8 or 16 pixels tall, depending on your game engine)

Gameboy Development Forum

#1 2020-03-30 11:00:54

Rearrange sprites in OAM

#2 2020-03-30 13:41:23

Re: Rearrange sprites in OAM

#3 2020-03-30 14:00:53

Re: Rearrange sprites in OAM

#4 2020-03-30 14:53:56

Re: Rearrange sprites in OAM

#5 2020-03-30 15:04:40

Re: Rearrange sprites in OAM

#6 2020-03-30 15:33:17

Re: Rearrange sprites in OAM

#7 2020-03-30 18:00:44

Re: Rearrange sprites in OAM

#8 2020-03-31 16:17:51

Re: Rearrange sprites in OAM

#9 2020-04-02 07:23:06

Re: Rearrange sprites in OAM

#10 2020-04-25 06:07:27

Re: Rearrange sprites in OAM

Board footer