Fake saving with passwords (Megaman style)

I was thinking about a really old way of "saving" a game with passwords, without actually saving anything.

For those not old enough to remember, Megaman used some kind of grid where you'd check a dot or not, and the combinaison would be your password and would unlock the levels and weapons you already got on your last play.

Now, if I were to do a quick-and-dirty way for a simple 9-levels platformer with just a couple of weapons, I know I could hack my way easily on a 10x10 grid where every grid square locks/unlocks something, but that would be SO easy to figure out, it would pretty much be unuseable. Manually entering a code for each combinaison would of course soon become out of hand with all the different possibilities.

What whas the logic behind those passcodes generation? Some games generated strings as well. I'd like to learn more about that if anyone has resources, links, ideas... so far my researches has not been that enlightening...

To me, the best password-entry design ever is Ardy Lightfoot on SNES. As a kid, I spent more time trying to hack that than actually playing the game...

And yes, I know this is 2020, and I also know how to save and load from disk files :)
 

GMWolf

aka fel666
One thing you can do is have a checksum column.

For an N×M grid of data, do some nah on it to generate an extra Column (N+1).
When entering a password, compute the same checksum on the N×M grid, and check if it matches column N+1.
That way not all passwords are valid.


If you already have a grid, you could treat each row or column as a binary number, and then string them together in a string.
By keeping your columns just 5 bits long you can ensure you it have real characters.

