Fahrve Lives!

We are still barreling towards the end of Retrochallenge 2015/01, and the Apple II port of Fahrfall is still progressing nicely. We must be getting close, as the star of our show has finally started showing-up for dress rehearsals. Yes, ladies and gentleman, Fahrve now joins our party!

Low-Res Perspective

Representing Fahrve on the Apple II is a little tricky, at least when using the low-resolution video mode. The CoCo version of Fahrfall uses a video mode with a resolution of 64x96, while the Apple II low-resolution mode is 40x48. Obviously some scaling is required, but at such low resolutions scaling inevitably leads to distortions. Fahrve was already only slightly better than a "stick figure", and on the Apple II that is more true than ever. In particular, cutting the vertical resolution in half forced some compromises in the shoulder details and the thickness of the feet. The extra horizontal thickness of the blocks forced spreading the Fahrve graphics a bit wider as well, in order to get separation for the arms and legs.

A Tale Of Two Fahrves

Another quirk of the Apple II low-resolution mode required some consideration. The color of each pixel is encoded with 4-bits of data and two pixels are encoded in each byte, but the two pixels encoded are on different lines. This means that two pixels encoded in the same byte when plotting a figure on an even numbered line are suddenly encoded in different bytes when plotting the same figure on an odd numbered line!

This problem is not really any different from the problem of plotting a figure in a mode where multiple horizontal pixels are encoded in the same byte. One option is to use shift and rotate operations to transform a source image into a properly adjusted set of values in the video buffer. But that method is slow, and already awkward when dealing with horizontally encoded pixels. Using bit manipulations on vertically encoded pixels seems potentially even more awkward.

A better performing option is to use a different version of each sprite for each data alignment option. This increases the amount of memory required for sprite handling, but in this case we only require two versions of each sprite, one version for even-numbered lines and a second version for odd-numbered ones. Since I already have to keep track of Fahrve's vertical position anyway, choosing which sprite to display is reduced to a simple odd/even check on that number.

Sidestep: The Issue

When Fahrve moves from side to side, I depict him with one foot up and the other arm up as if he is shuffling to the side. The foot/arm up combination alternates between left/right and right/left as Fahrve continues to move on the platforms. Obviously, each of these sprites needs odd- and even-numbered line versions as well. That is four versions of Fahrve for horiztontal movment alone!

Along with the sideways-moving versions of Fahrve, there are odd and even versions of Fahrve standing still on the platform. There are also odd and even versions of Fahrve falling through the air with his feet pulled up and his hands above his head. Altogether there are eight versions of Fahrve for Fahrfall. For maximum performance, these are implemented directly in code rather than as bitmaps in data. In truth, this extra code nearly doubled the size of Fahrfall. Of course, that took it from slightly more than 1K of code to just under 2K... :-)

As you can see, the game is really coming together. I have to admit that despite the lack of scoring, I can now occupy a few enjoyable moments of my time playing with Fahrfall on the Apple II. Still, it doesn't really look a lot like a game just yet. If you want to see how that turns-out then you'll still have to stay tuned!

Make Some Noise

There is a bit more than a week to go in the RetroChallenge 2015/01 event, with just this weekend and the next remaining.  It is getting to be crunch time! :-)  Fahrfall is far from complete, but it is shaping-up fairly well...

Where Am I?

Fahrfall does screen updates during the vertical blanking interval. This provides for smooth, well timed, and glitch-free animation. Only the Apple IIe and later Apple II models provide hardware support for this sort of timing, but I don't think that is a major limitation. A bigger problem is that while the IIe, IIc, and IIgs all provide support for synchronizing to the vertical blanking interval, they each do so in a slightly different (and incompatible) manner. In order to run on all of these Apple II machines, Fahrfall needs to be able to figure out which kind of machine is running it and to adapt accordingly.

Fortunately, it is not too difficult to identify the host machine. In fact, a pertinent Apple Technical Note ("Apple II Family Identification") is readily available on the Internet. Executing a simple ROM routine quickly identifies whether or not a IIgs is in use. If not a IIgs, then a couple of additional memory accesses to known ROM locations quickly distinguish between the IIc, the IIe, and older machines as well. All that remains is to make use of this information.

