Taking The Game to a new level

Finally, someone has taken the basic concept of The Game and added the one thing that was missing: brainwave scanning:

The gameboard—and premise—of Brainball is simple. The playing field sits on an orange table about the size of a typical card table. There’s a long, narrow strip of plastic running almost the length of the table with a small circular goal at either end. To play, you strap on a headband with three metal contacts and try to move the ball from the center of the table to your opponent’s goal.

Paradoxically, the key to winning a game of Brainball is trying not win. You control the ball by relaxing as much as possible; the contacts in your headband monitor your alpha and theta brainwaves. The lower the activity, the more the ball will move.

Comments Off

For Everlasting Peace

Mega Man 9 'box art'
Even “better” than the Mega Man box art: here he has an arm cannon and a gun!

Having now completed a play-through of Mega Man 9, I can safely say that it ranks right up there with Mega Man 2 and Mega Man 3.

The level design in the Dr. Wily stages is very impressive, balancing the fine line between challenging and unfair. You’ll die plenty of times — I certainly did — but each time you’ll know it’s because you screwed up, not because something came out of left field and killed you. There’s plenty of ways to meet a quick death, but never without first giving you a chance to figure out a new type of obstacle in a relatively benign environment. The level design loves to play with your expectations, with lots of twists on mechanics you’ve seen (or think you’ve seen) before. By the time you reach the screen deep in Wily Stage 3 with three 1-ups in it, you’ll know to be on your guard, even if you don’t yet know why.

A fantastic instance of challenging the player’s expectations comes in one of the screens in Wily Stage 1. I won’t spoil it for you, but if you’ve played the game, you know exactly the one I’m talking about. It took me a long time to figure out the trick needed to avoid certain death, and it’s sure to fool Mega Man veterans — heck, especially Mega Man veterans — the first time they encounter it. Whoever at Inti Creates who came up with it is a diabolical genius.

Plus, in retrospect, it’s amazing it’s taken this long for Mega Man to enter a boss’s chamber from the right side of the screen instead of the left.

The bosses in the Wily Stages are also excellent. They nicely avoid the cliche that Mega Man 4 and later fell into of a series of well-drawn but unremarkable screen-sized bosses with a single weak point. Each one here is unique, ranging from a sort of reverse tug-of-war using giant spiked balls, to a multi-screen behemoth, to a twist on a classic Mega Man boss that requires pattern memorization and/or getting into the zone to beat.

Also, Dr. Wily finally realized how effective the mandatory skull-themed robot he pilots during the final battle could be if he made the whole thing out of whatever alloy it is that deflects all of Mega Man’s weapons. And not to spoil the ending, but he even seems to have anticipated his inevitable defeat, beyond just having an escape plan.

Alas, though, the game isn’t perfect. Dr. Wily’s final form sadly follows the stale “disappearing and reappearing saucer” thing that started in Mega Man 4. I never cared much for that type of final battle, though at least the weapons available this time give you a few options for hitting the saucer when it’s well outside of jumping range. Also, even though Rush Jet works just fine underwater, I would’ve kind of liked to see the return of Rush Marine for that purpose, just because.

If I may boast for a second, I managed to get about 25% of the challenges completed on this first play-through quite by accident, including half the beat-a-robot-master-under-10-seconds ones and the one that involves never stopping in one stage (Galaxy Man’s stage for me, if you’re wondering). (I’ve also managed to beat Dr. Wily’s first two forms without taking damage, but there’s no prize for that.) I don’t know if I’ll ever pull off the harder ones like the never-miss-a-shot or never-take-damage ones, or even the tedious ones like beat-the-game-five-times-in-a-day, but I’ll definitely be playing through the game many more times.

Peeking at the downloadable content coming next month, there’ll be options for increasing the difficulty even more, and adding an option to play as Proto Man. Arguably these could’ve easily been part of the main game, but given that I would’ve gladly paid $20 for Mega Man 9 as-is instead of $10, I really can’t complain about shelling out another $8 for all the extras.