Again, a checksum system will ensure you have valid and invalid passwords (and that FFFFFFF doesn't unlock everything!)
 
Last edited:

FoxyOfJungle

Kazan Games
Well, in my opinion, what you can do is define pre-defined strings with the passwords of each level, with an array you can do this, for example:

GML:
level_pass[0] = "AKF543D";
level_pass[1] = "MF6DSG9";
level_pass[2] = "B4MS483";
level_pass[3] = "UF4HF6G";
Then, you compare the values when verifying the password (use a loop to verify all the values), if the entered password is equal to one of these values obtained through the loop, you go to the established room.

The above process would be done without saving any files or progress, just like games like The Lost Vikings, but it's just an example.

 
Yeah, like I said, it can be pretty simple for just locking/unlocking a game with n levels.
But think for a moment if you had also a secret weapon in each stage...the array now becomes n^n. And the complexity even increases if you'd want to "save" number of lives left, for example, would be n^n^max_lives, or something like that. Even for a NES-like 8-levels game, that seems like A LOT of typing.
Maybe my math or my thinking is not correct here, but it feels off still...

One thing you can do is have a checksum column.

For an N×M grid of data, do some nah on it to generate an extra Column (N+1).
When entering a password, compute the same checksum on the N×M grid, and check if it matches column N+1.
That way not all passwords are valid.


If you already have a grid, you could treat each row or column as a binary number, and then string them together in a string.
By keeping your columns just 5 bits long you can ensure you it have real characters.

Again, a checksum system will ensure you have valid and invalid passwords (and that FFFFFFF doesn't unlock everything!)
That hidden column is something I think could get me moving foward! Brillant!
Would you think it'd be viable having a (n+1)-by-8 grid where every "dot" except those of the last row each trigger each a different bit in the byte, and then go from there?
I'm guessing that way would enable me to convert to a string somehow easiee, too.
Am I on the right track with all this?
 
Last edited:

Nidoking

Member
Really, what you're looking for is an alternative encoding method for the information you already have. I'll admit that I've never actually done this before, but the approach seems simple, with steps that are complex. First, obviously, you need to have a way to serialize your save data into a string or number/collection of numbers. (I'd recommend a number-based system because strings would be mostly ASCII, which cuts down on the potential randomness.) Then, you'd need to provide a two-way translation between this serialized data and your chosen password scheme. I would expect that the Megaman approach would be to convert the whole thing into a giant (theoretical) binary number and use dots for the ones and empty spaces for the zeroes, or perhaps use ternary and have blue and red dots. This would essentially be a matter of turning each element of data you have into a relatively prime number, then adding together the numbers for the elements you're saving. Then, to read the password, you'd have to figure out which set of numbers adds to the value you retrieved. There are probably specific sets of numbers that would make that easier, like powers of 17, but that does run the risk of some positions being predictably empty for most of the passwords.

Something like Metroid offers more possibilities, because you've got lots of characters to work with. You could encode the data in binary, then take groups of six bits and turn them into one of 64 characters, for example (52 letters and then 12 symbols). If you want to be really clever about it, you could also use some of the characters in the password as dummy characters. For example, suppose that your password turns out to be 19 characters long. Make it an even 20, and come up with 64 distinct random orderings of the first 19 characters. When generating a password, randomly choose one of those orderings, arrange the password by it, and stick the character that tells you which order it is at the end (or into a specific position that will never change). The same progress can now be represented as 64 different passwords, but it's unlikely that players will notice or figure out how it all works. You could do this with a Megaman-style password as well, encoding an order into the grid and reading the remaining bits that way.

You also almost certainly need some kind of constant mask of bits to XOR with the generated numbers, just so your passwords are never a long string of zero characters.
 

GMWolf

aka fel666
Would you think it'd be viable having a (n+1)-by-8 grid where every "dot" except those of the last row each trigger each a different bit in the byte, and then go from there?
I'm guessing that way would enable me to convert to a string somehow easiee, too.
Am I on the right track with all this?
Seems reasonable.
No doubt you will run into snags; those types of systems often require some edge case handling.
But I think the only way to find out what they are is to encounter them as you write the system.
But as a general direction: seems pretty good to me.


One thing to consider is if you want your internal representation to be a grid, or if that's just how you want to present it to the player, and have something a little more descriptive internally.
 
@Nidoking that colored-dot idea is great. I think I'm starting to put this together. Maybe not beautiful, but I think would work.
Basically assigning each colored dot a value, and a grid where every cell has a unique value. Then do some maths and checks on the dot->grid relationship. There could be some logic where the sum of the color values indicates variable_1 value (say which stage is unlocked), and the sum of the grid cell placement indicates variable_2 (say which weapons are unlocked).
There could be "special cells" for bool, or cells that instantly invalidates any password when a dot is in it....

Plus, the colors would cut back on the size of the grid needed (visually) and the amount of 1994-like coding on my part.

Thank you guys.
 

GMWolf

aka fel666
@Nidoking that colored-dot idea is great. I think I'm starting to put this together. Maybe not beautiful, but I think would work.
Basically assigning each colored dot a value, and a grid where every cell has a unique value. Then do some maths and checks on the dot->grid relationship. There could be some logic where the sum of the color values indicates variable_1 value (say which stage is unlocked), and the sum of the grid cell placement indicates variable_2 (say which weapons are unlocked).
There could be "special cells" for bool, or cells that instantly invalidates any password when a dot is in it....

Plus, the colors would cut back on the size of the grid needed (visually) and the amount of 1994-like coding on my part.

Thank you guys.
Just make sure you plan to allow colour blind people to use it ☺
 

Nidoking

Member
cells that instantly invalidates any password when a dot is in it
I would avoid this in general. If you want the system to be difficult to crack, then the greater the variance, the more difficult it will be. A dot that isn't filled in any valid password is easily dismissed by people trying to manufacture valid passwords. I also wouldn't tie any specific password element to an element of game data. Ideally, you'd transform the saved data using something similar to a hash before rendering it into a password, but reversible so you can get the original data back from the password. Just so that flipping one bit of game data results in a completely different password. The random ordering would also help with that, because even the same data could generate many different passwords.
 
Just make sure you plan to allow colour blind people to use it ☺
You mean the same people that probably can't even read this forum? :p
Wish I had to care about that, as only me and a couple select friends enjoy the games I made, hahaha.

A dot that isn't filled in any valid password is easily dismissed by people trying to manufacture valid passwords. I also wouldn't tie any specific password element to an element of game data.
Yeah, I admit tying one would be kind of stupid, but I still like the idea of either kill-cells, or color-restricted ones. I'm not going for the full-blown bullet-proof thing, but something solid enough to prevent "accidental" entries, yet simple enough to remember or write down easily. It's just for learning, the fun of coding and having my friends go "nice". Thinking it could be useful for HTML games, tho it'd had to be solid AF (which I probably can't do that easily).

