csanyk.com

video games, programming, the internet, and stuff

Tag: password system

GameMaker Tutorial: Password systems 3: on-screen keyboard

Yeah, I know. Last article, I said in this article we’d cover parsing and validation and converting the password into gamestate data. We’ll get there eventually. But I want to take a detour and show you how to build an on-screen keyboard.

In the first article in this series, I handled the user input simply, by using the get_string_async() function. This is good enough to be functional, but has two main problems:

First, because we’re allowing input directly from the keyboard, the player can enter any characters at all, which means that we’d need to handle characters that are not part of our password’s alphabet. This means extra programming. Not necessarily a bad thing, if that’s what’s right for the user, but it is more work to write up validation scripts that properly handle our Base64 password alphabet.

Second, the user experience of typing a password into a textbox is fine, as far as it goes, but it isn’t at all like an authentic old school keyboard system. This is a somewhat debatable point — old school consoles used on-screen keyboards not because they were better than keyboard entry, but because there was no keyboard. Entering passwords this way is slower and more tedious. But, if we are going to re-create the experience authentically, we need to heed the conventions of the time.

Every onscreen keyboard in the old days was a custom implementation. No two were exactly the same, although there were a lot of commonalities, and most of the differences were cosmetic. The most common implementation was a grid of characters, which the player selected one at a time using the D-pad, pressing a button to enter the character, and another button to go back. When the entire password was entered, typically the player submitted it by pressing the Start button, or sometimes there was an on-screen button that the player would select with the D-pad. We’ll build something like that in this tutorial, although we’ll use the keyboard rather than a gamepad control. Implementing the gamepad controller input capability isn’t too difficult, though, so I’ll probably come back and add that eventually.

The Alphabet and the Font

One of the problems people have with writing down (and later reading) passwords is that certain characters look very similar (such as 0, o O, l, l, 5, S, 9, g, etc.) You can’t help the player’s handwriting, but at least when the game is displaying the characters on the screen, you should be sure to pick a font that makes these characters unambiguous. These symbols are merely labels which stand for a number value, so it doesn’t really matter what they are.

It’s not a bad idea to omit the similar looking characters, although for this tutorial I’m going to stick with the full alphabet. We’ll at least want a font that has very distinct characters to aid the player in recognizing them correctly. Google for “programmer” or “console” fonts, for suggestions on good ones to use, and pick something out that looks right for the style of game that you’re making. Make sure the capital “I” has serifs and the zero has a slash or dot in it, and so on.

The Onscreen Keyboard Object

oOnScreenKeyboard

Create

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!?";
font = fConsole;
var k = 1;
for (var i = 0; i < 8; i++){
 for (var j = 0; j < 8; j++){
 keyboard[i,j] = string_copy(alphabet,k,1);
 k++;
 }
}
row_selected = 0;
column_selected = 0;
instructions_text = "Press A to select letter. Press B to erase letter. Press Enter to submit password.";

input_string = "";
max_input_string_length = 4;

Draw

draw_set_font(font);
draw_set_halign(fa_left);
draw_set_valign(fa_top);
draw_text(10,10, "PASSWORD: " + input_string);

draw_set_halign(fa_center);
draw_set_valign(fa_middle);

for (var i = 0; i < 8; i++){
 for (var j = 0; j < 8; j++){
 draw_text(x+(32*i), y+(32*j), keyboard[j,i]);
 }
}
draw_rectangle((column_selected * 32) - 16 + x,
 (row_selected * 32) - 16 + y, 
 (column_selected * 32) + 16 + x, 
 (row_selected * 32) + 16 + y, 
 true);

Press Button1

(Pick whatever keyboard key you want for this.)

if string_length(input_string) < max_input_string_length {
 input_string += string_copy(alphabet, (row_selected*8) + column_selected + 1, 1);
}else{
 audio_play_sound(snBadPassword,1,false); 
}

Press Button2

(Again pick whatever keyboard key you want for this.)

input_string = string_copy(input_string,1,string_length(input_string)-1);

Press Enter

if validate_password(input_string){
 apply_password(input_string);
 room_goto(rmGameStart);
} else {
 bad_password();
}

Press Up

row_selected = (row_selected + 7) mod 8;

Press Down

row_selected = (row_selected + 1) mod 8;

Press Left

column_selected = (column_selected + 7) mod 8;

Press Right

column_selected = (column_selected + 1) mod 8;

That's it for the Events, but we need to write three scripts for the Press Enter event. These passwords are where most of the implementation-specific code is going to go.

