Behind the name

I saw this blog got a lot of attention in the last few days, so I though I’d at least post to say I’m still around, even if I haven’t done much recently. I even woke up the old twitter account, so you can follow me there if you like:

https://twitter.com/sf2platinum

Here’s the story behind the name: Back in 2011 the 20th anniversary of SF2 was coming up, and I wanted to get a release of my own SF2 implementation out in time, ‘platinum’ being the stone associated with 20th anniversaries.

Unfortunately, life took a few turns that saw me far too busy to come through with it, and it never panned out. Sorry.

Since then I’ve come back to the project from time to time, but never as dedicated as I was in 2011. I’d like to keep making progress whenever I can, but things are still pretty busy with other projects that pay the bills.

Behind the name

The AI Engine

By today’s standards, the Artificial Intelligence in Street Fighter 2 World Warrior isn’t very sophisticated. These days, when most people talk about AI they’re talking about machine learning. There’s not any of that in SF2. Anyone looking for some insight into how to write an AI engine for a game today will be disappointed.

Moves made by computer opponents are not made independently but are instead grouped into small scripts, written in a bytecode similar to machine language. A computer avatar has a repertoire of different scripts for each opponent they could face in the game*, and set of circumstances, such as a nearby fireball.

Instructions in the scripts can command the avatar to execute an attack (punch/kick/special/throw), walk or jump somewhere, and wait – either for a timer, or some condition such as the ability to throw another fireball.

Other instructions can directly manipulate variables in the AI state machine, test for certain conditions, and form primitive IF…END blocks. Here’s one of Ryu’s typical ‘easy’ attack routines: Throw three fireballs at you, and if you’re somehow silly enough to catch all three and get dizzy, run up to you and throw you.

ORG 0x99c88 sf2ua.bin
0x02,                   ; script header, type 2 
0x10, 0x50, 0x04, 0x00, ; throw a hi str fireball
0x00, 0x80,             ; wait until I have no fireball
0x10, 0x50, 0x04, 0x00, ; another hi str fireball
0x00, 0x80,             ; wait again
0x10, 0x50, 0x04, 0x00, ; another hi str fireball
0x92,                   ; are they dizzy?
0x04, 0x00, 0x18,       ;    walk until we're within 24 pixels  
0x00, 0x82,             ;    wait if they're still getting up
0x10, 0x84, 0x00, 0x00, ;    throw(4)
0x94,                   ; end if
0x00, 0x00, 
0x00, 0x00,             ; wait four frames
0x00, 0x00, 
0x00, 0x00, 
0x86,                   ; chain to another randomly chosen script

Apart from the header byte, the first byte of each row is the instruction byte. Instructions are grouped into avatar commands (0x0-0x7f) and control flow / variable access (0x80 – 0xff). Each of them mostly have a fixed number of parameters, for example the Attack instruction (0x10) always take three:

  1. The attack type (special moves are 0x50, 0x52, 0x54…, throws are 0x80, 0x82, 0x84…).
  2. The strength of the attack (in this case it’s a strong / fast fireball)
  3. A repetition count for attacks involving holds and multiple hits. (unused here)

 

The Wait (0x00) instruction usually takes one parameter, decoded as:

  • 0x0 – 0x7f: Wait for N frames
  • 0x80: Wait until I am able to throw a fireball
  • 0x81: Wait until opponent is within M pixels (additional second parameter)
  • 0x82: Wait until my opponent is attackable
  • 0xc0: Wait until opponent’s jump reaches height M (second param)

All of the instructions and many of the parameters are even multiples of two (there is no 0x01 instruction, for instance) so that they can be used directly against 16-bit jump tables. Low/mid/high strength translate to 0, 2 and 4, as are most internals in the game. Any odd numbers would cause a CPU bus error exception, which would result in the SF2 ROM restarting.

The AI engine has three main modes of operation:

  1. Waiting for an attack. Simple scripts are chosen at random which consist mainly of walking backwards/forwards small amounts.
  2. Actively attacking. Scripts such as the one above are selected.
  3. Reacting to an attack. Scripts suitable for countering the attack are selected. Sometimes. Depending on the AI difficulty setting the computer lets plenty of attacks through unguarded, of course.

For the first two modes, there are 8 levels of scripts, which are chosen based on how much time is left in the round. When reacting to an attack the scripts are chosen based on something called a yoke.

Each frame of animation for both avatars and projectiles contains a value for the yoke in the metadata, which the AI peeks at to select a script suitable for responding to that attack. The computer sees the yoke of your move as soon as you have input it, before the first animation frame has even displayed. As such it gets one more frame of advantage on top of your reaction time.

A question addressed in an earlier post in this blog was whether the AI “cheats”, and it certainly does. Charge moves such as blade kicks are simply executed as instructions, so they cannot fail. Guile can do a bladekick from a standing position simply because that’s what’s in the script. It’s probably possible for the AI to command special moves in the air. One instruction is available to disable collisions against the computer player for a certain number of frames. Using it, you could write a script to simply walk through an approaching fireball.