You brought a point that I'm actually right in the middle of thinkering, is that should multiple passcodes should be available for the same output.

But so far, I'm trying a 5x5 grid with 3 colors of dots. Each grid cell has a unique base value, and a flag for a restriction.
Each of the colors have 1) a unique base value, 2) a unique multiplier for each rows and 3) a unique modifier for each column.

So far all works (still in the middle of it, tho, it can go wrong any minute, now!), but this has the possibility of multiple outcomes if I don't pick my base values right so that a unique TOTAL VALUE variable can be reached with multiple dot positionning...

You gotta love problem solving!
 

TheouAegis

Member
I can actually weigh in on some of this. While I haven't actually looked too deeply into the Mega Man algorithms, since most people just feel compelled to write out every possibility rather than actually explaining the complex algorithm involved, I have looked at other password systems. I even transcribed (but not translated, that's one of my pet projects I may attempt to tackle at a future date) the Castlevania III password algorithm, which showed me some of the strengths and weaknesses of such password systems.

First off, regarding a dummy cell: Having a dummy cell requires you to have an intricate understanding of your password algorithm, if you want a true algorithm. They also make your algorithm less flexible, since if you want to make any changes to your game, such as extra stages or extra items, you'd have to change the dummy cell or work around it. They are also very easy to crack and only work against very casual gamers.

Many games, like Zombies Ate My Neighbors, just stored every password inside a giant array and then the password algorithm would just loop through the entire array checking each entry against the one entered by the player. These games only cared about what stage you would start on. Notoriously, this meant you started later levels with all the weaknesses you had in the first level, if the game involved collecting or grinding.

Some games, like Metroid and Kid Icarus, use complex algorithms that can store vast amounts of variable data, but in turn can be creatively broken (e.g., "ICARUS ANDTHE ARROWS FLYING"). These were also some of the least-liked algorithms, since they were a pain to write down and were susceptible to game-crushing typos. These kinds of passwords relied heavily on bit manipulation via multiplication, division, OR, XOR, and look-up tables.

Mega Man 2 supposedly toggled 2 bits per boss, with 1 bit meaning the boss was alive and the other bit meaning the boss was defeated. Just going off a quick glance, the password is two bytes and each cell mapped to a particular bit in the password (hard-coded). Some cells mapped to the same bit. If both bytes ORed together didn't equal 15, the password failed. Like I said, it was just a quick glance. I've seen people mention the energy tanks rotate the bits, but I haven't seen that code yet. I've seen people mention whatever value you put in row A determines which cells you need to fill out based on simple addition with a modulo, but I haven't seen that code yet (I did test it and it worked, but it required a cheat sheet). And cell A5 apparently doesn't get read. The point is, Mega Man 2's password is a teensy bit more flexible than ZAMN's, but not by much. I'm compelled to study it more later tonight.

Castlevania III combined all of these elements. It had cells mapped to bits, like in Mega Man. It used extensive bit manipulation like Metroid, and it had a few hard-coded modifiers (e.g., "HELP ME"). The player's name, difficulty level, and stage determined the password. Each icon in the CV3 password had a value of 1 to 3 and placing it inside a cell added that cell's value to the password, each cell itself having a value that was a multiple of 4. I think the password was 5 bytes long, but I can't remember. Unlike Mega Man 2, which required 9 dots placed in specific locations, CV3 could have anywhere from 2 to 12 icons, making it harder to fudge your way.
 

GMWolf

aka fel666
Here is a stupid brilliant approach:

