We are a 3 person team. Here are our games so far:

Archive for the ‘retro game internals’ Category

Retro Game Internals: Punch-Out Behavior Script

Friday, February 2nd, 2018

Last time we looked at match scripts which were the highest level scripts controlling opponents in Punch-Out. The basic function of a match script was to sequence opponent behaviors throughout the fight. Today we’ll dive into behavior scripts which are where those behaviors are actually implemented.

The following video shows an interpretation of what the behavior script for Piston Honda 1 might look like in something like plain English commands.

Animation Commands

Behavior scripts are in charge of sequencing animations in much the same way that match scripts were in charge of sequencing behaviors. The anim command plays a single specific animation, and the anim_rnd command plays an animation randomly selected from a list of 8 options. In the video above, whenever a random selection is made from a list of options, the chosen option is briefly highlighted in red. When Piston Honda throws his opening 2 jabs, he is using anim for each one. After that, he uses anim_rnd to randomly pick from a set containing 6 hook animations, and 2 empty animations. The result is that his third action will be to throw a hook 75% of time time, and to do nothing 25% of the time.

Animations will be played back synchronously from the point of view of the behavior script since the script interpreter is paused any time the animation system is not in its idle state.

Flow Control Commands

There are a few commands available to modify the execution of the behavior script itself. The pause commands can pause script execution for a specific number of frames, or a number of frames randomly chosen from a list of 2 options.

There are various branch commands available that optionally jump to a different part of the behavior script if certain conditions are met. The branch_rnd command has a specified probability that the branch will be taken each time it is executed. A special case of the probabilistic branch is branch_always which has a 100% chance of branching.

There is a simple looping mechanism built in to the behavior script interpreter that can be used to repeat sections of script a certain number of times. The set_loop_count command sets the current value of the loop counter. Then, each time the branch_while_loop command is executed, it decrements the loop counter by one and branches only if the counter is still above zero.

The final kind of branch checks the contents of memory to decide whether or not to take the branch. Piston Honda uses this branch_mem_test command to check if his most recent punch connected during his special behavior. Any time his punch connects, he branches directly to the next punch. If a punch does not connect, he uses a branch_while_loop command to keep punching only until he accumulates 5 failed punches.

Behavior Commands

There are 2 commands that behavior scripts can use to control the behavior system itself. The begin_behavior_main command is used to end whatever behavior is currently running and begin running the main behavior. This is different from a branch within the behavior script because the section of script that is considered to be the current “main” behavior can be changed during the course of the match by the match script (see the previous post about match scripts.)

The other command related to behavior is enable_behavior_change. Whenever a new behavior begins, it starts off in a locked state where any further requests to change behavior will be blocked. By using the enable_behavior_change command, the script is signaling that it is ready to allow other behaviors to happen. For example, in Piston Honda’s special behavior, the enable_behavior_change command is never executed and so if Mac gets tired during that time, the special behavior will continue to run. Knock down events will bypass this system however so if Mac gets knocked down during Piston Honda’s special, a behavior change will happen no matter what.

Up Next

With match script and behavior script out of the way, the final piece of the opponent script hierarchy puzzle is animation script. These are very low level scripts with a rich command set that run to implement the animations that the behavior scripts have been requesting. If you have any questions or comments, or you want to know when these (very infrequent) blog posts go up, please feel free to contact me on twitter @allan_blomquist

(Prev – This is part 4 of a series)

Retro Game Internals: Punch-Out Match Script

Tuesday, May 2nd, 2017

The match script controls opponent behavior at the highest level in a fight. The basic operation it performs over and over is to wait for a certain time during the round and then make some kind of change to the opponent’s configuration data. The following video shows the first round of the first fight against Bald Bull along with a representation of the match script that is controlling his overall behavior.

There are three basic operations that a match script can perform. The first is just to wait until the round timer reaches a specific value. The second is to request that the opponent change his current behavior. Behaviors are registered in a fight configuration table in memory and then called on at various times by both match scripts and the game engine itself. There are two behavior slots in the table that match scripts use that I’ll call the “main” behavior and the “special” behavior. Special behaviors are things like Bald Bull’s Bull Charge and Piston Honda’s Honda Rush, while main behaviors are the normal punches the opponent throws the rest of the time. The particular behavior scripts used to implement these behavior types can be changed by the match script mid-round, so fighters can start out using one main behavior and then switch to a different main behavior later on (you can see Bald Bull do this when the timer reaches 0:20 in the video.)