The details of these scripts will vary from project to project, but this is where we'll handle the validation, parsing, and conversion to gamestate data -- what I thought we'd be covering in this article. We'll cover our example versions of them in the next article.

GameMaker Tutorial: Password systems 2: encoding/decoding

As we established in the first article in this series, a game save password stores game state data. In this article, we’re going to talk about the low level details of how this is done. We won’t be talking much about the password itself, or the game state data. We’ll be focusing instead rather narrowly on how to encode and decode the data.

Numeric data

As far as numeric data is concerned, we’re only going to worry about encoding/decoding integers, for simplicity’s sake. For the most part, we’ll be concerned with positive integers, but we’ll cover negative values as well.

Actually, treating numeric GML data values as integers is a little bit tricky, since in GameMaker the only data types available are strings and reals (floating point numbers). For the most part you can treat a number as though it were an integer in GameMaker, as long as you don’t do math on the number that causes the digits after the decimal point to become non-zero values.

If you want decimal values, you can store the value as an integer, and then divide it by 10, or 100, or however many decimal places as you need after you decode it. Or, if you want to store a fraction, you can store the numerator and denominator as integers, and divide them after decoding them.

As long as you don’t deal in fractions and decimals, you can pretend that your numbers are integers, and GameMaker for the most part will act as though they are. This will come up later when we hit the limit for the largest integer value that we can encode using our method (16,777,215). I’ll explain why below, but for now it’s enough to know this should be a large enough value that we don’t really need to worry about trying to encode larger values, at least for most games.

The basic idea is that each character in your password alphabet stands for an integer value. Notice that the complete alphabet (26 upper case + 26 lower case) + the 10 numerals + 2 special characters gives you a range of 64 values; 2^6 = 64, so each character in a password can represent a 6-bit binary value.

A B C D E F G H
0 1 2 3 4 5 6 7
I J K L M N O P
8 9 10 11 12 13 14 15
Q R S T U V W X
16 17 18 19 20 21 22 23
Y Z a b c d e f
24 25 26 27 28 29 30 31
g h i j k l m n
32 33 34 35 36 37 38 39
o p q r s t u v
40 41 42 43 44 45 46 47
w x y z 0 1 2 3
48 49 50 51 52 53 54 55
4 5 6 7 8 9 ! ?
56 57 58 59 60 61 62 63

Beyond 63

What can you do if you want to store a value larger than 63? Simple, you just use a second digit in your base-64 number. Just like the next number after 9 is 10, in base-64 the next number after ? is BA. Until you’ve looked at base-64 numbers for a long time, it’s going to be very difficult to recognize the value represented by a base-64 number, but we don’t need to — we’ll tell the computer to do it for us with some gml scripts.

We said before that a 4-digit base-64 number stores 24 bits, or up to 16,777,215 in base-10. But for some numbers that might be overkill. If we wanted to, we could treat each digit as a single base-64 value, and add them together. For a 4-character base-64 string, this would give us a range of 0-252, nearly a byte. It’s a much less compact way of storing the data, but for small values it’s not too bad.

To do the conversion from base-10 to base-64 and back, we’ll need some gml scripts.

b64_to_dec(b64)

/*
Takes a string of a b64-encoded value and converts it to a real number
*/
var b64_alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!?";
var value = 0;
var digit = 0;
var neg = 1;

if string_copy(argument0,1,1) == "-"{
 argument0 = string_copy(argument0,2,string_length(argument0)-1);
 neg = -1;
}

for (var i = string_length(argument0); i >= 1; i--){
 value += (string_pos(string_copy(argument0,i,1), b64_alphabet)-1) * power(64,digit); 
 digit++;
}

return neg * value;

/*
Takes a real number and converts it to a base-64 encoded string. Supports integer values from 0-16777215.
*/

var b64_alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!?";
var value = abs(argument0);
var r;
var str = ""; 
var done = false;

while !done{
 r = value mod 64;
 str = string_char_at(b64_alphabet, r+1) + str;
 value = (value - r) div 64;
 if (value == 0){done = true;}
}

if (argument0 < 0){
 str = "-" + str;
}

return str;

Lastly, it will be handy to have a function that can pad a B64 encoded string to a specific length:

b64_padded

/*
Takes a base-64 encoded string (argument0) and pads it to padded_length (argument1) with leading "A"'s (0's). 
If the number is negative, the first character in the padded string will be a "-". If the padded_length is 
less than the length of the b64 value, the function returns -1 to signify an error. 

(Note the error code returned is a real number, -1, not to be confused with the correct output of 
b64_padded(-1,2), which would return the *string* "-1") 
*/

