[NES] Writing level editor for Prince of Persia. Epilogue. Dungeon
Chapter One , Chapter Two , Chapter Three , Chapter Four , Chapter Five , Epilogue
“Time after time, going through my favorite games, far and wide, finding all the possible secrets, I wanted to play them again and again, but with new levels, new secrets and new features, ” I wrote . Naturally, passing the same game in the "normal" mode, began the search for something that is hidden behind the scenes. If the game has hidden levels, rooms, receptions, or a password system, then it would be necessary all day and half the night past the blue screen to try to find it, and to crack the passwords. PoP was no exception. And although I didn’t find the password generation algorithm, I could still find a couple of methods that allow you to create the correct password from the existing one. It is true to say where the new password leads, until the moment it was used, I could not.
The password system of PoP for NES is now described in more than detail: there are methods for changing the existing password, as well as a description of the algorithm itself.
')
It is short, so I will give it in the first language that came to hand:
And now, going through the passwords (then on dendy, when the emulators in their current form and in the project were not), I got into strange places that were not explicitly provided by the developers:
or
Management in these "levels" works only partially, the appearance is strange, and you cannot get there from the main game.
Now, looking at how the engine stores data levels, I was even convinced that more than 14 levels in the game is simply not provided. Where do these passwords lead?
As it turned out, there are no overflow checks in the game. For example, placing in the editor more than the current active blocks in the room, you can get a frozen game, or other interesting artifacts in the form of a double appeared or something else interesting.
The lack of verification also applies to the procedure for compiling passwords, the algorithm of which provides for level numbers from 0 to 15. The developers, apparently, to save development time, decided that since the game does not constitute passwords that have levels 14 and 15 (in the indexing from 0), then no one will enter them. Yeah.
We know that in our three tables of pointers, of which the final level is built, only 14 elements and 15 from 16 are not provided there. Consequently, the level is constructed from garbage that comes across when interpreting the data following the existing tables into pointers. But why there can not fully manage the character?
The level is based on three types of data, each of which has its own table of pointers:
Also, there is auxiliary data:
Tables with pointers are exactly 28 bytes apart. In other words, they follow each other. And if so, then the pointers are not taken from the desired table, but from the next one. Since the data referenced by these pointers are also intermixed, going into 15 or 16 “levels”, we fall somewhere in the middle of that data array. Moreover, the data of one sense will be interpreted as data of another sense.
Let's try to visualize the view, say, 15 "level". Take the offset 0x1EB66 (header), add 28, and look at the pointer:
$ 8279 is even earlier than the first-level heading [$ 82D9]. It is clear that we get to the data that describe the geometry of the first level. But they will now be interpreted differently:
* 05 - we start in the 5th room;
* 00 00 - we start at position 00 and look to the right;
* The remaining data tells us that the guard will be located in each room somewhere in the upper left corner, with a few exceptions.
0x1EB4A + 28 = 0x1EB66: $ 82D9. The level will be based on the data that was once the first level header. But we will start from the fifth room, therefore, starting from $ 82D9, we need to skip 4 rooms according to the rule: +30 bytes, if the first byte is not #FF, otherwise +1 byte:
$ 82D9 = # 01. We add +30.
$ 82F7 = # 05. We add +30.
$ 8315 = # 08. We add +30.
$ 8333 = # 20. We add +30.
$ 8351:
Judging by the nature of the data, we got somewhere in the middle of a second-level room. The second level starts at $ 8331, therefore, it is somewhere inside the second room, which looks like this:
.
The guard should be located in the upper left corner, based on the presented header.
Now look at the level geometry.
0x1EB82 + 28 = 0x1EBA0:
Compare:
Since the border of this “room” does not coincide with the border of the second room of the second level, some displacement of the “architecture” to the left is seen. Also on the left is a break, which corresponds to the next room, but it does not, according to the incorrect level geometry.
Now I propose to see how the information about the guards in the level is used.
The procedure $ C0DA, as we remember, retrieves a pointer to the level header and places it at the addresses $ 6D: $ 6E, in register Y we have offset # 03, since the information about the guards is stored after the first three bytes, which are responsible for the prince’s position the beginning of the level. Further, it can be seen that if the first 5 bits add up to the number # 1E, then the iteration is skipped, otherwise the following structure is written to the addresses starting at $ 0710: <room number>: <guard coordinate> - two bytes per structure. If we have all the rooms filled with guards, then the last address where we can put the data will be $ 0740, after which, at the address $ 0742, the #FF marker will be placed. But addresses, starting from $ 0735, are used for another purpose - this is evident in the normal operation of the game, which means that in this situation a classic buffer overflow occurs.
At $ 0735, we have a flag stored, which is responsible for managing from the gamepad. If there is 0, then the management is standard, if not 0, then it is considered that we are in the starting room, where management is limited. Now, in this “level”, due to the fact that the coordinates of the guards have overwritten important data, in the $ 0735 cell is not zero, and if we put 0 in it, then we will be able to fully manage the prince. True, we will not be able to escape beyond this room, since the level geometry is broken.
The same applies to the 16 "level". 17 and above “levels”, if at the moment of typing the password of $ 70 to put down the desired number, get on the frank garbage and simply are not displayed.
In this article I tried to tell you that the common myth of the "secret" levels is not true. In principle, when analyzing the code of the game, and this was seen in previous articles, there are no secrets in the game at all: hidden rooms, levels or something like that. “Secret levels” is the banal absence of the necessary verification condition in the procedure for reading passwords.
As a result of the whole study, I can say the following: the game is extremely simple within the framework of the second mapper, and moreover, it was developed, most likely, in a hurry. One can see a pretty good base of the engine, but at the end it was clearly finished on crutches: the implementation of a twin or non-standard transitions between levels is just a hardcode, which is inserted in the middle of a smooth code. This is where the NES versions differ from the rest of the ports: the little things just didn’t comb at the end, although a couple of simple procedures were enough to bring to mind. If you add this in the form of a trivial patch to the engine, then you can achieve almost full compliance with the original version, and then, as it seems to me, the version on the NES will even win compared to the DOS version. At least the presence of music, a system of passwords and a darker atmosphere.
The series of articles on the reverse of the NES is over. Now the plans are to descend to the level below - the level of iron, as I want to play the new game on the real Dendy. This will be a couple of articles.
Disclaimer
“Time after time, going through my favorite games, far and wide, finding all the possible secrets, I wanted to play them again and again, but with new levels, new secrets and new features, ” I wrote . Naturally, passing the same game in the "normal" mode, began the search for something that is hidden behind the scenes. If the game has hidden levels, rooms, receptions, or a password system, then it would be necessary all day and half the night past the blue screen to try to find it, and to crack the passwords. PoP was no exception. And although I didn’t find the password generation algorithm, I could still find a couple of methods that allow you to create the correct password from the existing one. It is true to say where the new password leads, until the moment it was used, I could not.
Dungeon
The password system of PoP for NES is now described in more than detail: there are methods for changing the existing password, as well as a description of the algorithm itself.
')
It is short, so I will give it in the first language that came to hand:
Bash password generator
#!/bin/bash PLEVEL=$1 PTIME=$2 if ! [[ ${PLEVEL} =~ ^[0-9]{1,2}$ ]] ; then echo "Invalid level" >&2 ; exit 1 ; fi if ! [[ ${PTIME} =~ ^[0-9]{1,2}$ ]] ; then echo "Invalid time" >&2 ; exit 1 ; fi if [ "0" == ${PLEVEL} ] ; then echo "Level must be great than 0" >&2 ; exit 1 ; fi PLEVEL=$[PLEVEL-1] R1=$[RANDOM % 10] R2=$[RANDOM % 10] PASS0=$[((PTIME / 10)+R1) % 10] PASS3=$[((PTIME % 10)+R2) % 10] PASS1=$[((PLEVEL & 3)+R1) % 10] PASS7=$[((PLEVEL / 4)+R2) % 10] PASS2=$R1 PASS5=$R2 SUM=$[PASS0+PASS1+PASS2+PASS3] SUM=$[SUM+(SUM % 10)+PASS5] SUM=$[SUM+(SUM / 10)+PASS7] PASS4=$[SUM % 10] PASS6=$[SUM / 10] echo "${PASS0}${PASS1}${PASS2}${PASS3}${PASS4}${PASS5}${PASS6}${PASS7}${PASS8}${PASS9}" And now, going through the passwords (then on dendy, when the emulators in their current form and in the project were not), I got into strange places that were not explicitly provided by the developers:
or
Management in these "levels" works only partially, the appearance is strange, and you cannot get there from the main game.
Now, looking at how the engine stores data levels, I was even convinced that more than 14 levels in the game is simply not provided. Where do these passwords lead?
Overflow
As it turned out, there are no overflow checks in the game. For example, placing in the editor more than the current active blocks in the room, you can get a frozen game, or other interesting artifacts in the form of a double appeared or something else interesting.
The lack of verification also applies to the procedure for compiling passwords, the algorithm of which provides for level numbers from 0 to 15. The developers, apparently, to save development time, decided that since the game does not constitute passwords that have levels 14 and 15 (in the indexing from 0), then no one will enter them. Yeah.
We know that in our three tables of pointers, of which the final level is built, only 14 elements and 15 from 16 are not provided there. Consequently, the level is constructed from garbage that comes across when interpreting the data following the existing tables into pointers. But why there can not fully manage the character?
Remember the theory
The level is based on three types of data, each of which has its own table of pointers:
- The blocks from which rooms are built are 0x1EB4A;
- The level header is 0x1EB66;
- Level geometry - 0x1EB82.
Also, there is auxiliary data:
- Type of level;
- Palette;
- Type of guard;
- Amount of health;
- Other data that does not significantly affect the appearance.
Tables with pointers are exactly 28 bytes apart. In other words, they follow each other. And if so, then the pointers are not taken from the desired table, but from the next one. Since the data referenced by these pointers are also intermixed, going into 15 or 16 “levels”, we fall somewhere in the middle of that data array. Moreover, the data of one sense will be interpreted as data of another sense.
Let's try to visualize the view, say, 15 "level". Take the offset 0x1EB66 (header), add 28, and look at the pointer:
D9 82 61 86 91 89 F1 8C 06 90 85 92 0D 96 61 99 F3 9C CD 9F 2C A3 9B A6 5B A8 AC A9 >> 79 82 << ...$ 8279 is even earlier than the first-level heading [$ 82D9]. It is clear that we get to the data that describe the geometry of the first level. But they will now be interpreted differently:
05 00 00 02 06 03 01 00 02 09 00 00 13 0E 14 00 15 01 00 06 08 02 05 00 ...* 05 - we start in the 5th room;
* 00 00 - we start at position 00 and look to the right;
* The remaining data tells us that the guard will be located in each room somewhere in the upper left corner, with a few exceptions.
0x1EB4A + 28 = 0x1EB66: $ 82D9. The level will be based on the data that was once the first level header. But we will start from the fifth room, therefore, starting from $ 82D9, we need to skip 4 rooms according to the rule: +30 bytes, if the first byte is not #FF, otherwise +1 byte:
$ 82D9 = # 01. We add +30.
$ 82F7 = # 05. We add +30.
$ 8315 = # 08. We add +30.
$ 8333 = # 20. We add +30.
$ 8351:
20 00 00 14 01 03 21 03 14 14 20 00 00 14 14 14 14...Judging by the nature of the data, we got somewhere in the middle of a second-level room. The second level starts at $ 8331, therefore, it is somewhere inside the second room, which looks like this:
.The guard should be located in the upper left corner, based on the presented header.
Now look at the level geometry.
0x1EB82 + 28 = 0x1EBA0:
0C 03 C0 30 0C 03... That is, it will be somewhere around the $ 030C address in RAM (not in ROM!). The data on these addresses is obviously more than 24, which means that it will not be possible to go to the next room with all the desire.Compare:
Since the border of this “room” does not coincide with the border of the second room of the second level, some displacement of the “architecture” to the left is seen. Also on the left is a break, which corresponds to the next room, but it does not, according to the incorrect level geometry.
Set in motion
Now I propose to see how the information about the guards in the level is used.
$F284:20 DA C0 JSR $C0DA $F287:B1 6D LDA ($6D),Y @ $9FC7 = #$1E $F289:29 1F AND #$1F $F28B:C9 1E CMP #$1E $F28D:B0 0E BCS $F29D $F28F:A6 17 LDX $0017 = #$00 $F291:9D 11 07 STA $0711,X @ $0723 = #$00 $F294:A5 18 LDA $0018 = #$00 $F296:9D 10 07 STA $0710,X @ $0722 = #$00 $F299:E6 17 INC $0017 = #$00 $F29B:E6 17 INC $0017 = #$00 $F29D:E6 18 INC $0018 = #$00 $F29F:A5 18 LDA $0018 = #$00 $F2A1:C9 19 CMP #$19 $F2A3:D0 D9 BNE $F27E $F2A5:A6 17 LDX $0017 = #$00 $F2A7:A9 FF LDA #$FF $F2A9:9D 10 07 STA $0710,X @ $0722 = #$00 $F2AC:60 RTS The procedure $ C0DA, as we remember, retrieves a pointer to the level header and places it at the addresses $ 6D: $ 6E, in register Y we have offset # 03, since the information about the guards is stored after the first three bytes, which are responsible for the prince’s position the beginning of the level. Further, it can be seen that if the first 5 bits add up to the number # 1E, then the iteration is skipped, otherwise the following structure is written to the addresses starting at $ 0710: <room number>: <guard coordinate> - two bytes per structure. If we have all the rooms filled with guards, then the last address where we can put the data will be $ 0740, after which, at the address $ 0742, the #FF marker will be placed. But addresses, starting from $ 0735, are used for another purpose - this is evident in the normal operation of the game, which means that in this situation a classic buffer overflow occurs.
At $ 0735, we have a flag stored, which is responsible for managing from the gamepad. If there is 0, then the management is standard, if not 0, then it is considered that we are in the starting room, where management is limited. Now, in this “level”, due to the fact that the coordinates of the guards have overwritten important data, in the $ 0735 cell is not zero, and if we put 0 in it, then we will be able to fully manage the prince. True, we will not be able to escape beyond this room, since the level geometry is broken.
The same applies to the 16 "level". 17 and above “levels”, if at the moment of typing the password of $ 70 to put down the desired number, get on the frank garbage and simply are not displayed.
Epilogue in the epilogue
In this article I tried to tell you that the common myth of the "secret" levels is not true. In principle, when analyzing the code of the game, and this was seen in previous articles, there are no secrets in the game at all: hidden rooms, levels or something like that. “Secret levels” is the banal absence of the necessary verification condition in the procedure for reading passwords.
As a result of the whole study, I can say the following: the game is extremely simple within the framework of the second mapper, and moreover, it was developed, most likely, in a hurry. One can see a pretty good base of the engine, but at the end it was clearly finished on crutches: the implementation of a twin or non-standard transitions between levels is just a hardcode, which is inserted in the middle of a smooth code. This is where the NES versions differ from the rest of the ports: the little things just didn’t comb at the end, although a couple of simple procedures were enough to bring to mind. If you add this in the form of a trivial patch to the engine, then you can achieve almost full compliance with the original version, and then, as it seems to me, the version on the NES will even win compared to the DOS version. At least the presence of music, a system of passwords and a darker atmosphere.
The series of articles on the reverse of the NES is over. Now the plans are to descend to the level below - the level of iron, as I want to play the new game on the real Dendy. This will be a couple of articles.
Source: https://habr.com/ru/post/193406/
All Articles