Inti Creates could’ve easily relied on exploiting old-school Mega Man nostalgia and produced a lump of 8-bit shovelware, but they took the effort to recreate the quality of those games, not just their appearance. If there is a Mega Man 10 in the offing, let’s hope they don’t start slacking off.

Mega Man 9!

Mega Man 9 is shaping up to be precisely as awesome as I had hoped. If you wish to remain unspoiled in regards to this awesomeness, you best stop reading right now.

First off, they’ve nailed the old-school Mega Man look and feel and sound. One could imagine an alternate universe where this game came out after Mega Man 2. Except for being able to save your game instead of scribbling down grid passwords. And the challenges ranging from easy (kill a robot master using only the Mega Buster… yeah, that’s how you have to kill the first one) to nigh-impossible (beat the game without taking damage!). And the online leaderboard for speed-running the game. And the hooks for downloadable content. But hey, the menus for all those things are downright 8-bit.

The plot is, well, nobody plays a Mega Man game for the plot, and Mega Man 9 delivers what you’d expect, with the right amount of ridiculousness in the no-seriously-Dr.-Wily-isn’t-the-villain-this-time-honest!-ness. Eight of Dr. Light’s robots are running amok, and Dr. Wily insists that he’s finally reformed right before Dr. Light turned evil (and if you donate money to Dr. Wily’s Swiss bank account, you can fund development of something to stop Dr. Light’s robots!). Apparently everyone swallows this, and it’s up to Mega Man to blast some sense into the robot masters after Dr. Light’s arrest. (Why the police apparently have no qualms about Mega Man, clearly Dr. Light’s deadliest creation ever given his undefeated record against dozens of Dr. Wily’s robots, running free while all this is going on, has not yet been addressed.)

The level design has been pretty good, putting new and interesting spins on the classic elements. Anyone who’s ever played a Mega Man game knows that eventually they’ll come across two things: disappearing blocks over spikes and/or pits, and multi-screen drops through spike-lined corridors. I’ve played two levels so far, each fairly arbitrarily chosen, and I’ve already seen both.

Plug Man’s stage has several disappearing block sections, and manages to find new tricks with them that previous games never tried. I wonder how many players will fall to their doom when a block suddenly appears in front of the platform they were trying to jump to. Nice. (In fairness, you could very much see that coming if you bothered to watch the pattern before you started jumping around.)

Splash Woman’s stage has the spike drops. Early on, you land on a platform in the middle of the screen. The left drop has no spikes, the right one does. You get to choose which one to jump down. Choose wisely, and you can get a 1-up. Later on, you have to go up a series of spike-lined rooms, relying on platforms that slide across the screen to reach the next ladder. In a way, it’s like a block puzzle mixed with a spike drop, in reverse. I haven’t gotten past the third screen without wimping out and using Rush Coil to avoid the pair of spikes deviously placed in the dead center of the room, but I’m sure it can be done.

So far, even when there’s clearly inspiration from a previous game, there’s something new in the implementation here that keeps it from being the series of retreads that Mega Man 7 wound up as. Again in Splash Woman’s stage, the part where you have to ride bubbles to the top of the screen is straight out of Wave Man’s stage in Mega Man 5, but this time (a) it’s underwater, so you can jump really well, and (b) enemies shoot out at you from the sides of the screen.

The attention to detail is pretty nifty, too. Get hit by an octopus’s ink blob in Splash Woman’s stage, and Mega Man stays covered in ink until you switch to a different weapon. You can also buy a “book of hairstyles” from the item shop on the stage select screen to take off your helmet… until you die. There’s also a “book of costumes”, which I haven’t tried yet, but from its icon I’m assuming it dresses Mega Man up as Roll. (For the record, there are also items available which are actually useful, if you’re in to that sort of thing.)

The robot masters themselves haven’t disappointed so far. Plug Man’s shots travel along the floor, up the wall behind you, onto the ceiling, and then drop down right above you head, so you have to keep your eye both on what Plug Man is doing and the shots you’ve already dodged once. Splash Woman swims to the top of the screen while fish move across the screen, and then she drops tridents on you. The Mega Buster is much more effective against hear than Plug Man’s weapon.