//argument0 the b64 string to pad to length
//argument1 the length to pad to

b64 = argument0;
len = argument1;

if len < string_length(b64){return -1;} //too short, return error
if len == string_length(b64){return b64;} //just right; we're already done

var str = "";
if string_copy(b64,1,1) == "-"{
 str = "-";
 len--;
 b64 = string_copy(b64,2,string_length(b64)-1);
}
repeat (len - string_length(b64)){str+="A";}
str+=b64;

return str;

Negative Numbers

The scripts above handle negative values just fine. But the minus sign is not part of the base-64 alphabet. If we need to store negative numbers, we have a few choices.

We can expand our password alphabet to include a minus sign (or an arbitrary symbol that we can use as a substitute).

Or we can designate certain characters in the password to store a boolean which signifies whether a given numeric value stored elsewhere in the password is positive or negative. Then encode the absolute value of the number, and re-combine it later with the boolean that holds the sign.

Or we can sacrifice a bit in our base-64 encoded numbers and treat them as signed integers, such that A-g represent values 0 through 32, and h-? represent negative values -1 through -31.

Beyond 16,777,215?

The encoding/decoding scripts work for values up to 16,777,215, or ???? in b64. This value is (2^24)-1. Beyond that, the numbers do not encode/decode properly. The reason for this has to do with the way GameMaker stores numeric values. All numbers in GameMaker are floating point values. GameMaker uses a 32-bit floating point, of which 24 of those bits are used for the digits to the left of the decimal point. The remaining 8 digits are used for the fractional value to the right of the decimal point. This means that for a number above 16777215, we can’t store the value in a 32-bit floating point variable without losing some precision. This precision prevents us from cleanly encoding a value above 16777215 and decoding it back to the same value. Fortunately, such high values should be rare to encounter in the game state data.

What happens if you try to store a larger value depends on the build target. Some may lose precision, resulting in off-by-one conversions — data corruption. Others may fail to return a value entirely when the conversion script is called, which would result in total loss of the data. Certain build targets (I’m not certain which ones) may use 64-bit floating point values, rather than 32-bit. In this case, we can go even higher, up to (2^52)-1. This is a ridiculously large number, and it’s almost certainly more than enough for any game state value you might want to encode.

Tip for validation

If the password space allows a value larger than the max value for a given game state variable, you can use those larger values as a form of validation check. For example, let’s say that the maximum number of lives in your game is 255. This requires an 8-bit value, but since each character represents 6 bits, and we don’t want to bother splitting characters, we use 2 password characters, which represents 12 bits of data. We can use these additional value space between 256 and 4096 for a validation check.

The simplest method would be to reject any password that contains data in the lives bits that decodes to a value greater than 255. Another way to handle this is to use a math value to obfuscate the lives value. Since 4096/256 = 16, we can take the value of the two characters that we use to encode the lives count as follows: lives x 16 = password substring. Now, when you’re validating the password, you can mod the value of the characters that represent the lives by 16, and if the calculation doesn’t work out to 0, then you know the password isn’t valid.

Or you can make the “right” remainder be dependent upon some other part of the password — for example, when the Level is even, the lives substring should mod16 to 0, but when Level is odd, it should mod16 to 1, unless Level is divisible by 3, in which case… Sneaky/unnecessary complexity like this will make the password harder to understand, and therefore require more effort to crack the password system. Don’t fool yourself into thinking you’re coming up with a super secure uncrackable password, but it will make the password a little less obvious than a simple counter, and for password system crackers, will make the puzzle more fun.

String data

Old NES password games did not typically have any string variables to preserve in a save password. In fact, the few games where you could enter a name were all, to the best of my knowledge, battery backup games that used savefiles.

It’s simple enough to store a string in a password, though, since a password is a string. The only real issue is dealing with variable length strings. For a lot of reasons, it’s probably best to stick with a fixed length for strings and pad shorter strings with spaces, trimming them later when applying the password to game state.

However, it looks weird if your password has string values stored as plain text in the password — it’s an obvious indicator to the player that the password is storing data, which could invite mischief. So it’s probably a good idea to encode the data somehow.

We could encode strings by using the numeric ASCII values of the letters, and then convert them back, character by character. While not encrypting the data, it would be sufficiently obfuscated for our purposes.

I won’t bother implementing this for now, since our demo password only has 4 characters, and in any case it’s not really necessary, but it’s good to have an idea of how we might do it if we decide to later on.

Boolean data

