Building a cheat-bot

As a fun hacking project over Christmas I wrote a program to play Kuru Kuru Kururin for me. (Coincidentally, Nintendo re-released the game on the WiiU Virtual Console on Christmas Day.) A few people thought it was interesting so here’s how I did it including all the gory details of poring over the inner workings of a game by studying its code and data.

As for why? I find this kind of thing very enjoyable. The process of figuring out how a game works is a bit like solving a crossword or a sudoku puzzle. As you uncover more and more clues it becomes easier and easier. Sometimes you uncover interesting tricks the programmers used or you uncover bugs and glitches that you can exploit.

The game

Check out the game first if you’ve not seen it already. Here’s a video:

And here’s a couple of videos of what my hacking resulted in:

Hugging that wall, yeah.

What the!?!

Cheating is easy

With emulation, it’s really easy to cheat at games. You can slow the game down, even play it one frame at a time, and easily rewind if you make a mistake. Most emulators these days even come with tools to help you find out where the game stores things like the number of lives, or your health, and you can modify these values or stop them from changing altogether. I didn’t really want to modify the game though, I just wanted to find the fastest routes through the levels.

There’s a whole community of people who use emulators to try to craft the perfect run through games. A tool assisted speedrun, or TAS, is about finding the shortest series of button presses that get you through the game by whatever means. Usually this involves using bugs or glitches in the game like jumping backwards at high speed or escaping outside of the level. However, the TASers take it to the next level feeding inputs into the game with frame precise timing that no human could possibly manage.

TASers have done some amazing stuff lately, going a bit off-piste with their glitch finding to the point where they can take complete control of a game to make it run their own software — purely through button presses!

Anyway, I’m too lazy to spend hours and hours replaying the same levels over and over manually using frame advancing and save states so instead I decided to spend hours writing a program to find the perfect routes through the levels for me.

The plan of attack

The A* path finding algorithm is very well known and very straightforward to implement so that was what I planned to use to solve the levels. Each pixel within the maze would be a node for the A* algorithm to search. However, in Kururin it’s complicated a bit by the fact that the possible paths depend on the orientation of the Helirin (the stick).

To cope with this, instead of making a node for each reachable pixel within the maze, I made a node for each possible orientation at each pixel. I didn’t care about how long it takes to solve a maze or how much memory my program used (within reason), so sticking to the “keep it simple, stupid” principle, this is what I planned to start with.

So what did I need to get started with this cunning plan?

• The map data
• Rules on how the Helirin moves through the level
• How the game decides if a given position is safe or not
• Some way to play back my solutions into the game for testing

In this post I’ll focus on getting at the map data.

Finding the map data

As I mentioned, most emulators have a ‘cheat finder’ these days. There’s a great video on the Double Fine YouTube channel showing how an emulator can be used to modify a classic game using this technique.

Like all good cheaters, my first step was to find where the number of lives is stored in the game. I used the RAM search to find a list of memory locations containing the number 3, which is the number of hearts you start with:

Then I deliberately lost a life and searched just the locations that used to have a 3 in for ones that now contained 2.

And bingo, one address is left, 4582. (Actually 3004582 because IWRAM starts at 3000000.)

So why is that useful for extracting the map data? Well, losing a life is caused by the game deciding you hit a wall, and to know that it must have checked the map data! So next I used another tool in the emulator to halt the game whenever the life counter changes.

Knowing that the lives variable is located at 3004582. I used no$gba to set a memory breakpoint on this address (Ctrl+B, [3004582]!). Now when I lost a life the game halted on the line of code responsible. This code is at 80152C2:

080152BA MOVS R1, R5    ; R5 = address of helirin object
080152BC ADDS R1, #0x52 ; R1 = R5 + 0x52 = helirin lives counter
080152BE LDRB R0, [R1]  ; load lives counter into R0
080152C0 SUBS R0, #1    ; subtract 1
080152C2 STRB R0, [R1]  ; store new lives counter

