Posted on by

Let´s play money making game.

Let´s play money making game.

I decided earlier today that I should play through the first Zelda for the NES. It started out great. After having cleared the first palace, some sub-conscious memory from playing the game as a kid guided me to a “This is a secret to everybody”, which yielded no less than 100 Rupees. The unfortunate part of this otherwise great start was that the secret was located next to a “Money making game”. If you are at all familiar with the first Zelda, you have surely played the “Money making” mini-game.

The mini-game works by you selecting one out of three Rupees. The Rupees will then show their true values, which can be either -40, -10, 20 or 50. If you chose a negative value, Rupees will be taken away from you, where as a positive will add to your Rupees. In the case of my attempted play-through, I got 3x -40, aggressively shut off the console, and decided to find out how this cheating piece of software actually works.

 

Zelda Random

Initialization

To understand the probability of an outcome in the mini-game, I first had to understand how randomness works in Zelda.

Like most NES games, the random-seed is updated each frame. The seed is a 13-byte long number located from $18 to $24 inclusive. My guess is that the game uses different bytes for different random elements in the game, to make it seem less static. The “Money making game” only uses two bytes ($19 & $1A), so I only really looked at them.

When the game is powered on or reset, all values of this 13-byte long number is set to zero aside from the first byte, which is initially set to #$40.

05:B4EF    LDA #$00     ; memset(0x0000, 0x00, 0xF0);
; ...
05:B4F9    LDY #$EF     ; ...
05:B4FB    STA $0000,Y  ; ...
05:B4FE    DEY ; ...
05:B4FF    CPY #$FF     ; ...
05:B501    BNE $B4FB    ; ...
05:B503    LDA #$40     ; A = 0x40
; ...
05:B508 STA $0018    ; *0x18 = A

If you patch the code above at address $B503 to LDA #$00 (or use this Game Genie code: AAELGIAG), all randomness in the entire game is removed.

Advancing the seed

