Odds and Ends

Two things of note, neither of which is portentous enough to make into its own post:

• This has been making the rounds on the Internet for quite awhile now, but in case you haven’t seen it yet, GameHut’s Coding Secrets playlist is full of explanations of demo-like effects that were used on the Sega Genesis/Sega Mega Drive. If you’ve been enjoying reading about the techniques I’ve been finding here, that playlist is extremely relevant to your interests. (As for why now, it appears that one of the developers for Sonic 3D Blast is going in and making a Director’s Cut version of it as a ROM patch, and has been sharing relevant bits as he goes.)
• WordPress, or at least the theme I’m using on it, appears to have a glitch where escaped HTML entities get unescaped when you edit the post they’re in. This has resulted in a number of older posts that needed minor corrections or edits getting their code snippets corrupted as comparisons were taken as wacky HTML tags and edited out. I’m in the process of reviewing my old posts and making sure any damage has been fixed, but as a rule, code in the Github repository is the final source of truth.

Advertisements

Perfect Play Across Genres

(This is another “from the archives” post, republished from an earlier, smaller distribution. I’d built this out of a series of discussions I’d had on IFmud and similar places with people who mostly played in these genres.

I haven’t updated the text of it much, and of course the sample size is restricted to the folks I talked to. The authoritative tone of much of this article should perhaps be taken with a grain of salt. —McM)

In the excellent and insanely detailed article Shmups 101: A Beginner’s Guide to 2D Shooters, we find the following uncontroversial claim:

Theoretical Perfection: Perhaps the single most important quality for any respectable shmup to possess: it should be technically possible for a player to make a “perfect” run through the game, without getting hit even once. Put another way, there should never be spots where eating damage is 100 percent unavoidable—no matter the situation, your raw skills should always be sufficient to get you through if you’re good enough. Of course, only a select few gamers actually are that good, but this ideal MUST be legitimately attainable: failing to tie up this crucial loose end during development is guaranteed to hamstring any shooter, no matter its strengths in other areas.

It seems like this has a lot of resonance in other genres, too, and takes different forms:

Perfect Play Should Be Possible

• Platformers: Take this condition unmodified. A sufficiently good player should theoretically be able to finish without taking damage. (Health bars are native enough to platformers that this may be better phrased as “without dying”—nonlethal avoidable damage would be more likely to be acceptable in a platformer if the concept exists.)
• Fighting Games: Deterministic damage model. Randomized mechanics are anathema to serious fighting-game players, who hope to see their competitions are purely skill-based, not due in any way to die rolls. This is the predominant reason the Smash Brothers games weren’t taken seriously at fighting game tournments for many years.
• Interactive Fiction/Adventure Games: Much like the Fighting Game version, no random elements capable of deciding the game. Random elements may be acceptable, but there must exist some strategy that, properly applied, will win the game 100% of the time. This requirement is automatically met by puzzlebox games, and in a very real sense, in any game that has nothing isomorphic to randomized combat. However, even with randomized combat, it’s still possible to meet this requirement.

I would now want to add some variants to this, because when these are violated some group of even hardcore players gets turned off.

A Priori Perfect Play: “Perfect Information”

This is a known consideration, but does not hold nearly as strongly. The idea here is that the game provides perfect information to the player, so that perception, reflex, and execution are the only things tested. Violating this requirement makes the game—at least on a first playthrough—more of a mind game. These usually end up being specific subgenres.

• Platformers: If the player is not in danger, they can see a way to safely proceed. No invisible deathtraps, no leaps of faith. Invisible hazards may be acceptable if it is possible to guarantee their nonlethality vais some strategy and there is some cue that the strategy should be applied. (Violating this is an entire subgenre: “masocore”, of which Kaizo Mario World and I Wanna Be The Guy are the most famous, and the Karoshi games were the best.)
• Shmups: Memorization should be effectively unnecessary. This is arguably too strong—familiarity will help in any game with scripted components, which is all of the shmups of note. However, this is pretty close to the platformer requirement. If a path branches, both branches should be ultimately viable, or it should be possible to switch branches after it becomes clear that one is not viable after all. (Violating this is the “memorizer” subgenre, of which R-Type is the best known example.)
• Fighting Games: This would require that every move have a unique prefix, or at least that all moves with a unique prefix animation should all have identical counters. There isn’t a name for fighters that do this—I’m going to call them “reflex fighters” because they rely entirely on the reflexes and perception of the players. Unlike the other examples here, violating this requirement makes you mainstream&mash;modern fighters deliberately have moves with different counters have the same prefix as a way to simulate feinting, or, more directly, to add a mechanism by which two competitors can psych one another out. While fighting game enthusiasts loudly proclaim their fealty to “pure skill tests”, reflex fighters are considered a bridge too far—they move parts of the game they like out of the design space.
• Interactive Fiction/Adventure Games: Winning the game should not require exploiting knowledge from “past lives”. (Violating this is an entire subgenre: “Accretive PC” games, of which Varicella may be the most famous example.)

