While in the previous article I was only philosophizing, in this one, I’m getting somewhat less theoretical. It’s still a ways away from having working code, though.

I found an answer on the Retrocomputing Stackexchange site, explaining how software sprites “work”. In my own words:

Sprites are rectangles of image data that are put in video memory, so the video processor can display them on a video screen. Sprites always need one of the colors to be transparent (invisible). In a two-color display that usually is black (0), while the visible color is non-black (1). The invisible color could be considered the background color, the visible color the foreground color. However, with a background drawn on screen, things can get confusing.

To enable mixing of sprite images with the background image, for every sprite image there should be a mask to punch a whole into the background. The mask contains 0s where the sprite image is visible; 1s where the sprite image is transparent. It makes sense to precompute mask data for efficiency.

Sprite data is drawn on top of image data. First, the background is masked out where the sprite will appear, resulting in a “hole” in the background. Second, this hole is filled with sprite data. Of course, if the sprite was moved, the original background image of that previous location should be restored too.

On older PCs (read: in certain display modes) colors are planar, which means that each color is stored in its own block of memory, instead of combined into a single memory block (one or more bytes of color information per pixel). Each color plane has to be processed first by punching a hole with the same mask and then filling the hole with sprite image data, specific for that color.

The (generic) algorithm for drawing sprites is as follows:

  1. erase the previous position, if any, by copying the original background at the previous location
  2. establish the address of the rectangle in video memory where the sprite should appear
  3. apply AND with the mask on this rectangle to “cut” data behind the mask; now there is a hole in the background where the mask is
  4. apply OR with the sprite image data to insert it into the background image; OR will only draw inside the cut mask

On the C64, things are quite different if bitmap graphics is to be ignored (too slow in most cases). In two-color (monochrome) character display, there are 1000 character positions (25 lines of 40 characters). The characters can be programmed by changing their image data (8 rows of 8 columns of pixels). In character generator memory, blocks of 8 bytes (8 by 8 pixels) are stored for each of the 256 characters that are in a character set. To display a character, its code is stored in screen memory, depending on the character’s location (column and row) on the video screen.

Let’s imagine a single 8 by 8 character (organized as 8 rows of 8 bits, 64 bits in total). Since the characters don’t represent text, but rather images, it’s probably better to refer to them with the more generic term “glyph”. A glyph can be a character, but also an image, e.g. a sprite.

To remove a sprite from the previous position, the previous glyph code that represented the background in that position is put back in screen memory. The background glyph code should be stored somewhere separately if it isn’t possible to determine that code from its position alone.

To put a sprite in its new position, some bit manipulation has to be done, combining the original image data of the background glyph with that of the sprite and store the result into image data for the glyph that displays a sprite-on-background.

The data structure that contains a sprite could look something like this:

  • memory address in screen memory (2 bytes)
  • background glyph code (1 byte)
  • sprite-on-background glyph code (1 byte)
  • sprite image data (8 bytes)
  • sprite mask image data (8 bytes)

That is 20 bytes in total for displaying a single 8 by 8 square of pixels. That could be 8 bytes less if the sprite mask image data is computed on the fly.

From the steps above in the general case, the C64-specific steps would look like as follows:

  1. if the sprite was already being displayed, write the background glyph code into the memory address in screen memory
  2. calculate the current memory address in screen memory, based on the given sprite location
  3. store the glyph code in the memory address in screen memory in the background glyph code
  4. AND every of the 8 bytes of mask data with the corresponding bytes of background image data, as determined by the background glyph code and store the result in the 8 bytes of image data for the glyph that displays sprite-on-background
  5. OR every of the 8 bytes of sprite image data with the corresponding 8 bytes of the sprite-on-background image; store the result back into the sprite-on-background image
  6. write the sprite-on-background glyph into the current memory address in screen memory

That is a lot of overhead and storage space for sprite the size of a single character of text. If the sprite needs to be able to be moved left and right, up and down, with the resolution of a single pixel, things can get even more complicated and require even more resources (instruction cycles and storage space). It’s doubtful if this kind of accurate positioning is sensible, if one could use hardware sprites for pixel-wise movement instead.

I’m curious how this could be coded, and then recoded for efficiency (storage-wise and/or instruction-cycle-wise). I’m sure it depends on what is needed for the game.

To make it more interesting for video games, one would like to introduce colors, like in multi-color character mode, and bigger sprites. I might not get to this, because monochrome character mode seems daunting enough for me.