Another great nostalgic thing: Splash Woman and I managed to kill each other simultaneously, just like the first time I won-for-all-intents-and-purposes-even-though-the-game-didn’t-count-it against Cut Man way back in the original Mega Man. And just like then, Mega Man 9 counted it as a death rather than a victory. On my final life. Game over.

Count yourself sort-of-lucky, Splash Woman, for your days are numbered. Specifically, numbered 1, since tomorrow night it’s go time.

Mick Faldo v. the LHC

Damn you, Jamie, for planting the idea in my head. This is all your fault. The LHC won’t create a black whole and swallow the planet, but the following, a lyrical fanfic of an obscure parody song crossed with particle physics is so dorky it may collapse upon itself, forming a dork singularity from which nothing can escape.

I hope you’re pleased with yourself.

Well everyone hails
All their stories and tales
And Geneva now is a provider
Of stories that might
Tell of the epic fight
Of Mick Faldo and the large collider.

‘Twas a supercooled ring
Through which protons would zing
In hopes of maybe detecting Higgs bosons.
But a few people thought
It would turn all to naught
‘Cause they listened to credulous morons.

The scientists heard
Of these fears, quite absurd,
And explained that the worries were baseless.
But the fear-mongers told
About mini black holes
And reality-consuming strangelets.

Those fears and concerns
Failed to discourage CERN
And their plans to probe energies larger.
The opponents screamed “no!”
And they turned to the bow
Of Mick Faldo, the world-famous archer.

They asked, “If you have the time –
It won’t cost you a dime –
Could you stop it before things get much worse?
It packs far more power
Than a meteor shower
And it might destroy the whole universe!”

Mick Faldo replied,
“How would I get inside?
My success I could never guarantee.
And please done be miffed –
Though my arrows are swift,
They’re slower than .999c.”

But he tried nonetheless,
Aiming towards the ATLAS
And adjusting for underground weather.
But did his arrow trick work?

No, he felt like a jerk
When his shot pushed two hadrons together.

Still everyone hails
All their stories and tales
And Geneva is still a provider.
The story lacks harm
But it has a strange charm:
It’s Mick Faldo and the large collider.

Like Hell it Could

In case for some unfathomable reason you’re one of those people who thinks the Large Hadron Collider is going to destroy the planet (as though such a thing were that easy), there are no less than two websites you can check to see if the unthinkable (and impossible) has happened:

It always good to have multiple sources for this sort of thing, since there is some misinformation floating around out there. Plus, both of the two sites above have RSS or Atom feeds you can subscribe to, so that you’ll be notified in case the current status of the planet changes.

WARNING: Those prone to worrying about things like the end of the universe might want to avoid reading the HTML source of the first of those two links, lest they should see this:

The possibility that we are living in a false vacuum has never been a cheering one to contemplate. Vacuum decay is the ultimate ecological catastrophe; in the new vacuum there are new constants of nature; after vacuum decay, not only is life as we know it impossible, so is chemistry as we know it. However, one could always draw stoic comfort from the possibility that perhaps in the course of time the new vacuum would sustain, if not life as we know it, at least some structures capable of knowing joy. This possibility has now been eliminated.

The second special case … applies if we are now living in the debris of a false vacuum … This case presents us with less interesting physics and with fewer occasions for rhetorical excess than the preceding one.

S. Coleman and F. De Luccia (1980). “Gravitational effects on and of vacuum decay”. Physical Review D21: 3305.

Those prone to worrying about such things should probably also refrain from reading the above quote.

Please do not jump on the table

Last time, I mentioned one obstacle I ran into when writing a reverse engineering tool for Nintendo games. Namely, just because a piece of code is called using the JSR (Jump to SubRoutine) instruction doesn’t mean the code being called actually is a subroutine. Subroutines eventually execute an RTS (ReTurn from Subroutine) instruction to go back to the code immediately following the JSR. This bit of code in Super Mario Bros., however, doesn’t:

       asl          ;shift bit from contents of A
       pla          ;pull saved return address from stack
       sta $04      ;save to indirect
       sta $05
       lda ($04),y  ;load pointer from indirect
       sta $06      ;note that if an RTS is performed in next routine
       iny          ;it will return to the execution before the sub
       lda ($04),y  ;that called this routine
       sta $07
       jmp ($06)    ;jump to the address we loaded

