Monday, January 26, 2015

Over The Wall

We are now in the final lap of the Retrochallenge 2015/01 event! Time is short, and Fahrfall still lacks some key features (like keeping score)... Worse, I got a bit distracted while chasing a performance issue!!

Candy Canes Aloft

In Fahrfall, as the game progresses the color of new platforms changes periodically. I enjoy this feature, as it is both an indicator of how far the game has progressed (almost like a score...), and it rewards the player with something new in return for playing a bit longer. The graphics in the Apple II version won't allow for the "checker board" patterns available on the CoCo, but it will allow for both solid colors and a striped pattern that looks a bit like a "candy cane".

The existing code for drawing platforms only worked with single-colored platforms. I made the necessary modifications to allow for multi-colored platforms, and added some scaffolding to feed random color patterns to Fahrfall. This resulted in multi-colored platforms, but it also resulted in Fahrve's head disappearing before he reached the top of the screen!


Crossing The Line

For a while, I struggled to find the cause of this issue. I carefully checked the code changes, and I even went so far as to rewrite and test the changes in a step-by-step manner. I was almost at a loss as to the cause of this problem, until I noticed that Fahrve's head seemed to make it slightly higher up on the far right of the screen than on the far left. That observation led me to believe that I was overrunning the end of the vertical blank interval before finishing with drawing Fahrve.

With that suspicion in hand, I applied a trick for checking the timing of my vertical blank drawing work. When I start the vertical blanking period, I switch the video mode to showing text instead of low-resolution graphics. (These modes share the same video buffer on the Apple II, and the background data for the graphics screen displays as visible characters in text mode as well.) I switch the video mode back to graphics after Fahrve is drawn, which would be indetectable if done before the end of the vertical blanking interval. But as suspected, it was clear that my drawing code was not completing in time.

Redemption

Up until now, the code in the Apple II port of Fahrfall has largely grown organically. Heeding the axiom that premature optimization is the root of all evil, I have largely focused on getting things working rather than making them run as fast as possible. Unfortunately, at some point things that run too slowly simply aren't working, whether they are correct or not. Drawing during the vertical blanking interval is, in fact, a "real time" programming task! :-)

In my game loop, I was erasing the old platforms and the old Fahrve, calculating movement and detecting collisions, then drawing the new platforms and the new Fahrve. As an optimization, I delayed the movement calculations and collision detection until after drawing the new objects. This bought a little time, but not enough to meet the required deadline.

Something else I was doing sloppily was erasing the platforms. For this I was actually using the same routine I use to draw the platforms but with the data changed to use the background color. The new multi-color platform drawing code takes longer to do its job, and using that routine for erasing the platforms made that take longer as well. I replaced the platform erasing code with a simpler loop, and this was enough to meet the drawing deadline.


So, there you have it -- multi-colored platforms are possible on the Apple II port of Fahrfall. There isn't much time left during the vertical blanking interval for any other drawing tasks, but right now what is needed are less time-sensitive measures -- like scoring! I don't think I'll be able to reach a totally finished game by the end of the month, but I hope to get a bit closer than I am now. If you are curious to see where I end-up, then you will just have to stay tuned!

Sunday, January 25, 2015

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!

Friday, January 23, 2015

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!

Tuesday, January 20, 2015

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!

Sunday, January 18, 2015

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!

Tuesday, January 13, 2015

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!

Sunday, January 11, 2015

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!