Time for a change

One of the many neat things in Time Pilot '84 is that the background palette is different for each level. The map stays the same, just the colours change, presumably to give an impression of time travel between levels. It adds variety and helps give each level an identity.

I wanted to do something like this in my game but the 6847 VDG doesn't exactly spoil you with choice. In four colour modes, the palette can be one of two colour sets: Green-Yellow-Blue-Red or Buff-Cyan-Magenta-Orange.

The word you are looking for is 'hideous'

Simply switching between these two colour sets doesn't look very good. The alternate colours don't make much visual sense:

Colour set 0

Colour set 1. Yuck.

The problem is that the bright parts of the image are no longer bright, resulting in a very unnatural looking image. However, if the colours are swapped around, it can be made to look a lot better:

Not so ugly

Also usable

My God, it's full of ice cream.

All the colours in half a rainbow

As I was thinking about moving colours around, I wondered how many usable palettes could be made by rearranging the original set 0 colours. It turns out there are quite a few. Each image caption below describes how the colours have been remapped from the original Green-Yellow-Blue-Red palette:

Red-Yellow-Blue-Green

Green-Yellow-Red-Blue

Blue-Yellow-Green-Red

Blue-Yellow-Red-Green

Red-Yellow-Green-Blue

Yellow-Green-Red-Blue

Yellow-Green-Blue-Red

That's a pretty good result. Some of the permutations look more alien than others, but I think that fits this type of game, and they still make visual sense because the brighter colours are where they should be.

So I've now got all these variations on the background map just by swapping the colours around. Awesomeness. But how do I go about making all these palettes actually happen?

One way would be to have a different set of tiles per palette, but that seems very wasteful of memory. It would be more efficient to manipulate the image data in memory to achieve the colour change between levels. A function is required to map the colours from one palette permutation to another.

Green is the new red

Let's say the existing palette is the usual Green-Yellow-Blue-Red and we want to change it to Red-Yellow-Blue-Green. This means that the green pixels need to be changed to red, the yellow and blue pixels stay the same, and the red pixels need to be changed to green.

Let's now change the palette to Green-Yellow-Red-Blue. This changes red to green, yellow stays the same again, blue changes to red and green changes to blue.

The colour changes are defined by comparing the new palette to the current palette. The new palette defines what we want the colours to be, but we need to refer to the current palette to define the colours we are changing from. That means we need to store the current palette for future reference, so let's have four palette registers numbered 0-3, and initialise them by storing the values 0-3 to represent the standard palette. (Green=0, Yellow=1, Blue=2, Red=3)

Updating the palette registers is easy, we just need to store the new palette values in them, but we also need to generate information to define the mapping of current colours into new colours.

To give an example, if we imagine changing the colours of a target image pixel by pixel, what we want to know is if the target pixel is green, what does it need to change to? To find out we need to look at the current palette registers, determine which one contains green, and then get the new colour from the same position in the new palette. It sounds like a lot of work.

It would be more efficient if we first laid out the new colours in a logical order: New green, new yellow, new blue, new red. Then we would know where to look to find the new colour for green. The following piece of code does exactly that. It looks at the current and new palettes, updates the current palette and creates a nicely ordered four byte mapping table:

      ldx #current_palette
      ldy #new_palette
      ldu #palette_map
      lda #4
      sta count
loop  lda ,x    ; current palette entry
      ldb ,y+   ; new palette entry
      stb ,x+   ; update current entry
      stb a,u   ; store in new mapping
      dec count
      bne loop


We can now change the colours of all four pixels in one byte using some code like the following. It recolours the pixels in A using the mapping table at U:

      ldx #4     ; 4 pixels per byte
loop  clrb       ;
      lsla       ; get one pixel in B
      rolb       ;
      lsla       ;
      rolb       ;
      ora b,u    ; look up and combine entry from mapping table
      leax -1,x  ;
      bne loop   ; next pixel

It's a little on the slow side. If I use it to directly recolour the contents of the four shift buffers as well as the tile graphics, it takes over a second. The way I've made it faster is to build a table containing the results of converting each possible value from 0 to 255. This table can then be used to quickly lookup converted colours a whole byte at a time. Much faster.

Rewriting history

I've made it sound like I arrived at a neat and tidy solution fairly quickly. The reality is very different. My first solution involved a 16 byte lookup table to convert the high and low nybbles of each byte separately. Then I came up with a faster and more simple piece of code that generated a 256 byte lookup table using recursion.

At the time, recursion seemed like a natural solution to the problem of generating a table containing every permutation of colours. It was only while writing this post that I revisited the code to remind myself how it works and settled on the even more simple current solution. As I prefer the current solution so much more than the previous ones, I've decided to pretend that was how I did it in the first place.

If we've learned anything from Bill & Ted, it's that only the winners get to go back in time and set things up. That is, as long as you don't pay much attention to the git history...

Shift work

Would you believe it?!

All this talk about tiles has real world repercussions: The new reality is that when someone has a shower upstairs, water comes out of the cooker hood downstairs.

Now, I'm fairly sure that isn't one of the advertised functions of the cooker hood. I couldn't find any mention of it in the manual. Extract steam? Check. Provide light? Check. Dribble minging second hand shower water into my glorious and most sacred Saturday Morning Fry Up? No. I didn't think so.

So according to 'professional' opinion, it would appear that the tiles around the shower weren't done 'properly', by a person or persons 'unknown', or possibly me and my father-in-law, and now after six years it has started leaking. And I can't just regrout it. Oh no, that would be way too easy. Those tiles have got to come off, and the wall fixed. And new tiles put back, because when my Wife gets involved, stuff 'has' to change colour.