GameMaker doesn’t have a true boolean data type. The boolean constants true and false are equal to 1 and 0 in GML. Boolean expressions in GameMaker are handled by evaluating to a real number, and any number <0.5 evaluates as false, and 0.5 or greater evaluates as true. Therefore, to encode a boolean, all we really need to do is encode a value of 0 or 1. Or any other value that will evaluate to true or false.

But, since a single base-64 character can store up to 6 bits of data, and each bit can store a 0 or a 1, a single character could in theory store up to 6 boolean values, which means a 6x greater density than if we just stored one boolean value in each character.

To achieve this, we need to convert a base-64 value to a binary value, and vice versa. Then we would need to break the binary value into its individual bits, and designate each bit for a specific boolean value.

Note that the next few functions do not really deal with binary values, but rather with strings storing 0 and 1 characters, which we can convert to boolean values by using the real() function.

Edit: I’ve updated these functions with more elegant implementations, and replaced the brute force switch statement lookup table approach that I had here originally. Thanks to Ian Schreiber for the suggestion.

bin_to_dec(bin)

/*
Takes a string of a binary encoded value and converts it to a real value.
*/
var bin_alphabet = "01";
var value = 0;
var digit = 0;

for (var i = string_length(argument0); i >= 1; i--){
 value += ((string_pos(string_copy(argument0,i,1), bin_alphabet)-1) * power(2,digit)); 
 digit++;
}

return value;

dec_to_bin(dec)

/*
Takes a base-10 value and encodes it as a binary string
*/
var bin_alphabet = "01";
var r;
var str = "";
var done = false;
neg = sign(argument0);
value = abs(argument0);

while !done{
 r = value mod 2;
 str = string_char_at(bin_alphabet, r+1) + str;
 value = (value - r) div 2;
 if (value == 0){done = true;}
}

if (neg < 0) {str = "-1" + str;}

return str;

bin_to_b64(bin)

/*
Takes a 6-digit binary encoded string and converts it to a b64-encoded character.
*/

return dec_to_b64(bin_to_dec(argument0));

bin_to_bool(bin)

/*
Extracts the argment1-th bit out of the binary string supplied in argument0 and returns it, converted
to a real number. The real value can be interpreted as a boolean (0=false; 1=true).
Argument0 must be a string consisting only of "0"'s and "1"'s
Argument1 must be a number between 1 and string_length(argument0). 
*/

return real(string_copy(argument0,argument1,1));

bool6_to_bin(bool,bool,bool,bool,bool,bool)

/*
Takes six boolean values and concatenates them to create a 6-bit binary encoded string, 
suitable for converstion to a b64 value with the bin_to_b64() function.
*/

/*
force conversion of arguments to gml boolean constants
*/

if argument0{argument0 = true;}else{argument0 = false;}
if argument1{argument1 = true;}else{argument1 = false;}
if argument2{argument2 = true;}else{argument2 = false;}
if argument3{argument3 = true;}else{argument3 = false;}
if argument4{argument4 = true;}else{argument4 = false;}
if argument5{argument5 = true;}else{argument5 = false;}

/*
concatenate bools to string
*/
return string(argument0) + string(argument1) + string(argument2) +
 string(argument3) + string(argument4) + string(argument5);

bin_padded

//pads a binary encoded string (argument0) to length (argument1)
var bin = argument0;//bin string to pad
var len = argument1;//padded length

if len < string_length(bin){return -1;}
if len == string_length(bin){return bin;}

repeat(len - string_length(bin)){bin = "0" + bin;}

return bin;

These scripts should suffice for encoding/decoding all of our data values.

Advanced password validation with checksums and hashes

Additionally, to keep the player honest, you probably want some kind of tamper-proofing to go with your password encoding. Otherwise, it makes tinkering with the password to cheat too easy. For example, you could play the game, get a password, then get hurt, and get a new password, and by comparing the two, you could infer which characters in the password correspond to your health. Then, you could substitute different values for the password characters that correspond to your health health until you hit upon a value that gave you max health, or, depending on how the game works, even infinite health or invulnerability.

It’s true that deciphering password encoding schemes is a lot of fun, but we don’t want to make the system so easy that it invites cheating. Make the player work at it, and feel like they truly hacked something when they figure out your system.

To do this, we can reserve certain characters in the password for storing checksum values, or even hash values. Understanding hash and checksum math isn’t too difficult, but isn’t terribly necessary, either. We don’t need something impossible to crack, just something functional. There are better checksum functions than I’ll demonstrate here, but this should suffice to make the concept understandable to anyone.

Simple checksum

Using our 4-character example password, we can add an additional two characters for checksum data.