A single bit within the IIe indicates whether or not vertical blanking is active, so the IIe code simply polls that bit. The bit value for active vertical blanking is reversed on the IIgs, so a complimentary routine is provided for use on the IIgs. On the IIc the vertical blanking indication is tied to an interrupt source, so the IIc routine instead checks for an active interrupt and clears the interrupt source before returning. An indirect jump through a pointer in memory is used to choose the appropriate vertical blank synchronization routine at runtime. This should be sufficient to enable Fahrfall to support all of the later members of the Apple II family.

The older II and II Plus are also detected during Fahrfall initialization. Lacking any support for vertical blank synchronization, detection of these early Apple II machines currently leads to an early exit from Fahrfall. When Fahrfall is more complete, I may experiment with a more static delay loop for use on these early machines.  It won't be perfect, but it might be better than not running at all? Alternatively, it looks like the mouse interface card might be able to provide the necessary timing (if one is installed). Are there enough II or II Plus machines (with or without mouse cards) to make the effort to support those machines worthwhile? I have no idea...

Read The Fine Manual

Most programming of Apple II hardware is done through some sort of "soft switch" access. These are memory-mapped hardware registers that change and/or reflect the state of various bits of hardware on the Apple II. Most "soft switches" are accessed in such a way that the change of state occurs based on the location accessed rather than whether that access is a read or a write. However, "most" and "all" are different things...

The vertical blanking interval detection routine for the Apple IIc enables generation of a vertical blanking interrupt, but disables interrupts at the CPU. The interrupt is detected by polling a "soft switch" until the vertical blanking interval is indicated. During setup, another set of "soft switch" locations is accessed to enable the generation of that interrupt. But when I first ran Fahrfall on a IIc, the program simply hung.

I speculated that my polling loop was checking for the wrong condition, so I changed it to look for a '0' rather than a '1'. That stopped Fahrfall from hanging, but now the game ran too fast as it always thought an interrupt was pending. Ultimately, I figured out that my attempt to enable vertical blanking interrupt generation with read operations was not working. Changing those to write operations made the interrupt detection work as expected. Sometimes it pays to read the manual carefully!

Hear Me Roar

One of my favorite bits of Fahrfall on the CoCo is the simple sound effect used to simulate footfalls during player movement on the platforms. This effect uses the square wave audio output on the CoCo, following a pattern triggered during the vertical blanking interval. The Apple II audio hardware is similar to the square wave audio hardware on the CoCo, so I implemented an equivalent audio pattern triggered during the vertical blanking period while the player is moving horizontally on a platform. The sound effect on the Apple II sounds virtually identical to the effect on the CoCo version of Fahrfall. Fahrve still looks like a big, blue box, but now you can hear him coming!

I guess that covers the state of things for now. Hopefully I can find some time this weekend to add scoring, or to give Fahrve some shape, or... Well, I guess you'll just have to stay tuned!

Game On

A few more days have passed in the RetroChallenge 2015/01 event, and there is a bit more progress to report!  Step by step, Fahrfall is coming together on my Apple II.  Soon I will have a real game... :-)

Collision Detection

The main point of Fahrfall is to fall down the screen, land on a platform, and ride the platform back up the screen before you repeat the process.  For that to happen, the program needs to know when the player is in contact with a platform.  That problem is known as collision detection.

Collision detection in Fahrfall is fairly simple.  Each platform is represented in the computer's memory by a bitmap, with a '1' representing each section of the platform and a '0' representing each gap.  A variable keeps track of the horizontal position of the player on the screen, and that value is used as an index into a table containing bitmaps that represent the platform sections with which the player might collide in that horizontal position.  When the player's vertical position is immediately above a platform, a simple bitwise AND operation between the two bitmaps is done.  A non-zero result represents a collision (i.e. the player is standing on a platform).

Hidden Platform

As indicated, the collision check is done between the player and the platform on the line beneath the player.  This presents a problem when the player is all the way at the bottom of the screen, since all three platforms will be above it.  Without some accommodation, the platform data array will underflow and problems will be inevitable.

There are many potential solutions.  There could be an explicit check for this situation, with the result being either to skip the collision check or to immediately end the game.  Alternatively, a fourth entry could be added to the platform data array.  The fourth entry could contain an all-zero bitmap (so that no collision would ever occur), or it could contain the data for the next platform.

The latter option is what I chose to do.  This may seem silly, since only three platforms are displayed on the screen.  But adding a fourth (off-screen) platform introduces an interesting gameplay feature.  If the next platform would catch them, a player can be saved at the last minute through sheer luck when falling off the bottom of the screen!  This only happens if the fourth platform is just about to emerge, but it still adds an element of fun for those who reallly enjoy Fahrfall.