None of this could possibly be my fault. Obviously greater forces are at work and it was talked up as a result of this blog. So please, be more careful in future. Careless talk costs £31 per square metre (inc. VAT).

True story.

Back to my happy place

So far I've described methods for scrolling in any direction, by drawing a relatively small amount of graphics into a buffer, and then copying the contents of the buffer to the display. This has given us pixel by pixel vertical scrolling, but the horizontal scrolling is still byte by byte. i.e. four pixels at a time in the chosen graphics mode. So what do we need to do to make the horizontal scroll work at the pixel level?

Early on in this sorry saga, many hump days ago, I spoke of The Idea. This involved four buffers, each containing the same screen image shifted by different amounts. The only time bit-shifting would be required is when new graphics are drawn into a buffer: Just a thin strip to fill in new background as it appears at the edge of the screen. Once in the buffer, there it will stay until it scrolls out of view again, making room for new graphics as it does so.

I call these four buffers shift buffers, numbered from zero to three. Shift buffer zero contains unshifted graphics. It works in the same way as the single buffer in the byte by byte scroll. The other shift buffers contain the same graphics shifted between one and three pixels to the left.

Each time we want to scroll horizontally, we need to choose one of the buffers into which we will draw new graphics. To keep track of where we are, we need a horizontal pixel counter. This is incremented each time we scroll right one pixel. (i.e. the background moves left one pixel)

The bottom two bits of the horizontal counter can therefore represent the number of the current shift buffer and we can use those two bits to look up the address of one of four drawing routines, each dedicated to drawing into a specific shift buffer.

Scrolling right, the shift buffers will be accessed in the sequence 0-1-2-3-0-1-2-3, and the buffer and map pointers will be incremented by one byte each time we land on buffer zero. (Because we have scrolled a new byte into view)

It's a similar story for scrolling left, except the sequence this time is 3-2-1-0-3-2-1-0, and the pointers need to be decremented each time we land on buffer three.

The buffer pointer now works slightly differently, as it represents the same position in all four buffers. So instead of pointing to an absolute address within one buffer, it is now an offset to be added to the base address of the current buffer.

Fab Four

So what do the four drawing routines look like? The buffer zero routine is the same as the one we already have for byte-by-byte horizontal scrolling. The others have more work to do. They have to shift the graphics data left by an amount that suits each buffer.

Now, when the pixels are shifted left, one or more of them will fall off the left hand edge of each byte. This is no problem because these will already be in the buffer. They were drawn during a previous frame. The problem is what happens on the right hand side of each byte. Where do the new pixels come from to fill up the space left by the other pixels moving left?

We Can Work it Out

The answer is the new pixels come from the half of the tile immediately to the right of the one being pointed to by the map pointer. This might be the right hand half of the same tile, or the left hand half of the next tile, or occasionally the left half of the tile from the left edge of the map thanks to wrapping. In each case, it means we need to load two bytes of tile data to create one byte of shifted data. The first byte is found via the map pointer, the second byte via the (wrapped) map pointer plus one.

If we get the first byte in the A register and the second byte in the B register then we are ready to do some shifting:

Source bytes before shifting

Remembering that each pixel is made up of two bits, the following sequence of instructions will shift left by one pixel and form the basis of the shift buffer one code:

    lda ,u++  ; get 1st byte

    ldb ,s++  ; get 2nd byte

    lslb      ; shift left one pixel..

    rola      ; ..by shifting two bits..

    lslb      ; ..from B..

    rola      ; ..into A

    sta ,x    ; store in buffer

    leax 32,x ; next row in buffer

    ; insert code to check for buffer boundary here

    ; loop above instructions eight times for complete tile

The U and S registers have been set up to point to tile graphics data. The X register is pointing into the shift buffer. The A and B registers look like this after shifting:

Shifted one pixel left

The shift instructions can be doubled up to create the shift buffer two routine:

Shifted two pixels left

And tripled to create the shift buffer three routine:

Shifted three pixels left

Back to the LSR

But shifting three pixels left is not very efficient. We can achieve the same result by shifting one pixel right instead. It just means the result ends up in the B register instead of the A register:

Shifted one pixel right

The four drawing routines all have the same general structure, the same logic behind the pointers, and the same technique for faster drawing using unrolled loops. They are so similar in fact that I have defined them in a macro, reducing the amount of effort in development and debugging. The macro just needs to be given the number of pixels to shift left as a parameter.

Now, finally, I was able to scroll pixel by pixel horizontally, and at a very high speed. That day was a good day. Well, it was a good day until I started scrolling vertically. The graphics were not updating correctly when scrolling horizontally after scrolling vertically. It soon became obvious that the vertical scroll routine needed to draw in all four shift buffers. I added a routine to take the newly drawn vertical scroll data from shift buffer zero, and write suitably shifted versions to the other buffers. Then it worked properly.

Shameless handwaving

I made one major improvement to the horizontal scrolling after that. It comes from the observation that the shift buffers all use the same source data, and that the shift buffer zero routine is relatively fast. The improvement is to calculate tile graphics addresses during the shift buffer zero routine only, and store those same addresses for re-use by the other shift routines. There are a couple of subtleties: Addresses need to be calculated for both left and right hand edges of the screen, so that the correct addresses are available when we change direction. It also becomes necessary to scroll the contents of the address buffers up and down during vertical scrolling, to keep the addresses in sync with the display.

I think that's quite enough rambling on about the scroll engine. Next time, something else!