Sprite Rotation Algorithm

[+adamantyr]

Hello fellow 99'ers,

 

I was musing today about how to put together a good sprite rotation system in assembly language. Specifically, a system in which you swap sprites around to overcome the 4-sprite per horizontal line limit.

 

I think the first step to this is to treat the sprite attribute table as just a display system... in other words, your "screen objects" have to be abstracted out. So sprite #0 is not your player graphic, sprite #0 is just the first sprite on the screen, your "player" becomes an abstract data type that has a constantly changing "sprite assignment".

 

I've found a few articles, mostly related to re-creating classic Nintendo emulation, that discuss some ideas... this particular link has a good idea with a "priority" system:

http://stackoverflow.com/questions/2980198/emulating-old-school-sprite-flickering-theory-and-concept

 

But with the TI-99/4a, we have some mechanisms that let us be a bit smarter about it... we only NEED to rotate sprites if there are 5 or more on the same scanline, and a bit is set to indicate this state. It also gives us the top-most sprite number. The VDP timer will let us do sprite rotation on an interrupt every 1/30 of a second which should be good for visibility.

 

One thought I had was just a simple brute-force method... if the bit is set, every frame just grab the sprite attribute table and rotate every sprite one down. Continue until the bit is not set. Video-wise, this operation should be fast (read in 128 bytes, tag the back with the front four bytes, write it back, update your abstract object model so you know which sprites are which things.) but it also is pretty dumb.

 

Then again, a more intelligent system may consume too much time to do calculations and make it worse... has anyone crafted one of these before, any insights or suggestions?

 

Adamantyr

[Asmusr]

I have used sprite flicker algorithms in a couple of games. Not very intelligently or anything, just something very basic and fast.

 

I have a copy of the sprite attribute table in CPU RAM. In TI Scramble, for instance, I used up to 16 sprites, so the table was 64 bytes.

 

I start by setting up the VDP write address to the beginning of the sprite attribute table. Then:

 

In frame #1 I copy 64 bytes to VDP RAM starting from offset 0.

In frame #2 I copy 48 bytes to VDP RAM starting from offset 16 and then 16 bytes from offset 0.

In frame #3 I copy 32 bytes to VDP RAM starting from offset 32 and then 32 bytes from offset 0.

In frame #4 I copy 16 bytes to VDP RAM starting from offset 48 and then 48 bytes from offset 0.

Repeat ad lib.

If you have a main character that you don't want to flicker you can exclude the first attributes from the rotation, but then the other sprites will flicker more.

[Edit] The flickering aside, storing your sprite attributes in CPU RAM means that you will save lots of code when updating the attributes. And the routine to copy CPU to VDP can be made very fast with unrolled loops etc. You can even put it in PAD if it has to be very fast.

[Edit 2] I don't see any use of the 5th sprite flag (has it ever been used?). With the standard flicker algorithm the sprites will flicker if there are more than 4 in a row but otherwise keep steady.

[Tursi]

Rasmus essentially described the system I used in ColecoVision Mario Bros and Super Space Acer after a fair bit of investigation. My conclusion after all my research was that any system more clever that that is just wasting cycles - it won't appear to flicker unless there's 5 or more sprites on a line anyway, so there's no need to check for it, or create binary trees of the most important sprites, or several other systems I saw. As Rasmus did, you can rotate 4 sprites at a time rather than 1, since that's the limit anyway. It really gives you the best case for visibility.

[+adamantyr]

Thanks guys! Mulling it over this weekend, I realized that just storing the entire attribute table in CPU memory and rotating it IS the best option. And you're right, just constantly rotating sprites with NO logical checking is easiest... As long as you maintain a constant frame swapping, a single index value can be used to determine which sprite aligns with which object set.

 

One thing I'm certain of with the TI is that it will be WAY more efficient in terms of CPU processing over the classic Nintendo, which would have serious performance slow-downs as more sprites ended up on the screen.

 

Adamantyr

[TheMole]

I simply render the sprites in a CPU buffer in the order they appear in. When uploading to the VDP, I check the vblank interrupt counter. If it's odd, I upload in ascending order, if it's even I upload in descending order. Works pretty well, and there's only one check per frame instead of one per sprite.

[Tursi]

The rotation scheme described above is not a per-sprite test. You only need to know where to copy the first sprite from (I use a counter that I add and mask every time I update), and it's quickest to use two copy loops to handle running off the end and 'wrapping'.

 

An ascending/descending copy will work so long as you don't line up more than 9 sprites on a line (probably a pretty contrived case), the middle index sprite will never be seen.

[sometimes99er]

The rotation scheme described above is not a per-sprite test. You only need to know where to copy the first sprite from (I use a counter that I add and mask every time I update), and it's quickest to use two copy loops to handle running off the end and 'wrapping'.

 

An ascending/descending copy will work so long as you don't line up more than 9 sprites on a line (probably a pretty contrived case), the middle index sprite will never be seen.

I must be missing something.

 

So we're talking about the scheme describe by Rasmus ? Which brings every sprite to the top 4 at least once every 8th frame ? So no matter what, any sprite will get to the top 4 and hence be displayed ? Even if you have all 32 sprites on a line, they would all display (flash) ?

 

Even if you lock 1, 2 or 3 sprites, the 4th would roll through the remaining sprites making them visible once in a while ?

 

Edited September 22, 2014 by sometimes99er

[Willsy]

I must be missing something.

 

So we're talking about the scheme describe by Rasmus ?

 

No. Tursi was responding to post #5 by TheMole.

[sometimes99er]

No. Tursi was responding to post #5 by TheMole.

Oh. Thanks. The "rotation scheme described above" reference threw me off. It was actually two different references. - The rotation scheme and the ascending/descending copy one.

 

