September 22, 2012

An analog hack of the Xbox 360 controller - Part 2: Applications

The controller hack and DAC configuration are discussed in Part 1 of the blog. Now let's look at how it can be applied to achieve some impressive results in The Impossible Game, Super Meat Boy, Guitar Hero 3 and Halo.



How I Learned to Stop Raging and Win The Impossible Game

The Impossible Game is a 2D platformer that is one of the more popular Xbox Live Indie games (XBLIG). Simply described, you're an orange square moving through the level at a constant horizontal speed and you must jump your way to the finish while avoiding the spikes and pits. Each level (there are 3 in total if you buy the level pack) is about a minute and a half in length. Sounds easy, but you're in for a sizeable helping of rage if you plan on finishing. Numerous sets of triple-spikes are scattered throughout the levels, and there is only a couple video frames worth of forgiveness when jumping over these things.

So how can we output the jump button presses with the correct timings to get all the way through a level? No simple solution comes to mind. One approach is to build up the voltage sequence gradually through trial and error, each time adding one or two more jumps to get a bit further through the level. Tedious, yes, but we make relatively steady progress this way; once we've reached a certain point in the level, that part is "solved" in the sense that we'll be able to reach it every time using the same sequence. 

Following the procedure outlined above, it wasn't long before another problem cropped up. How can we ensure that our automated sequence of jumps is started at just the right time? It's very easy to be off by a few frames by manually starting the DAC sequence (clicking a button in the software) while eyeballing the Xbox screen. My initial plan for tackling this synchronization problem was to include the Xbox menu button press to start the level as the first part of the sequence. However, this didn't solve the problem completely, the reason being that the time it takes the Xbox to load the level and actually start the gameplay varied by as much as 6 or 7 frames. A more flexible approach is to allow small adjustments to the DAC sequence timing (say, a rewind or advance of 1 sample) after it has been started. This also serves as a remedy for any drift that accumulates between the DAC and xbox clocks over the long term. What we end up with is a simple set of controls for starting, advancing or rewinding the sequence in real time.  It's also helpful to have stop and reset buttons for when things go wrong and the level needs to be restarted.


This basic set of controls served quite well for most games, so let's have a quick look at the C# code used to implement it. Two software threads are required - one to handle the GUI button clicks and a second to communicate with the DAC. In NI-DAQmx the basic steps for operating the DAC are putting our voltage sequence into an array, creating a task for digital to analog conversion, configuring the task parameters (selected channels, sample rate, buffer size, etc.), writing the data to the DAC buffer (an onboard FIFO), and finally starting the task. The key point is to transfer the voltage sequence to the DAC in small chunks rather than all at once, thereby allowing the small timing adjustments (achieved by skipping or repeating one sample) or the task to be stopped early as the sequence progresses. Signalling between the two threads is primitive enough to be handled with a few booleans, and we don't even need mutexes to protect these variables (see this article). Finally, note the use of the helper class AOdataseq, which supports creation of the voltage array based on the channel mappings and voltage levels we've already calculated.


In the main thread:
// click event for Play button
private void button_ImpossibleGamePlay_Click(object sender, EventArgs e)
{
 /* some code for determining which sequence to play and creating the AOdataseq object D */
       
 // Launch the writer thread
 IGw = new IGWriter(D, VoltLev);
 IGthread = new Thread(new ThreadStart(IGw.Write));
 IGthread.IsBackground = true;
 IGthread.Start();
}
    
// click event for Stop button
private void button_ImpossibleGameStop_Click(object sender, EventArgs e)
{
 IGw.RequestStop();
}

// click event for Rewind button
private void button_ImpossibleGameRewind_Click(object sender, EventArgs e)
{
 IGw.RequestRewind();
}

// click event for Advance button
private void button_ImpossibleGameAdvance_Click(object sender, EventArgs e)
{
 IGw.RequestAdvance();
}


The worker thread:
// ---------------------------------- Impossible Game Writer class ------------------------------------
public class IGWriter
{
 private AOdataseq Dseq;
 private VoltageLevels vlev;
 private volatile bool stop = false;
 private volatile bool rewind = false;
 private volatile bool advance = false;

