Discussion of blits (transparent sprites)

Ancient history

Many many years ago (circa 1990) I remember playing StarControl on an 8086 in one of the school's computer labs. I was astounded by the speed of the game, and by the fact that all the ships could get close and actually get caught on each other. One example is when I was playing the Yehat (the banana ship) and Ken was playing the Ilrath (purple cloaking ship). I turned around and ran into him full speed and got stuck on one of the wings of his ship. In the brief moments I had to observe this collison he killed me... but I started thinking about animation in a whole new way. Before we had Starcon, we were playing a game called DefRec. One of the students of the school (Jared Tarbell) had written in it Turbo Pascal 6.0 and it used astounding VGA 256 colour graphics (which was difficult to do at the time since you needed a special BGI for it). His code used putimage() and getimage() to display the ships. As most of you probably have noticed, when an image is drawn with putimage, it wipes out a rectangular region around it. StarCon had pixel perfect animation. So, I started thinking about it...

The school I went to (which was separate from my normal high school) was a magnet school, and the classes were about an hour and a half long. This was wonderful since the teacher pretty much let you do whatever you wanted as long as you were doing something productive. Many hours were spent doing simple moving animations. Eventually I stumbled across the XOR/AND method of animation. Ken drew a really kool animated ninja that moved across a background. It was a decent speed, but you could see the XOR mask being drawn (keep in mind that this was on a 286 or 386 at most, and we didn't have the knowledge needed for double-buffering). So, my quest for better animation techniques ventured on...

I started learning some assembler and eventually ditched the BGI. Our next method of drawing transparent sprites was to use the CMP if zero technique. I'm sure most of you have done this at one point or another. You simply go along comparing every pixel to see if it is a zero. If it is, don't draw it. If it isn't, draw it. Well, that was nice in that it did the job, but is just wasn't fast on large images. Then the breakthrough...

Amigas and Cookie Cutters

But first, a side note. Transparent images on the Amiga are a piece of cake. This is due to a piece of hardware called a blitter. What the blitter did was cut a hole in the background that was the shape of the image you wanted to display. Then, it would draw the image in the hole. It was a fancy hardware cookie-cutter. I had an old demo of Leander, and occasionally it would crash. On one occasion it crashed right after the blitter had cut the hole but before the image had been drawn. This gave me the important clue I needed.

The Epiphany

In April of 1992 I was sitting at a local IHOP drinking coffee. I had drawn some sample images on the back of one of the place settings, and then it hit me. Instead of treating the image as though it were a bitmap, break the image into segments of pixels. That is, remove all the zeroes by converting the image into a series of runs and replacing the zeroes with an offset. The format was as follows:

First word: total_count (of segments)
repeat
  Next word: offset 
  Next word: run_count
  Run_count bytes: image data
for total_count times

The code to display that was incredibly easy:

	push	ds
	mov	es,Sega000
	mov	di,offset ;{y*320+x}
	lds	si,blit
	lodsw	; {total count}
	mov	dx,ax
@@lop:	lodsw	; {load offset}
	add	di,ax     ; {add offset}
	lodsw	; {load run_count}
	mov	cx,ax     ; {store in cx for rep}
	rep	movsb
	dec	dx        ; {dec totalcount, if not zero then more runs}
	jnz	@@lop
	pop	ds

That was it. It was incredibly fast and simple. Unfortunately, the getblit() routine took a really long time (several months) to write, as I was trying to do everything in a single pass fashion, optmized, and in assembly. This should be a good example of why you should optmizine your code after you have a working version of the routine. Still, when it was written it worked, and it was lightning. Nothing anyone else had done was even close to the speed. Of course, the getblit() routine created blits that only worked in 320x200, and required the image be at 0,0 on the screen so that the offsets would be correct (it simply scanned through screen memory creating the blit). While this was a very very poor method, the results were more than worth it.

Wally and His Weed Whacker

Well, the results were worth it until I started to write a parallax scrolling platform game called Wally and His Weed Whacker. The background was composed of 32x20 tiles, and the foreground was a bunch of 32x20 blits. Because some blits could be off the screen, I had to write blit clipping. That code was very difficult, and I never want to do it again. The left edge clipping was a nightmare, and the right edge required a lot of MODs by 320 (by way of a divide). Due to the linear nature of the blit, it was impossible to tell if the blit went over the right edge, so a nasty divide was needed for every single run. I've since come to my senses and rewritten the format. I'll discuss the technical side of Blit Format Version 2.0 (BFV2.0) later.

5 years later

Well, it is now 5 years later, the blit has come a long way, and the Enterprise has returned from it's 5 year mission. The basic premise of the blit is to take a bitmap, replace all the zeroes (or transparent colour, which is presumed to be zero) with an offset from the previous run of pixels, and then store all contiguous non-zero runs of pixels. If an image is made up of a large percentage of zeroes, the blit can be considerably smaller than the original bitmap. However, if there are a lot of runs of very few pixels (a checkerboard, for example), the image size can easily become many times larger than the original image. This is due to the overhead required for each run. Since you have to store an offset (usually a 16-bit value) and a count of pixels (also a 16-bit value) a checkerboard composed of a single on/single off pixel pattern would end up being at least 5 times bigger than the bitmap. The moral of the story is to not draw checkerboards with blit routines. As far as I can tell, if at least 10% of the image is transparent your blit will be smaller than your bitmap.

The "other" method, which is evil and bad and sloppy and you should never use it

I suppose since I've covered almost all of the known ways to draw a sprite transparently I should discuss compiled sprites. I've met people that use this method, and every time I do I wonder, "How do these people actually get jobs programming software?" A compiled sprite is a sprite that has been converted into code that draws it a pixel at a time. Usually you will run the bitmap through a compiler of sorts, and this compiler will spit out the code which can draw the image correctly (ie, draw a pixel, add some amount to di, draw another pixel, add some amount to di, etc). While this method is slightly faster than comparing for zeroes, almost all of your compiled sprites end up 4 times bigger than your bitmap. I've never found an appropiate use of these, and I abhor programmers that use them (if any will admit it). The code is completely useless in other resolutions as the offsets are hard wired into the code! Don't even think about clipping. And with higher resolutions using bank switching, it is nearly impossible to produce a useful compiled sprite.