Sprite Overlapping Problem

Sprite Overlapping Problem
by ZeroFusion on 2007-06-09 (#24810)

Hi, I'm trying to get my NES emulator to work, but I found big problem. In Duck Hunt, everything seems all right until the duck flies out. When it hides behind the tree on the left or the bushes on the right, it's weirdly clipped. Also, when the dog laughs out loud on me for having missed the duck, the grass behind which he is is NOT transparent (as it should be). See the screenshot:

I'm using per scanline engine (I know it's less accurate than per pixel engine, but just right now, I need at least some of the mapper 0 games working and I can switch to per pixel engine later).

Here's what do I do during drawing a scanline:

1. Draw any pixels of the background tiles being on the current scanline (non-transparent and transparent). I keep a flag of which pixel is transparent and which is not.

2. Draw non-transparant sprite pixels on the current scanline (from sprite 0 to sprite 63):
a) If the sprite is in the foreground, i simply draw it's pixels
b) If the sprite is in the background, i draw all it's pixels where BG is transparent
Anytime I draw a sprite pixel, I set appropriate flag that background is no longer transparent there.

Here's the code:

Code:

            if ((colorAddressOffset & 0x0003) && ((!(ppu.sprRAM[k+2] & 0x20)) || (transparencyMap[ppu.sprRAM[k + 3] + j]))) { // Not transparent
              colorIndex = ppu.readMemory(0x3f10 + colorAddressOffset);
              SDL_LockSurface(ppu.scanline);
                putPixel(ppu.scanline, ppu.sprRAM[k + 3] + j, 0, SDL_MapRGB(ppu.scanline->format, NES_PALETTE[colorIndex].r, NES_PALETTE[colorIndex].g, NES_PALETTE[colorIndex].b));
              SDL_UnlockSurface(ppu.scanline);
              transparencyMap[ppu.sprRAM[k + 3] + j] = false;
            }             

Can anyone tell me what do I do wrong? I want to implement scrolling in my emulator, but no sooner than the sprites are drawn correctly.

Thanks.

