Cost of unrestricted sprites

Question

All the game consoles of the second through fourth generations, and several early home computers, had sprites, which were valuable though costly, e.g. the VIC-II spent 2/3 to 3/4 of its area on sprites, and the Atari 800, which shipped three years earlier so was more restricted in number of transistors per chip, split the graphics system into two separate chips for their sake.

I don't know exactly how sprites work at the hardware level, but this pseudocode description https://wiki.nesdev.com/w/index.php/PPU_sprite_evaluation certainly looks very complicated, as does the circuitry in a die photo of the VIC-II.

One thing that strikes me about all these sprite systems is that they are unrestricted in what can overlap what; you can have all eight sprites overlapping each other, with parts of background showing through, so that each pixel can come from one of nine different sources, and the hardware guarantees to handle this perfectly.

Intuitively, it seems like it should be possible to greatly simplify the circuits if you can place some restrictions on this, e.g. if the programmer can guarantee that sprites will never overlap each other, and that they will be presented in numerically increasing order on each scan line. For many games, it would be trivial to make the no-overlap guarantee (e.g. enemy attack waves fly in set patterns that never overlap anyway) and cost little CPU time to also ensure numerically increasing order (sprite 0 always to the left of sprite 1 etc).

So:

Did historical sprite systems provide unrestricted positioning and overlap because the designers believed this was very valuable in reducing game development cost? Or was it because my intuition is wrong (which is quite possible; I'm a programmer, not a hardware engineer), and once you are implementing sprites at all, the cheapest implementation provides unrestricted positioning and overlap more or less automatically?

Answer 1

Hardware of this sort has to be able to cope with the worst-case scenario in any given dot-clock cycle. So it has to look at the top layer pixel, determine whether that is transparent, and if so go down to the next layer and repeat. Only when it finds an opaque pixel (which may be the background) can it determine the colour to drive the video output with.

Most sprite hardware of this era therefore handles only a limited number of sprites. In the case of the VIC-II used in the C64, that's 8 sprites. The sprite registers can be reprogrammed each scanline (and this is commonly done in the demoscene), so there can be many sprites on screen in total, but only 8 on any given scanline. In effect, this concept serves as a restriction on sprite placement, just as you describe.

Many SVGA cards for the PC can handle a single sprite, which is used for the mouse pointer; most of the early Macintosh display hardware (up to the PCI PowerMac era) didn't even have that.

Modern hardware, such as Broadcom's VideoCore series, can be capable of handling a much larger number of sprites. This is achieved through the use of buffering and read-ahead, so that the worst case can occasionally be accommodated even if it exceeds the throughput of the memory and processing hardware. But most games now implement sprites using the painter's algorithm, redrawing frames from scratch, rather than relying on the scanout hardware's capabilities; this is equivalent to providing enough read-ahead buffer for the whole frame.

Answer 2

TL;DR

Did historical sprite systems provide unrestricted positioning and overlap

It wasn't unlimited and unrestricted, but limited by chip resources or memory bandwidth - or in case of inbetween systems by both.

because the designers believed this was very valuable in reducing game development cost?

No. Keep in mind, they often crippled machines quite hard to save a few gates.

[...] and once you are implementing sprites at all, the cheapest implementation provides unrestricted positioning and overlap more or less automatically?

Yes, but:

• With off-chip sprite data the number of sprites is only limited by the RAM addressable (the way chosen to do so), but the number of sprites in a given time frame (like a line) heavily depends on the memory bandwidth available. The 9918 for example allows 32 sprites, but only 4 of them may share any given line.

• With on-chip memory the main limitation is the amount of chip space than can be afforded for storage - not much back then. Prioritization and access effort grows linear with the number of sprites available, but delivers free overlapping of any number of sprites

Well, and then there is the "inbetween" selected by some manufacturers:

• On-chip memory holds only management information (state, coordinates, etc.) but display data is held in off-chip RAM. The examples were Commodore's VIC systems. This combines the disadvantages of both. While it does allow full range checking, the number of sprites displayable within a line is limited by RAM access available.

  The number of sprites only scales up to how much data can be read within a line. After that, additional measures for priority management would be needed, increasing cost while delivering a diminishing benefit.

---

The Long Read

[Prefix: No need to be a hardware buff - the whole issue in hardware is much the same as in software. It's about optimized data structures and the time needed to process the data, and the more straight forward processing is, the more can be done in a given time. In contrast, hardware can parallelize certain tasks already at low/simple level, gaining performance in areas software can't follow]

To start with, it's important to keep in mind that sprites are not something great to have, but rather a way to position objects on a pixel base on systems that lack a memory (and processing) bandwidth to do so in plain bitmap. Still, why being a crouch to help around this, the are as well limited by the same mechanics - just, due different access patterns, in a different ways than the main CPU.

The basic process for a controller with multiple sprites is to decide which sprites to display on a line and in which order. This means going thru coordinate storage and comparing to find overlap and sequence within a line, then moving relevant data on bit level into an output register, mixing them, only keeping the highest priority one in case of collision and outputting it.

In general there are two major hurdles:

• Memory access within a certain amount of time and
• memory addressable when doing so.

Memory to hold sprite data can be used in two ways:

• General purpose screen memory.
• Specialized on chip memory.

While sprite controllers using general purpose memory do allow a large, almost unlimited number of sprites to be handled, their operation is rather slow because each item has to be fetched over and over again.

The very common 9918 family is probably the best example here. Despite being one of the very first designs, it can handle a whopping 32 (monochrome) sprites within a picture (*1). But not more than 4 of them can be (have parts) within the same scan line. This is simply due the fact that there isn't enough time to check all coordinates and fetch all display data to do so.

The most restricting factor is RAM bandwidth, as it defines how many checks can be made.

[Collision detection, BTW, is just a side effect of drawing them on a line, when data is touched for drawing its coordinates needs to be checked when to insert and in which order. This automaticly implies a check on pixel level, all needed in addition is a comparison on each pixel when drawn if there were two sprites active.]

Sprite controllers with dedicated, on-chip memory (registers) in contrast can reduce this stress and offer faster access or even parallel processing.

This comes at a cost of making (relatively) large on-chip memories. An 8x8 monochrome sprite needs 64 bits of storage. With decoding and buffers its safe to assume 10 transistors per (static) bit. In addition at least another 18-24 bits are needed for coordinates and control storage, resulting in more than 500 transistors (*2, 3). So 8 sprites would already eat up the whole budget of a 6502 type chip. Just for storage, without any display logic at all. Using the 6845 as base, it will be about the same - and we still haven't the most important part added: selection and priority logic.

So first the most restricting factor for sprites is RAM size, but selection and mixing will add as well.

First step to placing a sprite is selecting if one (or more) of them is to be inserted on the actual line. This can be done by:

1. Cycle thru all coordinate storage, find all the sprites that match the line and merge them. This is essentially the same as with off-chip storage. Except it can of course be done faster and storage can be organized in a way to allow more direct access.

2. Using tagged addressing to for sprite line. This means instead of some comparator looping over all sprite line entries to see if it's the actual line, each sprite gets a separate comparator for each of it's lines, firing if this line is the same as the actual one. This is very fast. Results are gained in parallel and basically instant. It does allow (in theory) an unlimited amount of sprites. Except, it's extremely costly. A comparator needs an effort similar to a storage cell. Adding one to each sprite line effectively doubles the chip size needed.

3. Using a tagged and indexed addressing. Here only the top line coordinate of a sprite is held in tagged memory. When its comparator fires, a counter is started with the sprite height marking it over the following lines as active.

Mixing is again done in a similar way, but now according to horizontal (pixel) position. Again each sprite needs to be checked when to start supplying pixels. Again a tagged construction will give the best results. But now the addressed pixels need as well to be selected and mixed according to priority.

The most versatile solution is to give each sprite a read out register. Whenever the pixel position equals the X coordinate of a sprite its active line is copied and addressed as the pixel stream advances. To address a dedicated pixel counter or a shift register can be used. Either way, this needs as much read out circuitry as there are sprites.

Additionally a priority logic is to be applied to see which of the pixel streams (background and all selected sprites) takes precedence. Such a logic is a rather simple network of switches. Simple, but space consuming as all of them have to be connected. Here lies a further way to spend (or save) on chip estate: the network gets way more simple if the assigned priority is fixed with each sprites storage. Variable priorities require a lot more connections.

[Visible or not is BTW a simple addition, as it just means sending 'transparent' thru the network during the whole sprite duration.]

Now, at first sight there might be a way so save some readout/shift register, by having them global and only load them with the top priority overlapping sprites. It would save on the registers and even more on the priority logic, as it now only needs considering the smaller number of high priority sprites.

Then again, the original priority logic is still needed to find the multiple top priority among all sprites - plus somewhat more complex logic is needed to load, reload, and eventually even rearrange the registers on the fly.

As a result, reducing the number of active sprites will not save but increase cost.

Bottom line: The main cost for on-chip sprites is storage, everything else that follows is linear. There is no gain in restricting functionality, making numbers of sprites limited by RAM available.

---

Are Sprites a Good Idea at all - or why did they vanish?

The underlying mechanics can easily be seen by how (2D) graphics evolved.

• First there was character based display, when moving only one byte per 64 pixels was already a considerable task.

• Next the definable characters were added to allow (comperable) high resolution graphics. Kind of a compromise between full scale bitmap and character based (indexed) graphics, keeping memory bandwidth needed for manipulation mostly down.

• About the same time sprites were added to allow fast manipulation of a few pixel wise moveable objects.

• When memory not only became large enough to house full size bitmap, but as well fast enough to allow in time bitmap manipulations, sprite based controllers got replaced by specialized DMA engines called blitters. These could perform full bitmap manipulation faster than the still rather slow main CPU, while getting rid of all sprite based limitations.

• Finally, when main CPUs got fast enough to not only handle its program, but as well sufficient data in time, all of this got abandoned in favour of plain bitmap.

Sprites always have been a substitute to circumvent (memory) speed issues.

---

*1 - Of course this number can be even further increased by exchanging them on the fly.

*2 - Motorola's 6810 128 Byte RAM had ~7000 transistors, or ~7 per bit.

*3 - Yes, this can be reduced by using dynamic storage, which would save a lot on the storage side, but at the same time needs refresh logic. Refresh logic doesn't scale with size. So while it is almost insignificant with large memories, it doesn't do well for small amounts.

Answer 3

if the programmer can guarantee that sprites will never overlap each other, and that they will be presented in numerically increasing order on each scan line.

A hardware designer's response would be "programmers can't actually guarantee that." And they'd be right.

The hardware would have to be designed to do something sensible if those rules were broken. They often would be during development of games, owing to annoying things called "bugs", but if the hardware were to drop a frame, or otherwise misbehave, there would be endless complaints and the hardware would acquire a reputation for unreliability. That's deadly for a manufacturer.

The best way to design hardware if you want it to become popular is to give it simple and reliable behaviour, and restrict its capabilities to what you can implement with that restriction. The market successes of fairly simple 8-bit machines like the Commodore 64 illustrate the point.

Answer 4

Supposing you have a fixed pixel output clock then the bottlenecks are:

• shifters, since you need to be sure you may need to sample any sprite at the current location; and either:
  • bandwidth to fill those shifters, if you're a TMS descendant (which includes all 2d Sega consoles) and are fetching sprite contents from regular video RAM; or
  • storage for what will go into those shifters, if you're more like an Atari or a C64 and are expecting the programmer to push into dedicated registers.

Guaranteeing no overlap would be a benefit only if you can resolve the reloading the shift register problem.

If you want to run with the Atari/Commodore approach of requiring the programmer to push contents then you're going to put a huge burden on the CPU (and, actually, on at least some of those systems you've already got that options, as some will allow sprites to be triggered arbitrarily many times per line as long as the ephemeral coordinates match up).