Level Lives Health Ammo Checksum
A-? A-? A-? A-? AA-??

Let’s say the game state data is encoded with the following 4 values from our cipher table, above:

Level Lives Health Ammo
password char B D ? ?
base-10 value 1 3 63 63

A simple checksum for this would be 1+3+63+63 = 130. Of course, this checksum isn’t very strong; any four values for Level, Lives, Health, and Ammo that add up to 130 will have the same checksum. But it does stop someone from changing a single character in the password and getting another valid password.

To add the checksum value to the password, we need to encode 130 as a base-64 value. This would be a 2-digit base-64 number: 22. According to our base-64 encoding table, the value 2 is encoded by the symbol C. So, 22 == CC. So the entire password would be:

Level Lives Health Ammo Checksum
password char B D ? ? CC
base-10 value 1 3 63 63 130

Note that since 63*4 = 252, the highest the checksum value will ever go will be 252, or D8.

If you wanted to get really crazy, you can scramble the order of the characters, shuffling checksum characters in between the data value characters. But we’re not that concerned with obfuscation, so we won’t bother with an example of this.

In the next article, we’ll cover how to design the password specification in greater detail, and write some sample scripts that takes the password, validates and decodes it, and assigns the stored values to re-create the game state.

Part 3

GameMaker Tutorial: Password systems 1: password entry

In old school console games, especially for the NES, it was common to enter a “code” or “password” in order to resume play where you had left off previously. Back in the day, memory was extremely expensive, and very few games implemented a battery backed RAM solution that allowed the player to Save and Restore a game.

Instead, a system of encoding the game state data into a long “password” was often used in lieu of a real save system. In addition to encoding the game state, these password systems often had some kind of validation built into them, so that not just any arbitrary input would be accepted. For fun, sometimes games would have special, secret codes that would enable cheats. For a few players, cracking the encoding system to enable you to configure the gamestate to your exact wishes was a kind of advanced meta-game, excellent for budding young hackers. There is great nostalgia value in these systems if you are into old school retrogaming.

Password systems (general overview)

If you want to build a password save system, at a high level there are a few things you need to do:

  1. Password Entry
  2. Validation
  3. Encoding/Decoding GameState
  4. Password Display

This article will cover Password Entry, while future articles will cover the other topics.

Get the input

For simplicity’s sake, let’s assume a four-character code will encode all the information that we need. In practice, most 8-bit NES games used much more than this, but for a simple input demo this should be sufficient.

The easiest way to enter a string in GameMaker is the get_string_async() function.

save_pw = get_string_async("Enter password", "");

Since get_string_async is an asynchronous function, it does not return a value immediately. We need to add an Async Event to catch the return value when the function calls back to the main program. The correct Async Event to use for this function is the Dialog event. The get_string_async() function doesn’t simply return a string value, though; rather, it returns a data structure called a ds_map, which contains 3 values: an id, a status, and the result. The result is the string that was entered by the player, the password that we are looking for.

We can put the following code in the Dialog Event to handle the return callback:
Dialog Event:

var i_d = ds_map_find_value(async_load, "id");
if i_d == save_pw{
 if ds_map_find_value(async_load, "status"){
 password = ds_map_find_value(async_load, "result");
 }
}

The interface that get_string_async() provides is not very satisfying, aesthetically, but it works well enough for now. (We’ll explore a few other methods later that will more faithfully replicate the “password entry” screens from old NES games, in a future article.)

Right away, we have a few problems with simply getting a string:

  1. Because get_string_async() allows the player to enter any string they want, the player may enter a string of arbitrary length. For our demo, we need them to enter a string that is exactly the right length.
  2. The get_string_async() is not constrained in the characters it will allow the player to enter. Passwords for NES games varied in their alphabets, but many would allow A-Z, a-z, 0-9, and often spaces and special characters. Some games would allow only capital letters, while others would allow lower and upper case. One serious flaw with the old password systems was that the letters were displayed in fonts which often made it difficult to differentiate certain characters, like 1 and l, or 0 and o, etc. Later NES games sometimes corrected for this by using a more distinct font, or by omitting the ambiguous characters from the alphabet entirely.

There are many ways to constrain the allowed characters, but we don’t need to get super fancy with it for our demo.

In the next article, we’ll demonstrate how to decode the password — that is, to translate the password value to game state information. Finally, we’ll demonstrate how to generate and display the password when the game is over (or paused, or at a save point, or whenever it’s appropriate for your game), so that the player can write it down and enter it the next time they play to resume where they left off.

Part 2

csanyk.com © 2016
%d bloggers like this: