robotfindskitten, part 3. Dan’s MEGA65 Digest for December 2023.

Our robotfindskitten adventure continues! In part 1, we introduced the robotfindskitten experience, and described tools and techniques for building an rfk game in BASIC 65. In part 2, we started building a similar toolkit in assembly language, starting with KERNAL routines, memory access techniques, and screen memory registers. This month, we complete the toolkit, and I present my own attempt at an assembly language version of the game.

But first, a whole bunch of new stuff!

MEGA65 News

R5 main board in testing!

The new R5 main board test units have arrived and Paul has started the “bring-up” process, adapting the FPGA core to the design changes. With some minor corrections to the assembly, this should resemble the main boards that will ship with new MEGA65s going forward, including all pending pre-orders. Many thanks to Paul, Trenz Electronic, and the hardware testing team for the work they are doing.

Unicone, by deathy

deathy has another new game release! In Unicone, you are chasing a unicorn that poops ice cream. Move your ice cream cone left and right to catch falling ice cream scoops dropped by the unicorn. A fun game in the tradition of Kaboom! (or its lesser known ancestor, Avalanche), Unicone features high resolution graphics, sampled sounds, a wide variety of control schemes, and a unique ice cream balancing mechanic for extra challenge in later levels. Download Unicode from Filehost.

Want to see how it works? deathy has generously released the C source code to Unicone using an open source license, and the assets using a Creative Commons license. The code builds with the Calypsi C cross-compiler, a modern retro development suite by hth313 that recently added support for the MEGA65’s 45GS02 CPU. Check it out!

The Ghosts of Blackwood Manor, by Stefan Vogt

Stefan Vogt, the author of the adventure games Hibernated and The Curse of Rabenstein, has a new adventure out for multiple platforms including the MEGA65. The Ghosts of Blackwood Manor is an interactive horror game with three possible outcomes, and each outcome fills out the story.

And of course, Ghosts is getting another gorgeous boxed release from poly.play! Pre-order the boxed release, and get it digitally right now for a donation of your choice.

Gurce’s BASIC 65 Dev Vlogs

Gurce has been doing a series of live stream development vlogs coding a game from scratch in BASIC 65, using the Eleven programming environment. The game, currently titled “Way of the Imploding Foot” (or just “MegaFoot” for short), is a side-view fighting game, featuring low resolution block character graphics, animated fighting characters, and parallax scrolling.

You can start with episode 1, and subscribe to find out about new live streams. Also check out the Github repository for the game, or just try the latest D81 disk image. When browsing the repo, be sure to locate the .ELPC files (such as FOOT.ELPC), which contain the code in Eleven syntax viewable as a text file on a PC.

Gurce is welcoming contributions on this project! If you’d like to try implementing a feature in BASIC using Eleven, let Gurce know on the Discord.

Discord upgrade!

The MEGA65 Discord is the MEGA65 community’s real-time meeting spot, a great place to ask questions, show off your projects, and meet other MEGA65 enthusiasts. Thanks to MEGA65 Discord moderator KiDra, the Discord now has a fresh new structure and some really cool new features! Here are just a few highlights:

• New section layout. Channels and resources are now organized in sections based on how you engage with the project, such as regular use, programming, and platform development. Click or tap a section title to collapse sections you use less often.
• Discord forums. Sections now include Discord forums in addition to text chat channels. Forums are especially useful for asking technical questions: each question stays visible in a list, and answers and discussions stay organized by topic. Once you have the answer you need, you can close the discussion, and it stays in Discord search history for others to find.
• Voice/video rooms. Sometimes it’s just easier to talk, you know? Hop into a voice room to start an audio or video chat. Show off your work, collaborate on a project, or just hang out.
• The Pin-Board. All of the most important community resources in one well-organized section! Announcements, official project status, and links to resources.
• Events. Want to organize a club meeting, schedule an online conference, or throw a party? Let everyone know by posting an event! Everyone will be able to express interest in your event and request an automated reminder when the event draws near.
• Self-service posting roles. To help keep the announcements and events channels clean and on-topic, we ask that anyone who wishes to post to them read a brief description of how they are used, in the #role-setup channel. Acknowledging the description grants permission to post, automatically.
• Starred posts. Did someone post something you think more people should see? Give it a ⭐️ reaction emoji! If enough people star the post, it will be advertised in the #starred-posts channel. This works from any public channel.
• Project channels. These discussion channels for specific MEGA65 projects by the community can be used for collaboration, on-going user support, or just dev logging and rubber ducking by the project developers. Want a channel for your project? Propose one in the #signup channel.