If you're going with a TMS-esque fetch-sprites-from-memory then either you need time to search the whole list again, which is unreasonable bandwidth, or you're going to require programmers to have the sprite list fully sorted. That's sorted per scan line. So you're actually doing very little to save time over the developer just drawing the sprites for themselves — indeed possibly you're doing worse because if you draw the sprites yourself then you're effectively doing a bucket sort, which is why almost nobody thinks of painting sprites as a pixel sorting problem.

Most interesting data point is probably the Gameboy. It has an advantage that almost no other sprite system has: there's no deadline. It is in full control of its display clock, and it uses that fact. The amount of time spent outputting pixels per line is variable. It uses an algorithm close enough to:

• seed a 16-bit shifter with the first two columns of background;
• if the current scroll position isn't exactly column-aligned, spend some cycles shifting prior to outputting any pixels;
• when shifting the output:
  • if there are now fewer than 8 pixels in the shifter, fetch some more background;
  • if no sprite is positioned at the x position now reached, output whatever is at the head of the shifter and continue;
  • otherwise, spend some cycles fetching the graphic that goes with the sprite at the current x, composite those onto the shifter, then continue.

Therefore the output is irregularly clocked, with pauses accruing whenever the output position hits the start of a sprite.

Yet Nintendo capped themselves at 10 sprites per line, for two reasons:

1. to put an upper limit on line generation time, making them able to enforce 60Hz output (otherwise whatever is left over after shifting is available to the programmer to access VRAM; line cadence is fixed despite lines being variable length); and
2. to ensure that the number of comparisons per shift position has a fixed cost.

Point (2) there being specifically to avoid the programmer having to sort anything. In fact, they ended up at the opposite extreme: on most other systems you can affect sprite priority through sprite ordering. On the Gameboy you can't, priority is a direct function of position. So Nintendo started from relaxed time constraints and ended up doing the opposite of leaning into offering benefits for sorted sprite data.

Possibly the Nintendo example is informative in another sense: sprite quantity just isn't what they were optimising for. Programmer ease seems to have been the preference.

EDIT: for more specifics on the Gameboy, I'm really sorry, but all I can find is a video. It's a good video but still just a video.

Answer 5

The other posts about hardware and gate costs better answer your question, but I'll add this as a counterpoint: A situation where a game programmer decided not to take advantage of hardware collision detection (in this case, for the Atari 8-bit port of Super Pac-Man):

On the 400/800 I noticed that people knee-jerked toward using the player-missile hardware way too early in the design process, and that these special resources tended to blind people to the box’s real power…

Hardware collision detection sucks in a lot of instances, but people used it because it was there to be used. The player loses a life because one of his outlying pixels happened to hit a single enemy pixel — that’s really unforgiving, and games that used it irritated the heck out of me. You know the tension when a Pac-ghost is right on your tail and you whip around a corner and get that last dot just as the ghost is about to eat you? You can’t get that feeling with pixel-perfect collision detection, the game just bloody clobbers you, and it feels mechanical and unfair…