Moving On Up

With collision detection all sorted, making the player ride the platforms is a simple matter.  When a collision is detected and the platforms move up, the player is moved up at the same time.  Similarly, if a collision is detected then the player does not move down.  To make this work properly, collision detection must be run whenever there is movement of either the player or the plaforms (i.e. sometimes twice in a frame).  Aside from that, making the player ride the platforms was just a simple matter of programming.

So the basic gameplay mechanics of Fahrfall are complete in this Apple II port of the game.  At this point you can "play" using the joystick, so long as you don't care about keeping score.  Nevertheless, there are still plenty of features and embellishments missing.  So there is still more to come...I hope you will stay tuned!

Halftime for RC2015/01

We are now roughly half way through the Retrochallenge 2015/01 event!  I am still making progress, but I don't have a very cohesive topic for a blog post at the moment.  Since it has been a few days since the last update, I will just touch on a few random bits here and there...

Line By Line

In an earlier post, I mentioned that the video memory in the Apple II has a peculiar layout.  For example, the data for line six is offset in memory from the data for line seven by a different amount than the offset between the data for lines seven and eight.  This makes moving an object on the screen from line to line more complicated than simply adding or subtracting a fixed offset from the previous address.

Previously I wrote a routine that would convert a screen line number to a base address in video memory.  I have since rewritten that routine by replacing a shift-and-add multiplication with some bitwise operations, thereby improving its performance.  Nevertheless, the routine is long enough that I would like to limit how much it is used.

I was able to implement somewhat simpler routines for moving up or down one line at a time.  These routines combine simple offset adjustments with checks and adjustments for crossing 8-line boundaries.  The results are somewhat simpler than the direct calculation routine, with corresponding performance improvements.  A single-line offset is simple enough to be practical and common enough to be useful, especially for Fahrfall.

Point Break

The 6502 only has a handful of registers for use by the programmer, none of which are large enough to hold an actual address.  Addresses for data access can be embedded in the program code, but either that would limit a given function to accessing only predetermined memory locations or it would require the use of self-modifying code that rewrites the addresses whenever different memory locations are used -- ugh!

Fortunately, the 6502 does provide a couple of means for storing an address in memory and then using that address as the object of an indirect memory access.  Unfortunately, those options require storing the address somewhere within the 256-byte "zero page".  Those locations are in high demand, and the Apple II firmware pre-allocates most of that memory for its own use.  Fortunately I was able to find enough space to fill my immediate need for a drawing pointer.

When I only had platforms on the screen, I could get by with a single drawing pointer.  Even though there are three rows of platforms, their relative positions makes it easy to adjust the drawing pointer to point to each platform in turn.  Unfortunately, the player object needs its own drawing pointer value which is independent of the platform drawing pointer.  Of course, the player drawing pointer needs the same sorts of manipulations as the platform drawing pointer needs.

One option would be to use separate "zero page" locations for each pointer and to duplicate the pointer manipulation routines for the player object drawing pointer.  A better alternative is to use a single "zero page" location for the active drawing pointer and to save/restore this value to/from separate memory locations for different uses.  The second option effectively treats the "zero page" drawing pointer as a 16-bit register, providing me with the flexibility I need for what I want to do.

Ode To Joy

Fahrfall is an arcade-style game, so it makes sense to use a joystick to play the game.  The joysticks on the Apple II use an analog circuit based on an RC time delay.  The actual timing is done at the CPU by counting the number of cycles that are spent executing a tight loop while a capacitor is charged.  Coding such a loop seems simple enough, but doing so is unnecessary -- the Apple II firmware already contains such a function at a well-known location.

Reviewing the actual code of the firmware's joystick reading function reveals that there is little opportunity for improving its performance.  Consequently, I used the Apple II firmware to read the Y-axis of the joystick.  This returns an 8-bit number which represents the position of the joystick on that axis.  Fahrfall only needs to know the general direction for movement, not the actual position.  So, I added code to take the number representing the joystick position and to test it for left and right ranges.  I also included a dead zone in the middle to represent "no movement".

Well, that covers a few micro-topics related to my port of Fahrfall to the Apple II.  I also finished reading Assembly Lines: The Complete Book, so I guess I am now a trained Apple II programmer...