Once the seed has been (re-)initialized, the games starts to advance it once per frame from its initial value (#$40).

The seed is advanced using the follow logic:

07:E542    LDX #$18
07:E544    LDY #$0D
07:E546    LDA $00,X @ $0018 = #$40
07:E548    AND #$02
07:E54A    STA $0000 = #$00
07:E54C    LDA $01,X @ $0019 = #$00
07:E54E    AND #$02
07:E550    EOR $0000 = #$00
07:E552    CLC
07:E553    BEQ $E556
07:E555    SEC
07:E556    ROR $00,X @ $0018 = #$40
07:E558    INX
07:E559    DEY
07:E55A    BNE $E556

or, rewritten in Python:

def _ror(val, carry):
    next_carry = bool(val & 1)
    val = (val >> 1)
    if carry:
        val |= 0x80
    return val, next_carry

def random_init():
    return [ 0x40 ] + ([ 0 ] * 12)

def random_advance(seed):
    carry = bool((seed[0] & 0x02) ^ (seed[1] & 0x02))
    for i in range(0, len(seed)):
        seed[i], carry = _ror(seed[i], carry)
    return seed

So essentially, if the value at address $18 is #2, or the value at $19 is #2, set the highest bit in $18. Don’t do this if both are #2 at the same time. Then just shift all 13-bytes as one big integer one step to the right. This algorithm is very well distributed. Below are three distribution matrices for the value at address $18.

Note, index (0, 0) at the top left corner of the matrix shows the number of times $18 has been #0, moving right to index (0, 1) shows the number of times it has been #1, and so on.

At 10,000 frames:

37, 40, 38, 36, 37, 40, 38, 36, 32, 40, 34, 46, 35, 45, 49, 34,
39, 29, 38, 37, 30, 41, 41, 46, 40, 35, 43, 41, 47, 42, 29, 43,
37, 40, 34, 35, 46, 34, 39, 46, 37, 38, 45, 39, 39, 39, 38, 46,
36, 41, 32, 33, 40, 38, 31, 45, 51, 32, 33, 40, 32, 37, 40, 44,
35, 43, 37, 47, 33, 39, 45, 37, 42, 44, 44, 33, 34, 33, 39, 39,
40, 42, 43, 29, 46, 47, 43, 37, 36, 42, 41, 31, 41, 33, 40, 46,
32, 37, 37, 37, 33, 43, 35, 41, 49, 33, 40, 33, 34, 30, 37, 43,
44, 48, 42, 31, 30, 36, 37, 35, 32, 46, 35, 40, 31, 52, 42, 49,
40, 34, 39, 38, 35, 40, 42, 47, 36, 35, 37, 41, 40, 39, 40, 38,
38, 40, 42, 48, 45, 43, 37, 38, 37, 30, 35, 35, 36, 31, 40, 41,
41, 44, 38, 47, 40, 43, 28, 32, 45, 34, 48, 41, 39, 33, 36, 40,
33, 33, 44, 43, 42, 35, 33, 35, 41, 40, 33, 32, 46, 38, 43, 47,
40, 34, 38, 42, 38, 39, 34, 41, 36, 46, 44, 42, 33, 37, 28, 42,
45, 43, 40, 31, 33, 42, 29, 39, 30, 45, 36, 37, 40, 32, 44, 44,
42, 43, 40, 38, 49, 43, 35, 29, 39, 38, 35, 35, 41, 43, 35, 45,
41, 30, 50, 33, 47, 34, 47, 45, 39, 37, 46, 52, 45, 46, 49, 61,

At 30,000 frames:

107, 112, 107, 119, 107, 114, 120, 120, 111, 116, 118, 112, 117, 118, 121, 119,
115, 116, 112, 112, 117, 119, 107, 116, 120, 117, 117, 117, 116, 122, 118, 121,
112, 118, 115, 120, 112, 122, 114, 113, 119, 119, 120, 116, 113, 113, 118, 116,
117, 116, 121, 117, 117, 120, 118, 116, 115, 120, 117, 115, 120, 120, 120, 116,
114, 116, 119, 117, 115, 117, 119, 119, 113, 118, 122, 119, 116, 116, 117, 114,
118, 120, 121, 117, 119, 120, 120, 114, 113, 118, 113, 118, 116, 117, 116, 115,
118, 115, 112, 119, 119, 118, 119, 120, 118, 116, 118, 116, 117, 121, 118, 119,
113, 118, 118, 118, 117, 117, 120, 116, 112, 122, 117, 121, 117, 122, 119, 115,
112, 114, 114, 121, 120, 116, 115, 120, 120, 108, 118, 111, 120, 116, 117, 120,
115, 119, 122, 115, 121, 117, 119, 118, 113, 121, 120, 117, 119, 110, 122, 115,
118, 118, 117, 118, 119, 119, 118, 118, 119, 119, 119, 118, 118, 118, 115, 115,
116, 115, 116, 122, 117, 114, 120, 121, 116, 116, 117, 121, 114, 118, 119, 118,
113, 119, 117, 118, 113, 112, 117, 118, 121, 119, 116, 118, 118, 121, 112, 123,
118, 115, 117, 119, 119, 117, 116, 116, 118, 120, 118, 123, 116, 121, 116, 121,
114, 120, 113, 116, 121, 116, 120, 115, 115, 120, 118, 116, 121, 120, 119, 118,
121, 111, 119, 117, 118, 117, 121, 121, 120, 114, 118, 121, 117, 117, 115, 119,

And after 32,768 (#$8000) frames, the algorithm has gone the full circle ($18 now back to #$40, and $19 is #$00):

127, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
129, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,

As you can see the algorithm is very well distributed, no numbers are over- or under-represented. In fact, the only value to appear less frequently than the other numbers is zero (0), which is always seen one time less than the other numbers during a full circle (#$8000 frames). Now, with NTSC running at 60hz, this means that there is one less zero being generated per ~9 minutes, which will have negligible effect on the probability.

Money maker logic

The code that decides what Rupee has what value is ran once as you enter the game room, the only way to change the their value is to leave and re-enter the room. The values the Rupees are assigned are written to $448, $449 and $44a, representing the left, the middle and the right Rupee respectively. Let’s have a look at the actual code.

The game starts by figuring out what layout-configuration to use. The game always constructs the price array as { RND_LOSS, -10, WIN }, and then re-arranges it in accordance with the randomly chosen layout configuration.

01:864F    LDA #$FF
01:8651    LDY #$06
01:8653    CMP $0019
01:8655    BCC $865D
01:8657    SEC
01:8658    SBC #$2B
01:865A    DEY 01:865B    BNE $8653 

or, in Python:

v = 0xFF
config = 6
while v > 0:
    if v < seed[1]:
        break
    config -= 1
    v -= 0x2B

The above code computes what layout configuration to use. There are 6-possible outcomes (0-5). What layout configuration to use is based on what value-interval the byte at $19 has. The table below shows what layout the algorithm yields on what $19 value. Note that the probability for layout zero (0) to occur is slightly less than the rest of them.

Layout 0 - 0x00 to 0x28 (41 values)
Layout 1 - 0x29 to 0x53 (43 values)
Layout 2 - 0x54 to 0x7E (43 values)
Layout 3 - 0x7F to 0xA9 (43 values)
Layout 4 - 0xAA to 0xD4 (43 values)
Layout 5 - 0xFF to 0xD5 (43 values)
Having chosen what layout to use, the game then reads that configuration using this code:
01:865D    LDX $85CA,Y ; $85CA is shown below as start_offset
01:8660    LDY #$02    ; Number of bytes to copy
01:8662    LDA $85B8,X ; $85B8 is shown below as layout_config.
01:8665    STA $046C,Y ; Copy layout-configuration to $0x46C-0x46E (inclusive)
01:8668    DEX
01:8669    DEY
01:866A    BPL $8662

or, in Python:

start_offset  = [ 0x02, 0x05, 0x08, 0x0B, 0xE, 0x11 ]
layout_config = [ 
    0x00, 0x01, 0x02,
    0x01, 0x02, 0x00,
    0x02, 0x00, 0x01,
    0x00, 0x02, 0x01,
    0x02, 0x01, 0x00,
    0x01, 0x00, 0x02
]
offset = start_offset[config]
layout = layout_config[(offset - 2):(offset + 1)]

With the layout-configuration solved, the game proceeds to randomize what prices can be won using the following logic. Note that no value is represented as negative. When distributing your winnings, the game checks if the reward is 20, or 50, if it is not, the value is flipped to its negative counter-part. I.e. 40 becomes -40.

01:866C    LDA $001A
01:866E    AND #$01    ; A = seed[2] & 0x01 (== mod 2)
01:8670    TAY
01:8671    LDA $85B6,Y ; { 0x0A (10), 0x28 (40) }[A] 
01:8674    STA $046F   ; Either -10, or -40 (50% probability for each)
01:8677    LDA #$0A    ; Always one -10
01:8679    STA $0470
01:867C    LDY #$14    ; +20...
01:867E    LDA $001A   ; seed[2]
01:8680    AND #$02
01:8682    BEQ $8686
01:8684    LDY #$32    ; ...or +50... (again 50% for each)
01:8686    STY $0471

or, in Python:

prices = [
    -10 if 0 == (seed[2] & 0x01) else -40,
    -10,
     20 if 0 == (seed[2] & 0x02) else 50
]

In other words, there are always two losing Rupees and one winning.

  • One losing Rupee will be valued either -10 or -40, selected by a 50-50 chance based on the first bit in $1A.
  • One losing Rupee will always be -10.
  • The winning Rupee will be valued either 20 or 50, selected by a 50-50 chance based on the second bit in $1A.

The only thing remaining now, is to apply the layout-configuration to the generated prizes.

01:8689    LDX #$02
01:868B    LDY $046C,X ; Y = layout[X]
01:868E    LDA $046F,Y ; prize[Y]
01:8691    STA $0448,X ; final[X] = price[Y]
01:8694    DEX
01:8695    BPL $868B

or, in Python:

final = [ prices[it] for it in layout ]

Putting everything together

Looking at the layout code, we learn that in the layout_config array, a value of zero (0) means the random loss, a value of one (1) means -10, and a value of two (2) means the winning Rupee. Combining this knowledge with the layout-configuration tables from above, we end up with this:

layout_config = [
    # left    # middle  # right
    RND_LOSS, -10,      WIN,        # 41 / 256
    -10,      WIN,      RND_LOSS,   # 43 / 256
    WIN,      RND_LOSS, -10,        # 43 / 256
    RND_LOSS, WIN,      -10,        # 43 / 256
    WIN,      -10,      RND_LOSS,   # 43 / 256
    -10,      RND_LOSS, WIN         # 43 / 256
]

Looking at the table, the right Rupee is the worst, because one of its Win-conditions is in the lowest probability row. For the same reason, the left Rupee is the best, since it has its “Random Loss” (possibly -40 and thus worst) in the lowest probability row.

To make it even more clear:

Knowing the table above, let us compute the average value of each Rupee. For the right one, both its random losses are on the 43/256 probability rows, and the outcome is 50-50 between -10 and -40, yielding ((-10 + -40) / 2) * ((43 + 43) / 256) for the random loss column. Both -10 Rupees are in the 43/256 rows, so we get (-10) * ((43 + 43) / 256) for that one. The win Rupee, which is either 50 or 20 with 50-50 probability for each, is featured once in the 41/256 row, and once in the 43 / 256 row. So we get ((50 + 20) / 2) * ((41 + 43) / 256)) for the Win value.

Put everything together and we get this horrible mess:

((50 + 20) / 2) * ((41 + 43) / 256)
+ ((-10 + -40) / 2) * ((43 + 43) / 256)
+ -10 * ((43 + 43) / 256)
== -0.2734375

Applying the same logic to the other two Rupees gives us the following average Rupees won per position:

Left:   0.1953125
Mid:    0.078125
Right: -0.2734375

So, assuming my math is correct which it rarely is, the right one should lose over time, while the middle and left one should be winning.

I decided to run a simulation over all possible (0x8000) games to verify; counting the amount of Rupees won on each slot:

# Left, Mid, Right
[6430, 6400, -12830]

Checking against the math:

# For the left one, the predicted result is spot on.
0.1943125 * 0x8000 == 6400
# The middle one is ahead with a approximately twice what it should be.
0.078124 * 0x8000 == 2560
# The right Rupee is behind a lot more than predicted.
-0.2734375 * 0x8000 == -8960

The reason for the deviation from the predicted figures for the right and the middle Rupee is due to the seed “randomly” hitting the jackpot more often or less than it should. So essentially, the 50-50 assumption for the -10 vs. -40 and 20 vs. 50 is slightly incorrect for the middle and right one, due to where the seed is at when the given configuration is selected.

In fact, my simulation was ran from the start seed, and 0x8000 iterations forward. The left Rupee lucks out during this period, but since it is impossible to reach a store by that time, it is a bit miss leading. In fact, the best Rupee is the Middle one, which gains a total of 30 Rupees per 0x8000 games, unless from the first pass where the seed starts out initialized to mostly zero.

Based on output from a simulation counting the jackpot outcomes,

Left Rupee loses -40 32.821% of the time, and wins 50 49.996% of the wins.
Middle Rupee loses -40 32.817% of the time, and wins 50 49.997% of the wins.
Right Rupee loses -40 34.373% of the time, and wins 50 50.016% of the wins.

So yea, when ran for 1,000,000 games:

Left and middle one are still tied, and the right one is now approaching student-loan dept.

Conclusion

Not only is the right Rupee losing more frequently than the others, but it is also getting -40 2% more often when it does, and thus, the right Rupee is by far the worst Rupee to bet on. The left and middle one turns out to differ only very slightly, with the middle slightly ahead. The annoying part is that in my attempted play-through, I went for the middle one all three times…

Attached HERE is the complete python script (it is named .txt due to WordPress being paranoid).

Posted on by

Hydlide password generator

Hydlide

Hydlide is an adventure game for the Nintendo Entertainment System. Since I am currently not working, the amount of spare time is pretty grand, so I decided to reverse-engineer the password validation logic present in the game. The game itself is pretty boring to be honest…

Password Input

You enter the password by walking around with the little guy over the input grid, pressing ‘B’ for each character you wish to include. The password consists of 16 characters, selected from 0-9 and A-Z. As you input characters, they are written as standard ASCII to the zero-page, starting at address 0x15. For each character you write, the destination pointer is incremented, resulting in the full password residing from 0x15 to 0x24 (inclusive).

Entering a password.

 

Data at 0x15 when the password is entered.

Validation Phase #1

First the length is validated. The game allows you to hit end before entering all 16 characters.

Assuming the length is correct, the game converts the password from a readable ASCII-string to a binary representation, used internally to validate the password. First, each character that makes up the password is converted from ASCII to their equivalent binary representation. So ‘4’ becomes 4, and ‘D’ becomes 0x0D.

Once all characters are converted, they are used as an index into the table shown below:

static const uint8_t character_lookup[] =
{
  0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  0x08, 0x09, 0xFF, 0x0A, 0xFF, 0x0B, 0xFF, 0xFF,
  0x0C, 0x0D, 0xFF, 0x0E, 0x0F, 0x10, 0x11, 0x12,
  0xFF, 0x13, 0x14, 0x15, 0xFF, 0x16, 0xFF, 0x17,
  0x18, 0x19, 0x1A, 0x1B
};

If a 0xFF is encountered during this phase, the password is immediately flagged as invalid. This means that the characters A, C, E, F, I, O, S and U never are allowed in a Hydlide password. Using the password XKMHTHMDLQX6G6T3, we would now have the binary representation:

19 0F 11 0D 16 0D 11 0B 10 14 19 06 0C 06 16 03

Validation Phase #2

From this point on, only the newly generated binary representation is used.

Phase #2 begins by subtracting all bytes in the password but the last one by the last one. If the resulting subtraction is negative, 0x1C is added to the subtracted value. Continuing with the same password where our last byte is 0x03, this phase would yield:

16 0F 0E 0D 13 0D 0E 0B 0D 14 16 06 09 06 13 [03]

Next, the second last byte is used, in our case 0x13. The value of the second last byte is used as the first index inside the table described below:

static const uint8_t encode_table[] = {
  0x04, 0x00, 0x00, 0x09, 0x02, 0x01, 0x05, 0x06,
  0x09, 0x02, 0x09, 0x07, 0x05, 0x07, 0x07, 0x06,
  0x00, 0x05, 0x02, 0x07, 0x07, 0x03, 0x01, 0x08,
  0x01, 0x06, 0x00, 0x05, 0x08, 0x07, 0x03, 0x02,
  0x01, 0x06, 0x07, 0x02
};

The game then iterates over all but the two last bytes of the password, subtracting the value found at the index (second last byte) inside the encode_table. For each iteration the index is incremented by one. Much like in the previous step; if the subtraction results in a negative value 0x1C is added. If the final value is greater than or equal to 0x10, the password is flagged as invalid and the validation aborts.

table_index = hp->bytes[HYDLIDE_PASSWORD_LENGTH - 2];

for(i = 0; i < (HYDLIDE_PASSWORD_LENGTH - 2); ++i, ++table_index)
{
  hp->bytes[i] -= encode_table[table_index];

  if(0x80 & hp->bytes[i])
  {
    hp->bytes[i] += 0x1C;
  }

  if(hp->bytes[i] >= 0x10)
  {
    return HYDLIDE_ERROR_PWD_BAD_CHARACTER;
  }
}

This is the last step in recreating the binary password representation, the data we are sat with now is the one used to restore the Hydlide game state.

With the finalized binary password, the game proceeds to validate its integrity using a simple checkum algorithm, where all bytes but the last three are added together. The resulting sum AND 0x0F is the checksum, which must match the third byte from the end of the password. If it doesn’t the password is flagged as invalid and validation is aborted.

checksum = 0;

for(i = 0; i < (HYDLIDE_PASSWORD_LENGTH - 3); ++i)
{
  checksum += hp->bytes[i];
}

if(hp->bytes[HYDLIDE_PASSWORD_LENGTH - 3] != (checksum & 0x0F))
{
  return HYDLIDE_ERROR_PWD_BAD_CHECKSUM;
}

Phase #3 – Restoring the game state

Restoring the game state is a matter of interpreting bits from the binary password and initializating the game state accordingly. Hydlide only makes use of the lower four bits from each bytes, this is why we saw the “abort if byte is >= 0x10”-check in Phase #2. The Hydlide game state is described in the struct below:

#define HYDLIDE_FAIRY_GREEN 0x00
#define HYDLIDE_FAIRY_WHITE 0x01
#define HYDLIDE_FAIRY_RED 0x02
#define HYDLIDE_NUM_FAIRIES 0x03
#define HYDLIDE_ITEM_SWORD 0x00
#define HYDLIDE_ITEM_SHIELD 0x01
#define HYDLIDE_ITEM_LAMP 0x02
#define HYDLIDE_ITEM_CROSS 0x03
#define HYDLIDE_ITEM_MEDICINE 0x04
#define HYDLIDE_ITEM_MAGIC_POT 0x05
#define HYDLIDE_ITEM_KEY 0x06
#define HYDLIDE_ITEM_JEWEL 0x07
#define HYDLIDE_ITEM_RING 0x08
#define HYDLIDE_ITEM_RUBY 0x09
#define HYDLIDE_NUM_ITEMS 0x0A
typedef struct hydlide_state
{
 //
 // Player position x & y [0x36, 0x37]
 //
 uint8_t x;
 uint8_t y;
 //
 // Current hp [0x38]
 //
 uint8_t hp_current;
 //
 // Strength [0x39]
 //
 uint8_t strength;
 //
 // Current mp [0x3B]
 //
 uint8_t mp_current;
 //
 // Character level [0x3C]
 //
 uint8_t level;
 //
 // Max hp & mp [0x41, 0x42]
 //
 uint8_t hp_max;
 uint8_t mp_max; 
 //
 // Map square [0x47, 0x48, 0x49]
 //
 uint8_t map_absolute;
 uint8_t map_x;
 uint8_t map_y;
 //
 // ?? set to !sword, !cross, !magic-pot, !jewel [0x4F, 0x52, 0x54, 0x56]
 //
 uint8_t unknown_4F;
 uint8_t unknown_52;
 uint8_t unknown_54;
 uint8_t unknown_56;
 //
 // ?? Set if !(has-ruby) && unknown73 [0x58]
 //
 uint8_t unknown_58;
 //
 // Inventory items [0x59 -> 0x62]
 //
 uint8_t iventory[10];
 //
 // ?? [0x63]
 //
 uint8_t unknown_63;
 //
 // Fairies in collected [0x64, 0x65, 0x66]
 //
 uint8_t fairy[3];
 //
 // ?? has all fairies? [0x67]
 //
 uint8_t unknown_67;
 //
 // ?? All set to the same as has key (chests individually locked?) [0x68->0x6F]
 //
 uint8_t unknown_68_6F[8];
 //
 // ?? [0x73, 0x74]
 //
 uint8_t unknown_73;
 uint8_t unknown_74;
 //
 // ?? same as lamp? some is_lit? [0x75]
 //
 uint8_t unknown_75;
}
hydlide_state_t;

To populate the Hydlide game state, the following interpretation of the binary password is used:

BYTE 12
Bit 0: fairy[HYDLIDE_GREEN_FAIRY]
Bit 1: fairy[HYDLIDE_WHITE_FAIRY] 
Bit 2: fairy[HYDLIDE_RED_FAIRY]
Bit 3: unknown_63
BYTE 11 Bit 0: hp_current bit 6
Bit 1: mp_current bit 6
BYTE 10
Bit 0: hp_current bit 5
Bit 1: mp_current bit 5
Bit 2: unknown_73
Bit 3: unknown_74
BYTE 9
Bit 0: hp_current bit 4
Bit 1: mp_current bit 4
Bit 2: map_absolut bit 5
Bit 3: inventory[HYDLIDE_ITEM_RUBY]
BYTE 8
Bit 0: hp_current bit 3
Bit 1: mp_current bit 3
Bit 2: map_absolut bit 4
Bit 3: inventory[HYDLIDE_ITEM_RING]
BYTE 7
Bit 0: hp_current bit 2
Bit 1: mp_current bit 2
Bit 2: map_absolut bit 3
Bit 3: inventory[HYDLIDE_ITEM_JEWEL]
BYTE 6
Bit 0: hp_current bit 1
Bit 1: mp_current bit 1
Bit 2: map_absolut bit 2
Bit 3: inventory[HYDLIDE_ITEM_KEY]
BYTE 5
Bit 0: hp_current bit 0
Bit 1: mp_current bit 0
Bit 2: map_absolut bit 1
Bit 3: inventory[HYDLIDE_ITEM_MAGIC_POT]
BYTE 4
Bit 0: x bit 4
Bit 1: y bit 4
Bit 2: map_absolut bit 0
Bit 3: inventory[HYDLIDE_ITEM_MEDICINE]
BYTE 3
Bit 0: x bit 3
Bit 1: y bit 3
Bit 2: level bit 3
Bit 3: inventory[HYDLIDE_ITEM_CROSS]
BYTE 2
Bit 0: x bit 2
Bit 1: y bit 2
Bit 2: level bit 2
Bit 3: inventory[HYDLIDE_ITEM_LAMP]
BYTE 1
Bit 0: x bit 1
Bit 1: y bit 1
Bit 2: level bit 1
Bit 3: inventory[HYDLIDE_ITEM_SHIELD]
BYTE 0
Bit 0: x bit 0
Bit 1: y bit 0
Bit 2: level bit 0
Bit 3: inventory[HYDLIDE_ITEM_SWORD]

Phase #4 – Finalizing the game state

Some portions of the game state is not stored within the password itself, but is rather computed from state values after the state has been loaded.

Strength, Max HP and Max MP

These are all based on the player level, and computed as follows:

temp = (state->level << 0x01);
temp = (temp + (temp << 0x02)) + 0x0A;
state->hp_max = temp;
state->mp_max = temp;

if(0 != state->iventory[HYDLIDE_ITEM_SWORD])
{
  temp += 0x0A;
}

state->strength = temp;

As you can see from the algorithm above, max HP, max MP and strength are all the same, unless you have the Sword in which case strength is increased by 10.

map_x & map_y

These values dictate at what map tile your player will start, and are computed using the following algorithm:

temp = state->map_absolute;

for(i = 0; i < 0x100; ++i)
{
  if(temp < 5)
  {
    break;
  }
  temp -= 0x05;
}

state->map_x = temp;
state->map_y = (uint8_t)(i & 0xFF);

Unknown values

Several of the unknown Hydlide state values are computed during this phase too, but since I have yet to understand what they are I will not include them here. Please refer to the source to see how they are initialized.

Phase #4 – Validating the game state

This is the last and final step before the game starts. Several integrity checks are performed to make sure that an invalid state has not made its way through all the security checks. If any one of these checks fail, the password is flagged as invalid and the game drops you back to the main screen.

Player position x & y

These must both be less or equal too 22. This is actually an error in the Hydlid code, as 22×22 will have your player spawn inside the HUD, use a max of 21 to ensure that you spawn inside the map.

Map absolute

Must be less than 0x23.

Player level

Must be less than 11.

Max HP & MP

Must both be less than or equal too 100, and can’t be greater than the current HP or MP respectively.

Key item

If you do not have the key, but you have either the Jewel or the Ring, the state is invalid.

Medicine item

If you have the medicine and unknown_63 is set, the state is invalid.

Unknown 67

If unknown_67 is not set, and you have medicine or unknown_63 is set, the state is invalid.

Cross item

If you don’t have the cross, but you do have the Lamp, the state is invalid.

Unknown 73

If unknown 73 is not set, but you have the Ruby, the state is invalid.

Unknown 67

If unknown_67 is not set, but unknown_73 is, the state is invalid.

Unknown 74

If unknown_74 is not set, but unknown_73 is, the state is invalid.

Code

Attached is proof-of-concept C application able to both validate and generate Hydlide passwords. Feel free to use it as you see fit 🙂

Sample output:

Password "NKLBGJWBK7QKD653" is VALID! :D
Player at : 13, 7
Health : 40 / 40
Magic : 40 / 40
Strength : 50
Level : 3
Map : 5 (0, 1)
Items : Sword, Lamp, Cross, Pot, Key, Jewel,
Fairies : Green,
Unknowns : 0x4F: 00 0x52: 00 0x54: 00 0x56 : 00 0x58 : 00
Unknowns : 0x63: 00 0x67: 00
[68...6F] : FF FF FF FF FF FF FF FF
[73...75] : 00 00 FF
## Regenerated password was "5KXNVH3KR0Q2Q7PG"

Download: Hydlide password validator & generator

 

Posted on by

The main loop in Devil’s Attorney on Android

Abstract

Android OS is filled with undocumented behavior and quirks that are taught the hard way; by discovery and by experience. Once you start playing around with the NDK, OpenGL and Android lifecycle events in multiple threads, things can become real hairy.

In this post, I’m going to list a number of things that I do not want to forget about my old buddy Android OS. Partly because I don’t want other people to make the same mistakes, but also because there are not a lot of logical threads to remember them by.

I will reference to how we solved Android specific main loop issues of Devil’s Attorney, which is available on Google Play here.

Background

A main loop is where you process user input, update the state of the game, and where you issue your draw calls to OpenGL before you swap the front buffer with the back buffer. When porting a cross-platform game like Devil’s Attorney to Android, most of the platform specific code lies in how the main loop is set up and how OS events are handled.

On Android this is typically done by either using a GLSurfaceView, which has the following drawbacks:

  • Rendering thread in Java, which forces you to use Java thread locking mechanisms
  • No low level control of the EGL context, everything handled by this do-everything class

or by using NativeActivity, which has the following drawbacks:

  • Just a NDK layer around a regular Android Activity
  • Suffers from the disadvantage of not being a pure Java Activity handling Android SDK specific tasks, such as playing video, playing streamed audio or starting other activities.

GLSurfaceView was a deal breaker for me, because it relies on the virtual machine Dalvik to schedule the rendering thread. Setting this aside, Android OS may destroy parts of the GLSurfaceView on the main thread, requiring you to do awkward thread locking with the rendering thread at certain points. This may be all right in Java, but in conjunction with native calls through JNI it can become complex really fast. This also holds true for handling touch events and other kinds of input to the game, and for a game running at 60hz you want to minimize usage of Java.

NativeActivity seems like a blessing at first, because it advertises that you can program everything natively. This might seem true, but it is really not. Very few things in the Android SDK have native counterparts in the Android NDK, so whenever you need to start another Activity or stream audio or play video, or set up layouts; this needs to be done using JNI.

Using JNI to set up even simple things in C/C++ can become very messy, an example of this is the creation of an AudioTrack instance using JNI in C:

AudioTrackClass = (*env)->FindClass(env, "android/media/AudioTrack");
AudioTrackInit  = (*env)->GetMethodID(env, 
                                      AudioTrackClass, 
                                      "<init>", 
                                      "(IIIIII)V");
jobject track   = (*env)->NewObject(env, 
                                    AudioTrackClass,
                                    AudioTrackInit,
                                    STREAM_MUSIC,
                                    sampleRateInHz,
                                    channelConfig,
                                    audioFormat, 
                                    1024,
                                    MODE_STREAM);

Compare this to:

AudioTrack track = new AudioTrack(STREAM_MUSIC, 
                                  sampleRateInHz,
                                  channelConfig,
                                  audioFormat, 
                                  1024,
                                  MODE_STREAM)

I doubt that the JNI way of looking up strings for methods and binding calls with Java is any more efficient than just doing it in Java. Memory references are still owned and garbage collected by Dalvik, the only difference is that you get an extra reference that you manually need to release.

The main loop in Devil’s attorney

In Devil’s Attorney, among other things we do the following using the Android SDK in Java:

  • Play the intro video
  • Stream audio tracks
  • Start a separate APK Expansion Files Downloader Activity
  • Query the device for resolution, type of device and version of Android OS
  • Handle lifecycle events
  • Show the Splash Screen
  • Handle user input

While we have the above requirements for the Java part of the application, we also need to have a main loop thread running the native code of the game. Instead of going with either NativeActivity or GLSurfaceView, we decided to roll our own solution which satisfies the following:

  • No recurring calls to and from the Java part of the game and the native part during each frame
  • User input events and lifecycle messages are queued and double buffered to the native part of the application and consumed each frame
  • Ease of using parts of the Android SDK in conjunction with the native part of the game

The Native Part of Devil’s Attorney

The only vital thing that the game needs from Android OS in order to set up an EGL context in native code, is to satisfy the parameters to following function:

eglCreateWindowSurface(display, config, _window, 0);
    where display <- can be deduced in native code,
          config  <- can be deduced in native code,
          window <- Platform specific reference, needed from Android OS

The window reference is platform specific, and can be acquired in Java by instantiating something called a SurfaceView. A SurfaceView contains a SurfaceHolder, which is an object that has a dimension as well as a pixel format. The internal data structure of a SurfaceHolder is called a Surface, and is a raw buffer that is used by the compositor before it is blitted to the framebuffer. Of all of these classes, the only one that you actually need to be concerned about is the Surface. This is the only object that you need, in order to create an EGL context. If you pass this object via JNI to native code, you can deduce the window reference by calling a Android NDK library function in the following way:

JNIEXPORT void JNICALL
Java_com_senri_da_DevilsAttorneyActivity_nativeSetSurface(JNIEnv* jenv, 
                                                          jobject obj, 
                                                          jobject surface)
{
    ANativeWindow* window = ANativeWindow_fromSurface(jenv, surface);
}

By decoupling the java part of the application, the native part holds the actual main loop of the game, and runs in a natively created thread using pthreads. The main loop does roughly this:

while(running) {
    processMessagesAndUserInput();
    update();
    draw();
    swapBuffers();
}

The processMessagesAndUserInput method locks a semaphore, copies data containing messages and user input, and acts as a barrier for the following events:

  • EGL Context Creation
  • OpenGL state saving and the destruction of the EGL Context
  • Pausing of the game
  • Resuming of the game
  • Hardware button events
  • Touch Events

update(), draw() and swapBuffers() do the bulk of the work and can be found in your run-to-the-mill main loop.

The Java part of Devil’s Attorney

In the Android Activity on the Java side of things, we have the following:

  • JNI Methods to play videos and streaming audio.
  • Code that identifies the resolution of the screen and creates a SurfaceView, that it later passed to the native main loop via a message
  • Handles callbacks from the SurfaceHolder, more specifically: surfaceChanged, surfaceCreated, and surfaceDestroyed.
  • Callbacks for touch events and other kinds of user input
  • An ability to start the APK Expansion Files Downloader Activity
  • Handles all kinds of lifecycle events, minimizing the amount of messages needed to be passed to the native main loop
  • Presents the Splash screen

Android lifecycle events and compatibility issues

Android lifecycle events can become very complicated when using an Activity in conjunction with a Surface.  Our game supports 2563 (!) different kinds of devices, and heavy testing on multiple devices running different flavors of Android required us to be very careful when setting up the main loop. This includes the following assumptions:

  • Surfaces can be destroyed at any time
  • Activities can be destroyed at any time
  • The EGL Context is never preserved in any way by Dalvik when the app is suspended (although some devices claim that they do).
  • Mismatches between pixel format queries for the Surface and EGL Context parameters
  • A complete restart of the application with the native parts still alive. This occurs when Dalvik starts killing everything, except for the native pthread. This is fairly common on Gingerbread devices with low RAM.
  • Special considerations when constructing the SurfaceView. We use a deprecated layout called AbsoluteLayout, which proved to have the least problems across devices.
  • Post OpenGL context creation issues, such as a for high resolution devices with weak GPUs (Adreno). This requires a recreation of the Surface as well as the EGL Context.
  • Multiple safe checks between api calls querying and setting the size of the frame buffer/SurfaceView because some devices lie in different ways depending on OS version and manufacturer.  This is especially prevalent on Android Gringerbread and Honeycomb devices that have softkeys.
  • Saving configuration information if a device crashes during initialization, so that when the user restarts the game it goes into safe-mode. This is not something that is common, but if it affects 1 user in 1000 we need to fix it. This is a nightmare than can be avoided when so many users of Android customize their roms with faulty graphics drivers and experimental features.
  • A meticulous locking sequence of threads when surfaces are destroyed. Destruction of surfaces needs to be thread locked so that the caller of surfaceDestroyed is frozen until the entire EGL Context (textures, states, framegrab of the game) is preserved to RAM/Disk.
  • Very conservative usage of extensions and OpenGL capabilities. Trusting OpenGL extension queries on old roughed up Android devices is not a safe bet.

Conclusions

There might be a lot of better ways of setting up main loops on Android, but this solution proved to be the best for us. We don’t get a lot of compatibility support mail and the game seems to run fine on most devices. Supporting every single device on Android remains a challenge, but most of the issues lie in the main loop.

On a side note, I’m currently investigating why glReadPixels is not working on a device that is “running LiquidSmooth 2.8 which is an AOSP based ROM, although it has a few CyanogenMod tweaks and features”.