Basic Toolkit Perfect Play

Perfect play should be possible using only the most “basic” of the game’s mechanics. This is not always considered a feature, because it by definition is making some skill tests totally optional, and sometimes that means removing them entirely.

• Fighting Games: No special move should be only counterable by another special move; no matter what strategy your opponent takes, it ought to be theoretically possible for a sufficiently skilled player to win using only the basic toolset of basic attacks, defenses, dodges, and throws. (This is more or less true for all fighting games, under equal circumstances. Special abilities may be better at it, and if a player has been trapped by his opponent specials may be his only way to break it, but if you’ve gotten into your opponent’s head, there’s no need for anything fancy to win.)
• Platformers: This is generally automatic. Most platformers—and in particular most challenge platformers—only have basic mechanics, and they are always available. When this is not the case, powerup-free runs should always be possible.
• Shmups: In addition to “dying should be optional”—the basic perfect play criterion—bombing and powerups should also be optional. Guaranteeing this is usually how you guarantee the perfect play condition.
• RPGs: No system mastery traps; any “sensible” build should be capable of beating the game. This is the genre where it’s most likely to not be considered a feature, because by definition it means that optimization doesn’t pay off as much as it could. Even so, games that encourage specialization (like Alpha Protocol or Deus Ex) carry with them an implicit promise that any specialization will eventually see you through, ideally with that specialization. Breaking this will still be considered OK as long as the core Perfect Play rule still applies.
• Interactive Fiction/Adventure Game: The game should be beatable using only standard verbs. More or less automatically achieved by mouse-driven graphical adventures unless they do something amazingly gimmicky—not usually as valued in IF, which prefers the weaker requirement “properly clue all required nonstandard verbs”. What qualifies as a “standard verb” is a community consensus, which doesn’t really help novices. Still, if a standard verb can do something, the standard verb should at least be a synonym.

Perfect Play From Any Point

Regardless of the game’s situation, a sufficiently good player can provide a “perfect tail” from any point.

• Shmups: Intrinsically impossible, since being one frame away from death will usually be too late. Weaker versions of this may apply.
• Platformers: Intrinsically impossible for the same reason as for shmups; restricting to “possible starting from any point where the PC is not in immediate danger” is usually automatic if perfect play is possible at all.
• Interactive Fiction/Adventure Games: This is traditionally measured on the Zarfian Cruelty Scale; any game with a rating of “Polite” or lower meets this criterion if it also meets the perfect play criterion. Community consensus is that this is very important, but not strictly mandatory.
• Fighting Games: This is almost automatic. The basic concept here is that comebacks should always be possible, and since damage is deterministic and there is always a psychological component of some kind, if a player is not in the middle of being defeated by a trap or combo, a comeback will be possible.

Structured C64 BASIC: A Complete Example

Now that we’ve worked through the basic principles, let’s go through a worked example. I don’t work in BASIC much, but the largest program I’ve written that’s pure BASIC is a directory-editing program for disk images, weighing in at about 120 lines of code. It should serve to demonstrate the core principles.

The Problem

When I was organizing some of my projects and other programs into disk images, I kept running into a host of minor irritations endemic to disk work on the C64. My initial list of goals was:

• The ability to reorder directory entries, including entries that didn’t refer to any files. You see, instead of storing directory entries as a linked list, CBM DOS stored as an array and when a file is created the first “empty” entry is used. That means that if you’ve deleted files, your newly created files appear seemingly randomly in the middle of the listing, instead of at the end. That’s super-annoying so I wanted to be able to move those gaps down to the end of the list.
• Undelete files.
• Hide files so that they existed on the disk but didn’t show up in directory listings.
• Create unloadable delimiter files that did exist in the directory listing, as dividers or headings.

Deletion and renaming were easily managed with ordinary disk commands, so I wasn’t as interested in those. I didn’t need a DOS shell or directory commander—I needed a program that would let me do things to the directory structure that the DOS didn’t provide as commands.

Now, as it turns out, that whole list can be boiled down to three operations:

• Exchange two entries in the directory listing.
• Alter the file type of a file in the directory listing.
• Optionally scan the directory structure and adjust the block allocation map to match it.

