Reverse Engineering a Gameboy Advance Game: Let There be Tilemap! — Part 5
This post is part of a series entitled Reverse Engineering a Gameboy Advance Game. Read the introduction here. Read the previous post here.
Follow me on Twitter to more computer fun 🐦
Cool! At last we managed to extract the tilemap of the level, which is fantastic by itself… but it’s still not sufficient for what we’re aiming to achieve, right? So let’s move forward! Let’s plot the tilemap!
But we have the following challenge: the dump of the tilemap is a linear vector, while the level is a two-dimensional matrix. Therefore we need to find the value that determines the level “linebreak” (our \n, let’s say). For example, the vector [1, 2, 3, 4, 5, 6] could be plotted as a two-dimensional matrix in 4 different forms: 1x6, 2x3, 3x2, and 6x1 — all of these are valid forms, but only one would represent the dimensions applied in the game.
How can we find the correct values?
And we have another complication: a level in the game Klonoa has various stages. Could each stage has a different size, or will the entire tilemap use the same dimensions, and therefore we can plot it just once? Furthermore, there’s still the bizarre chance of the tilemap not being a rectangular matrix, after all, I have no idea how the game was developed!
We have several doubts… but keep calm, for we have some clues right away. So we’ll start with one of the clues we already have, which is the size of our vector! In this case, the first level of the game has a vector of size 25203. Cool… Or rather, very likely, we have two natural numbers which, multiplied, result in 25203. To show some mathematical formulas, we have the following:
H·W=25203
H,W ∈ ℕ
Therefore, we need to discover the length or height of the level, and after that it’s enough to divide to get the remaining variable, which gives us everything we want!
Another clue we already have is that the tilemap specifies the tiles horizontally, from left to right. For example, the vector [1, 2, 3, 4] with 2x2 dimensions plots the following tilemap:
1 2
3 4
These two clues, although simple, are fundamental.
The first idea that came to mind was to walk and get Klonoa’s X position from one extreme of the level to the other extreme of the level. In this way, who knows if I could find the length of the level? Or at least an approximate value?
I tried doing this a couple of times, both for the entire level and for a single stage, but I wasn’t able to get a good value or even an approximation… so let’s go to the next idea… (in another chapter I’ll explain in more detail why this didn’t work, but to summarize, it’s because the matrix of the OAM is 4x the matrix of the tilemap, and I only unraveled that much later).
After spending some time philosophizing and sketching ideas on paper, I thought of the following: we know that the tiles are specified from left to right and, at some point, there’s a “linebreak” restarting at position 0 and continuing on, until returning to the same X position it was at before, but with the next Y.
That is, with that we can calculate the length of the level! Already got the idea? Let me draw it!
x x x x a x x x x <- I’m on tile a
x x x x b x x x x
x x x x a x x x x <- from a to b there are 9 bytes (= 9 tiles),
x x x x b x x x x that is, the length of the tilemap is exactly 9
In other words, if we find the memory addresses of two tiles with one right below the other, we can use this idea to calculate the length of the tilemap!
At first, I thought of finding this using elements of the tilemap which are easy to visualize both in the game and in memory — that is, some structure with different tiles, which has some particular repetition, both on the first row and on the second. Therefore, I first tried to do this with a large bridge found in the second level, after all, it would be difficult to find another sequence of bytes equal to this in another part of the level, right?
Then I used IDA’s sequence of bytes (alt + b) tool to find this set of bytes in sequence, both on the first line and on the second, in order to calculate the distance between them. However, it was more difficult to use this method, as I ended up lost between the tool and the searches for correct bytes, since I needed to do everything in static form — and so I moved on to another approach with a very similar idea.
Remember that when we were trying to understand the game’s physics we figured out how to find the position in memory of the tile that Klonoa was standing on, right? No!? It’s okay; really I’ve talked about a lot of things between then and now… let me remind you… When instruction 0800FF7E is executed it gets the memory address of the tile ID that Klonoa is standing on from R0 — and we can use that to our advantage now!
We can find a position of a certain tile dynamically, and we can modify the tilemap in memory until we find the tile that’s directly below it. See the walkthrough below:
First, we obtain the position of some tile. For this, we just need to put a breakpoint on instruction 0800FF7E. In this case, the tile in this part of the bridge is located at 02008437.
Then we modify this tile, to leave it “marked.”
And then we need to locate the tile directly below the one we marked. For this, we can erase some nearby tiles to lower Klonoa and leave him closer to the tile that’s below the one we marked. Therefore, we know that Klonoa is at 020085D7 — that is, the tile below the one we marked is shortly after that!
And thus, we can mess with the other tiles until at last we hit the one below the tile we marked.
We got it! After a few tries, we discovered that the tile right below the one we marked is located at 020085DB.
Subtracting 02008437 from 020085DB gives 1A4, which, in decimal, is 420 — in other words, the total length of the level is 420! Since the total size of the level is 25203, the height would be 25203 / 420, right? Well… that gives a decimal value… it’s almost 60… it would be exactly 60 if the total size of the level was 25200… either my calculations are completely incorrect or there are 3 extra bytes there…
Could there be some bytes of metadata we don’t know yet? So, I started to do some analysis, comparing the tilemap I extracted from the first level with those of other levels and also with the game’s memory. And something caught my attention: the first three bytes of the extraction weren’t in the game’s memory! And this same behavior, of the first 3 bytes not being in the game’s memory, also occurred with the tilemaps of the other levels I extracted.
These first 3 bytes are for something other than representing the tilemap of the level… that is, the total size of the level really is 25200 — it all checks out! The length is 420 and the height is 60! I even felt like an accountant doing all this number juggling.
But then we go to one of the most fun parts of the project! Now we’ll plot the tilemap with everything we’ve gained! We need to put all of our ideas into practice!
Our final objective was always to make a complete level editor for Klonoa, however, something very important in any development of more complex software is, before doing the actual project, to create a Proof of Concept (POC) in the simplest way possible, with code that’s easy to write, quick to validate the idea, and painless to discard when we move on to developing the real project.
Then, in the first moment, I decided to write a tool to plot the map to a BMP file, as it seemed to be a quick way to put the idea into practice. In addition, I always wanted the tool we’re going to develop to be a web app, so a user could just type a URL and start designing their own levels — in other words, I would need to develop it in a language which runs in a browser, and JavaScript is the one I have the most experience with for that. Yes, we’re going to write a reverse engineering tool in JS.
Therefore, let’s plot the level in a BMP image using JS; and for that I chose the popular library jimp.
After struggling for a few hours to understand the library and JS itself, and how to open a file to read its buffer, the code in the end was very simple, and the result is very interesting!
You can see the source code for this first version here.
Wow! That is Fantastic! Check it out: it all really works! We weren’t delirious this whole time!!! For the first deliverable of this project we managed in fact to plot a level of the game Klonoa, see where we walk, each obstacle, each little part of it.
Originally, I hadn’t arrived at dropping the first 3 bytes, however, when plotting the second level, I saw that it had borders which were a bit “misaligned”…
What happens if we drop them?
And it ended up being much better! We’re on the right track.
Now let’s do some legwork, searching in No$GBA for the tile ID of each tile in order to define a color for its type (each tile of grass has the same color, the same for rocks, etc.), and if the tile is for the background we’ll leave it semi-transparent. What will the result be?
AND IT’S WORKING! At last we managed to plot it in an elegant form! You can see the code for this version here. Note that the code is very dirty, but it’s okay — this is just a simple POC.
And check out this interesting detail: in the upper left corner, in a region inaccessible to the player, there’s a portion of different tiles. This is a technique which was very common in game development, putting a collection of available tiles in a corner, to serve as consultation during the level’s development, and placing this consultation within the actual tilemap is a practical way to save memory, as you can read more about here. Besides that, those white bars in the middle of the level represent the “portal” which divides one part of the level from the other.
Now that we managed to map a color to each tile ID for one level, I tried to see if they would be the same for other levels…
And it ended up being bizarre… Unfortunately, different levels use different mappings… Apparently, I would need to develop something awesome to discover what each tile ID represents in the game — something which would demand a lot of time to do, and as that’s not essential for the moment, I left it for later.
It even makes sense that each level has a different mapping for the tiles, since one level can use a different collection of tiles than another level and, in all, the game must have over 255 different types of tiles.
See that we are getting even closer to creating our level editor! After various studies, in the end we are succeeding in producing a useful artifact — in this case, plotting a level to a BMP file.
We could even get started already on developing the web tool itself, but before this we’re going to include in our POC the code related to the OAM (monsters, diamonds), to leave our POC more complete and thus we’ll be more prepared when we develop the real project.
Where will the data related to the level’s OAM be stored? Will the data be moved to Slow WRAM when a level is loaded or not? How will it be structured? We’ll see more in the next post!