 //- Constructor
 public IGWriter(AOdataseq D, VoltageLevels vl)
 {
  Dseq = D;
  vlev = vl;
 }

 //- Writes the data to the DAC while checking for commands (called when worker thread is started)
 public void Write()
 {
  Task myTask = new Task("IGWriterSequence");  // create the task

  try
  {
   // create the analog output channel
   myTask.AOChannels.CreateVoltageChannel(Dseq.ChanList, "", vlev.Vmin, vlev.Vmax, AOVoltageUnits.Volts);

   // configure timing and stream properties
   myTask.Timing.ConfigureSampleClock("", Dseq.Fsamp, SampleClockActiveEdge.Rising, SampleQuantityMode.ContinuousSamples);
   long BufSize = 1000;
   myTask.Stream.ConfigureOutputBuffer(BufSize);
   myTask.Stream.WriteRelativeTo = WriteRelativeTo.CurrentWritePosition;
   myTask.Stream.WriteRegenerationMode = WriteRegenerationMode.DoNotAllowRegeneration;

   // create the channel writer object
   AnalogMultiChannelWriter writer = new AnalogMultiChannelWriter(myTask.Stream);

   // create some variables to facilitate writing data in chunks
   int xsamp = 0;     // sample index (into the voltage array Dseq.dao)
   long Nsampwritten = 0;    // total number of samples written to the DAC buffer
   int Nchunkwritten = 0;    // total number of chunks written
   int Nsampchunk = 60; //120;   // default chunk size (samples)
   int Nd;      // size of current chunk
   double[,] d;     // holds the current chunk

   while (xsamp < Dseq.Nsamp)  // loop until the entire sequence is written
   {
    // check for stop
    if (stop)
    {
     myTask.Stop();
     myTask.Dispose();
     stop = false;
     return;
    }
     
    // check for advance
    if (advance)
    {
     xsamp += 1;    // increment sample index
     advance = false;
     if(xsamp >= Dseq.Nsamp)
      break;
    }
     
    // check for rewind
    if (rewind)
    {
     xsamp -= 1;    // decrement sample index
     rewind = false;
     if(xsamp < 0)
      xsamp = 0;
    }
     
    // determine current chunk size
    Nd = Nsampchunk;
    if (Dseq.Nsamp - xsamp <= Nsampchunk)   // last chunk is smaller than normal
    {
     Nd = Dseq.Nsamp - xsamp;
     // ugggggh, this should avoid the buffer underflow exception but it apparently isn't supported by the device
     //myTask.Stream.NextWriteIsLast = true;
    }
               
    // copy the current data chunk into a temp buffer
    d = new double[Dseq.NumChan, Nd];
    for (int xchan = 0; xchan < Dseq.NumChan; xchan++)
    {
     for (int m = 0; m < Nd; m++)
      d[xchan, m] = Dseq.dao[xchan, xsamp + m];
    }

    // write the current data chunk to the DAC buffer
    if (Nchunkwritten == 0)   // first chunk (write immediately and start the task)
    {
     writer.WriteMultiSample(false, d);
     myTask.Start();
    }
    else   // all other chunks (wait until DAC buffer is partially empty before writing)
    {
     while (Nsampwritten - myTask.Stream.TotalSamplesGeneratedPerChannel > (long)(Nsampchunk / 2))
     {
      Thread.Sleep(0);  // sleep if we're not yet ready to write this chunk
     }
     writer.WriteMultiSample(false, d);
    }
     
    xsamp += Nd;   // increment sample index
    Nsampwritten += Nd;  // increment samples written count
    Nchunkwritten++;  // increment chunk count
   }

   // wait until task is done
   myTask.WaitUntilDone();
   myTask.Dispose();
   return;
  }
  catch (DaqException ex)   // handle any exceptions
  {
   if(ex.Error != -200290)   // silently ignore the buffer underflow exception
   {
    //throw new DaqException("IGWriter", ex);  // pass the exception to the calling function
    MessageBox.Show(ex.Message);   // display the exception message
   }
   myTask.Dispose();
   return;
  }
 }
  