have a loop that loops through all the different combinations:
Code:
for(var level = 0; level < maxLevel; level++)
for(var weapon = 0; weapon < maxWeapon; weapon++)
for(var unlockA = false, unlockA != true; unlockA = true)
for(var unlockB = false, unlockB != true; unlockB = true)
...
{
  //body
}
Then for each combination generate a random string of number:
Code:
...
{
   var code = "";
   for(int i = 0; i < passLength; i++)
  {
    code += irandom(0,9);
  }
...
}
put the random string and combinations into a map:
Code:
...
ds_map_add( global.passwordMap, code, {
  level: level,
  weapon: weapon,
  ...
});
and voila, you have a map of passwords to game states.
By setting the seed before generating the level you can ensure every run has the same passwords.

the final code could look something like this:
Code:
random_set_seed(42);
global.passwordMap = ds_map_create();
for( var level = 0; level < maxLevel; level++)
...
{
  var code = "";
  for(int i = 0; i < passLength; i++)
  {
    code += string(irandom(0,9));
  }

global.passwordMap[? code] = {
    level : level,
    ...
  }
}
then when "saving", loop through every entry of the map and find one that matches the current save state, return the key for that.

this is a assuming you dont have an intractable number of combinations of course.
 
What is wrong with this forum I can't even attach a 3Mb gif to a post...anyway...some screenshots will have to do!
Moving foward, I can see why it's no bueno to restrict cell->dot relationship, except where there could potentially be 2 cells with the same value on some combinaisons. I still have to make it a little more foolproof and then reverse-engineer myself to generate passwords based on the CELL_SUM result.
Basically, each row and column have a value, a cell base value being the product of that. The dot has a modifier based on it's color. Add all that up to get the total "score", or password.
Having that big a number as a result makes me thinking I could "store" a big bunch of variables and flags if I cleverly bitwise-operate the heck out of that.

and voila, you have a map of passwords to game states.
By setting the seed before generating the level you can ensure every run has the same passwords.
This gets me thinking... is there a way I could retreive some sort of unique computer ID, then generate a seed from that? Passcodes wouldn't be able to be shared between players, tho there's an obivious downside than one's passcode can't carry over a different machine...but still would work ok for "most" users, I guess.

Some helpful documents I found outlining several games' password systems.
Will read that for sure, thanks!

@TheouAegis Thanks for the tips! Lot of food for the brain after a day of coding, I will have to read that back again tomorrow, lol. In the meantime, a quick game of CV seems appropriate, I havent played that in probably 15 years, "educational purposes" is an amazing excuse!!
 

Attachments

kburkhart84

Firehammer Games
This gets me thinking... is there a way I could retreive some sort of unique computer ID, then generate a seed from that? Passcodes wouldn't be able to be shared between players, tho there's an obivious downside than one's passcode can't carry over a different machine...but still would work ok for "most" users, I guess.
I'm not familiar with the actual implementation of these things(which is why I hadn't chimed in until now, though I'm looking and learning). However, in my opinion, in no way should you have the machine determine the password. This feels bad to me for multiple reasons.

1. Machines get replaced...you wanna make the player play through the game over again?
2. Sometimes its better to let the players "cheat." Not only do you empower them, but if a player if extremely frustrated with a level and just wants to skip it, a friend can help them with the password, and they keep playing...if that's impossible, they may just quit...which is bad.
 

TheouAegis

Member
Basing the password on the player name in Castlevania 3 was questionable enough already. And even then, there were only 8 sets of passwords, since CV3 ANDed the namesum into the algorithm, so even if your name was different from your friend, you could still possibly use your friend's password.. Like kburkhart said, you shouldn't restrict the password to one particular machine.


Castlevania III -- from someone using (an older version of) GM with code examples, no less
The name of that person seems familiar...
 
I'm not familiar with the actual implementation of these things(which is why I hadn't chimed in until now, though I'm looking and learning). However, in my opinion, in no way should you have the machine determine the password. This feels bad to me for multiple reasons.

1. Machines get replaced...you wanna make the player play through the game over again?
2. Sometimes its better to let the players "cheat." Not only do you empower them, but if a player if extremely frustrated with a level and just wants to skip it, a friend can help them with the password, and they keep playing...if that's impossible, they may just quit...which is bad.
100% agree. Point 2) makes me think again about Ardy Lightfoot, where the passcode screen was a platform level with some 4-5 different blocks (I think they were fruits, or something of the sort) which you'd place in various spots, the combinaison of which determined the passcode entered. You had to leave the screen to see if it worked (and that would reset the blocks position), so that "prevented" blindly spamming passwords (but not to the 13 years-old I was in 1999, loll).