A quirk of behavior changes from match scripts is that they are overridden by behavior changes requested by the game engine. The game engine uses four of the behavior slots to request new behaviors when Mac loses all of his hearts and becomes tired, recovers from being tired, gets up after being knocked down, and after the opponent gets up after being knocked down. If the match script has issued a request for a behavior change, but one of those four game engine events happens before that request can be honored (requests can’t be honored until the opponent is in an idle state), then the game engine will get to set the behavior it wants and the request from the match script will be lost. Some fighters, like Bald Bull, request their special behavior multiple times in quick succession. The only purpose of this seems to be to reduce the chance that any one of the requests will be accidentally skipped.

The third basic operation of a match script is to patch memory. Most memory patches affect the fight configuration table where the behavior scripts are registered. In addition to behavior selections, the table also contains data related to the difficulty of the fight. For example, when the timer reaches 0:30 in the video, Bald Bull changes his guard matching parameters making it so you can no longer fake him out by tapping up and then throwing a punch to the body. Match scripts have the ability to patch arbitrary memory addresses also, but the only time it is used is at the beginning of Mike Tyson round 2 to make it so that you will get a star the first time you punch him while he is idle.

Up Next

The next kind of script we’ll look at will be the behavior scripts. These are what the match script and game engine have been selecting to run and are where the actual punching behavior gets put together. If you have anything you’d like to see covered or any questions about a post you can contact me on twitter @allan_blomquist

(Prev – This is part 3 of a series – Next)

Retro Game Internals: Punch-Out Overview

Sunday, April 23rd, 2017

Each fighter in Mike Tyson’s Punch-Out!! is controlled by one or more interpreted bytecode scripts. The player character, Little Mac, runs a single script that contains the logic for each action available to the player (dodging, blocking, punching, etc.) The opponent characters are controlled by 3 tiers of independent scripts that work together to create the opponents’ behavior.

Match Script

The highest level opponent script runs throughout all 3 rounds of the fight and controls the major changes in opponent behavior. I’ll call this script the “match script.” The main job of a match script is to set the behaviors that the opponent will run in response to various events during the fight. For example, a certain behavior will be selected to run immediately after the opponent gets up after being knocked down, or when the player runs out of hearts and becomes tired. These behaviors are recorded in a table and will be invoked by the game engine in response to the appropriate events. The match script also sets up initial values for configuration options related to the difficulty of the fight (like the amount of time that the opponent will remain vulnerable after missing a punch.) Finally, the match script will begin waiting for certain time markers during the fight to make changes to the values it has previously set.

Behavior Script

The next lower level opponent script tier is the “behavior script.” This level is in charge of sequencing the specific punches and attacks the opponent is supposed to perform as part of his current behavior (as dictated by the match script.) Behavior scripts execute commands like “throw a right jab, pause for 28 frames, randomly throw either a left or right uppercut, repeat all that 5 times.” They also have commands for reading and writing any memory location from the underlying game engine so behaviors can be very dynamic.

Animation Script

The lowest level opponent script tier is the “animation script.” These scripts perform the nitty gritty details of a single punch, block or special attack as part of a behavior (as dictated by the behavior script.) Commands found at this level include things like “set the opponent’s current frame of animation to sprite #23, move him down and to the right by 1 pixel every 2nd frame for the next 10 frames, change frame of animation to sprite #24, play sound effect #7.” In addition to animation related commands, animation scripts also sequence various gameplay state changes that are closely tied to the movements of opponents. For example, as part of a long animation for a special attack, an animation script might insert commands to make the opponent vulnerable to being knocked down with a single punch during a very specific window of time. Like behavior scripts, animation scripts can read and write arbitrary memory from the game engine to achieve more dynamic effects.

Little Mac Script

The script that Little Mac runs is most similar to the opponents’ animation scripts. It changes the current frame of animation being displayed and moves the player around on screen as needed. Like the animation scripts, Little Mac’s script is also what sequences certain gameplay events like when exactly Mac is considered to be punching the opponent, or when he should register as blocking or dodging. The player’s input is what drives Little Mac’s script in the same way that behavior scripts drive animation scripts for the opponents.

Each of these 4 script systems is processed by a different interpreter. Although many of them share some common functionality like basic flow control and raw memory access, each system implements its own version instead of sharing code (or opcode space) with the others. This allows each type of script to be very domain specific and make efficient use of a small set of targeted commands. Script data accounts for about 22% of the non-graphics data on the game cart (the actual machine code for the game engine is only about 17%) so having a compact representation for scripts was very important.

Up Next