by dvdmth on 2007-06-09 (#24814)

I suggest drawing sprites first, then the background second.

When drawing sprites, be sure to draw only the first eight sprites that exist on the scanline. Also, sprite 0 has highest priority and should be drawn over top of all other sprites. Sprite 63 has lowest priority. Even if sprite 0 is background and sprite 1 is foreground, sprite 0 will still cover sprite 1.

When drawing the background, draw only where a foreground sprite pixel doesn't already exist. Background sprites should be covered only by non-transparent background pixels.

Sprite vs. sprite priority MUST be done before sprite vs. background priority. Suppose sprite 0 is background, sprite 1 is foreground, and the two overlap at a point where the background is not transparent. Because sprite 0 has priority over sprite 1, it will be drawn over top of sprite 1. However, since sprite 0 is a background sprite, it will be covered by the background, causing the background to be visible at that location. (This "priority quirk" causes some graphical glitches in certain games, by the way. Other games take advantage of it, however, so you have to emulate it.)

by ZeroFusion on 2007-06-09 (#24831)

Thanks very much, dvdmth, I tried what you suggested, but with no luck. I tried to solve it whole afternoon a now I found out that my emulator behaves very strangely:

After drawing all apropriate sprites on current scanline, I do this to determine the color of current BG pixel:

Code:
if (!(pixels0 || pixels1)) {
colorIndex = ppu.readMemory(0x3f00);
} else {
colorIndex = ppu.readMemory(0x3f00 + (pixels32 | (((pixels1 & pixelTileOffset) >> (7 - j)) << 1) | ((pixels0 & pixelTileOffset) >> (7 - j))));
}

So far it seems no problem to me. Then I tried to draw all BG pixels where there was no foreground pixel and (there wasn't background pixel or the current color wasn't the transparent one) - just like you suggested. I looked like this:

Code:
if (!frontSprites[i * 8 + j] && (!backSprites[i * 8 + j] || (pixels0 || pixels1))) {
SDL_LockSurface(ppu.scanline);
putPixel(ppu.scanline, i * 8 + j, 0, SDL_MapRGB(ppu.scanline->format, NES_PALETTE[colorIndex].r, NES_PALETTE[colorIndex].g, NES_PALETTE[colorIndex].b));
SDL_UnlockSurface(ppu.scanline);
}

The funny thing is (and I don't know why it behaves this way) that only solution that worked for me was to exchange the condition when to draw BG pixel like this (where bgColorIndex = ppu.readMemory[0x3f00]):

Code:
if (!frontSprites[i * 8 + j] && (!backSprites[i * 8 + j] || (colorIndex != bgColorIndex))) {
SDL_LockSurface(ppu.scanline);
putPixel(ppu.scanline, i * 8 + j, 0, SDL_MapRGB(ppu.scanline->format, NES_PALETTE[colorIndex].r, NES_PALETTE[colorIndex].g, NES_PALETTE[colorIndex].b));
SDL_UnlockSurface(ppu.scanline);
}

My palette mirroring seems to be working correctly, so I don't understand why if-and-only-if operation (pixels0 || pixels1) <=> (colorIndex != bgColorIndex) fails

EDIT: I forgot to say that between code 1 and code 2, there're NO addtional lines in my emulator source (ie. there's absolutely no change of pixels0, pixels1 or colorIndex being changed). Really strange

And I would like to ask one more question: which sprites count to the total of 8 per scanline? Do I have to count every sprite, that spans current scanline, or just those sprites where at least one of the (non-transparent?) pixels is on the current scanline?

by tepples on 2007-06-09 (#24836)

ZeroFusion wrote:
And I would like to ask one more question: which sprites count to the total of 8 per scanline? Do I have to count every sprite, that spans current scanline, or just those sprites where at least one of the (non-transparent?) pixels is on the current scanline?

There are 8 sprite sliver registers in the PPU. In order for the PPU to determine that there are no nontransparent pixels in an 8x1 pixel sprite sliver, it still has to fetch that sprite sliver from CHR memory. So yes, you count all sprites that span this scanline.

by blargg on 2007-06-09 (#24841)

In my NES emulator I draw the background scanline first, then sprites in order. For each pixel I have an extra flag. When set, it prevents further modification of that pixel. The background clears this flag, and sprite drawing sets it for non-transparent sprite pixels. Sprites that are behind the background set the flag and modify the pixel itself only if it was transparent, causing the correct behavior of forcing the background pixels in front of other sprites after the current one. Just wanted to note that you can draw the background first, and that it can still be efficient (I'm able to process four sprite pixels at a time, using some bit manipulation to replace only non-transparent pixels appropriately).

by ZeroFusion on 2007-06-10 (#24846)

Thanks, tepples.

blargg wrote:
Just wanted to note that you can draw the background first, and that it can still be efficient (I'm able to process four sprite pixels at a time, using some bit manipulation to replace only non-transparent pixels appropriately).

Yeah I thought so, but I was absolutely desperate and could not find any mistake, so I tried to render sprites first as dvdmth suggested.

Anyway, I've made a further investigation into Duck Hunt. FceUXD's debug shows me that there aren't any entries in the sprite or image palette that match background color and aren't on address dividable by 4. In my opion, this can only mean that the grass BG tile behind wich the dog's hidden, really has transparent pixels and my palette mirroring has to be wrong somewhere (otherwise the (pixels0 || pixels1) condition would pass).

by Disch on 2007-06-10 (#24851)

you shouldn't be matching background colors to anything. The actual color used anywhere is completely irrelevent as far as transparency goes.

"Color 0" on the 4-color CHR is always transparent, regardless of what is in the palette, or what palette the current sprite/bg is using. That is to say -- opacity can be determined by doing a simple check:

Code:
if( pixel & 3 )
{
// pixel is opaque
}
else
{
// pixel is transparent
}

Where 'pixel' is the pixel before any palette lookup.

Absolutely nothing else matters when determining opacity/transparency. opaque pixels can still be opaque even if their color matches the BG color. And transparent colors are still transparent even if their respective entry in the palette does not match $3F00.

EDIT
---------------------

To elaborate on my approach... I actually do a 2-stage rendering process. While slower overall (since it essentially involves rendering everything twice), it's quite easy to work with, and allows for emulation of the pipelining effect of fetching BG tiles (not really applicable in your case though... since you're doing scanline based rendering)

The idea involves having 2 intermediate buffers -- one for BG pixels and one for sprite pixels. The sprite buffer would be flushed and refilled with sprite pixels only during HBlank on each scanline. The BG buffer would be filled as tiles are fetched (and the end of the previous scanline, and during rendering) during the scanline.

The gimmick here is that these intermediate buffers would only have the palette index of the color to render ($00-$0F for BG, and $00-$1F for sprites ... see below). Because of this, I can use the high bits of the sprite render buffer for some flags to hold additional properties of the pixel. For example -- $80 would indicate the sprite pixel has background priority.. and $40 would indicate the pixel belongs to sprite 0 (so you can do sprite-0 hit checks later, when the pixel is rendered).

Note that I reserve $00 as a fully transparent pixel in the intermediate buffers. Therefore, $10 would never be in the sprite intermediate buffer, since $10 would be transparent.

Actual factual last-stage rendering would then simply have to examine the appropriate sprite and BG pixels from the intermediate buffers, and choose whichever one takes priority (if any). This makes priorty checks during rendering pretty simple:

Code:
u8 a, b;

a = bg_intermediate_buffer[ current_x + fine_h_scroll ];
b = spr_intermediate_buffer[ current_x ];

// this is a neat trick to handle BG/Spr disabling, as well as clipping
// in the left 8-pixel column. I'll discuss this more later
if(current_x < bg_clip) a = 0;
if(current_x < sprite_clip) b = 0;

if(a && (b & 0x40) && (current_x != 255))
ppu_status_2002 |= 0x80; // sprite 0 hit!

if(b & 0x80) // low sprite prio
{
if(!a) // if BG pixel transparent
a = b & 0x1F; // use sprite pixel instead (mask out unwanted flags)
}
else if(b) // high sprite prio and opaque sprite pixel
a = b & 0x1F; // use sprite pixel

lookup_palette_and_output_pixel( a );

A note about my clipping:

$2001 can enable/disable clipping of the left 8-pixel column for sprites and BG independently. It can also disable BG or sprite rendering in full. All this clipping or disabling does is replace the output BG/sprite pixel with transparency where appropriate (note that this is done before sprite-0 hit checks). Also note theis does not include the special case where BG and sprite rendering are both disabled -- in which case the PPU enters an "off" state and operates quite differently.

I emulate this simply by keeping two variables, labelled above as 'bg_clip' and 'sprite_clip'. These would either be set to 256 (disabled), 8 (enabled with clip), or 0 (enabled, no clip) during my $2001 write handler.

< /rambling>

by ZeroFusion on 2007-06-10 (#24859)

Disch wrote:
And transparent colors are still transparent even if their respective entry in the palette does not match $3F00.

Thanks a lot, this seems to explain my problem with conditions: while (pixels0 || pixels1) condition tests only if the pixel is or isn't transparent by checking whether it's pallete entry is dividable by 4, the (colorIndexOffset != bgColorIndex) checkes whether current pixels color index isn't same as the "transparent's" color index.

According to what you've just written, the first condition could never possibly give good result - it would never prevent from drawing those pixels whose colorIndex was same as transparent color index (having palette offset dividable by 4) and offset of those pixel's color was not dividable by 4 (ie. there's color entry in the palette on the position not dividable by 4, and the color is still the same as the transparent one).