One in front of the other

My game uses a semi top down perspective, kind of like the old school zelda games. That means I have to keep track of which object is in front of the other. If I don't, the player might end up looking like he is walking across the top of an enemies head, when in fact he is supposed to be behind him.

So how do you accomplish this on the NES? Well, the sprites are drawn in a prioritized order from the OAM (Object Attribute Memory). Whichever sprite comes first in the OAM will be drawn on top of the ones after. The simplest way to achieve this is to keep a sorted list of all the objects, sorted by their Y coordinate. Then I can copy the sprites to the OAM buffer in this order every frame.

I settled with a simple insertion sort, since it is a very simple algorithm, and performance is very good on almost sorted lists. Since the objects don't warp around the map at high speed, chances are the order of the list won't change much from frame to frame. So I spent this week writing a special sorted buffer and an insertion sort routine. I say this week, since I ended up with some stupid little bug that had me debugging forever. I finally just deleted the routine and rewrote it, and bang! Now it works. Assembly can sure make the simple things crazy hard.

Now on to the next problem. I mentioned in my last post that the NES can only handle 8 sprites at once on a scanline. After that the sprites with lower priority simply disappear. Since I now have 15 characters potentially on the same scanline at the same time, I had to figure out how to handle that. I can't do a simple random order of all the sprites since that would undo all the work of sorting them in the first place. So what to do?

For now I have a simple solution based on the PPU sprite overflow flag. This flag is automatically raised by the PPU when it detects more than 8 sprites on a scanline. It's supposed to be buggy and unreliable, but I think it works OK so far. If this flag is raised, I cycle all objects in groups of four. That way, most overlaps stay fine, but some glitches might occur (and do). They are very small, however and are overshadowed by the flickering anyways.

Here is a little video showing 15 characters animated and walking around randomly on the screen. Youtube can only show 30fps, so the flickering looks a bit strange with the frame blending. Anyways, I think it looks OK.

I'm not 100% done with this part yet, but I have a working solution. I also have a better idea down on paper and I might implement it in assembly this week or later on, which might improve the result. The trick I will use requires me to make some assumptions about the game, like that all sprites will be 2 sprites wide and 2 sprites high. That will work fine for this game, since the only time I might use bigger sprites is in boss battles, and I can use another algorithm for those.

My plan is to scan through the sorted list and find every occurrence of 5 or more objects that are closer than 32 pixels from each other in the Y direction. That means those objects will have to be cycled and I can leave the rest alone. That way I can minimize the errors in "Y ordering" and only sacrifice it for the ones that are really necessary.

Going 8x8 or 8x16

In my last post I mentioned that I wanted 60fps with 6 enemies on screen at once. Why 6? Well, there is a logical explanation for that number. The NES does not work like a typical raster display that you find in a PC. Instead it uses a very specialized PPU, or graphics chip. The graphics chip can output a background made up of various tiles, and up to 64 sprites on top of this background.

This tile based display greatly reduces the amount of RAM used for the display, and it also offloads the heavy act of drawing the graphics to the PPU, while the CPU can spend the time doing other stuff. Compare the NES to a common PC of its time, and the advantages of using this design for a game system is easy to see.

Sprites are independent graphics objects that can be placed anywhere on top of the tiled background. They do not have to follow the tile grid, and are therefore perfect for players, enemies, bullets etc. There are however some limitations to the sprites. A sprite on the NES can be either 8x8 pixels or 8x16 pixels. Each sprite can have one of four palettes, each consisting of three colors plus transparent.

Examples of how the meta sprite would be split up in 8x8 or 8x16 mode.

The player and enemy sprites in my game are roughly 16x24 pixels large. That means I can either choose to use 8x8 sprites, and each character will take up 6 of the 64 possible sprites, or I can choose 8x16 sprites and have each character only use 4 sprites. So why choose 8x8? Well, as the NES has a very limited graphics memory, there is a better chance that I can be able to reuse a sprite twice or more. For example, the top of the head might be the same in all frames of an animation, so I don't have to store it twice. Plus, when using 8x16 sprites, I have to save the empty space beneath the character and waste space.

I had initially started by using 8x8 sprites, making the maximum number of characters available on screen at once 10. I also knew that I had to save some of the sprites for things like effects, crosshairs, health indicators and stuff like that. So I was left with 6 enemies and two players.

Having a maximum of 8 characters on screen also fit nicely into the sprite limitations per scanline on the NES. One of the biggest limitations of the NES is that it can only show 8 sprites on one scanline. If you try to show more, they will simply not appear at all. What most programmers did to solve this problem is to draw the sprites in a different order each frame. That way, when there were too many sprites on a scanline at once, they would only become invisible every other frame. This was very common on the NES and can be seen in almost any game.

Sprite flickering example in Megaman 2 (esp at around 1:06)

Since my characters are 16 pixels wide, they use two sprites. So if all characters happened to stand next to each other, half of them would disappear. The simple solution, since I know there is no possible way more than 16 sprites can show up at once on a scanline, is to just draw the sprite buffer backwards every other frame (If I need to, more on this will come). That's why I wanted 6 enemies at once.

But I have since become greedy. This is a game about zombies. No zombie apocalypse has ever been much to call home about with only 6 zombies. I want hordes of them! That is why I have chosen to change thigs up and go for 8x16 sprites instead. This means I have a theoretical limit of 14 zombies and 2 players on screen at once. I'm still not sure I will be able to pull this off, but that's what I'm aiming for.

As you can tell from my sprite, I can still get away with the 3 color limitation when using 8x16 sprites. The pants need to use a different palette, but the top of the body only uses three colors.

Next up is the great challenge of drawing the sprites in order and keep track of what to flicker and when. More on that soon.