In the following posts in this series I’ll go into more detail about each of these different kinds of scripts and explore how they interact to create gameplay. I’ll also look briefly at the hidden rules of the game like what determines when an opponent gets up after a knock down, and how star punches are awarded. If you have anything you’d like to see covered or any questions about a post you can contact me on twitter @allan_blomquist

(Prev – This is part 2 of a series – Next)

Retro Game Internals: Punch-Out Passwords

Saturday, March 7th, 2015

The NES game “Mike Tyson’s Punch-Out” uses a password system to allow players to continue from certain points in the game. Each password consists of 10 digits, each of which can be any number from 0 to 9. There are 2 kinds of passwords that the game will accept, which I’ll call “regular” and “special” passwords. Special passwords are specific sets of 10 digits that the game looks for and reacts to in a unique way when they are entered. The complete list of special passwords is as follows:

  • 075 541 6113 – Busy signal sound 1
  • 800 422 2602 – Busy signal sound 2
  • 206 882 2040 – Busy signal sound 3
  • 135 792 4680 – Play hidden circuit: “Another World Circuit” (must hold Select button and press A + B to accept password)
  • 106 113 0120 – Shows credits (must hold Select button and press A + B to accept password)
  • 007 373 5963 – Takes you to fight against Mike Tyson

The other kind of passwords that the game accepts are the regular passwords. Regular passwords are a coded representation of the progress that you’ve made in the game. The game data that is encoded into a regular password includes:

  • Number of career wins
  • Number of career losses
  • Number of wins by knockout
  • Next opponent to fight

Encoding Passwords

We’ll use an example game with 24 wins, 1 loss, 19 knockouts and starting at the world circuit title fight against Super Macho Man to see how passwords are generated.

The process of encoding this game state into a password begins by collecting your number of wins, losses and KOs into a buffer. The game represents each number in binary-coded decimal form with 8 bits per digit and 2 digits for each value. So for our 24 wins, that’s one byte with the value 2, and a second byte with the value 4. Then comes the pair of bytes for the number of losses and one more pair for KOs for a total of 6 bytes of data. The diagram below shows these 6 bytes with their values in both decimal and binary on the bottom.

punchout01

The next step is to generate a checksum over those 6 bytes. The checksum byte is calculated by adding the 6 individual bytes together and then subtracting the result from 255. In our case we have 2 + 4 + 0 + 1 + 1 + 9 = 17 and then 255 – 17 = 238.

Next we shuffle some of the bits from the 6 bytes into a new buffer. We can think of the new buffer as a single 28-bit intermediate value that we’ll begin to fill in piece by piece. The bits from the first buffer are split into groups of 2 and moved around to different hard coded positions in the second. This is the first of a few steps whose sole job is to obfuscate the data make it difficult for players to see how passwords are generated.

punchout02

Notice that not all of the bits from the original buffer are transferred into the new intermediate buffer. These bits are ignored because they are known to always be 0. Your number of losses in particular only needs to contribute 2 bits of information to the password because of the rules of the game. If your total number of losses ever gets up to 3, you’ll get a game over and never get a password. Therefore, you only need to be able to represent the numbers 0, 1 and 2 for your number of losses and that requires only 2 bits.

Next we shuffle more bit pairs into the intermediate buffer. The first four pairs come from the checksum value that we computed earlier. The other pair of bits comes from the opponent value. The opponent value is a number that tells which opponent you’re going to fight next after you enter your password. There are three possible opponent values that can be used:

0 – DON FLAMENCO (first fight of major circuit)
1 – PISTON HONDA (first fight of world circuit)
2 – SUPER MACHO MAN (last fight of world circuit)

Since we wanted to generate a password that puts us at Super Macho Man, we’ll use 2 for our opponent value. The checksum and opponent value bits are then shuffled into the intermediate bits as follows:

punchout03

The next step is to perform some number of rotations to the left on the intermediate bits. A single leftward rotation means that all of the bits move one place to the left, and the bit that used to be the leftmost bit rotates all the way around to become the new rightmost bit. To calculate the number of times we’ll rotate the bits to the left, we take the sum of the opponent value and our number of losses, add 1, and take the remainder of that result divided by 3. In our case we have 2 + 1 + 1 = 4. Then the remainder of 4/3 is 1 so we’ll rotate the intermediate bits to the left 1 time.

punchout04

At this point the intermediate bits are thoroughly scrambled and now it’s time to start breaking them apart to come up with the digits that make up our password. Passwords need 10 digits so we’re going to break our 28 intermediate bits into 10 separate numbers that we’ll call password values P0, P1, P2, etc. The first nine password values will get 3 bits of data each, with the final value getting just 1 of the intermediate bits. To round out the final password value, we will also include bits that represent the number of rotations we performed in the previous step.