We will continue to evolve and improve the Discord based on the needs of the community. If you have any feedback or questions on the new layout and features, feel free to discuss it in the #mega65 channel, or contact anyone on the admin team. Thanks again to KiDra for setting all of this up!

Bad Apple… in BASIC?!?

As a follow-up to MEGApple, MirageBD’s high fidelity Bad Apple demo for the MEGA65, Nobato has a new version, this time in BASIC65! Bad Basic65 Apple Demo comes on multiple D81 disk images and can swap disks automatically from the SD card. The music is an original SID arrangement, using BASIC65 PLAY statements.

Boot B65APPL1.D81 to start. It takes a few minutes to load and decompress data into upper RAM—this is all in BASIC, remember—but once it begins, it runs smoothly, start to finish.

Don’t miss the Little Bad Basic65 Apple bonus disk, also included in the archive!

45GS02 assembly language mousepads and posters

A couple of weeks ago, I mentioned that I designed a 45GS02 assembly language quick reference, and you can purchase this design as a mousepad or a poster. Many thanks to everyone who has ordered a mousepad or poster so far! Proceeds go to supporting this Digest and my other work on the MEGA65 project.

I especially like how the mousepad turned out. It’s fun to look at, I can keep it on my desk as a mousepad, and it’s actually useful as a quick reference for MEGA65 assembly language programming. I just used it a couple of days ago to remind myself how the stack-related instructions work.

I’m using Zazzle to make and distribute these. They ship worldwide, and the shipping rates seem reasonable, only about 10 euros to ship the mousepad to Germany. I’ve had one report that there were technical issues trying to pay with PayPal. They also support credit cards. If you have issues, let me know, and I can try to figure it out.

The mousepad is a perfect companion for our robotfindskitten project. Speaking of which…

Finishing robotfindskitten in assembly language

To complete our robotfindskitten program in assembly language, we need to accept keyboard input, generate random numbers, de-duplicate choices, pause to animate the (very simple) ending sequence, and select from the list of item descriptions.

Accepting keyboard input from the KERNAL

A common way for a program to accept keyboard input is another KERNAL routine, getin at $FFE4. This loads a PETSCII code into the Accumulator if a key has been pressed, or 0 if not. This isn’t necessarily the best method for using the keyboard as a game controller, because it includes typing features like key repeat. But it’s easy to use, and for rfk, the built-in key repeat is reasonable behavior.

getin = $ffe4
; ...

-   jsr getin
    beq -
    cmp #17
    beq cursor_down
    ; ...

cursor_down:
    ; ...

In older versions of the ROM, the getin routine uses CIA registers to scan the keyboard. With the latest beta test version of the core and ROM that I mentioned last month, getin uses a new typing event queue implemented in hardware for greater accuracy. Your program will get the same result from either version: the pre-conditions and post-conditions of getin have not changed.

A program that doesn’t use the KERNAL can access the new hardware registers directly, or can implement its own keyboard scanner based on the CIA chips. See a Commodore 64 reference for information on how to do that.

getin also supports features like the function key macros and input redirection, which don’t apply to a game but could come in handy for other types of programs. getin and chrout are both part of the KERNAL’s input-output system, of which the screen and keyboard are only two possible devices.

Chaos

We need a way to select randomized locations and appearances for the items. In BASIC, we used the RND() function for this purpose. What can we do from assembly language?

The MEGA65 has a dedicated hardware register that produces random values. To use it, a program must loop to wait for a “not ready” flag to clear, then read the generated random number from a register. The act of reading the number restarts the process, setting the “not ready” flag while it works on a new number. Internally, the number generator is using a fluctuating oscillator to generate values, and it needs a brief amount of time between reads to produce good results.

random = $d7ef
random_ready = $d7fe  ; bit 7
; ...

-   bit random_ready
    bmi -
    lda random
    ; A is a random number between 0 and 255

Important note: If you test your software in the Xemu emulator, be sure to use the “next” branch release. As of this writing, the random number register implementation is not in the latest stable release, and the ready-wait loop will never exit.

The distribution of values returned by this register is even across all possible byte values 0 to 255. Because this distribution is over a range sized by a power of two, you can reduce the range to a smaller power of two by ignoring some of the bits. For example, to get a random value from an even distribution of 0 to 63, use the and instruction to set the upper two bits to 0:

    and #%00111111
    ; A is a random number between 0 and 63