Edited September 22, 2014 by sometimes99er

[artrag]

If you assume that the 5th sprite problem can happen only once on the screen, there is an optimal solution that uses the info in the status register concerning the plane where the condition occurred.

 

The idea is easy to be explained (even if a bit tricky to be implemented):

- read the status register at each frame;

- if the 5th sprite condition occurs, read the last 5 bits of the status register - say plane X

- move on the top of the SAT sprites with plane >= plane X

- add to the SAT sprites with plane from 0 to plane X-1

 

Now, in the SAT, you have on top priority the sprites that in the previous frame had position from plane X to end SAT (0xD0) and, with lower priority, planes from 0 to plane X-1 in the previous frame.

In this way, at each frame, the first sprite that has disappeared (and eventually others with lower priority equally disappeared) are moved on the top and get visible

 

You can try with pen and paper and you will see that if the 5t sprite condition occurs only once on the screen, (you can have 5 sprites or more but on the same line) the flickering that will result is optimal i.e. each sprite gets a visible position with the highest possible rate.

 

Anyway, usually I use sprite reversal, that is robuster than the above algorithm and allows to have more than 32 sprites on the screen (up to 64 flickering sprites)

Edited September 22, 2014 by artrag

[Asmusr]

Anyway, usually I use sprite reversal, that is robuster than the above algorithm and allows to have more than 32 sprites on the screen (up to 64 flickering sprites)

 

That sounds interesting. How does it work?

[artrag]

In odd frames, copy sprites to SAT starting from the first, in even frames, copy sprites to SAT starting from the last. In both cases, stop when the SAT is full.

 

If you have more that 32 sprites (e.g. 64) the first 32 will appear in odd frames, the last 32 in even frames.

 

About the 5th sprite problem, you will see in odd frames the 4 sprites with lowest position in your list, in even frames the 4 sprites with highest position.

This solution allows to deal with up to 8 sprites per line, but not with 9 or more.

Edited September 22, 2014 by artrag

[Tursi]

The rotation scheme allows for more than 32 sprites as well.

 

Anyway, lots of options out there.

[marc.hull]

In odd frames, copy sprites to SAT starting from the first, in even frames, copy sprites to SAT starting from the last. In both cases, stop when the SAT is full.

 

If you have more that 32 sprites (e.g. 64) the first 32 will appear in odd frames, the last 32 in even frames.

 

About the 5th sprite problem, you will see in odd frames the 4 sprites with lowest position in your list, in even frames the 4 sprites with highest position.

This solution allows to deal with up to 8 sprites per line, but not with 9 or more.

 

Very clever. Doesn't cost you Anything time wise and the staststastically low probability of a middle of the list problem is worth it. Hope you stick around.... thanks. !!!

[+OLD CS1]

Nice. Can you post a demonstration? I am curious how it looks in practice.

[artrag]

Nice. Can you post a demonstration? I am curious how it looks in practice.

 

Use an msx emulator (openmsx,bluemsx, meisei) and choose an msx1 with the TMS9918A (any msx1 NTSC).

 

URDIUM3c.rom

URDIUM48.rom

Edited September 23, 2014 by artrag

[artrag]

A side note on sprite reversal.
As plane priority is reverted at each frame you can get 3 color objects using two sprite layers.
The 3dr color is the mix of the colors of the two layers and will appear in the area where the two sprites overlap.

The effect works well on CRT monitors and on slow moving objects.

It is very good to define details or shadows.
Look at enemies in the 3c rom to see how the trick appears.

 

[EDIT]

This is a video of the effect, but due to the limited frame rate of youtube videos, in order to have a better idea you have to see on emulators or on the real machine

Edited September 27, 2014 by artrag

[Asmusr]

A side note on sprite reversal.

As plane priority is reverted at each frame you can get 3 color objects using two sprite layers.

The 3dr color is the mix of the colors of the two layers and will appear in the area where the two sprites overlap.

 

Amazing. I can't wait to try the 3 color technique on the TI.

 

I also ended up using the sprite reversal algorithm for Sabre Wulf because it seemed to produce slightly better results than the rotation algorithm.

[Asmusr]

I noticed that the sprite flicker routine in Sabre Wulf, which is currently the sprite reversal algorithm, doesn't seem to have any effect when I play the game on a EU console connected to a 6-7 years old Samsung flat screen TV set using the PAL modulator. It looks like the TV set is only displaying half of the frames produced by the TI, so there are no flickering sprites - just black boxes - when there are more than 4 sprites on a row because the reverse frames are being ignored. I'm thinking a new algorithm where you start at a random sprite and wrap around when you reach the end of the SAT would solve this problem. But before I try it it would be interesting to know if anyone else have notice this issue. Not for Sabre Wulf in particular but just that their TV set seems to be skipping every 2nd frame generated by the TI.

[artrag]

Black boxes? This is strange. You should see nothing if the odd frames are missing

[Asmusr]

An update: I tried it on my second TV set, a newer 40" Sony Bravia that directly supports the composite input from the EU TI, and this does not have the same problem. But I would still like to know if anyone else have noticed the frame skipping issue on their TVs.

 

 

 

Anyway, here's your chance to investigate which DVDs my children are watching.

[Asmusr]

Black boxes? This is strange. You should see nothing if the odd frames are missing

 

Well, that's what I mean by 'black box'. The sprites are just missing scan lines as if there was no sprite rotation algorithm,

[Tursi]

It's possible that your TV is attempting to deinterlace the image from what it expects is 60hz interlaced to 30hz progressive -- some modern TVs will do that. Flicker in that case will end up looking like alternating lines (depending on the quality of the deinterlacing).