punchout05

Finally we add a unique hard coded offset to the password value in each position. The final password digit is then the remainder of that sum divided by 10. For example in the seventh position we use an offset of 1, so we have 5 + 1 = 6, and then the final digit will be the remainder of 6/10 which is 6. In the fourth position the offset we use is 7, so we have 5 + 7 = 12, and then the final digit is the remainder of 12/10 which is 2.

punchout06

Now we have the final password digits which we can try out in the game.

punchout07

Decoding Passwords

The process of decoding a password back into the numbers of wins/losses/KOs and the opponent value is a straight forward reversal of all the steps outlined above and is left as an exercise for the reader. There are two notable mistakes however that the game makes when decoding and verifying player supplied passwords.

The first mistake happens in the very first step of decoding a password which would be to subtract out the offsets to get back to the password values. The original password values contained 3 bits of data each, which means their values before the offsets were applied must have all been in the range 0-7. However, a player might supply a password that results in a password value of 8 or 9 after the offset is subtracted out (modulo 10.) Instead of rejecting such a password immediately, the game fails to check for this case and instead allows the extra bit of data in the password value to pollute the collection of intermediate bits in such a way that passwords are no longer unique. Because certain intermediate bits could have either been set by the password digit that they correspond to OR the extra bit of a neighboring password value, there are multiple passwords that can now map back to the same set of intermediate bits. This is why you can find different passwords that give you the same in-game result, where as they would have been unique otherwise.

The second mistake is a bug in the logic the game uses to try to validate the data after decoding the password. The conditions that the game tries to enforce are:

  • checksum that is stored in the password matches what the checksum should be given the win/loss/KO record stored in the password
  • loss value is 0, 1 or 2
  • opponent value is 0, 1, or 2
  • rotate count stored in the password is the correct rotate count given the loss value and opponent value that were stored in the password
  • all digits of win/loss/KO record stored in the password are in the range 0-9
  • wins is >= 3
  • wins is >= KOs

If any of these conditions are not met, the game intended to reject the password. However, there is a bug in the implementation of the final check (specifically when comparing BCD encoded numbers.) Instead of actually checking for wins >= KOs, the game will allow cases where the hi digit of wins is 0, the lo digit of wins is >= 3 and the hi digit of KOs is less than the lo digit of wins. For example, a record of 3 wins, 0 losses and 23 KOs will be accepted by the game (as demonstrated by the password 099 837 5823) when this was intended to be rejected (since you can’t have won 23 fights by knockout if you’ve only won 3 fights total.)

Conclusion

The particular details of this encoding scheme are unique to Punch-Out, but the general idea of taking some important bits of game state, transforming them in a reversible way to obfuscate their relationship to the original game state, and then using them to generate some number of symbols to show to the player as a password is fairly universal. Checksums can be used to make sure that accidental random changes to the password (if your finger slips while entering it) are most likely to result in an invalid password instead of some other password representing a random other game state.

If you’d like to offer feedback or keep track of when new posts in this series become available, you can follow me on twitter @allan_blomquist

(This is part 1 of a series – Next)

Retro Game Internals: Contra Conclusion

Monday, May 12th, 2014

To round out my discussion of Contra I’m going to cover a few miscellaneous topics that don’t warrant a full writeup on their own. Some of these things are details of the game’s programming and some are just interesting things about the game itself that I never knew before. I’ll start off with a table of contents for this series for easy reference and then dive into the last few details.

Previous Posts about Contra

Random Numbers

Contra has a single global 8-bit value that it uses as the source of randomness throughout the game. The way that it updates the random value each frame is kind of interesting in that it doesn’t implement any particular algorithm that you can call on once per frame to get the next number in the sequence. Instead, the next random value is generated by spinning in a tight loop during the time that the game is idle and waiting for the next display frame to begin (while waiting for the vblank interrupt.) During that time, the game continually adds the current frame counter value into the random number over and over again until the video hardware in the NES signals to the game that it’s time to begin processing for the next display frame. One consequence of this approach is that the particular sequence of random numbers you’ll get is heavily dependent on the exact cycle level operation of the CPU and the interaction between the CPU and the video hardware. That means that even if two emulators implement the logic of the CPU instructions perfectly, they will still generate different random sequences if their timing is not exact. You can see an obvious manifestation of this in the attract mode of Contra which plays back a pre-recorded stream of button input and relies on determinism to replay the demo exactly the same each time. Below is a side by side comparison of the same frame of the attract mode running on two different emulators. Notice that the running soldier that has randomly spawned on the lower right part of the screen selected a single spawn when running on Nintendulator and a triple spawn when running on NESten. This is because the sequence of random numbers being generated by the two instances of the game is not the same. Fortunately, the influence of the random numbers is small enough to not completely break the attract mode playback.