If the range size is not a power of two, it is feasible to simply “re-roll” for a number within the desired range. This causes all picks outside the range to be distributed evenly across the desired range, so it does not skew the results. Of course, this can take an arbitrary number of tries to roll a value in range, so you can speed this up by combining both techniques: get a number 0 to 255, zero out the unused bits, then test whether the result is in range and re-roll if not.

-   bit random_ready
    bmi -
    lda random      ; 0 to 255
    and #%01111111  ; 0 to 127
    cmp #80
    bcs -
    ; A is now a random number between 0 and 79

To get a random number larger than 255, fetch two random numbers and treat them as a single 16-bit number. You can use similar techniques to narrow the range.

Another option is to implement a pseudorandom number generator in your own code. Such algorithms range in power and complexity and can be difficult to get right, but applications like simple games can often get by with something as simple as a linear-feedback shift register (LFSR). Pseudorandom number algorithms generate a sequence of numbers based a starting number, known as the seed. It can be an advantage during testing to use a known seed to get a predictable result. For the final program, you can use another source of randomness, such as the hardware random number register, to determine the seed.

If you’d like to try this, read the Wikipedia page on LFSRs carefully. See also this video from Retro Game Mechanics Explained on how the game Super Mario Bros. 3 nerfs its card shuffling algorithm by misusing an LFSR, apparently accidentally.

Avoiding duplicates

When we discussed random selection in BASIC last month, we put in some extra effort to store all previous choices in an array, and re-rolled the dice when we accidentally chose an already-selected character, location, or description. This ensured that no two items would be placed on the same location, which would not only appear as fewer items on the screen but might cause the kitten to be hidden by another item. Depending on how it was implemented, the robot might touch the location and only see the Non-Kitten Item even if the kitten was also at the same location. Ensuring diverse characters and descriptions also maintains variety in the gameplay, to avoid the disappointment of seeing the same description more than once in a game.

The assembly language version of this isn’t different, it’s just a bit more cumbersome than in BASIC. I allocated some array-like memory within the program’s memory space for this purpose, like so:

num_items = 20  ; max 127
item_description: !fill num_items*2
item_screen_code: !fill num_items
item_x: !fill num_items
item_y: !fill num_items

(Alternatively I could have put this on the base page, or elsewhere between $1700 and $19FF, which is available for program use.)

I wrote three assembly language routines that detect whether the value at position X is equal to the value at any position 0 through X-1, the idea being that as I fill the array from position 0 upward, I can check each item against the previous items. I needed three routines because each value is stored in a different way: characters are stored as one-byte screen codes, descriptions are stored as two-byte addresses (which we’ll see more of later in this article), and coordinates are stored as coordinate pairs in two separate lists.

Here’s the simplest of the three routines I came up with that checks for duplicate screen codes:

addrl = $00
addrh = $01
vall = $02

is_unique_byte:
    ; Y,Z: starting address of byte set
    ; X: index of last item
    ; Returns: Carry Set if item at X appears elsewhere in the set
    cpx #0
    beq @is_unique
    sty addrl
    stz addrh
    txa
    tay
    lda (addrl),y
    sta vall
-   dey
    lda (addrl),y
    cmp vall
    beq @is_not_unique
    cpy #0
    bne -
@is_unique
    clc
    bra @end
@is_not_unique
    sec
@end
    rts

A few notes:

• The routine accepts the starting address of item_screen_code in the Y and Z registers. I could have hard-coded the address into the routine, but this way I could potentially re-use it with a different array, or in another program.
• It uses the Carry flag as the return value, where Carry is set if a duplicate is found. The routine is not responsible for choosing new random values or updating any memory. It’s important to separate responsibilities between routines to make code easier to write, test, and re-use.
• It uses base page variables and indirect indexing (via the Y register) to access the array and remember the value under test. 6502-style CPUs have very few registers, so programs must rely on the base page (or the stack) to wrangle variables.
• With the Acme assembler, a symbol whose name starts with an @ character is a “cheap local:” it is only valid between two global symbols (such as is_unique_byte). This way I can re-use these symbol names in my other duplicate test routines.

These routines were challenging to get right! The algorithm isn’t complicated, but one errant instruction can cause all kinds of havoc. I found it useful to insert a brk instruction early in my program so that it would open the MEGA65 Monitor. From here, I would test these routines by writing values into the arrays, setting the registers, calling the routines, and inspecting the Carry flag.

To do this, I needed to determine the raw addresses of the routines and the arrays assigned by the assembler. You can tell Acme to generate a report of all of the addresses it used throughout the program, using the -r command line argument:

acme -r rfk_report.txt rfk.asm

