A bit of a shift. (computer graphics) (part 8) (column) David Lubar.

Let me open with a short story. A year or two ago, I was convinced that there was some standard set of graphics routines along the lines of those in ROM, and that these routines were used by all the top programmers. It was a natural enough assumption, since many early programs did use some version of the hi-res routines supplied by Apple in the demo tapes. I was sure some "souped up" version of these was making the rounds.

Bob Bishop was kind enough to straighten me out, explaining that there were no standard routines. Indeed, many programmers created specialized routines for each new game. The key to these routines is the concept of pre-shifted shapes.

After learning of this, I procrastinated for a while, afraid that the task of coding such concepts would be enormous. Finally, I gave it a shot, and was pleasantly surprised to learn that a plotting routine for pre-shifted shapes is both simple and short. Before presenting the code, however, I want to go over the ideas behind shifting shapes. Unlucky Seven

If you have followed this series from the start, you already know how each bit in a byte is mapped to the screen. For those who are just joining us, here is a quick recap. Each byte in screen memory controls seven pixels. The highest bit controls color. The other seven bits are free to produce patterns of lit and unlit dots.

The bits appear on the screen in what seems to be a backwards fashion. The lowest bit produces the leftmost pixel of the group. To put a specific shape on the screen, you must create the bit pattern and place those bytes in screen memory.

As we saw when dealing with character graphics, such shapes can be moved across the screen by moving the bytes to successive horizontal positions. But moving a byte causes a shape to move seven bits. Smooth animation requires smaller moves. As a first example, let's examine the case of the simplest possible shape--a single dot.