So collisions in Super Pac-Man were done with cross-shaped bounding boxes on the player and the ghosts. You could overlap the ghosts slightly, get away with it and feel like you cheated the game a little.

The entire post—indeed, the entire blog—is well worth diving into for first-hand accounts of developing for the Atari 8-bit & 16-bit lines, Atari's corporate culture/history, technical insights, and working for the Tramiel family.

Answer 6

The Atari 7800 kept almost all information about sprites, including positions, in general-purpose RAM, re-fetching it every scan line. Any time the RAM spent serving up sprite data was time stolen from the CPU, so the amount of data one could display was very dependent upon how much CPU time one wanted to have left.

The hardware didn't make decisions about whether or not to fetch sprites based upon their positions. Instead, the programmer would divide the screen into zones of 8 or 16 pixels, and for each zone provide a list of sprites in that zone. For each sprite in the list, the data in RAM would specify the X position, mode, and either a data address for the bitmap, or the address of data that would specify the least-significant-byte of the bitmap address (useful for blocks of text). I don't remember exactly how much data could be accommodated, but I think it could accommodate about six sprites that were about a third the width of the screen, or a couple of dozen really small sprites, or various quantities in between.

Answer 7

One thing that strikes me about all these sprite systems is that they are unrestricted in what can overlap what; you can have all eight sprites overlapping each other, with parts of background showing through, so that each pixel can come from one of nine different sources, and the hardware guarantees to handle this perfectly.

The majority of earlier games can have more than 5 or 6 moving objects on the screen. And you cannot predict where they can be. Take Pacman for instance: 4 sprites for the ghosts, that can overlap, and 1 sprite for the main character, that can be very close to the ghosts too.

And arcade machines are a different case: they know what game they'll have to run, so the hardware is designed with the game in mind. Not the case with generic consoles/computers.

So 8 unrestricted sprites isn't a luxury. If there were less, it would be even more difficult to use.

For instance, the Amiga (OCS) has 8 sprites, but they can have 3 colors max (+ transparent) and each group of 2 sprites share the same 4 color palette.

The sprites can also be combined into bigger/more colorful ones, that makes 4 of them now...

In a lot of games, the sprites are multiplexed by optimizing their vertical display using dynamic reuse of the registers according to scanlines. When a worst case happens (ex: all bullets are roughly on the same rasterline) you get flashes. See? there are restrictions even with 8 sprites, because 16-bit games have a lot of simultaneous objects on the screen.

Also (still on the amiga) when you cannot use sprites because you don't have enough of them, or they're too small, or not enough colors, you have to use classic graphics. Even with a shifting/blitting chip, you have to perform some masking & some restoring of the background. And it costs CPU/blitter time. In amiga games, sprites are used in combination of other classic non-sprite techniques mostly to gain cycles.