 //- Request stop
 public void RequestStop()
 {
  stop = true;
 }

 //- Request advance
 public void RequestAdvance()
 {
  advance = true;
 }

 //- Request rewind
 public void RequestRewind()
 {
  rewind = true;
 }
}

Enough rambling, here are the results in video form.




Super Meat Boy

Super Meat Boy is a popular Xbox Live Arcade (XBLA) platformer that's well worth the $10 price tag. This game features many short levels divided up into chapters, the singular goal being to save Bandage Girl from the villainous Dr. Fetus (a la Mario Brothers). Failure to do so implies death by gravity, incineration, blunt instrument trauma, impalement, frickin' laser beams, rotary saw, ... and you get the idea. The control scheme allows for running, jumping, latching onto walls, sliding on walls, and accelerated movement via a speed button.

One of the basic principles in moving Meat Boy around the levels quickly is to maintain momentum wherever possible and rely heavily on wall jumping for direction changes. Often times this involves taking a slightly different path than the crow would fly. After playing the game for many hours and getting a look at just how ridiculously good some players are (check out the youtube links at the bottom of this post), I'd say the level of skill required to master Meat Boy physics is surprisingly high.

Following the same strategy of building up the 'solution' to a level one step at a time, which is quite feasible for Meat Boy due to the shorter levels, I focused on:
  • 2-8 The Sabbath
  • 6-3 Echoes
  • 6-5 Omega
  • 7-13x Bleach
  • Warp Zone 5-7 (The Kid)
The first 4 levels above were picked because they're good for speed running. The warp zone is just an annoying set of levels that demands some precision to avoid dying a hundred times.





Guitar Hero 3

Does this franchise need any introduction? To be honest, I almost dismissed the entire Guitar Hero (GH) series at the outset due to the sheer number of controller actions required to finish a song - we're talking a few thousand button presses for the more challenging songs played on Expert difficulty. The task of manually figuring out all these note timings seemed insurmountable. However, the simplicity of GH's graphical presentation offers a tantalizing possibility - what if the analysis could be automated using optical recognition? As it turns out, the game supports a 'no fail' cheat that allows you to play all the way through a song without hitting a single button. This means we can capture a video of the entire song and analyze it frame by frame in software to determine the note timings.

For this idea to work, a video capture card that's capable of a solid 60 fps is extremely helpful. The comparatively low time resolution of a 30 fps capture might be worked around by jumping through some hoops in the optical processing algorithm, but barring that we end up with many instances of closely spaced notes being resolved as a single longer note. I use the Hauppauge HD-PVR which is capable of a stable 720p60 through component inputs. This card features a hardware h.264 encoder which does a pretty good job with the quality vs compression tradeoff.

Problem solved, right? Not quite. I had decided to use the Matlab video processing tools for optical recognition because the ffmpeg library was looking like too much effort. Unfortunately, my version of Matlab did not have proper support for the MP4 format output by the HD-PVR, and many of the video converters out there are downright useless for format shifting h.264 MP4s at 60 fps. Despite its dubious name (AVS 4 ME? TY! <3), the AVS Video Converter supports conversion from h.264 to WMV or Microsoft MPEG4 AVI (both of which could be read by Matlab) at the source frame rate and with a good amount of options for controlling quality. Still, there were a lot of headaches due to dropped frames whenever Guitar Hero's light show was especially seizure inducing, but these were eventually resolved by using variable bit rate encoding and raising the bit rate of the output file.

The optical recognition requirements are not very demanding - we need only identify the presence or absence of colored notes moving down the fret board, a far cry from OCR of text or handwriting. For each video frame, presence or absence of a note can be determined by comparing the average color inside a small, statically located rectangle to a threshold based on the known note color. See the illustration below.


Going from left to right, define c1, c2, c3, c4, c5 as the average color inside the rectangles on an RGB scale of 0 to 255. Detection was based on:

Note color Criteria (note is present)
Green c1.green > 120
Red c2.red > 120
Yellow (c3.red > 120) && (c3.green > 120)
Blue (c4.green > 70) && (c4.blue > 120)
Orange (c5.red > 120) && (c5.green > 70)

These criteria were set according to the body color of the notes, but they also give a positive result for the white base and top of the note. The dark background of the fret board gives a negative result. For example, in the frame shown above, only a red note would be identified. The raw detection results over the entire song are then translated into a sequence of button presses (start time and duration of each press) and stored in a text file, which is subsequently loaded and converted to a voltage sequence by the DAC software.

That's the basis of a simple optical recognition algorithm that performs reasonably well on most songs. However, to achieve a really good score there are some other issues that must be addressed:
  • Insufficient resolution - Even with 60 fps video captures, closely spaced notes of the same color are occasionally resolved as a single note.
  • Duration too long - With the simple detection rule described above, regular notes usually work out to a button press duration of 4 frames. When this is long enough to overlap with the start of the next note of a different color, it will be interpreted as a mistake by Guitar Hero.
  • Timing offset - Multiple simultaneous notes comprising a chord will sometimes be detected with a 1 frame offset. This tends to happen in frames where the (statically located) rectangles land just on the edges of the notes.
  • Sustained notes - In 'no fail' mode the colored tracer on a sustained note disappears after about 10 frames. This leaves us without any knowledge of how long the sustained note actually is.
  • Star power phrases - These are sequences of star-shaped notes that increase the player's reserve of star power when executed correctly. Whammying sustained notes gains even more star power, but without a way to automatically identify these parts of the song, we don't know when to whammy.
  • Star power activation - Star power gives a big score multiplier on every note hit over its duration, so activating it at just the right points in the song is critical. There's also a technique known as 'squeezing' that abuses the timing window to get a extra few notes into an activation.
Most of the resolution, timing, and duration errors could be flagged automatically during optical recognition and manually corrected in the text file. The sustained note durations and whammies were added after reviewing the relevant sections of the captured video. As for the star power activations, fortunately a rather dedicated group of GH3 players has already systematically worked out the optimal activation points (star power paths) for most songs. So, all things considered, it still took me several hours of work on each song to get a nearly optimal result after the first cut of optical recognition.

Finally it's time for the results. The three songs shown here - One, Raining Blood and Through the Fire and Flames - played on Expert difficulty are widely considered to be the most challenging in the game.






Halo

It would have been an unforgivable oversight to finish without visiting the Halo series. More specifically our old friend Halo 2, a game that was rife with button glitches. If you listen hard enough you can still hear the echo of high-pitched screams of "cheater!" reverberating over the XBL mic. There has been many a heated debate on the topic of Halo 2 glitches over the years, and it's enough to say that the spectrum of opinions ranges from 'game-breaking' all the way up to 'game-saving' blunder by Bungie.

So, I put together a few short clips that focus mainly on Halo 2. There's also a Halo Reach golf hole that illustrates the sort of aiming and timing precision that can be achieved with the controller hack. A few random bits of MLG Halo history are sprinkled in for good measure. It's a video that will be hard to appreciate unless you're a Halo player, and even then the highest compliment you might find is 'nerdy'.




Wrap-Up

Thanks for reading. I pursued this project because I find it interesting from a technical standpoint, not to promote cheating in video games. Quite a lot of effort was needed to refine the Super Meat Boy and GH3 results to the point of being first rate, which I felt was necessary to show the capability of the controller 'hack'. All games were played offline so as not to pollute the leaderboards with tool assisted scores.

Thanks to:
  • CodeCogs for the online LaTeX equation editor.
  • YCOURIEL for the C# to HTML formatting utility.
  • xIMunchyIx for his Impossible Game video, which I shamelessly frame counted in parts of levels 2 and 3 to lessen the workload.
  • telesniperXBL, Takujixz, and ExoSDA for their Super Meat Boy speed runs.
  • ScoreHero, in particular debr and Barbaloot, for the optimal star power paths and note charts.



An analog hack of the Xbox 360 controller - Part 1: The Hack

What sort of 'hack' is possible on a video game controller that lacks a general purpose processor?

The first idea that came to mind was to mimic the USB communications between the controller and the Xbox. If we could record the signals transmitted and received using a scope or a more specialized USB signal analyzer, we could spoof the controller by manufacturing our own packets. Sounds feasible as long as the packet structure is simple and consistent, i.e., no encryption or scrambling, and we're able to convince the console that it's talking to a controller. I'm no expert on USB, so I discarded this idea as too much effort and prone to failure.

A simpler approach is to use a digital to analog converter (DAC), wired directly into the controller circuit, to simulate the button presses and stick movements. This might be thought of as an exploit of the 'analog hole' of an input device, the dual of its more well-known form in output devices such as speakers and displays. Of course, we need to know the points in the circuit to connect to and the required voltage levels. Armed with a multimeter, I was able to figure out the essentials of the controller circuit, as shown below.



The controller buttons should be familiar: A, B, X, Y, Back, Start, LB and RB (left and right bumpers). Note that the Guide button, stick clicks and D-pad buttons aren't shown because none of them were used. The left (LS) and right (RS) analog sticks are each comprised of separate horizontal (h) and vertical (v) potentiometers to allow for two axis movement. The left (LT) and right (RT) triggers are also pots, though they're effectively treated as buttons in most games (more on this later). All input signals are routed to an ASIC which presumably handles most of the the controller processing chores - debouncing, A/D conversion for the pots, forming the data packets, USB communications, etc. As shown in the diagram, all inputs except the bumpers are conveniently accessible via test points that can be easily soldered to. It's also worth mentioning that the controller board used for this project is a wired model marked as year 2007. Earlier or later models may differ depending on any revisions to the controller circuit, although I did inspect a 2010 model which appeared to be identical.

A quick word about the DAC. Our basic requirements are a high number of channels with hardware-synchronized simultaneous output on all channels. Sample rate is a non-factor as pretty much any DAC will support at least 60 samples per second, which is, as far as I know, the highest rate at which any Xbox game processes input. We do however need DC coupled outputs, and this requirement ruined my initial plan of repurposing a cheap sound card DAC. Rather than going for a fully home brew solution, I eventually settled on the National Instruments PCI-6713 which I was able to find used for a reasonable price. This is a PCI card with 12-bit resolution, 8 output channels, a voltage range of ±10 V, current drive capability of ±5 mA per channel, and an easy to use software API.

Buttons

Buttons are the easiest type of input to handle. They are active high on the Xbox controller and can be asserted by applying a voltage of 1.0 V or higher. The addition of a series resistor RS is just a safety precaution to avoid directly driving the ASIC when the controller is turned off and also to avoid driving Vcc if we accidentally press one of the buttons while the DAC is connected. Choosing RS = 2.0 kΩ results in a voltage drop of about 6% of the DAC output voltage VA (suggesting an input impedance of around 30 kΩ for the buttons), so we should not increase RS too far beyond this value.


Sticks and Triggers

The most straightforward approach for dealing with the analog sticks and triggers is to desolder the potentiometers and apply the DAC voltage directly. However, I've found it useful at times to be able to manually operate the sticks and triggers in the usual way without relying on the DAC, so I decided to leave them on the controller. In this configuration we can use a series resistor R2 and an appropriate VA to control the wiper voltage VX. The total pot resistance of 10 kΩ is divided into its two parts, R1a and R1b, which represent the resistance between the corresponding end terminal and the wiper.


From the diagram:


Sticks
  
With the stick in its resting position and without connecting the DAC, I measure a typical voltage of VX = 0.80 V = Vcc / 2. This suggests that the pot has the same range of rotation in either direction, R1a = R1b = 5.0 kΩ. Solving for VX,


Pushing the stick all the way left / up results in VX = 1.60 V = Vcc on the horizontal / vertical pot whereas pushing it all the way right / down results in VX = 0 V. This tells us the range of voltages that we must be able to produce for VX, thereby guiding our choice of R2 and VA. From the equation we can see that a large R2 will lend too small an influence to the DAC output, so let's try R2 = 1.0 kΩ:


The required values of VA are well within the range of the DAC and the current draw is only I2 = ±0.32 mA.

In practice, the voltages required to simulate a full stick deflection are smaller than those listed above. This is because the holes cut in the controller shell limit the stick's range of movement to about 60% of its actual mechanical range, and obviously the system is designed with this factor in mind. Full stick deflection can be achieved with VX = 1.30 V for left / up and VX = 0.30 V for right / down, which, if we keep R2 at 1.0 kΩ, corresponds to VA = 1.50 V and VA = 0.10 V respectively. There is also a 'dead zone' of about ±0.1 V centered around the stick's resting position which must be exceeded to generate any action. The purpose of the dead zone is to mitigate small voltage offsets due to mechanical imperfections in the potentiometers. An illustration of the critical VX values and their relationship to physical movement of the stick is provided below.



Triggers

With the trigger in its resting position and without connecting the DAC, I measure a typical voltage of VX = 1.40 V = 0.875 Vcc. This means that R1a = 1.25 kΩ and R1b = 8.75 kΩ when the trigger is inactive.


Pressing the trigger results in VX = 0.35 V. Thus, the triggers are active low, and it turns out that VX = 1.30 V or lower is sufficient for a trigger press. This can be realized with the following choices of R2 and VA:


Again these voltages are well within the DAC specs, as is the max current draw of I2 = -1.14 / 4.7 k = -0.24 mA. There are a couple subtle reasons for not attempting to pull VX any lower - it's unclear how much extra current (I1) can be sourced from the power supply, and we'd also like to avoid burning out the pot.

Hardware Setup

Nothing fancy - just the controller, DAC breakout board, and a breadboard for the resistors and signal connections. Following an unfortunate incident that involved me snagging my foot on the controller cord, duct tape was gratuitously added.



Software

Before we can do anything interesting we need some basic software for controlling the DAC. The Windows version of the DAC driver (known as NI-DAQmx) has support for .NET, so I decided to work in C#.  I wrote a GUI based program to accommodate the basic controller functions as well as some more advanced features. The main sections of the program can be seen in the screenshot below:
  • Voltage Levels - The DAC output voltages we've already calculated for operating the buttons, sticks, and triggers. Obviously, the sticks can accept a continuous range of voltages, but we can specify the minimum and maximum of that range as well as a default voltage that represents no movement.
  • Channel Map - Sets the mapping of DAC output channels to the various controller inputs. These will change depending on what game we're playing.
  • Controls - Replicates the basic functionality of the Xbox controller and provides access to a list of predefined control sequences (macros). These control sequences can be very short, such as a glitch requiring a couple well-timed button presses, or much longer and more complex sequences involving many controller actions.




Individual button and trigger presses can be implemented by outputting the active voltage for a few frames followed by one sample of the inactive voltage. This is because we're actually simulating pressing and releasing the button, and the DAC latches and holds the final sample in the sequence. Panel controls adorned with arrow images were used as a rudimentary means of simulating the analog sticks. A left mouse click on a panel is translated into a brief stick press (such as when navigating a menu) whereas a right mouse click starts a continuous sequence of voltages, applied to the horizontal and vertical pots, corresponding to the mouse position within the panel (such as when rotating or moving in a game). In all cases the DAC sample rate is set to match the typical Xbox frame rate of 59.94 fps. While this is not absolutely essential, nothing is gained by using a higher sample rate and doing so actually makes things more awkward when dealing with complex sequences.

At this point you might be wondering if our modified controller could be used to play Xbox games with a keyboard and mouse like in PC games. It's possible, but the extra lag introduced between the mouse actions / key presses and the DAC output would be intolerable for the discriminating gamer. What we're left with is basically a dumb record player whose main ability is synthesizing prearranged controller sequences with precise timing and good repeatability. Fortunately there are a variety of games, primarily from the platformer and rhythm genres, in which these two attributes are enough to become an excellent player.

That's all for the first part of this blog. It's long enough that I decided to break it up into two parts. If you haven't fallen asleep yet, give Part 2 a read to see what we can actually do with this contraption.