[a continuation of Custom NES Video Codec]

Data compression is all about analyzing the nominal characteristics of a particular type of data and understanding how that data can best be coded using the least amount of information. Let’s look at some of the characteristics of NES video:

Fun NES Screenshots:
Battletoads	Blaster Master

The Guardian Legend	Shadowgate

The data is primarily composed of a background made up of 8×8 tiles that is overlaid with a series of 8×8 sprites (or 8×16 sprites which are technically just 2 stacked 8×8 tiles). The sprites may be moving over a background that stays in the same place from frame to frame. Or, the background might scroll horizontally, vertically, or both from frame to frame.

To illustrate using the above screenshots as examples, Shadowgate is a game in which the entire frame does not change very often. There is no background scrolling. In Blaster Master, the background scrolls in every direction and the status is represented as sprites on the left side of the screen. The Guardian Legend, when it does scroll, only scrolls in either the vertical or horizontal directions but never both at one time. It also uses a split screen for a status area; only the top 3/4 of the screen scrolls. Battletoads will be a severe aberration to any underlying assumptions that this codec makes. It achieves graphical effects that were considered very sophisticated on the NES. The screenshot above depicts a level in which there was a horizontally-split status screen and a vertical scrolling split.

If it becomes necessary to encode a block losslessly, it should often be possible to encode in using 4 bits vs. 5 bits. There is a good probability that a given 8×8 block will either be a background tile block or a sprite block. When this is the case, that block can only be rendered with one of the 16-color palettes. Thus, encode each pixel with only 4 bits (with an extra bit or two in front of the block to indicate encoding mode). It may be a little complicated to differentiate between a background/sprite/mixed block during encoding, though.

The driving force behind this video coding brainstorm is that a particular frame either does not change very much from one frame to the next. Either that, or the frame essentially remains the same from one frame to the next while shifting (scrolling) some small number of pixels either horizontally, vertically, or both.

Some games use trickier graphics such as split-screen status bars (like in the Battletoads and The Guardian Legend screenshots above). Some may have an inordinate amount of sprite action. So it may be useful to define a slice that is 8 pixels tall. When encoding each row, take into account the various directions it could have moved. Also, notice whether it has moved at all. Analyze current frame on a per-slice basis and figure out which ones have scrolled.

This codec is meant to be lossless. Thus, it is not necessarily appropriate to compare it to a lossy, constrained bit-rate codec such as MPEG-4. Still, it would be interesting to see how such a codec stacks up against MPEG-4 (and, more recently, H.264), which is what the movies are encoded with. I wrote a little tool to analyze exactly how many bytes are being used to encode the video on various videos taken from the Time Attack site. Here are some statistics (all stats assume 60 frames/second):

• tmnt-timeattackv2-walkerboh.avi
  68550 video frames, 19m2s running time, 43812013 total video bytes
  38364 avg video bytes/sec, 639 avg video bytes/frame
  min video frame = 8 bytes, max video frame = 20927 bytes
• battletoads-timeattack-phil,genisto.avi
  73386 video frames, 20m23s running time, 133500622 total video bytes
  109158 avg video bytes/sec, 1819 avg video bytes/frame
  min video frame = 7 bytes, max video frame = 30814 bytes
• aboyblob-timeattack-sjoerd.avi
  25148 video frames, 6m59s running time, 13294322 total video bytes
  31728 avg video bytes/sec, 528 avg video bytes/frame
  min video frame = 0 bytes, max video frame = 34679 bytes
• shadowgate-timeattack-walkerboh.avi
  35539 video frames, 9m52s running time, 13651521 total video bytes
  23060 avg video bytes/sec, 384 avg video bytes/frame
  min video frame = 38 bytes, max video frame = 43470 bytes

Hmm, I am not sure what to make of the minimum video frame size for Shadowgate. That’s one game where the frame does not change much. Then again, with these time attack videos, there is never a dull moment or frame (these folks are on a deadline!).