#5053 - NovusAmor - Fri Apr 18, 2003 5:09 pm
I'm trying to figure out how to condense about 252 bits of data into a 7 letter(A-Z, 0-9) password. Does anyone have a good method or algorithm that could achieve this or something similar? For example look at the original Metroid(NES) password.
Robert
www.neopong.com
#5055 - sgeos - Fri Apr 18, 2003 5:38 pm
A to Z is 26 possibilities, 0 to 9 is another 10 possibilities. 36 possibilities to the power of seven (seven digit password) is 78364164096 possibilities.
2 to the power of 252 requires over 75000000000000000000000000000000000000000000000000000000000000000000000000000 possibilities.
There is no solution for the problem you describe. Here is a working solution: A to Z is 26 possibilities, 0 to 9 is another ten. Cut a few characters that look the same so that we only have 32 possibilities total. That comes out to one character per 5 bits. 252/5 is over 50, so we'll need 51 characters to store this data.
51 characters times 5 bits = 255 bits. 252 bits are used for the password, that means that there are 3 bits that can be used for security. 2 to the power of 3 = 8. One in every 8 passwords entered will be valid.
You'll need to write something that will pack and upack you 5 bit characters into you actual data. I could have just said this at the start, but I think you need to cut down on the data that you are storing using your password. Storing thing like money and life as an exact figure are very expensive when it come to the number of bits available.
Personally, I always figure out how many possibilities my password system gives me, including security bits at this stage. I figure out what I can actually store from there.
I like 10 security bits, or one in every 1024 passwords is valid. =)
-Brendan
#5056 - pollier - Fri Apr 18, 2003 5:42 pm
It seems to me that in raw form you're only going to get about 35 bits of data stored on those 7 characters; even with some kind of compression I really doubt you can fit that much data in so few characters. You probably either need to save less information, restructure it, or use more characters.
I don't know much about Metroid passwords, but they're variable length, which might mean they're compressed. (???)
EDIT: sgeos beat me to the punchline! Read his, it's a lot more comprehensive.
_________________
(Works for me!)
Last edited by pollier on Fri Apr 18, 2003 5:44 pm; edited 1 time in total
#5057 - NovusAmor - Fri Apr 18, 2003 5:44 pm
That's basically the same conclusion I came to. Unfortunately I've got to figure something out since the publisher doesn't want to spend the extra money on an EEPROM. Are there any tricks I might have over looked such as having ranges that are the same multiple or lookup tables?
NovusAmor
#5059 - pollier - Fri Apr 18, 2003 6:11 pm
Seven characters is simply not enough...
Look-up tables would work, with a big sacrifice in accuracy; also, if your game is stage-oriented there's probably lots of assumptions you can make when loading the data, ie. lots of state flags for key points can be revamped if one can't be set without the other being previously set.
I just hope you're not trying to encode a non-linear RPG's savegame :)
_________________
(Works for me!)
#5060 - sgeos - Fri Apr 18, 2003 6:20 pm
Even non-linear RPG savegames can be done using a password system. You need to keep track of what the "current quest" is, progress for that quest, and completed quests.
-Brendan
#5061 - pollier - Fri Apr 18, 2003 8:40 pm
Well, technically, everything can be saved with a password system, but once you start encoding RPG savegames it gets a bit unreasonable. I was assuming the player wants to store his/her stats, party, inventory, etc. as well as the quests <-- which would still take quite a number of characters for any 'normal' RPG these days...
_________________
(Works for me!)
#5062 - tepples - Fri Apr 18, 2003 10:15 pm
| sgeos wrote: |
| Here is a working solution: A to Z is 26 possibilities, 0 to 9 is another ten. |
According to EGM, Nintendo has not allowed vowels in passwords since about the Super NES era because parents have complained about games giving obscene sexual slang as passwords.
| Quote: |
| Cut a few characters that look the same so that we only have 32 possibilities total. |
Many Super NES games such as Mario Is Missing! and Tetris Attack used variations on the following alphabet:
$0123456 789BCDFG HJKLMNPQ RTVWXYZ_
(the $ replaces the S that looks like 5).
| Quote: |
| Personally, I always figure out how many possibilities my password system gives me, including security bits at this stage. |
My preference: Squeeze the state into 32 bits and use 8 checksum bits for a total of 40 bits or 8 characters.
| pollier wrote: |
| once you start encoding RPG savegames it gets a bit unreasonable. |
Darn straight. The 48-character passwords in The Lord of the Rings for Super NES were a female wolf.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#5063 - sgeos - Fri Apr 18, 2003 10:23 pm
> Well, technically, everything can be saved with a password system, but
> once you start encoding RPG savegames it gets a bit unreasonable.
> I was assuming the player wants to store his/her stats, party,
> inventory, etc. as well as the quests <-- which would still take quite a
> number of characters for any 'normal' RPG these days...
It can't be a 'normal' RPG as such. You'll probably want to recreate player stats from their level/exp values/quests complete and hardcoded pseudorandom seed numbers. If it is a choos your own party RPG, then the seed number will be part of the password. Equipment needs to be restricted to "levels".
Really the inventory is the killer. Even 8 items for 3 characters is a lot of bits! Storing exact amounts of cash/xp is also a problem. This can be solved by using something like c[xp] * v, where c[xp] is a hardcoded constant based on your XP level and v is the number of bits that are set aside for this type of thing.
-Brendan
#5064 - sgeos - Fri Apr 18, 2003 10:29 pm
> According to [i]EGM[/i], Nintendo has not allowed vowels in passwords
> since about the Super NES era because parents have complained about
> games giving obscene sexual slang as passwords.
I did not know that. Sounds reasonable.
> My preference: Squeeze the state into 32 bits and use 8 checksum bits
> for a total of 40 bits or 8 characters.
Not unreasonable. I'd probably just sqeeze it doen to a set of 32bit states and then pass each one through a reversable RNG.
[quote="pollier"]once you start encoding RPG savegames it gets a bit unreasonable.[/quote]
Darn straight. The 48-character passwords in [i]The Lord of the Rings[/i] for Super NES were a female wolf.[/quote]
I still suspect that the origninal Japanese version of Dragon Quest II for the NES beats them all =) It was the equivalent of 3 sentences in hiragana!
-Brendan
#5067 - mbcook - Sat Apr 19, 2003 3:55 am
Exactly what are you trying to encode? If you could tell us what the things are (and how big each one is in bits) then I'm sure we could find a way to cut that a decent ammount.
Other than that, your best using a battery backup ram or something. That's alot for a password. I think the above is the best idea.
_________________
--Michael
#5074 - tepples - Sat Apr 19, 2003 4:36 pm
| sgeos wrote: |
| and then pass each one through a reversable RNG. |
Such as which ones? Do you know of any good ciphers using a 32-bit block size?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#5106 - sgeos - Mon Apr 21, 2003 3:28 am
>> and then pass each one through a reversable RNG.
> Such as which ones?
I couldn't find any, so I had to write them on my own.
> Do you know of any good ciphers using a 32-bit block size?
Good, no. I wrote it myself. =P The "mixer" algorithm I wrote does use a 32 block size though. It preformed better on the statistical tests than I ever could have hoped for. The chi square results indicated it as a suspect non-random sequence. It uses the fibonacci sequence and an internal state the shifts and combines itself based on the fibonacci component.
-Brendan
#5119 - NovusAmor - Mon Apr 21, 2003 3:55 pm
Sorry but I can't really disclose the exact info to store. I have however, after hours of staring at the design doc, reduce the number of bits by about half.
As far as mixers go I've looked at compression and encryption techniques and none offer what I really need. Compression/encryption is not a guaranteed size every time. I thought rijndael might work but I'm not sure what the laws are for exporting it so I'm not going to consider it.
I was hoping someone might have an example from an old school game that they could tell me about.
_________________
Robert
Senior Programmer
NeoPong Software, Inc
www.neopong.com
#5131 - sgeos - Mon Apr 21, 2003 6:59 pm
| NovusAmor wrote: |
| I was hoping someone might have an example from an old school game that they could tell me about. |
It uses nowhere near the magnatudite of bits that you requre, but I'll explain the Megaman 2 password system.
Each rows has 5 columns. The top row is simply your number of energy tanks, from zero to four. After that there are two cells for each boss, one of them is used if the stage remains to be beaten, and another if it has been cleared. There is a different map of stage on/off cells for every number of energy tanks.
-Brendan