This gave me my first look at the game code. Now all I had to do was read backwards through the code to see what caused the game to think I’d hit a wall. This would also help me with the third piece of information I needed for my solution which is how the game determines this.

The main things I was looking for were branches in the code, i.e. the decision points. However, it isn’t as simple as “helirin hits wall” and then “player loses life”. If the helirin is in the start zone or a health zone then it’s invulnerable. Also, after you hit a wall you are safe for a few frames. Other things happen too, like a time penalty is awarded, sparks appears and the helirin is knocked back. Some of the branches would likely be related to these events too.

Let’s take a look at some more disassembly. The code immediately before the health removal is this:

08015294 LDR R0, =0x3004420 ; some sort of global object
08015296 LDRB R0, [R0, #0x16] ; perhaps the current game mode?
08015298 LSLS R0, R0, #24 
0801529A ASRS R0, R0, #24 
0801529C CMP R0, #4 ; check for mode 4
0801529E BEQ 080152BA 
080152A0  MOVS R1, R5 ; R1 = helirin
080152A2  ADDS R1, #0xB8 ; R1 + 0xB8 = time value
080152A4  LDR R0, [R1]
080152A6  ADDS R0, #180 ; add 180 = 3 second time penalty
080152A8  STR R0, [R1]
080152AA  LDR R2, =215999 ; 216000 = 60 * 60 * 60 frames = 1 hour
080152AC  CMP R0, R2 ; has the timer exceeded 215999?
080152AE  BLS 080152B2
080152B0   STR R2, [R1] ; if it has set it back to 215999
080152B2  LDR R0, =0x80176F5 ; looks like more code here
080152B4  MOVS R1, #0x10
080152B6  BL 08004104 ; call out to a function

Two important ‘magic numbers’ appear in the above snippet that helped me figure out what it was doing: 180 and 215999. The game runs at 60 frames per second (many GBA games do) and when you hit a wall you receive a 3 second time penalty. 60 * 3 = 180, so this must be the code for applying the time penalty! The timer can only display 6 digits so 59:59.99 is the largest possible value, this definitely has to be the timer.

The time penalty is only applied when the value at memory address 3004436 is not 4 however, so maybe that value indicates what mode the game is running in (in some modes perhaps you don’t receive a time penalty). These little clues are how you figure out what each memory location is used for and what various snippets of code are doing.

Something I didn’t figure out immediately from looking at this code is what the call to 8004104 does. In hindsight, it’s not that difficult to deduce though. When you get a 3 second time penalty a sprite appears on the screen to show this. The call here creates that sprite. In fact, the 80176F5 refers to the code that deals with the +3s sprite and 8004104 is a routine used throughout the game for creating objects. Knowing this is pretty handy because it lets us immediately identify any other places where objects are being created which can be a great clue to what’s going on.

Moving up, the next piece of code has our first two interesting branches:

0801525E MOV R3, R10 ; R3 = R10 = ???
08015260 MOVS R0, #0
08015262 LDRSB R0, [R3,R0]
08015264 CMP R0, #0
08015266 BNE 0801531E
08015268  MOV R0, R8 ; R8 = ???
0801526A  LDR R1, [R0]
0801526C  LDR R0, =0x40008
0801526E  ANDS R0, R1
08015270  CMP R0, #0
08015272  BNE 0801531E
08015274   MOVS R0, 0x900
08015278   ORRS R1, R0
0801527A   MOV R2, R8
0801527C   STR R1, [R2]
0801527E   MOVS R0, #20 
08015280   STRB R0, [R3] ; 20 stored to R10

Two branches jump to 0801531E, which skips over the code that removes a heart. But first, what are R10 and R8? Checking further up I found:

080151E4 MOVS R2, #0x55
080151E6 ADDS R2, R2, R5
080151E8 MOV R10, R2 ; R10 = R5 + 0x55
080150FE MOVS R0, R5
08015100 ADDS R0, #0xBC
08015108 MOV R8, R0 ; R8 = R5 + 0xBC

So both of them are values inside the helirin object (which is located at R5). Following the code above, if the value at R10 is non-zero then a life is not lost. If it is zero then it is set to 20. It’s a fair guess that this is the invulnerability timer. The other code seems to be dealing with some sort of flags bitfield which I’ll ignore for now.

The next bit of disassembly:

08015246 MOV R2, R9
08015248 LDRH R0, [R2]
0801524A CMP R0, #0
0801524C BEQ 0801525E
0801524E LDR R0, [R5, #0x14] ; load X position
08015250 LDR R1, [R5, #0x24] ; load X movement amount
08015252 SUBS R0, R0, R1     ; reset X position
08015254 STR R0, [R5, #0x14] ; store X position
08015256 LDR R0, [R5, #0x18] ; load Y position
08015258 LDR R1, [R5, #0x28] ; load Y movement amount
0801525A SUBS R0, R0, R1     ; reset Y position
0801525C STR R0, [R5, #0x18] ; store Y position

This snippet contains a couple of very important clues. I’m still assuming this is code that runs when the stick has hit something because I haven’t come across a branch which suggests otherwise yet. As you can see from my comments I’m guessing this code is resetting the X and Y positions of the helirin. It’s in a pair (X & Y coordinates), and it makes sense that if the stick has moved into a wall then the game would probably want to move it back to a safe position (the position before it hit the wall). Therefore perhaps the values at 24 and 28 are the amount it was moved by.

So much for deduction and guesswork. We have an emulator at our disposal with super powerful tools like RAM watch and search. Whenever I made guesses about what values might be I was able to check them very easily in the emulator. I looked at what value was in R5 when the emulator halted when I lost a life which gave me the memory address of the helirin object: 3004530. Adding on 14 and 18 gives the addresses for what I suspected were the helirin X & Y coordinates. A RAM watch in the emulator confirmed this. Moving right or left caused the X value to change, up or down, the Y value. Hooray for logic (and guesswork)!

Another pattern we find in the disassembly is this kind of thing:

0801523C ADDS R3, #1
0801523E MOVS R0, #12
08015240 LDRSB R0, [R5, R0]
08015242 CMP R3, R0
08015244 BLT 080151F2

R3 is being incremented and then checked against some value to see if it’s smaller. 80151F2 is before 8015244 in the code stream so the code is branching backwards. This is clearly the end of a loop. In C this might look like this:

code80151F2:
    // do stuff
    r3 += 1;
    if (r3 < r5[12])
        goto code80151F2;

Or more likely:

for(int r3 = 0; r3 < r5[12]; ++r3)
{
    // do stuff
}

Taking a look at what’s inside the loop there is a call to our suspected ‘create object’ function. Another trick we can use to figure out what a piece of code is doing is to disable it. As an experiment we can try removing the loop that calls ‘create object’ to see what effect it has on the game. One way to do this is to edit the ROM file in a hex editor. Some emulators also let you modify code while the game is running.

Changing the conditional branch at 080151EC to unconditionally skip over the loop in question caused the star impact particles to disappear! So I think that confirms that the routine at 8004104 is responsible for creating sprites.

Modifying branches to skip over code like this is one way that cheat cartridges like the GameShark and Game Genie work.

Using all these techniques it’s not too difficult to eventually figure out how the game works by keeping track of what it stores at various addresses and what each piece of code does.

GIMME MAPS!!!

There is another loop before the one that emits the star particles that calls a routine located at 08013D0C. This routine uses a table at 081DA788. So let’s take a look at what’s there:

081DA788 DCD 0 
081DA78C DCD 0
081DA790 DCD 0
081DA794 DCD 0
081DA798 DCD 0
081DA79C DCD 0
081DA7A0 DCD 0
081DA7A4 DCD 0
081DA7A8 DCD 0xFFFFFFFF
081DA7AC DCD 0xFDDDDDDF
081DA7B0 DCD 0xFDBBBBDF
081DA7B4 DCD 0xFDB99BDF
081DA7B8 DCD 0xFDB99BDF
081DA7BC DCD 0xFDB99BDF
081DA7C0 DCD 0xFDB99BDF
081DA7C4 DCD 0xFDB99BDF
081DA7C8 DCD 0xFFFFFFFF
081DA7CC DCD 0xDDDDDDDF
081DA7D0 DCD 0xBBBBBBDF
081DA7D4 DCD 0x99999BDF
081DA7D8 DCD 0x99999BDF
081DA7DC DCD 0xBBBBBBDF
081DA7E0 DCD 0xDDDDDDDF
081DA7E4 DCD 0xFFFFFFFF
081DA7E8 DCD 0xFFFFFFFF
081DA7EC DCD 0xDDDDDDDD
081DA7F0 DCD 0xBBBBBBBB
081DA7F4 DCD 0x99999999
081DA7F8 DCD 0x99999999
081DA7FC DCD 0xBBBBBBBB
081DA800 DCD 0xDDDDDDDD
081DA804 DCD 0xFFFFFFFF

It kind of looks like groups of 8 dwords (32 bit values), where each hexadecimal digit (or nibble) represents a colour. Sometimes you can easily spot this kind of data in a hex editor or emulator’s memory viewer just by looking at it.

With a little bit of Python magic (and the PIL) I extracted these blocks into an image:

import Image
rom = file('0048 — Kuru Kuru Kururin (E)(Mode7).gba', 'rb')
rom.seek(0x1DA788)
blocks = []
for i in range(0x400):
    block = ''
    for byte in rom.read(32):
        byte = ord(byte)
        block += chr((byte & 15) << 4)
        block += chr((byte >> 4) << 4)
    blocks.append(Image.fromstring('L', (8, 8), block))
rom.close()
img = Image.new('L', (256, 256))
tile = 0
for y in range(0x10):
    for x in range(0x10):
        img.paste(blocks[tile], (x * 16 + 4, y * 16 + 4))
        tile += 1
img.show()

Collision tiles

This certainly looks like the blocks that the map is made out of!

A bit more digging reveals that the code at 08013D0C checks if a particular point in the level is clear or if it’s a wall. Analysing this routine reveals that the map data is stored at the very beginning of the GBA’s EWRAM at address 2000000. The first two 16 bit values contain the map’s width and height and this is followed by a sequence of 16 bit tile values. The tiles can be flipped horizontally or vertically by setting bits 10 and 11 of the tile number. This is essentially the same way that the GBA stores background map data for use by the display hardware.

Having located the map data, I used the emulator to save out the RAM and extended my python script to create an image of the map:

for i in range(0x400):
    blocks.append(blocks[i].transpose(Image.FLIP_LEFT_RIGHT))
for i in range(0x800):
    blocks.append(blocks[i].transpose(Image.FLIP_TOP_BOTTOM))
level = array.array('h', file('cave1.bin', 'rb').read())
w, h = level[:2]
img = Image.new('L', (w * 8, h * 8))
for y in range(h):
    for x in range(w):
        data = level[y * w + x + 2]
        tile = data & 0xFFF
        img.paste(blocks[tile], (x * 8, y * 8))
img.show()

Collision map for first cave level

Looks pretty good! I eventually traced the map data decoding back a bit further by finding the code that wrote the map to EWRAM (using another memory breakpoint). The maps are stored in ROM with some simple Lempel-Ziv compression. Armed with this information I was able to extract all the maps from the ROM.

Break time

Phew, ok, that’s all for this time. Next time I’ll explain how the game moves the helirin through the level and how I used that in conjunction with the map data to start solving the levels.