Things are coming together, but there is still more to come.  I hope you will stay tuned!

Trivial Triumph

Today I did something clever on the Apple II.  I applied some recently acquired knowledge to address a gap in the random number generation for my Fahrfall port, and I was proud of it.  Unfortunately, I may have solved a problem that didn't exist...

Standing Start

Previously I discussed the use of a software-based linear feedback shift register (LFSR) for generating pseudo-random number sequences.  The LFSR is really just an equation that generates a sequence of numbers, each based upon the value of the previous number in the sequence.  Given a fixed starting point, the LFSR will always generate the exact same number sequence.  Consequently it is important to "seed" the LFSR so that it starts at an unpredictable point in its sequence.  A common technique for seeding an LFSR would be to use a rapidly changing variable (such as a time-based counter) to seed the LFSR.  Since the Apple II lacks any timing source, I looked for other options.

Clever Display

After a while, I recalled learning about a quirk of the Apple II hardware that allows a program to read the byte of video data currently being displayed on the screen by reading from one of the "soft switches".  Others have used this mechanism to synchronize a program for the proper timing of video updates by writing appropriate "sentinel" data to the video buffer.  That method of synchronization relies on precise cycle counting and seems unsuitable for a game or other interactive program.  But maybe the mechanism it uses could be pressed into service here?

It is very difficult for a human to know what portion of the video buffer is being displayed at any given moment, so reading the displayed video data during program setup should yield the data from a more-or-less random position in the video buffer.  Of course, the video buffer will often contain largely uniform values (e.g. spaces on the text screen).  For best results, steps should be taken to minimize the duplication of data values within the video buffer.  Consequently, I wrote an ordered sequence of values to the video buffer.  During program initialization I read from a video "soft switch" to retrieve values to use for seeding the LFSR.  This yielded satisfactorily random sequences across multiple program starts.

Reality Bites

With my LFSR getting a reasonable seed value, I was feeling rather pleased with myself.  After just a couple of weeks of playing with the Apple II, I may have just invented a new technique for generating a random number seed!  Even if it turns out that others have done this before me, I still discovered this all on my own!  Nevertheless, I wondered if I could find any evidence of someone else doing something like this?

For what its worth, I did not find any documentation of anyone using this technique for generating a random number seed on an Apple II.  That doesn't mean that no one has ever done it, and it doesn't even mean that no one ever wrote it down.  It only means that I didn't find any evidence of that in a few minutes with Google -- YMMV!

However, in my search of Apple II random number generation techniques I did find another interesting tidbit.  Apparently the firmware on the Apple II updates a loop counter in the zero page (at locations $4e and $4f) every time the keyboard is checked for input.  While the value of this number might be predictable if a program is automatically started after boot (perhaps when using an emulator?), in the real world this method is just as good and it is a lot easier to use.

So, I guess I'll just seed the LFSR the easy way -- at least I got to feel smart for a little while!  This is the sort of stuff that makes the Retrochallenge lots of fun, so I wanted to post this update for everyone's enjoyment.  There will still be more to come, so I hope everyone will stay tuned!

Any Port In A Storm

Well, I guess by now the jig is up...  Having so far demonstrated a lack of imagination in the Retrochallenge 2015/01 event, I am falling back to something familiar.  I am porting Fahrfall as an exercise in learning to program the Apple II.  At least that lets me concentrate on learning Apple II software architecture and 6502 assembly language rather than toying with game design...?

Random Patterns

Almost any game needs a source of random numbers.  The most obvious use of random numbers in Fahrfall is the generation of randomized platforms, but they are also used in the "game over" audio and for a few behind the scenes functions.  Of course, computers really have no way to pick truly random numbers, so some technique must be used to generate "pseudo random" number sequences that are not easily predictable by humans.

There are several techniques available for generating "pseudo random" numbers.  The one that I tend to use is a software implementation of a linear feedback shift register (LFSR).  In the CoCo version of Fahrfall, I implemented a "Fibonacci" LFSR.  This time I implemented a "Galois" LFSR because it seemed a bit easier for the 6502 to process.  The code is so simple and fast, I may go back and reimplement a "Galois" LFSR for the CoCo version of Fahrfall as well!

Step By Step

I am using the low resolution graphics mode on the Apple II.  This mode provides a broad array of colors while minimizing the amount of data required to paint a screen.  The resolution is lower than the video mode used on the CoCo version of Fahrfall, but I think it is adequate to provide enjoyable gameplay.