As I mentioned before, the above code treats the “return address” that JSR pushed onto the call stack as the address of a jump table, with the index into the jump table passed in the A register.

The reverse engineering tool needs to be aware of this, since otherwise it won’t know about the jump table, and thus won’t find the executable code pointed to by the jump table’s entries.

To solve this problem, I added a little static analysis routine that inspects all the code called by a JSR, checking for stack-based shenanigans. A normal subroutine may push and pop values on and off the call stack, but it will leave the return address alone, and when the RTS is reached, the return address will be at the top of the stack. A jump table engine like the above will pop the “return address” off the stack and end not with a RTS but with an indirect JMP (JuMP). Truly weird code will do something else.

My program now uses the Boost Graph Library to build a control flow graph of the executable code it’s located, showing all the possible paths of execution through the program. The analysis runs as a depth-first traversal of each alleged subroutine, checking what the depth of the call stack will be at each instruction.

Naturally, the analysis is only a heuristic. It’s possible for the code to be a normal subroutine and look like a jump table engine if, say, it manually pops the return address off the call stack and does an indirect JMP to it instead of an RTS. I’m making the assumption that the code isn’t deliberately obfuscated like that.

During testing, I tried running the jump table engine detector against Mega Man to see what would happen, and look at what it found:

PRG4_1562: txa
PRG4_1563: asl A
PRG4_1564: tay
PRG4_1565: iny
PRG4_1566: pla
PRG4_1567: sta $F4
PRG4_1569: pla
PRG4_156A: sta $F5
PRG4_156C: lda ($F4),Y
PRG4_156E: tax
PRG4_156F: iny
PRG4_1570: lda ($F4),Y
PRG4_1572: sta $F5
PRG4_1574: stx $F4
PRG4_1576: jmp ($00F4)

The details of how it works are different (it passes the index in the X register instead of A, and it only uses two bytes of zero-page memory instead of four), but it does the same thing as the jump table engine in Super Mario Bros. The fact that my detector seems to work on two different games written by two different developers is a good sign — both that the detector works, and that the jump-table-via-subroutine trick is likely to be used in many games. (The detector also found a few subroutines that do some other form of stack weirdness, but I haven’t look yet at just what’s going on with those.)

The reverse engineering tool doesn’t actually make use of this new information yet, but that’s the next thing on the to-do list.

Comments Off

Going in reverse

In case you’re wondering what I’ve been up to with the relative silence here lately, for some reason I’ve decided to write a reverse engineering tool for NES games. This might eventually lead to answering a long-standing question, or even lead into a revival of Wallace.

One of the challenges with writing such a tool is figuring out just what the various bytes in a ROM image even mean. In most operating systems, the internal structure of executable files contains some structural information. In particular, the executable code itself (aka .text, counterintuitively) is stored separately from global data (aka .data) that the executable code uses. So right off the bat, you can find the machine code and disassemble it back into something fairly readable.

No such luck with a NES ROM image. While there is segmentation in the file format, it’s based on whether the memory bank in question is part of CPU memory (PRG, or “program”, banks) or PPU memory (CHR, or “character”, banks). CHR banks contain the pattern tables that store the game’s graphics, so those are pretty straightforward to interpret.

However, PRG banks store both code and data in whatever layout the developers chose to. All you have to go by is the fact that the uppermost 6 bytes of CPU memory contain pointers to three pieces of code: the non-maskable interrupt handler (invoked by the PPU), the reset handler (invoked after power-on or reset), and the software interrupt handler (invoked by the BRK instruction). That’s all you know for sure about the memory layout.