The bit pattern for such a shape might be 00000001. This, if placed in screen memory, would produce a single lit pixel in the leftmost position of the byte (as mentioned, the bits plot in a "backwards" in location $2000. The first pixel of the hi-res screen would be lit. If the byte were moved to $2001, the pixel would jump seven places. To produce a small move, the byte value must be changed.

The seven positions, in hex, are 01, 02, 04, 08, 10, 20, and 40. If you put these values into location $2000, you will see a single dot move toward the right, one step at a time. Note that it alternates colors. If you skip every second value, the bit will move two locations at a time and maintain its colour.

Now, if you wanted to animate such shape in a program, you could perform the shifts on the fly, figuring out the required value based on the desired location of the pixel. For the case of a single dot, this is a simple, brief calculation. But, for any more-complex shape, the process becomes tedious and slow. Bits that are shifted out of one byte must be shifted into the next byte, and the hi bit must be skipped over.

The solution, and a technique used in virtually all modern games, it to pre-shift the shape. The programmer first creates the byte pattern for the shape. Then he calculates six more sets of values, one for each of the possible starting positions for the shape.

Basically, there are two ways to calculate the shifts. One is to use graph paper and actually draw the shape seven times, then figure out the byte values. The other method is to calculate the first set of byte values, then just shift the numbers for each new view. These seven shifted versions are placed in a table. A plotting routine can access the correct set of bytes and place the shape in the desired location.

Figure 1 shows one method for creating such a table. Note that the shape, when shifted, requires an extra byte to the right for expansion. A shape generally requires an extra byte for each line, except in cases in which only the first bit of the rightmost byte is plotted. In such cases, that bit will not be shifted far enough to require another byte.

Once the table of the seven shifts is produced, we need a way to access the desired shift. One method is to use an index. The table is preceded by a series of index bytes giving the location of each shifted image. To allow flexibility, the index doesn't give an absolute location, but instead gives the offset from the beginning of the table. In contrast to the standard format, this offset is given with the hi byte first. If you look at the plotting code, you will see that this method saves a bit of time when calculating the address. Thanks go to Mark Pelczarski for informing me of this neat trick.

Since shapes can be various sizes, and we want the plotting routine to handle whatever we feed it, each shifted definition is preceded by information on the height and width of the shape. First comes a value telling how many bytes across the shape is, followed by the number of lines the shape occupies vertically. A sample table is shown in Figure 2.

So, now we have a table containing the correct values required to place a shape on any bit within a byte. The next step is to produce a routine that will display this table. Here, we begin to encounter the diversity of graphics styles.

There are many ways to put an image on the screen, and many ways to handle the various indexing requirements. The routine presented here lies somewhere between simple but slow code and fast but complex dedicated routines. It is a good starting point, and can be the basis for many kinds of subroutines. Afterwards, we shall look at some of the other approaches in use. For now, let's get down to plotting. Hatching Plots

Since the plotting code is subroutine, it will require certain parameters. Obviously, we must tell it the desired x and y coordinates of the shape. And, in case we are dealing with more than one shape, we should also provide a shape number.

Because the table contains versions of the shape for each bit position within a byte, it is convenient to break up the x coordinate into its bit and byte values. For example, horizontal location 0 is considered byte 0, bit 0. Location 2 is byte 0, bit 3; location 7 is byte 1, bit 1; and so on. You might recognize this as MOD 7 arithmetic. Later, we'll look at methods for calculating this value.

For now, take a look at Figure 3, which shows the byte/bit system. They coordinate is just the desired vertical locations. So much for the parameters. Let's take a look at the routine.

The code, shown in Listing 1, first uses the shape number to find the location of the desired shape definition. This is contained in a table. The table can be placed in any free area of memory. I chose to put it after the screen lookup table. When using this program, you will have to place the proper index values for your shapes in this table.

Next, the program uses the value XBIT to determine the location of the desired shifted version of the shape. This is where we get to the one tricky part of the code.

The 6502 is gifted with a less-than-huge selection of index registers. We will be using indirect Y to place the bytes on the screen. This leaves the X register for accessing each byte of the shape. Since indirect X indexing is slow and awkward, the ideal approach is to use absolute X indexing. In order to do this, we must resort to self modifying code.

The routine accesses the shape bytes with the command LDA ADDRESS, X. Before reaching this code, the value of the address is modified to point to the desired shape bytes. Once this has been done. We can start plotting.

Each shape is preceded by its width and height in bytes. This information is moved in a scratch area (the sample program uses part of the unused hi-res area for scratch storage, but this can be changed to zero page locations to increase speed of operation).

The program contains two loops; the inner loop grabs each byte of a line, and the outer one loops through each line of the shape. The code also checks for screen boundaries, clipping any shape that goes beyond the screen. This half page of code is all that is required to place a shape on the screen. The code also contains a collision check. This, and the check for screen boundaries, are excess baggage. If your application doesn't require them, they can be eliminated.

As mentioned, the code requires you to pass on bit and byte values for the x coordinate. There are several ways to obtain this value. One way is to perform a MOD 7 loop. Take the x coordinate and divide it by seven. The result is the X byte; the remainder is the bit.

A faster approach is to use a set of lookup tables, one containing the byte values, the other containing the bit values. The byte table would begin with seven 0's, the seven 1's, seven 2's and so on. The bit table would cycle from 0 through 6 repeatedly.

The easiest way to create such a table is to write a Basic program that POKES the values into memory, and then to save the table to disk. The third method is to update the byte and bit values constantly as the shape moves. But this is slow and tedious.

One advantage to using the byte/bit method is that objects can be tracked when they leave the screen. Since the screen is only 40 bytes across, and since the byte variable can go up to 255, you can keep track of the position of an object over an area that is actually more than six screens wide.

As an example of how this plotting routine might be used, Listing 2 contains a program that demonstrates animation and collision detection. It puts a small square and a ball on the screen. You control the ball with the keys, using A, Z, left arrow, and right arrow for movement, space to halt movement, and escape to leave the program (this is the same control method used in the character animation program we saw a while back). Whenever the ball hits the square, the program restarts. Naturally, any real game would do something more spectacular at this point.

Note that the MOD subroutine only handles values up to 255. To go higher, the routine would have to be modified to handle a two-byte value. The plotting routine uses exclusive or to draw and erase the shape. This is just one of many possible approaches, which brings us to our next topic and our question of the month.

Charles Kluepfel wrote to ask whether exclusive or is still the best method for plotting, or whether other techniques have made it obsolete. Getting It On

A byte can be placed on the screen in various ways. Each method has advantages and drawbacks. The advantage to exclusive or it that it leaves the background undisturbed. The first EOR puts the shape up, a second EOR with the same shape and coordinates erases the shape, restoring the background. Any number of shapes can overlap, and they can be removed in any order, leaving the background the way it was after the last shape leaves.

The disadvantage is that when shapes overlap, black areas are produced. If two identical shapes are plotted in the same location, both will vanish until one is moved. Still, EOR is fast and efficient, and has been used with fine results in many games. Bandits and Tsunami are two good examples of games that use exclusive or for plotting.

A faster method is to use a straight block draw. Here, instead of the sequence of an exclusive or followed by a store, the shape definition is just stored to the screen. The shape actually wipes out anything underneath it.

While this wiping out might seem to be a liability, it has one powerful aspect. Since it wipes out whatever was there before, it can be used to erase itself.

If the shape is defined with a blank border around it, and the border is as high and wide as the larget move the shape will make, the image never has to be erased. Every time it is plotted, it will wipe out the old image. This produces fast plots.

The biggest disadvantage is that as shapes overlap, the top shape will pipe out a portion of any shape plotted previously. Good examples of this technique can be seen in Space Eggs and Gorgon.

For really clean animation, the shape can be put on the screen with ORA. This produces some of the cleanest graphics around, at the cost of some loss of speed. Take a look at the portion of Beer Run where the blimp passes behind the ledges. I asked Mark Turmell how he achieved this clean animation. He explained that he combines orring with page flipping. The shapes are placed on the unseen screen with ORA, and erased with AND or just by storing 0's to the area occupied by the shape. IT is this erasure that creates a potential problem.

When a shape is erased using AND (generally, the shape byte is first EORed with $FF, producing a "negative" of the mask, and then ANDed with the screen), any background beneath the shape is also erased.

There are two possible solutions. One is to store the original background somewhere. The other is to redraw anything that might be erased. In Beer Run, the ladders are redrawn every time.

These, and other methods, are all in current use. The selection depends on the specific requirements of the program. Once you are familiar with these techniques, you will be able to tell how most games are done by just looking carefully at the graphics. Each technique has its distinct signature.

There is no need for each shift of a shape to be identical. It is possible to produce internal animation by changing positions in each of the seven shifts. This way, as an object moves horizontally, it also becomes animated. I am not positive, but I believe this is the technique used in Apple Panic to animate the running man and the enemy apples.

If the shape is to be moved one pixel at a time, the animation is created in sequence from the first to last shift. If the shape is moved two bits at a time to preserve color, the sequence is 1,3,5,7,2,4,6 since this is the order in which the shifted versions will occur.

For internal animation when a shape is moving vertically, or remaining in one place, you merely use a sequence of different shapes. In some cases, two views are sufficient; at other times, more are needed.

Not only are there many ways to put an image on the screen, there are also various approaches to a plotting program. As mentioned, the one above lies in the middle as far as speed and complexity are concerned. Some programs contain highly dedicated plotting routines, similar to the dedicated scrolling mentioned last month. Since such routines can vary enormously depending on the nature of the program, I'll just discuss the basic concept here.

Let's say you want to plot many instances of a single shape. Since the width and height of the shape will be constant, there is no reason to pass this information to the plotting routine. A special routine can be coded which is designed for a shape of that particular size.

Going further, it is conceivable that you would have seven plotting routiness--one for each shifted location--each of which contained the desired byte values, thus avoiding any need to index into a table for the shape bytes. The use of indirect Y, one of the bottlenecks of graphics, can be bypassed using routines that already contain the required addresses. And, as already mentioned, any frills, such as collision detection or boundary checks, can be stripped when not needed.

In general, whenever speed is essential, the plotting routine should be as specific and dedicated as possible. This eats up memory, but 48K is a lot of space. Come to think of it 48K is an incredible amount of space. I believe the first version of Microchess was written to run on a 1K Kim.

Many early Apple games, including some very nice graphics by Bob Bishop, were written in under 16K. I am currently involved in writting games for the Atari VCS which has a grand total of 4K of ROM and 128 bytes of RAM.

While I'm on the topic, and since even the most virtuous of columnists has been known to fall from grave with an occasional boast or plug, I may as well mention my new game, Fantastic Voyage (based on the movie and distributed by Fox Games). It has a few neat graphic touches, such as a clock and oscilloscope, and all in all I'm pleased with the