The encoding of pixel data in the low resolution mode is a bit easier to wrap one's mind around than the encoding used for the other Apple II video modes, but it is still a bit odd.  Sixteen colors are available and two pixels are encoded in a single byte -- so far, so good.  What is weird is that the two pixels represented by a single byte are stacked vertically rather than horizontally, so the two pixels in a byte represent parts of different lines.  Weirder still (at least to me), the most significant nibble of the byte represents the lower line.

In any case, this pairing of pixel data caused me to implement my earlier "moving platforms" code experiment using 24 line pairs rather than 48 separate lines.  This code structure seemed a bit awkward, since I will likely want to process player inputs and do other things in between platform movements without having to duplicate code for odd and even platform locations.  So, I refactored the code to handle 48 different platform positions and to plot the platforms with properly encoded pixel data.

Refactoring

Continuing along the same path, I did more refactoring of the remaining bits of my code.  That code was developed organically as I initially toyed with the Apple II.  Now that the code is going to be a game, it needs to adopt a structure conducive to that end.  That means moving various bits of inline code into reusable subroutines, minimizing and/or removing duplicate code segments, changing labels here and there, etc.  This also includes beating the overall structure of the code into a traditional game loop.  As it now stands, the code forms a skeleton upon which I can hang the rest of Fahrfall.

Now that I've confirmed that I am working on a port of Fahrfall, it might make sense to move further coverage of this effort to the Fahrfall blog.  I considered doing that, but that might be a bit confusing for folks following the Retrochallenge contest.  I'll just keep the cover here for now.  If the effort is a success, then I'll move further coverage to the Fahrfall blog later.  So if you want to watch the progress of porting Fahrfall to the Apple II, then you just have to stay tuned!

Taking Shape

I'm still plodding along with the Apple II, and getting more comfortable with programming the 6502.  So far, I am having some good fun!  I'm still not committed to any specific programming goal, but an idea is starting to take shape...

Fill In The Blank 

Old-fashioned video monitors (including televisions) literally drew images one line at a time, sweeping across and down the screen in the process.  Image data in a computer generally is stored in RAM, and the contents of that memory is scanned by the video hardware as the video signal is generated and sent to the monitor.  Computer programs that do not account for the timing of those scans while updating image data in memory tend to generate transient video "glitches" when a screen in shown on the monitor while that screen is being updated.  A common technique for avoiding such glitches is to ensure that image data is updated during the vertical blanking interval.  This is a period in the video signal which is literally reserved for the time it takes to move the electron beams in a CRT from one corner of the screen to the other.  During this period, nothing is drawn on the screen.  This is an ideal time for updating image data in memory.

The original Apple II and Apple II+ hardware did not provide any mechanism intended for software to synchronize with the vertical blanking interval, but the later Apple II models were more accommodating.  Unfortunately, dealing with vertical blank synchronization seems to have been a creative outlet for the engineers at Apple back in the day -- the IIe, IIgs, and IIc all do it differently!  I even found a Google Groups discussion about the topic.  For now I am just going to use the method for the machine I am actually using in my coding experiments, the IIe.  Something more robust can come later, if necessary.

Oversize Load

The early coding examples in Assembly Lines: The Complete Book place code into memory starting at address 768, an open area of memory not used either by Applesoft BASIC or by the system monitor.  However, that unused chunk of memory is not unlimited.  As I added code in my own experiments, the size of that code crept slowly up.  At one point, the program would immediately crash when it was run from the monitor -- not cool.  Of course, the tail end of my code was overwriting something important to the proper functioning of the monitor program.  So the lesson is "know where your code lives"... :-)

Serial Killer

As I mentioned in an earlier post, my development environment includes a serial (i.e. RS-232 over Bluetooth) link between the Apple II and my workstation across the room.  This provides me with a number of conveniences, but it has the drawback that I can't touch the Apple II when I'm running code on it.  The only way to interact with a program (including telling it to stop) is over the serial port, which means my code experiments need to know how to talk to the serial port.  So, I figured-out how the 6551 on the Super Serial Card is addressed and I wrote some code to let me poll the serial port for input -- remote access problem solved.

Well, that wraps up this progress report.  I am having fun, and I am expanding my retro computing horizons.  There is still more to come, so I really hope you will stay tuned!