This gives us all the operations I want to perform. Any permutation can be built out of an exchange primitive. Deletion and undeletion involve changing the file type to or from “not a file” and then performing the scan for the block structure. Hiding files is accomplished by changing the file type to “not a file” and then not performing the scan, leaving its blocks protected and inaccessible. And delimiter files can be created from any other file by setting their file type to the special delimiter type.

The Initial Drafts

The basic implementation strategy falls out of the considerations above. To do reordering and file type manipulation, I would load all the disk blocks that hold the directory into memory, edit them in place, and then write them all back out at the end. The DOS provides a special “validate” command that does the directory structure scan and block allocation reconciliation. I would also add a “move slot A to slot B” command that performed repeated exchanges, to simplify moving gaps in the directory to the end of the list.

My first draft stored the directory blocks in a two-dimensional array of integers. One array dimension was the disk blocks, and the other was the bytes within them. This worked, and it was relatively simple to implement, working much like our sector-dumper program from last time did. However, it was impossibly slow; exchanging directory entries involved multiple loops that would copy values around, each executing dozens of times. If I wanted to get decent performance out, I’d need to write it in machine code, or create a completely external tool to handle it. Neither of these options appealed to me much.

I then set about trying to implement the core operations more efficiently, which in turn meant changing the data structures. The alterations were pretty drastic.

First, instead of reading and writing every single sector in track 18 (where the directories and allocation maps were stored), I would only read entries in the directory listing itself. These are arranged as a singly linked list. I created an array SN% that stored the order of tracks to write back and a variable NS for the actual number of sectors we read. I then created a parallel array D% to hold “dirty bits”—these all started as zeroes and got a 1 written to them if I ever altered anything in that relevant sector. At the end of the program, I would only need to write out those sectors that I actually changed. In the extreme this could result in me doing seventeen times less work.

That leaves the contents of the directory entries themselves. These were 30-byte data structures that my exchange-directory-entries routine would be copying back and forth as blocks. Instead of copying blocks of array entries back and forth, I kept each directory entry as a string and simply edited them or swapped references around as needed. These entries were stored in an array named DE$.

Finally, to keep myself honest, I added a couple of variables to check to see if I’d ever deleted or undeleted any files to remind me whether or not I should validate the disk.