The monitor commands r and m inspect registers and memory, respectively. To update values, you can move the cursor up to the lines that these commands print, change a value, then press Return. (Remember that addresses and values are in hexadecimal.) To call a subroutine, use the j command. See my tutorial on the MEGA65 Monitor, as well as appendix M of the manual, for more information.

Avoiding other bad choices

There are two more cases of bad item placement worth considering, at least briefly.

The robot also appears on the playfield along with the items. We need to make sure that an item doesn’t land on the robot’s starting position. My solution is crude but effective: I put the robot in the upper left corner of the playfield, then limit item placement to be within a one-tile border. This way, there is never an item where the robot starts, and the robot can move unimpeded around the entire edge of the playfield.

With items placed entirely at random within the border, it is possible, however unlikely, that four items might surround a fifth item. And if that fifth item is the kitten, then the robot will never be able to find it! Tragedy! I admit, I did not bother to solve for this edge case in my implementations, but it’s worth thinking about how this might be solved. One way is to test a chosen item location for surrounding items, and re-roll if a bad case is noticed. A complete solution would have to handle extremely unlikely cases like 19 items forming a wall around the kitten, and would probably involve path finding algorithms or other magicks.

A simpler solution is to only place items on odd numbered rows and columns. For example, within an 80-column width, pick a number from 0 to 38, double it, then add one. This produces a column coordinate from 1 to 77 and guarantees at least a one-space gap between items. Do the same for the row coordinate, and the robot is assured a clear path to every item.

Calm

One of the responsibilities of the CIA chips is to keep track of time. For coarse-grained timing, the CIA has a built-in “time of day” clock that counts up by tenths of a second. If your main loop executes faster than ten times per second, you can count upwards by tenths of a second simply by testing for when register $DC08 changes. The bottom four bits are a “binary-coded decimal” value between 0 and 9, representing the tenths-of-seconds value of the CIA’s clock. This can be a bit crude because you might be testing the register just before it ticks, so the actual delay might be off by as much as one tenth of a second.

todtenths = $dc08

wait_briefly:
    lda todtenths
    sta last_todtenths
-   lda todtenths
    cmp last_todtenths
    beq -
    sta last_todtenths
-   lda todtenths       ; Wait two ticks to pause between 1/10th
                        ; and 2/10ths of a second
    cmp last_todtenths
    beq -
    rts

last_todtenths: !byte $00

You can achieve a more precise wait loop delay using a feature of the VIC video chip. The VIC uses a finely-tuned high speed mechanism to describe the entire screen to a connected display many times per second, one line at a time from top to bottom, known as the raster scan. The current raster line number is stored in the RC register, as nine bits: bits 0 through 7 are at address $D012, and bit 8 of the number is stored as bit 7 at address $D011. In the same way that you can wait for the CIA TOD tenths register to change, you can wait for these register values to change for much shorter durations.

wait_very_briefly:
    ; Wait for bit 8 of the raster count to flip negative then positive,
    ; for a delay between 1 and 2 frames.
-   bit $d011
    bpl -
-   bit $d011
    bmi -
    rts

The tricky bit (because there’s always a tricky bit) is that the number of raster lines and the rate at which the screen is drawn differs depending on the video mode of the MEGA65. Back in the day, PAL and NTSC were competing standards for analog video signals, used for both transmission and rendering on cathode ray tube (CRT) displays. Commodore sold computers with different VIC chips in different regions to be compatible with the technical standard used in the region for televisions. As a result, Commodore games that used raster-based timing ran differently depending on which VIC chip was in the machine. A game might animate slower or faster than was intended, or it might play music at a different speed. In other cases, a game would only function correctly with one kind of VIC chip, and just trip over itself when running with mismatched VIC timing.

The MEGA65’s VIC-IV chip can generate PAL-like or NTSC-like video signals, as separate modes. Some MEGA65 owners are using displays (vintage or modern) that only support one of the modes. I asked everyone about their display modes in the 2023 survey, and 81% of the MEGA65 owners that responded have their video mode set to PAL by default, vs. 18% set to NTSC. Modern digital displays can often support both modes, but only 56% of owners were confident that their display could do this. A program can force the MEGA65 into one mode or the other using registers, but it’s best to leave it in the mode selected by the user in the configuration or Freezer menu.

The upshot is this:

• In PAL mode, the RC register counts up to 312 raster lines, at a rate of 50 times per second (50 Hz).
• In NTSC mode, the RC register counts up to 263 raster lines, at a rate of 60 times per second (60 Hz).