Reading that Megaman 2 article is eye-opening, tho. Thinking adding colored dots to the system as a way of storing more variables, each variable having a color, or something like that...
All in all, this kind of passeord system is clearly a case of MANY MANY possible ways of doing basically the same thing. The only difference being how unhackable, expandable and reuseable you want it to be, it seems.
 

TheouAegis

Member
So the Mega Man algorithm uses a 2-byte array. Byte 0 is for dead bosses, byte 1 is for alive bosses. There are 20 possible cells for each boss, each mapped to a particular DOA bit and byte. These default values are what will be referenced strictly when cell A1 is set. As you should know by now, cells A1 thru A5 are for Energy tank quantity in order.
Code:
var testETANK = 0;
var bitDOA = [0,0];
var bitROBO = [00,01,00,16,04,32,00,08,16,128,08,02,04,00,01,64,128,02,32,64];
var byteROBO = [00,00,00,00,01,00,00,01,01,00,00,01,00,00,01,01,01,00,01,00];
Each cell in the password grid is has a sequential value, starting with 0 for A1 and going up to 24 for E5. However, once one of the ETank cells has been counted, it skips down to the next row of cells immediately. This is how the number of ETanks affects the other 20 main cells. So if A2 (cell 1) is set, the code jumps to B2 (cell 6) and thus cell B2 use B1's DOA mapping; likewise if A4 is set, B4 will have the same DOA mapping as B1. What this amounts to is a "rotation" of the cells, so B2 becomes B1 and B1 becomes E5.
Code:
for(var i=0; i<4; i++;) {
    if cellPW[i] {
        testETANK = n;
        break;
    }
}

i += 5;
for(n = 0; n<20; n++;) {
    if cellPW[i] {
        bitDOA[byteROBOT[n]] |= bitROBO[n];
    }
    if ++i == 25
        i = 5;
}
The code then checks if all bits have been set between the two bytes. An XOR would have been more logical, but OR is fine since the game forces the player to use just 8 bits. Naturally, for each boss, if its dead bit is set, its corresponding weapon bit is set. The transport items were granted at the same time as the weapons. The bosses with bit value 1 (Heat Man) and 2 (Air Man) provide ITEM-1 and ITEM-2 respectively, so just a simple "& 3" is all that's required to fetch the item bits there. The boss with bit value 32 (Flash Man) provides ITEM-3, so we need to get his bit value down to the next available item bit; 32 divided by 8 is 4, which is the lowest available bit for ITEM-3.
Code:
if bitDOA[0] | bitDOA[1] != 255 {
    return error.message;
}

global.WEAPONS = bitDOA[0];
global.ITEMS = (bitDOA[0] & 3) | (( bitDOA[0] & 32) >> 3);
global.eTANKS = testETANK;
I didn't look at the encoding algorithm because I have to get up for work in 6 hours. 😭 It should be fairly easy to derive based on this, however. Also, you cannot have more than 4 ETanks using the password since A5 is actually skipped. And as you can see, there are no "dummy" values used to trick gamers trying to make up passwords arbitrarily. If a cell happens to be a "dummy" in Mega Man 2's set of possible codes, it's simply because of a "flaw" in the password algorithm. I think there might be a game or two that uses a "dummy", but I'm sure they're uncommon.
 
