[NES] Writing level editor for Prince of Persia. Chapter Three First lines of code
Chapter One , Chapter Two , Chapter Three , Chapter Four , Chapter Five , Epilogue
The research process is a very entertaining process. When you scatter the binary porridge that is in the file, it turns out a very slim architecture that is hidden behind the veil of those funny squiggles that are displayed in a hex editor (or even worse - in a text editor). The approach to the research process does not necessarily have to be accompanied by subtle technologies; sometimes it is easier to break everything up with a hammer and study the fragments. Well, as in childhood.
Jumping between the data stubs, I found that starting at offset 0x18010 in the ROM file, the first room begins to transform when the data changes. But first, look at the data:
We can say that these data quite fall under what we assumed earlier. One can see quite slender rows of duplicate bytes (that is, clearly not a code), and they, by the eye, are not similar to any encrypted data. Let's first try to carefully change E0 to E1:
There was a platform that never was.
Adding successively to each byte one by one, we make sure that one byte is responsible for one unit in the room. Therefore, a data block with a size of 30 bytes is responsible for the room (the room consists of 10x3 blocks).
This could be understood using the debugger, but what makes this or that code difficult to say at once, and what it does afterwards with this data is a rebus. It is easier (but not safer!) To use the good old “spear” method.
')
Since one byte is responsible for one block in a room, it would be nice to understand for which type of block a certain value of byte is responsible. When searching, it turns out that there are 32 different blocks, some of which draw graphic garbage, and some of them destroy the game. Once there are 32 blocks, this means that the first 5 bits of the values ​​are responsible for the type of block. Changing the remaining three bits in a byte, we find out that they are responsible for the characteristics of the block. For example, the value # 04 is a closed grille, and # 24 is an open.
And finally, if we iterate through the bytes outside of this 30-byte block, make sure that other rooms change. Here, however, the order of the rooms is some kind of chaotic. The same chaotic order was when we changed the unit in another data block earlier and the prince appeared in one room, then in another. We didn’t succeed in biting us then.
Consider that block closer. We recall that the displacement of that block is 0x18340 and go to it. We put a two instead of one and the prince jumps to another room. Let's try to find this room by editing the data in the previous block. Looking over it, we find out that this is the next 30 bytes after the first 30-byte block responsible for the first room. Therefore, that one is the room number. And the room number is the 30-byte block number. Well, then the rooms are numbered, and numbered from one.
Well, now we know that our rooms have a serial number, which means that this serial number is stored somewhere in the memory. While we do not need to look for him, but remember for the future.
At the moment we know that there is an indefinite size data array from which rooms are built. Each room is described by a block of 30 bytes. After the rooms there is a certain data structure with an indefinite size. Let's call it the “header” of the level. And after ... Actually, how do you know what goes next? Turn to what we already know.
Let's try to calculate how many rooms we fit between the beginning and the “heading”, considering that one room is 30 bytes in this array:
30 is not divisible. Dead end? As if not so. Let's try to make a level map with room numbers. We can do this for now only by moving the prince by changing the first byte of the “header”. By successively moving it from room to room, we find that it either ends up in another room, or the game does not start at all. Exclude numbers that fail, and the rest will be placed in accordance with their position in the game:
It is difficult to say what the developers were guided by, but if you do not rely on the numbers, the scheme is quite plausible.
Let's try to compare these rooms with what we have in our array. From 1 to 12 rooms we have on the scheme, but 13 (and then 18 and 24) is missing. We consider its offset:
Turn and see:
#FF? And then what comes next? We go to room 14 and see that in it in the upper left corner there are 3 "concrete" blocks, then a platform, and then a column. It is very similar to the fact that the first three "concrete" blocks of the fourteenth room are described by numbers # 14, the platform is # E1, and the column is # 03. Consequently, for #FF there is already a description of room No. 14, and room No. 13 itself has been reduced to one byte, #FF. It looks like #FF is a kind of marker, meaning that the room is missing. The situation is similar for both 18 and 24 rooms.
But numbers 25 and higher, apparently, no longer exist, since after the #FF marker, which tells us that room 24 is not present, there is a set of data that doesn’t look like the previous ones:
You can, of course, play around with these numbers, but let's look at our scheme.
The same numbers appear in the found array. Let's try to guess.
It can be seen that the numbers 5, 6 and 2 stand on a multiple of 4 places. So, the environment of one room is described by a four-byte structure, the first of which is the room number on the left. Based on the level map, it can be seen that the remaining three bytes describe the rooms on the right, above and below. Moreover, if there is no room, then there will be 0 at the appropriate place. The number of these structures is exactly 24, after which the “heading” of the level begins. If so, then we can build a maximum of 24 rooms (then, by studying the code, we will be convinced of this).
Last time, we found an array of pointers to some data structures, which we called "headers." Moreover, when reading the array, a doubled sequence number of the level was used as an index. So the next two bytes in this array are a pointer to the same structure, but of the second level. We study and its:
Array of pointers:
We meet there the following data:
Here is the first number # 05, so the prince starts in the room with the sequence number 5. But the next two bytes are no longer zeros.
If you play with them, we find out that # 0D is the position of the prince in the room. The total possible positions are 10x3 = 30, where 10 is the width of the room, which means # 0D = 13 is the position 3x1, that is, it will be in the place of the fourth block on the left and in the place of the second one from the top. The next byte with the value #FF is its direction: if #FF, it will turn around and look to the left, if not #FF, then it will remain to look to the right. The only strange thing is that in the first level he does not change his position. But we will find out later.
Let's see what follows the first three bytes.
As we remember, in the first level, when the first byte was changed, a guard appeared in the room. So these numbers are somehow responsible for the presence of the guard in the room.
Let's go back to the first level and write # 02 (as last time) to the fourth field. The guard appeared very close to the prince. We put # 03. Appeared, but already far away. Looking through the values ​​down to # 1D, we make sure that this byte is responsible for the position of the guard. But when we put 0x1E it disappears. But 0x1E = 30 in the decimal representation, which means that if we set the limit value of the position, this will mean that there is no guard in the room. Apparently, the remaining bytes are responsible for the guards in other rooms. That is, the next byte is responsible for the presence of the guard in the second room, then in the third, and so on. However, this is confirmed by a simple check. Also, by checking it turns out that only the first 5 bits of the values ​​are responsible for the position of the guard, the remaining 3 bits are not used, no matter how we twist them.
So we have the following data structures:
But after all, what's inconvenient: the pointer that we have (from the array of pointers) leads us to the “title”, which means we will have to count the beginning of the level shift. Let's take a look at the debugger and see how it is considered.
We know that our beginning is at offset 0x18010, which means it will be in memory right at $ 8000. But we have several banks, so we will track only the right one. We will not count its number, we will simply tell the debugger that we are interested in reading at $ 8000, with the first byte being equal to # E0 (the first block in the first room of the first level):
The first stop hi to us to the procedure:
In cells $ 0E: $ 0F we have the address $ 8000. He got there from familiar $ 6D cells: $ 6E, to which values ​​from $ 52 and $ 53 cells were added. In cells $ 52, $ 53 are now zeros, so we are interested, as in $ 6D: $ 6E are numbers # 00 and # 80.
At the very beginning of the procedure, we see a call to another procedure at $ C0C7. We climb there:
At the beginning we see the call to the familiar procedure sub_C0D5 (which returns to us in the X register the doubled ordinal level number), and then the reading from the last bank. We consider the rule we developed:
We look:
For sure. Pointers to our "bricks". If we climb in the vicinity of this code, we will see three similar procedures - they go almost one after the other. We have seen two of them, and the third (0x1EB82) refers to an array that leads to the room layout structure.
Like everyone collected? As if not so.
In principle, we can rebuild the level from the foundation and up to the roof, but what about the bars? They also need to be able to manage. Let's try to study their behavior.
We place the prince in room number 5, since there are two lattices in it at once and as many as three buttons. One of them closes the lattice, and the other two - open. Then I had a stupor: how could I link the buttons with the bars, being a developer?
To begin with, what we can do now is to move a button or a grid and look at the effect.
The first lattice after moving has ceased to open. The button when moving also stopped working. But if you swap two buttons (“high” and “low”), then the “low” button (in the image it is two positions to the left of the “high” on which the prince stands, is not visible) began to open, and “high »Close. So, the positions (as before, we will be counting from zero, and the rooms from one) of the buttons and grids are uniquely connected, but how? I wrote down these positions in the bar and got this label:
Reflecting on this table, I somehow mechanically climbed into the HEX-editor and decided to look again at the “heading” of the level. Contrary to my expectations, after the end of the array, placing the rooms of the guards, did not begin the second level, but an array of some more data. The second level began immediately after them.
The bytes almost exactly repeated my entries in the table, only instead of a colon there were either 00 or 01. Considering that, opposite the first record, I have the word “closes”, and opposite the others “opens”, it is easy to see that 00 says that in this bundle the grating will open, and 01 - close. The audit showed that it is so. Now we have also found the mechanics responsible for the door opening mechanism.
Well, the editor is almost ready? It is enough to take three offsets, define from them pointers to three structures (Rooms, level geometry and "header") and display in the editor. As if not so.
The algorithm for placing rooms is quite simple: starting from the initial room, we “interrogate” recursively the neighboring rooms, placing them on a coordinate grid. The first room we will have is at (0,0), the room on the left is at (-1, 0), the bottom room is at (0, 1), and so on. Then we take the “most negative” coordinates X and Y, and add their absolute values ​​to the coordinates of all the rooms. Thus, we get a map of the entire level.
Everything is fine, but at the 10th level, the algorithm throws an exception: they say that room No. 1 refers to room No. 3, and room No. 3, in turn, refers to 00, which means that there are no rooms above it. In the game, we also can’t get “under” room number 1 (level 10 begins with it).
Approximately sketching room number 3, it became clear that this is the very starting room with which the game begins. In it, we are offered to go to the right and start the game again, or to the left, where we type the password and get to the appropriate level.
Room number 3 has a neighbor - room number 12. And yes, there is a bottle and an exit door in it.
Thus, it will be enough for us in the editor to take into account these rooms, and to draw the level map.
We came close to writing the editor. We have almost everything to do construction. We can only figure out how to convert the dungeon in the palace and vice versa. We are able to change the appearance, but not the color yet.
I have not thought about the name of the editor for a long time: there is PrincEd, which is for the DOS version, and we have NESPrincEd, which is for the NES version.
At this stage, I thought that now it was enough to write a shell and the editor was ready. How then was I mistaken ... And in the fourth chapter, which is called "He himself runs!" Or a skeleton in the closet ”, we will see this.
Disclaimer
The research process is a very entertaining process. When you scatter the binary porridge that is in the file, it turns out a very slim architecture that is hidden behind the veil of those funny squiggles that are displayed in a hex editor (or even worse - in a text editor). The approach to the research process does not necessarily have to be accompanied by subtle technologies; sometimes it is easier to break everything up with a hammer and study the fragments. Well, as in childhood.
Open HEX-editor
Jumping between the data stubs, I found that starting at offset 0x18010 in the ROM file, the first room begins to transform when the data changes. But first, look at the data:
E0 E0 E0 01 21 01 21 01 14 14 13 13 21 03 00 14 14 14 14 14 14 14 14 14 0E 03 0B 21 01 14 ...We can say that these data quite fall under what we assumed earlier. One can see quite slender rows of duplicate bytes (that is, clearly not a code), and they, by the eye, are not similar to any encrypted data. Let's first try to carefully change E0 to E1:
There was a platform that never was.
Adding successively to each byte one by one, we make sure that one byte is responsible for one unit in the room. Therefore, a data block with a size of 30 bytes is responsible for the room (the room consists of 10x3 blocks).
This could be understood using the debugger, but what makes this or that code difficult to say at once, and what it does afterwards with this data is a rebus. It is easier (but not safer!) To use the good old “spear” method.
')
Looking around
Since one byte is responsible for one block in a room, it would be nice to understand for which type of block a certain value of byte is responsible. When searching, it turns out that there are 32 different blocks, some of which draw graphic garbage, and some of them destroy the game. Once there are 32 blocks, this means that the first 5 bits of the values ​​are responsible for the type of block. Changing the remaining three bits in a byte, we find out that they are responsible for the characteristics of the block. For example, the value # 04 is a closed grille, and # 24 is an open.
And finally, if we iterate through the bytes outside of this 30-byte block, make sure that other rooms change. Here, however, the order of the rooms is some kind of chaotic. The same chaotic order was when we changed the unit in another data block earlier and the prince appeared in one room, then in another. We didn’t succeed in biting us then.
Consider that block closer. We recall that the displacement of that block is 0x18340 and go to it. We put a two instead of one and the prince jumps to another room. Let's try to find this room by editing the data in the previous block. Looking over it, we find out that this is the next 30 bytes after the first 30-byte block responsible for the first room. Therefore, that one is the room number. And the room number is the 30-byte block number. Well, then the rooms are numbered, and numbered from one.
Well, now we know that our rooms have a serial number, which means that this serial number is stored somewhere in the memory. While we do not need to look for him, but remember for the future.
At the moment we know that there is an indefinite size data array from which rooms are built. Each room is described by a block of 30 bytes. After the rooms there is a certain data structure with an indefinite size. Let's call it the “header” of the level. And after ... Actually, how do you know what goes next? Turn to what we already know.
We arrange the rooms
Let's try to calculate how many rooms we fit between the beginning and the “heading”, considering that one room is 30 bytes in this array:
0x182E9 - 0x18010 + 1 = 0x2DA = 730 .30 is not divisible. Dead end? As if not so. Let's try to make a level map with room numbers. We can do this for now only by moving the prince by changing the first byte of the “header”. By successively moving it from room to room, we find that it either ends up in another room, or the game does not start at all. Exclude numbers that fail, and the rest will be placed in accordance with their position in the game:
It is difficult to say what the developers were guided by, but if you do not rely on the numbers, the scheme is quite plausible.
Let's try to compare these rooms with what we have in our array. From 1 to 12 rooms we have on the scheme, but 13 (and then 18 and 24) is missing. We consider its offset:
0x18010 + 12( )*30( ) = 0x18010 + 0x168 = 0x18178 .Turn and see:
FF 14 14 14 E1 03...#FF? And then what comes next? We go to room 14 and see that in it in the upper left corner there are 3 "concrete" blocks, then a platform, and then a column. It is very similar to the fact that the first three "concrete" blocks of the fourteenth room are described by numbers # 14, the platform is # E1, and the column is # 03. Consequently, for #FF there is already a description of room No. 14, and room No. 13 itself has been reduced to one byte, #FF. It looks like #FF is a kind of marker, meaning that the room is missing. The situation is similar for both 18 and 24 rooms.
But numbers 25 and higher, apparently, no longer exist, since after the #FF marker, which tells us that room 24 is not present, there is a set of data that doesn’t look like the previous ones:
05 00 00 02 06 03 01 00 02 09 00 00...You can, of course, play around with these numbers, but let's look at our scheme.
- The first room is surrounded by rooms 05 and 02;
- The second room is surrounded by rooms 06, 01 and 03;
- The third room is surrounded by rooms 02 and 09;
- ...
The same numbers appear in the found array. Let's try to guess.
- To the left of the first room is the fifth;
- To the left of the second - the sixth;
- To the left of the third - the second;
It can be seen that the numbers 5, 6 and 2 stand on a multiple of 4 places. So, the environment of one room is described by a four-byte structure, the first of which is the room number on the left. Based on the level map, it can be seen that the remaining three bytes describe the rooms on the right, above and below. Moreover, if there is no room, then there will be 0 at the appropriate place. The number of these structures is exactly 24, after which the “heading” of the level begins. If so, then we can build a maximum of 24 rooms (then, by studying the code, we will be convinced of this).
We call the guard!
Last time, we found an array of pointers to some data structures, which we called "headers." Moreover, when reading the array, a doubled sequence number of the level was used as an index. So the next two bytes in this array are a pointer to the same structure, but of the second level. We study and its:
Array of pointers:
D9 82 61 86 91 89 ...- First level:
D9 82->$82D9-> offset in the file0x182E9; - Second level:
61 86->$8661-> offset in the file0x18671; - ...
We meet there the following data:
05 0D FF 1E 9E ... (funny, here too, after the first three bytes, the numbers ending in 0x0E again go)Here is the first number # 05, so the prince starts in the room with the sequence number 5. But the next two bytes are no longer zeros.
If you play with them, we find out that # 0D is the position of the prince in the room. The total possible positions are 10x3 = 30, where 10 is the width of the room, which means # 0D = 13 is the position 3x1, that is, it will be in the place of the fourth block on the left and in the place of the second one from the top. The next byte with the value #FF is its direction: if #FF, it will turn around and look to the left, if not #FF, then it will remain to look to the right. The only strange thing is that in the first level he does not change his position. But we will find out later.
Let's see what follows the first three bytes.
As we remember, in the first level, when the first byte was changed, a guard appeared in the room. So these numbers are somehow responsible for the presence of the guard in the room.
Let's go back to the first level and write # 02 (as last time) to the fourth field. The guard appeared very close to the prince. We put # 03. Appeared, but already far away. Looking through the values ​​down to # 1D, we make sure that this byte is responsible for the position of the guard. But when we put 0x1E it disappears. But 0x1E = 30 in the decimal representation, which means that if we set the limit value of the position, this will mean that there is no guard in the room. Apparently, the remaining bytes are responsible for the guards in other rooms. That is, the next byte is responsible for the presence of the guard in the second room, then in the third, and so on. However, this is confirmed by a simple check. Also, by checking it turns out that only the first 5 bits of the values ​​are responsible for the position of the guard, the remaining 3 bits are not used, no matter how we twist them.
Putting it all together: Builders, architects and guards
So we have the following data structures:
- "Bricks" of which rooms are built. The structure of an unfixed value;
- The layout of the rooms. Fixed in length (4x24 bytes);
- A small structure that describes how and where the prince will appear (3 bytes) - the “header” of the level;
- A structure describing the location of the guards by room (24 bytes).
But after all, what's inconvenient: the pointer that we have (from the array of pointers) leads us to the “title”, which means we will have to count the beginning of the level shift. Let's take a look at the debugger and see how it is considered.
We know that our beginning is at offset 0x18010, which means it will be in memory right at $ 8000. But we have several banks, so we will track only the right one. We will not count its number, we will simply tell the debugger that we are interested in reading at $ 8000, with the first byte being equal to # E0 (the first block in the first room of the first level):
The first stop hi to us to the procedure:
$C0F6:20 C7 C0 JSR $C0C7 $C0F9:A5 52 LDA $0052 = #$00 $C0FB:18 CLC $C0FC:65 6D ADC $006D = #$00 $C0FE:85 0E STA $000E = #$00 $C100:A5 53 LDA $0053 = #$00 $C102:65 6E ADC $006E = #$80 $C104:85 0F STA $000F = #$80 $C106:8C 0B 04 STY $040B = #$03 $C109:A0 00 LDY #$00 $C10B:B1 0E LDA ($0E),Y @ $8000 = #$E0 ;; <<<<< $C10D:AC 0B 04 LDY $040B = #$03 $C110:60 RTS In cells $ 0E: $ 0F we have the address $ 8000. He got there from familiar $ 6D cells: $ 6E, to which values ​​from $ 52 and $ 53 cells were added. In cells $ 52, $ 53 are now zeros, so we are interested, as in $ 6D: $ 6E are numbers # 00 and # 80.
At the very beginning of the procedure, we see a call to another procedure at $ C0C7. We climb there:
$C0C7:20 D5 C0 JSR $C0D5 $C0CA:BD 3A EB LDA $EB3A,X @ $EB3A = #$00 $C0CD:85 6D STA $006D = #$00 $C0CF:BD 3B EB LDA $EB3B,X @ $EB3B = #$80 $C0D2:85 6E STA $006E = #$80 $C0D4:60 RTS At the beginning we see the call to the familiar procedure sub_C0D5 (which returns to us in the X register the doubled ordinal level number), and then the reading from the last bank. We consider the rule we developed:
$EB3A+0x10010=0x1EB4AWe look:
00 80 31 83 9B 86 C1 89 ...For sure. Pointers to our "bricks". If we climb in the vicinity of this code, we will see three similar procedures - they go almost one after the other. We have seen two of them, and the third (0x1EB82) refers to an array that leads to the room layout structure.
Like everyone collected? As if not so.
Open the door
In principle, we can rebuild the level from the foundation and up to the roof, but what about the bars? They also need to be able to manage. Let's try to study their behavior.
We place the prince in room number 5, since there are two lattices in it at once and as many as three buttons. One of them closes the lattice, and the other two - open. Then I had a stupor: how could I link the buttons with the bars, being a developer?
To begin with, what we can do now is to move a button or a grid and look at the effect.
The first lattice after moving has ceased to open. The button when moving also stopped working. But if you swap two buttons (“high” and “low”), then the “low” button (in the image it is two positions to the left of the “high” on which the prince stands, is not visible) began to open, and “high »Close. So, the positions (as before, we will be counting from zero, and the rooms from one) of the buttons and grids are uniquely connected, but how? I wrote down these positions in the bar and got this label:
Button Room - Button Position : Door Room - Door Position05 - 02 : 05 - 09 - the “low” button closes the second grid.05 - 04 : 05 - 05 + 05 - 09 - the first “high” button opens both grids.05 - 08 : 05 - 09 - the second “high” button opens only the second grid.Reflecting on this table, I somehow mechanically climbed into the HEX-editor and decided to look again at the “heading” of the level. Contrary to my expectations, after the end of the array, placing the rooms of the guards, did not begin the second level, but an array of some more data. The second level began immediately after them.
05 02 01 05 09 05 04 00 05 09 05 04 00 05 05 05 08 00 05 09 ...The bytes almost exactly repeated my entries in the table, only instead of a colon there were either 00 or 01. Considering that, opposite the first record, I have the word “closes”, and opposite the others “opens”, it is easy to see that 00 says that in this bundle the grating will open, and 01 - close. The audit showed that it is so. Now we have also found the mechanics responsible for the door opening mechanism.
Editor
Well, the editor is almost ready? It is enough to take three offsets, define from them pointers to three structures (Rooms, level geometry and "header") and display in the editor. As if not so.
The algorithm for placing rooms is quite simple: starting from the initial room, we “interrogate” recursively the neighboring rooms, placing them on a coordinate grid. The first room we will have is at (0,0), the room on the left is at (-1, 0), the bottom room is at (0, 1), and so on. Then we take the “most negative” coordinates X and Y, and add their absolute values ​​to the coordinates of all the rooms. Thus, we get a map of the entire level.
Everything is fine, but at the 10th level, the algorithm throws an exception: they say that room No. 1 refers to room No. 3, and room No. 3, in turn, refers to 00, which means that there are no rooms above it. In the game, we also can’t get “under” room number 1 (level 10 begins with it).
Approximately sketching room number 3, it became clear that this is the very starting room with which the game begins. In it, we are offered to go to the right and start the game again, or to the left, where we type the password and get to the appropriate level.
Room number 3 has a neighbor - room number 12. And yes, there is a bottle and an exit door in it.
Thus, it will be enough for us in the editor to take into account these rooms, and to draw the level map.
nesprinted
We came close to writing the editor. We have almost everything to do construction. We can only figure out how to convert the dungeon in the palace and vice versa. We are able to change the appearance, but not the color yet.
I have not thought about the name of the editor for a long time: there is PrincEd, which is for the DOS version, and we have NESPrincEd, which is for the NES version.
At this stage, I thought that now it was enough to write a shell and the editor was ready. How then was I mistaken ... And in the fourth chapter, which is called "He himself runs!" Or a skeleton in the closet ”, we will see this.
Source: https://habr.com/ru/post/192028/
All Articles