The actual image size is twice this many lines, fully refreshed at half these rates. The full image is drawn interlaced, with odd lines and even lines alternating with each refresh. 50 Hz or 60 Hz is the refresh rate; 25 Hz or 30 Hz is the frame rate.

It is possible for a program to achieve precision timing independently of video mode using the CIA chips and a system feature known as interrupt handling. Interrupts can also be used for raster-based timing. High speed games are most likely to use raster-based interrupts for timing because it makes it easier to control screen updates, and they will either live with the consequences of the different video modes, or use sophisticated techniques to work around them. Interrupts are a big topic, so we’ll leave that for another Digest.

robotfindskitten doesn’t need precise timing for anything, so raster timing is overkill in this case. I use CIA TOD tenths to add a simple delay to my found-kitten experience, and otherwise rely exclusively on keyboard events (and delays introduced by the key repeat handler) to drive the gameplay logic.

Data

We’re almost done! We have all the tools we need to display messages, choose and place items, animate the robot, move the robot based on keyboard input, and check for item interactions and the win condition. We just need a way to store, select, and display the 400+ possible item descriptions.

We’ve already seen how to add the bytes of a text message to the program in Acme, and to assign a label to its address:

message: !pet "\"I pity the fool who mistakes me for kitten!\", sez Mr. T.",0

What we need is a way to select from a table of messages by an index. For my robotfindskitten implementation, I used a Python script that reads the NKI descriptions from a text file, and generates !pet directives for all of them, with labels such as i1, i2, and so on. The script also generates an address look-up table with all of the generated labels in it. This puts the starting address of each description into memory at regular two-byte intervals. The program can find the description for a given index by multiplying the index by two (the asl instruction will do the trick), adding it to the address of the lookup table (nki_table), then reading the description start address from that location. Each description ends with a 0 byte, so the message printing routine knows where to stop.

nki_desc_count_mask = $01ff
nki_desc_count = 401

nki_table:
!16 i0,i1,i2,i3,i4,i5,i6,i7
!16 i8,i9,i10,i11,i12,i13,i14,i15
; ...

i0: !pet "\"I pity the fool who mistakes me for kitten!\", sez Mr. T.",0
i1: !pet "That's just an old tin can.",0
i2: !pet "It's an altar to the horse god.",0
; ...

Here’s the full procedure for assigning a unique description to a Non-Kitten Item, using the techniques we’ve discussed:

1. For each item, use the random number register to generate 16 bits (two bytes).
2. Apply a bitmask to cut down this 16-bit value to a 9-bit value, the smallest mask that would account for the maximum number of descriptions (512 > 401).
3. Compare the result to the actual maximum number of descriptions, and re-roll until the selected number is within range. This is the description index.
4. Multiply the index by two to get the offset into the lookup table. Add this to the lookup table’s starting address.
5. Read the description starting address from the lookup table at that location.
6. Store the description address in the item_description array, then test whether it is a duplicate. If so, start again from step 1.

Using tools and scripts to generate data embedded in a machine code program like this is an essential skill, especially for games. Some assemblers have powerful directives that make embedding and manipulating data easy, such as Acme’s !binary directive that pulls in binary data from a file. Kick Assembler’s inline scripting capabilities are especially impressive. I find it useful to know a modern scripting language like Python so I can write my own data conversion tools that generate either assembly code or binary data that can be embedded in my programs.

If you don’t want to write your own scripts to generate the NKI description table, you can borrow the source code for my version, linked below.

The final robotfindskitten program

Here are my final versions of robotfindskitten for the MEGA65, in both BASIC and assembly language:

• rfk-bas.prg : robotfindskitten in BASIC 65; BASIC source code in petcat format
• rfk-asm.prg : robotfindsktiten in MEGA65 assembly language; assembly language source code for the Acme assembler

I don’t claim that either of these are the best possible versions of this program. If you find ways that either of these can be improved, or if you have used different designs or techniques in your program, please let me know!

Whew! That’s a whirlwind of programming topics for three Digest issues. Hopefully this is enough for you to get started writing a robotfindskitten of your own, or extending these ideas to making other kinds of games. For example, you could add a system of walls or a maze generator to make locating items more challenging. Or, you could add other non-player robots that move when the player does, attempting to interfere with the search. Maybe when a non-player robot encounters an item, the item gets relocated on the playfield! It’d be a much less zen experience, but more like a game.

Huge thanks to everyone who has jumped in to support the Digest on Ko-fi so far! We’re off to a good start to funding the Digest through 2024. If you would like to become a supporter, visit: https://ko-fi.com/dddaaannn

See you next year!

— Dan