In principle, this is enough. You can start at the addresses indicated by those pointers and start reading off instructions, following any branches or jumps along the way. We aren’t actually executing anything, just stepping through the structure of the code to find where all the instructions are. We don’t know what the program will actually do when it executes — for example, we don’t know which way a branch will go — but for our static analysis, we can just trace both code paths until we run out of code. When we’re done, everything we’ve reached is an instruction and can be disassembled, and anything else is data (or filler).

Of course, since nothing can be easy, this static control flow analysis fails if the program does anything tricky. Chances of running into something tricky are pretty good. For example, take a look at this bit of code from a full disassembly of Super Mario Bros.:

      lda OperMode     ;this is the heart of the entire program,
      jsr JumpEngine   ;most of what goes on starts here
      .dw TitleScreenMode
      .dw GameMode
      .dw VictoryMode
      .dw GameOverMode

JSR is the “jump to subroutine” instruction: it pushes the address of the following instruction onto the stack and jumps to the specified address. When an RTS (“return from subroutine”) is executed, that return address gets popped off the stack and jumped to. So, normally, the code after a JSR will get executed once the called subroutine does an RTS.

But clearly, that’s not what’s happening here, since we have eight bytes of data immediately following the JSR, instead of code. In particular, four 16-bit addresses. Needless to say, my current executable-code-detection algorithm chokes on this. What’s going on? The code for the JumpEngine “subroutine” reveals all:

       asl          ;shift bit from contents of A
       pla          ;pull saved return address from stack
       sta $04      ;save to indirect
       sta $05
       lda ($04),y  ;load pointer from indirect
       sta $06      ;note that if an RTS is performed in next routine
       iny          ;it will return to the execution before the sub
       lda ($04),y  ;that called this routine
       sta $07
       jmp ($06)    ;jump to the address we loaded

For those who don’t speak 6502, this is basically a clever way of implementing a jump table. On entry, the A register contains the index of the table, and the top of the stack contains the address of the jump table itself. The routine multiplies A by 2 (the size in bytes of an address) and stores it in index register Y. It then writes the Yth entry in the jump table to memory address $0006, and then jumps to the address stored there.

The slightly convoluted routine to implement this is needed to get around the limitations of the 6502 processor — in particular, the fact that registers are too small to store an address. But for our purposes, this sort of thing demonstrates that we can’t blindly assume a JSR invokes a “normal” subroutine — we have to check whether the alleged subroutine does any kind of stack trickery like that, and if it does, not assume that the instructions following the JSR will get called.

Of course, since now I have a need to do two kinds of static analysis (the “executable code detector” and the “tricky subroutine detector”), ad hoc navigation methods through the PRG banks won’t cut it. Luckily, it looks like the Boost Graph Library will give me a fairly easy way to make the PRG banks look like a proper graph (without actually having to build one explicitly), at which time I can implement static analysis routines using standard graph traversal algorithms. That shouldn’t be too hard — most problems there will probably come from learning how to write the necessary wrappers around my classes.

Also, note how I’ve been talking as though I know for certain where each of the PRG banks will appear in memory. Well, nothing can be easy. NES ROMs make use of mappers, which swap different PRG and CHR banks into memory at runtime, sort of like how a virtual memory system does paging. Dozens of different mappers exist, each with different possible behavior. With just static analysis, all I can go off of is knowing which set of banks might be mapped to which ranges of addresses, without knowing which combinations will actually exist at runtime.

In fact, if writing an emulator, implementing the CPU is arguably the easiest part. The real pain comes in trying to implement each of the mappers, which vary widely from ROM to ROM based on whichever crazy hardware the developers used to get around the Nintendo’s memory limitations. No standardization whatsoever.

Of course, there’s lots of other challenges to reverse engineering a ROM. I haven’t even covered everything about just figuring out which bytes are for what — figuring out the text table, for example, has its own interesting issues. And that’s before we get to the point of actually figuring out what the ROM does when you run it.

If this were a program to generate driving directions, it’s still at the point of trying to figure out which squiggles on the map are roads and which are rivers. A critical thing, sure, but still a long way from the goal.