All of these changes were a fairly significant rewrite. I did the implementation in C64List (which was also the initial import into Github, and while I made some basic efforts to make the code look nice when LISTed, I was pretty lackadaisical about it. Code flow jumped all over the place, modules were huge and all had differently-sized ranges of lines assigned to them. You couldn’t ever really type LIST with a line range and have any idea of what you would get.

So as written, in the modern era, with modern cross-development tools, this draft was basically fine. It would not have been fine in the 1980s. It would have been extremely difficult to understand or modify without printing out the entire source code and studying it as hardcopy.

So, before I do a walkthrough of the program itself, let’s fix that.

Structuring Constraints

For the purposes of this project, I set the strictest set constraints that I’d commonly seen used in programs published with the intent of being typed in by the end user:

• The code will be organized into blocks, each of which is assigned one hundred line numbers. Block 0 is lines 0-99, block 1 is lines 100-199, and so on.
• Line 0 of each block (the line that is an even multiple of 100) will be a comment explaining what the block does.
• GOTO statements will only ever target locations within the same block.
• GOSUB statements will always target the beginning of a block and nowhere else.
• Blocks will be self-contained: any block you enter with GOSUB will be exited with RETURN. (The main program is a special case, and we’ll cover that below.)
• A reader should be able to type the code verbatim into a C64 without using input abbreviations or tricks. (The C64 line editor had a limit of 80 characters, but BASIC lines could be up to 255 characters long, and this limit wasn’t enforced until after all the keywords had been compressed to a single byte. Clever users could use special keyboard abbreviations to make lines that were over 80 bytes long when LISTed, or use program generators to produce lines that were much longer. This constraint demands that we structure the code so that this is never necessary.)
• A block will fit on the screen when LISTed. There needs to be room for both the intial comment and the reiterated BASIC prompt after the LIST completes.

I then added some additional structure that made sense for this program.

• Blocks would be further grouped into megablocks of ten blocks each. These would comprise related blocks that cooperated to perform some task.
• Megablock 0 would hold the main program and general utilities. Any GOSUB statement that called into a routine would either be calling a block in megablock 0, a block within their own megablock, or the first block in some other megablock (that is, an even multiple of 1000).
• Block 0 would be the entire main program. The only things it would do would be initialize globals and call into the other megablocks, and the last line in the block would be END. Blocks 1 through 9 would be reserved for general-purpose routines. (This was uncommon. Generally, 9 blocks wouldn’t be enough for your general purpose routines, and so a set of megablocks near the end of the program would be used for them. Likewise the main program would be kept near the end instead of the beginning. Extremely low-numbered blocks would hold routines that needed to run very quickly, taking advantage of the way backwards branches are faster at lower line numbers. Our directory editor is I/O bound basically all the time and doesn’t care about this.)

Of all of these restrictions, only the requirement that each block fit on a C64 screen when LISTed made my task harder. The others provided a structure that made the outlining and implementation simpler.

Structure is your friend. That’s not unique to BASIC, either.

Let’s take a walk through the final program.

Hacking the Virtues: Becoming the Avatar in Five Easy Steps

(This is another “From the Archives” post; this is a lightly edited version of an article that was originally only posted to a private forum. I’ve cleaned it up a bit and presented it for general audiences. —MCM)

A while back I went on an Ultima IV kick, since I’d never really gotten around to beating it as a kid and it was one of the great Open-Source Ports alongside The Ur-Quan Masters. If you’re unfamiliar with the game, Ultima IV is unusual in that there’s no particular Final Boss threatening the land and in dire need of a sound thrashing by a team of stalwart heroes; the goal of the game is instead to become a paragon of Virtue and then collect and wield various mystical items to cement your status as the Avatar of the Virtues.

As you may have guessed, this also means that you get to run rampant if you decide that Virtue is for little people, and, indeed, the accidental moral of the story is that the correct way to become a paragon of Virtue is to lead a highly profitable life of crime and then use the proceeds to finance various good works.

I hadn’t realized that as a kid, and so my playthroughs tended to end with me getting lost, trapped, or otherwise incapable of meaningfully continuing because my foes were far more powerful than I was and I couldn’t gear up enough to take them down. I had not learned from the example of the Saga of Steve the Avatar. This is the tale of Steve, who becomes the Avatar and then has various further adventures (the saga continues through Worlds of Ultima: Martian Dreams, Ultima VII Part 1: The Black Gate, and Ultima VII Part 2: Serpent Isle) despite being a complete and utter sociopath. And yet, despite being an utter sociopath, Steve is also a paragon of Virtue. Being the Avatar is awesome.

(Be aware that these Let’s Plays are not remotely safe for work with respect to language or content. Only some of that is Nakar’s additions to the works—all of these games predate the rise of the ESRB and game ratings generally and, well. The early 1990s were a different time.)

After having this epiphany, I resolved to try to set right what had once gone wrong, by going wrong where before I had gone right. And it worked pretty well, except that I noticed that my Virtues weren’t quite behaving the way I’d expected them to, given what I’d seen in the Saga of Steve. So I whipped up a little program to study my save file and give me precise Virtue information as I acted. Once I had proof stuff was wrong, I went sourcediving. This is what I found.

This is also, of course, packed with spoilers for Ultima IV, which remains an excellent game (and one that is freely available, as noted above; GOG.com also provides the original in convenient ready-to-run form, also for free). Most of the fun of the game involves working out the principles on which the world operates and how those bits fit together. The Virtue system is heavily involved with this, so this article will give away a lot of those details. If you plan to play or are playing the game, you should probably stall out before you read further.

C64 BASIC: Disk I/O

It’s time to start actually doing floppy disk I/O in C64 BASIC. This was a little tricker than one might like, because the Programmer’s Reference Guide only covers the most generic forms of the OPEN command, and the drives’ own manuals were infamously opaque. Still, there’s enough information in them to let us do the work.

We’ll start with the basics; we’ll create a data file and put some text in it, then read it back out. Here’s a program that writes the text:

   10 OPEN 1,8,2,"HELLO WORLD,S"
   20 PRINT#1,"GREETINGS FROM BUMBERSHOOT SOFTWARE"
   30 PRINT#1,"THIS MESSAGE SHOULD PRODUCE A SEQ FILE."
   40 CLOSE 1
   50 PRINT "THE FILE IS WRITTEN."

And here’s the very similar program to read it back out:

   10 OPEN 1,8,2,"HELLO WORLD,S"
   20 INPUT#1,A$:PRINT A$
   30 IF ST=0 THEN 20
   40 CLOSE 1
   50 PRINT "EOF: STATUS IS";ST

OPEN takes four arguments, normally. The first argument (the 1) is BASIC’s name for this open file. The second is the device number, which is 8 as usual for the first floppy drive. The third is specific to the device—disk drives let us use any number from 2 to 14 for this—and it serves a very similar purpose to the first argument. For now it’s arbitrary, but it will become relevant later when we are giving the disk commands directly. We go with 2 as the lowest legal value. Lastly, the final argument is the filename and any optional parameters. The “,S” at the end tells us that this is a SEQuential file.

ST is a special variable that is set whenever we do any I/O. This is 0 on success, and various bits are set if the operation fails in various ways. The result 2, for instance, means the file was not found, and as we can see…

64 is End of File. Unlike feof() in C, though, this is is set on the last legal read, not the first illegal one. That makes the loop logic look a bit different than we might otherwise expect.

To do anything more fun, though, we’ll need to work at the byte level, not the formatted BASIC level. We’ll do that below the fold.

My other current project

In addition to the retrocoding projects I’ve been working on lately, I’ve also got a significant hobby project that’s more modern: I’ve joined the team working on the VICE project. This is, and has been for some time, the primary emulator system for 8-bit Commodore systems and their peripherals.

The core emulation itself has been fine for a long time, but the project is old enough that it has accumulated a huge number of ports that are not really continually maintainable as people move in and out of the project. I will primariily be assisting with the creation of a new UI built out in GTK3 that should both simplify and rationalize the Unix port while also letting it run natively on non-X11 compositors like Wayland, and also grant a degree of cross-platform support.

Working on VICE with GTK3 is fairly interesting from the standpoint of my other projects here. It is, itself, of course, a retrocoding platform in its own right. But GTK is a C library, and while it has been built on an extremely complicated object system, GTK3 in particular turns out to encourage you not to use it directly. This makes many of the design considerations I’ve touched on before regarding object-oriented design in non-object-oriented languages more immediately relevant. And as not merely a GUI library but one that’s aggressive about being full-featured and under continuous development, there’s a lot of undocumented critical knowledge to getting decent results out, and not only mastery but even basic competence seems to rely a great deal on experimentation and oral tradition. That’s a very similar demand on one’s skills, coming off of my efforts to understand the way demoeffects work.

I probably won’t be writing much directly about VICE development. But as unusual things pop up, I will try to spin them off into self-contained sample programs and articles about them.

C64 BASIC: Performance Tuning

There’s a bunch of heuristics and rules for getting BASIC code to run slightly faster. Some of them even actually help. The core principles, though, are that command interpretation is work and so you want to do as little of it as possible. This has some occasionally surprising side effects. That means that to be sure what’s going on you’ll need to do some measurement.

Our Sample Task

For our initial experiments, we will put the checkerboard graphic at a hundred random places on the screen. Now, while Sinclair BASIC would let us place the cursor with a command like

PRINT AT INT (RND*22),INT (RND*32);"{H}";

we don’t have PRINT AT in Commodore BASIC. The KERNAL, however, does have a routine called PLOT at $FFF0 which will position the cursor for us. Thus, here is our first cut at the routine, in petcat format:

  10 print "{clr}{gry3}";
  20 s=ti
  30 for i=1 to 100
  40 y=int(rnd(1)*24):x=int(rnd(1)*40)
  50 poke 781,y:poke782,x:poke783,0:sys 65520:print"{CBM-+}";
  60 next i
  70 e=ti
  80 print "{home}{lblu}total time:";(e-s)/60

UPDATE, 10 Sep 2017: This listing has been updated to fix the POKE to 783 (clearing the status flags). The original post zeroed 780 instead, which cleared the accumulator. The PLOT command requires the carry flag to be clear in order to move the cursor. (Otherwise it reads the cursor position instead of setting it.) This edit does not alter the timing information.

We time our program by consulting the TI variable. This is initialized to 0 at power-on and increments every time the clock-tick IRQ is processed. That’s 60 times per second under normal operation, and 0 times per second when we’ve disabled interrupts. We don’t have to worry about interrupts this time, so TI works fine and will give us frame-level accuracy.

Running this program shows an average runtime of 4.47 seconds. That will be our baseline.

Lowering Instruction Count

Our inner loop is executing seven full BASIC commands per loop, all to perform cursor positioning. This isn’t even the usual way people did cursor positioning, though; usually they would exploit the way you could put cursor-move characters into strings. String operations permit a lot of work to be done and can be surprisingly fast. If we add a new line and then replace line 50:

  15 y$="{home}{24 down}"
  50 print left$(y$,y+1);tab(x);"{CBM-+}";

This speeds up the average runtime to 3.87 seconds, which is nearly 15% faster. That’s not bad at all, and clever use of LEFT$ and RIGHT$ can be used to get reasonable horizontal scrolling effects in pure BASIC.