Last edited:
So the Mega Man algorithm uses a 2-byte array. Byte 0 is for dead bosses, byte 1 is for alive bosses. There are 20 possible cells for each boss, each mapped to a particular DOA bit and byte. These default values are what will be referenced strictly when cell A1 is set. As you should know by now, cells A1 thru A5 are for Energy tank quantity in order.
Code:
var testETANK = 0;
var bitDOA = [0,0];
var bitROBO = [00,01,00,16,04,32,00,08,16,128,08,02,04,00,01,64,128,02,32,64];
var byteROBO = [00,00,00,00,01,00,00,01,01,00,00,01,00,00,01,01,01,00,01,00];
Each cell in the password grid is has a sequential value, starting with 0 for A1 and going up to 24 for E5. However, once one of the ETank cells has been counted, it skips down to the next row of cells immediately. This is how the number of ETanks affects the other 20 main cells. So if A2 (cell 1) is set, the code jumps to B2 (cell 6) and thus cell B2 use B1's DOA mapping; likewise if A4 is set, B4 will have the same DOA mapping as B1. What this amounts to is a "rotation" of the cells, so B2 becomes B1 and B1 becomes E5.
Code:
for(var i=0; i<4; i++;) {
    if cellPW[i] {
        testETANK = n;
        break;
    }
}

i += 5;
for(n = 0; n<20; n++;) {
    if cellPW[i] {
        bitDOA[byteROBOT[n]] |= bitROBO[n];
    }
    if ++i == 25
        i = 5;
}
The code then checks if all bits have been set between the two bytes. An XOR would have been more logical, but OR is fine since the game forces the player to use just 8 bits. Naturally, for each boss, if its dead bit is set, its corresponding weapon bit is set. The transport items were granted at the same time as the weapons. The bosses with bit value 1 (Heat Man) and 2 (Air Man) provide ITEM-1 and ITEM-2 respectively, so just a simple "& 3" is all that's required to fetch the item bits there. The boss with bit value 32 (Flash Man) provides ITEM-3, so we need to get his bit value down to the next available item bit; 32 divided by 8 is 4, which is the lowest available bit for ITEM-3.
Code:
if bitDOA[0] | bitDOA[1] != 255 {
    return error.message;
}

global.WEAPONS = bitDOA[0];
global.ITEMS = (bitDOA[0] & 3) | (( bitDOA[0] & 32) >> 3);
global.eTANKS = testETANK;
I didn't look at the encoding algorithm because I have to get up for work in 6 hours. 😭 It should be fairly easy to derive based on this, however. Also, you cannot have more than 4 ETanks using the password since A5 is actually skipped. And as you can see, there are no "dummy" values used to trick gamers trying to make up passwords arbitrarily. If a cell happens to be a "dummy" in Mega Man 2's set of possible codes, it's simply because of a "flaw" in the password algorithm. I think there might be a game or two that uses a "dummy", but I'm sure they're uncommon.
Yeah, all very clever, especially the part where the ET dictates the position of the other dots. Simple, yet super brillant.

I did had a little bit of a dream about passwords last night (lol), and something crossed my mind. I'm thinking about scaling down the grid from 5x5 to a 3x3 grid, where EVERY square must be filled with colored-dots. One dot could dictate the required position of the others as in MM, and if I look at a SUDOKU grid, there's only one possible outcome per grid, so I guess I could use that to validate the entered passwords. I'll give it a go later today, I think it could simplify it all a lot.
But looking back, I can see why they decided to automatically unlock the weapon when you beat the boss, just "saving" an extra variable seems like a quantum leap in complexity, versus just saving what stage you're at.
 
Sooooo, I think I came up with something quite good, if I may say so myself!
Same principle as before, but simplified a lot. 3x3 grid, with the base cell value dispatched as follow:

1 - 1 000 - 1 000 000
10 - 10 000 - 10 000 000
100 - 100 000 - 100 000 000

Then there's n colors of dots available (no more than 9), each with a multiplier going fron 1 to n.

Dot_multiplier*cell_base_value will not overlap or ever conflict with one another since none can add up to more than n (which is <= 9).

Once filled, you'll end up with a sequence looking like
xxx xxx xxx

Then, with a couple (or a lot...) of checks and div, you can hardcode some results and then be good to go (finally!) to the game start with all your variables set as they were before.
Same principle as the bit operations, but with (to me), much better readility.

My project is way too much of a mess to share, but I think it's one of the things that everyone does with their own little twist anyway.

I love those problems that get solved on the can, hahahaha!
 
Last edited:
Top