One of the (more hidden) test screens in the game performs a sanity check on the AI bytecode. It’s not immediately obvious what it’s for as it just displays “OK” and nothing else, but the disassembly reveals the developers were perhaps testing and developing the AI code on CPS machines. The error messages in the test code reveal names for some of the instructions as MOSI, KON, KYON, TIGA, TAN, GTAN and END IF, but apart from the obvious latter name I haven’t figured what they might mean.

Viewers at home can find Ryu’s AI bytecode starting at ROM address 0x9966e on sf2ua. Set a breakpoint at 0x2ad2a to stop at the main entry to the AI code. Avatar AI state variables start at 0x200 from the player struct (0x5c6 and 0x8c6 for P1/2 respectively on sf2ua).

[* WW contains no scripts for battling the four bosses since that shouldn’t happen, and in any case the formulae for each of the opponents are all the same anyway! Maybe the developers ran out of ROM space or time, but the WW computer players use the same formula no matter who they’re fighting]

The AI Engine

Not just code, but data too

Originally the project included a lot of data structures dumped directly from the ROMs, such as sprite animation, palettes, hitboxes, AI bytecode and more. The only data not ported were the actual tiles; the game depended on four tile ROMs from the original game to be present.

Since all this data from the code ROMs is a considerable part of the original code, I decided to pull it all out and require the entire ROM set to be present, basically as much as you’d need to run the game in Mame.

This has its own difficulties, for a start we need to do endian-swapping each time we read anything larger than a byte. I wondered how much this would impact performance, but it turns out not very much. Some CPUs even have special instructions just to do this.

It also has some benefits. Getting the data out of the ROMs and into C-style structs and byte arrays was error prone, and the utility I wrote to do this sometimes messed up and produced incomplete / corrupt data. Many arrays are jagged. Sometimes sentinel elements are used. Sometimes I had to guess lengths of arrays and got it wrong. Going to the ROMs for all this ensures nothing is missing.

I wrote a compatibility layer to take care of locating these structures and doing the necessary byte-swapping.

As an example, here’s how an 2D jagged array of words would be stored.

00001ff0 lea 0x2000(%pc), %a6    ;get address of row table
00001ff4 move.w (%pc, %d0), %d0  ;get offset of row pointed by %d0
00001ff8 lea (%d0, %a6), %a6     ;add offset to base address
00001ffc jmp some_routine_that_uses_this_data

00002000 dc.w 0x0008   ;first row starts at 0x2000 + 0x8 = 0x2008
00002002 dc.w 0x0018   ;next row starts at 0x2000 + 0x18 = 0x2018
00002004 dc.w 0x001a   ;and so on
00002006 dc.w 0x0020

00002008 dc.w 0x1234   ;first element of first row
0000200a dc.w 0x5678   ;second element of first row
....
00002016 dc.w 0x8888   ;last element of first row
00002018 dc.w 0x1235   ;first (and only) element of second row
....
0000201a dc.w 0x1236   ;first element of third row

I guess they did it this way to save a little space at the cost of a couple of extra instructions, as opposed to just using 32-bit pointers, although there was plenty of free space in the ROMs.

Switch-style statements are very similar (and very frequently used throughout the code). Case variables are often kept to even numbers to avoid having to do pointer arithmetic. An example from the state-machine:

000077dc  302d 000c   move.w (game_mode_3, %a5), %d0
000077e0  323b 0006   move.w (#6, %pc, %d0.w), %d1
000077e4  4efb 1002   jmp    (#2, %pc, %d1.w)
;the jump-offset table follows
000077e8  000a        dc.w 0x000a ;jump to 0x77f2
000077ea  0016        dc.w 0x0016 ;jump to 0x77fe
;... several more ...
; here is case 0:
000077f2  546d 000c   addq.w #2, (game_mode_3, %a5) ;next time do the next case
000077f6  4eb8 2794   jsr 0x2794   ; reset display state
000077fa  4ef8 2c8a   jmp 0x2c8a   ; initialize both players (tail call)

000077fe  546d 000c   addq.w #2, (game_mode_3, %a5) ;again, next time to the next case
00007802  4eb8 1698   jsr 0x1698   ; set up palettes
00007806  4ef8 1ae2   jmp 0x1ae2   ; set up scrolls (tail call again)

This is more or less equivalent to

switch (g_game_mode_3) {
    case 0:
        g_game_mode_3 += 2;
        reset_display_state();
        init_players();
        break;
    case 2:
        g_game_mode_3 += 2;
        set_up_palettes();
        set_up_scrolls();
        break;
    /* more cases */
}

If the case is odd, the machine will crash with a bus error exception. This is why 2 is added to g_game_mode_3. If the case is greater than the number of elements in the jump-offset table, the behaviour is undefined. I’ve put default clauses in all my switch statements to land in the debugger to let me know something’s up.

Not just code, but data too

Random number generator

The random number generator is pretty simple. A 16-bit seed is stored which for convenience in code is split into two 8-bit values. The routine is at 0xdd4 in the sf2ua ROM. Here’s the equivalent C code:

short sf2rand(void) {
    int x = (g.randSeed1 << 8) + g.randSeed2;
    x *= 3;
    x = x >> 8;
    g.randSeed2 += x;
    g.randSeed1  = x;
    return g.randSeed2;
}

As far as PRNGs go it’s pretty poor, but good enough for our purpose here. The output of it is often bitmasked to limit its values (e.g. masked with 0xf to get a number from 0-15, masked with 0xe to get an even number from 0-14, and so on), and also used as a bit index with the BTST instruction to get a 1-in-N chance.

For example, to get a 1-in-4 chance:

if( 0x88888888 & (1 << (sf2rand() & 0x1f)))

The RNG is seeded with exactly the same value every time the machine starts (there’s nothing else to seed it with, no RTC, nothing), so it always produces the same string of random numbers.

If you start the machine, wait for the player invite screen to start, insert a coin and play with Ryu, you will face Dhalsim on your first fight. If you insert your coin while the copyright warning is still printing, you’ll face Blanka instead.

One of these days I should analyse it to see when the seed returns to its initial value, i.e. when the sequence starts repeating.

Random number generator

Guile’s World Warrior bugs

One of the first things I went looking for was to see what the cause of Guile’s Invisible Throw bug (and others). This is why I started with the earliest, buggiest version, SF2UA, date 910206.

A ‘move’ in Street Fighter is encoded using three variables, one to signal whether the move a standing / crouching / jumping attack, another for punch / kick, and an ID. Another variable tracks whether they are standing, walking, attacking, or executing a power move. These are used in finite state machines which are called each frame to process the animations.

The bugs result from still checking for power move input after an ordinary attack has been selected (because players are allowed to charge back while still executing other moves), and a nasty side effect of the button decoder setting the Punch/Kick variable directly without even know the player’s context.

First, we’ll look at the ‘Stance’ bug. You get it by being close enough to your opponent to do the upside-down kick (within 70 pixels), charging back, pressing roundhouse to begin the kick, and then doing a sonic boom before the kick completes. You have to press fierce after the roundhouse, and within the same window that a Sonic Boom would be allowed. Guile executes his upside-down kick, but instead of returning to a standing position, he gets stuck on the last frame of the upside down kick animation. He can be hit out of this, but the AI players don’t usually do this as they think he’s still doing some sort of kick that seems to last forever. Vega gets very confused and does his slide attack repeatedly.

The upside-down kick is Standing, Kicking move #6.

What happens is the standing kick gets selected, and the animation begins normally. The Sonic and Blade state machines keep running throughout attacks; this is necessary to allow players to charge back/down while still executing a move. At this stage, because we’ve charged back for long enough, and are now pressing forward, the Sonic Boom state machine is now checking for a button press, and when it detects one it calls the button decoder.

The button decoder (you’ll find it at address 0x3296 in the SF2UA ROMs) is basically a chain of ‘if’ statements that test a bit for each button, and set the corresponding Punch/Kick and Strength, bailing out at the first match.  The last condition, a strong kick, isn’t even tested for, it’s returned by default is no other buttons are detected. It only makes sense to call the subroutine if it’s already known a button is down.

Punches are tested before kicks, and when we press our punch button the player Punch/Kick variable gets set to ‘Punch’, so our player’s state is now Standing, Punching move #6 which actually represents one of Guile’s throws. The animation doesn’t change, but the state machine for the throw runs instead. This is at 0x2f922.

Where the state machine for the kick simply waits for the animation to finish and then sets the player’s state and sprite to a normal standing pose, the state machine for the throw is different. It looks for a special flag in the animation that signals that the character being thrown should now be released, but this never comes so Guile gets stuck in this state.

All of Guile’s bugs centre around this setting of one of his kicks, which then get turned into punches with the same ID by this bug in the button decoder, and were fixed in the next release (sf2ub, sf2eb, and sf2jb).

Guile’s World Warrior bugs

SF2 AI – does it cheat?

I’ve seen a few questions floating around about whether the AI can cheat – specifically whether it needs to charge Bladekicks or Sonic Booms like a human player does.

No, it doesn’t.

The built-in AI programs are simple lists of moves that aren’t subject to the normal human rules of needing to charge back a certain amount of time before performing a move like a Sonic Boom, and the computer controlled opponent can execute them without these requirements.

For some moves, such as E.Honda’s Hundred-Hand-Slap, Chun-Li’s Thousand-Foot-Kick, etc. the AI scripts include a couple of moves to make it look like they are subject to the same rules as human input (and also a clue to new players how to execute the moves), but the AI machine is capable of launching into any power move as easily and instantly as any ordinary attack.

SF2 AI – does it cheat?