prng_difference

Structure of Arrays

Contra stores all of its data about enemies and bullets in structure-of-arrays format instead of the more object oriented array-of-structures format. The reason for this doesn’t have to do with CPU cache utilization or SIMD instructions like you might expect, but is instead a consequence of the NES having 16-bit memory addresses but only 8-bit CPU registers. If you want to access data indirectly through a pointer, you can’t store the address of the object in the pointer and then hard code the offset to the member you want in the load instruction because the address of the object probably won’t fit into a CPU register. Instead, you need to flip everything around and hard code the full 16-bit address of an array of members for multiple objects into your load instruction and then use the register to hold the offset within the array to get to the member that belongs to the object that you’re interested in.

Screen Space

In Contra, everything happen in screen space. The positions of the players and the positions of the enemies and bullets are all stored and manipulated within the coordinate system of the screen (i.e. a position of 0 always means the point in space that is currently at the left side of the screen, no matter where within the level the screen has scrolled to.) This is an optimization that seems a little counter intuitive at first because you would think that storing all of your positions in screen space would make things like scrolling a lot more complicated. Now instead of just changing a single scroll position variable to scroll the screen, you have to manually move the positions of every enemy, player and bullet every frame to simulate scrolling. The reason that this actually ends up being a good thing to do is that it saves a lot more time than it costs each frame. Scrolling is more complicated, but it really just boils down to adding 1 extra number into an object’s position as it updates each frame which is often just 1 extra CPU instruction per game object. The big win is that now all calculations related to the positions of things can be done using 8-bit values (the NES screen is 256×240 pixels so you can locate any position on screen with pixel precision using a single byte for X and Y.) Since the NES only supports 8-bit arithmetic natively this ends up being way faster than trying to emulate 16-bit arithmetic to handle 16-bit world positions. This of course only works for a game like Contra where the relationship between world space and screen space is a simple translation without any scaling or rotation possible (i.e. transforming from world to screen space happens to be commutative with other translations even though applying transforms is not commutative in general.) If the camera could zoom out in the game then things would start moving too fast and if the camera could rotate then things would go in the wrong direction.

Subtle Behavior

There are a number of things in Contra that change according to how many times you’ve played through the game in a single sitting, and which gun you currently have. The following is a complete list of the differences, where FINISHED would be 0 the first time through the game, 1 the second time through, etc. and GUN is 0 for your default weapon, 1 for Fire, 2 for Machine gun or Laser and 3 for Spread:

  • Level 8 mid boss and final boss HP = 55 + (16 * FINISHED) + (16 * GUN)
  • Level 8 mid boss projectile HP = 2 + FINISHED
  • Level 8 mouth things in wall HP = 4 + (2 * FINISHED) + GUN
  • Level 8 scorpions HP = 2 + FINISHED + GUN
  • Level 8 pods around final boss HP = 24 + (2 * FINISHED) + (2 * GUN)
  • Level 6 boss HP = 64 + (8 * GUN)
  • Red cannons that comes up out of the ground wait less time to begin shooting at you for greater FINISHED
  • Random enemy spawns are more frequent with greater FINISHED and GUN, and when FINISHED is 0 they take care not to spawn right on top of you and only spawn on the right side of the screen in the first level
  • Gray turrets in walls rotate to target you faster, and wait less time to target again after shooting bullets with greater GUN
  • Soldiers that shoot bullets tend to shoot more bullets per round with greater GUN
  • Cannons on screen for level 2 and level 4 bosses, as well as the bosses themselves, wait less time between shooting at you for greater GUN
  • Level 8 mid boss shoots 3 projectiles at a time when GUN is 3, but only 2 otherwise
  • Speed at which scorpions drop down on you from the ceiling during final boss fight increases proportional to GUN

Conclusion

Contra is one of my favorite games on the NES and as a game programmer it was a lot of fun to dive in and figure out exactly how it works. I’m always amazed at how much game developers of the time were able to get out of hardware that is ridiculously slow and limited compared to today’s consoles. If you have any feedback about this series of posts please let me know so I can come up with a plan for if/when/what I’ll cover next. You can reach me on twitter @allan_blomquist or comment below.

(Prev – This is part 7 of a 7 part series)