Getting saved games to work raised some interesting problems, which I’ll go over here although not in a great deal of detail as it could get to be a very long post!
Checksums
When loading a saved game, I want to know if it was tampered with. This is to avoid cheating – in that if my saved game contained “Herbs:200” it would be very tempting to just change that to “Herbs:200000”, and also to make sure that what I have in a saved game was what I expected after any other encoding (which will come later). The former isn’t just about trying to defeat the evil hackers who want to cheat to prove they’re the best in the world, but also to stop a casual user being tempted to cheating trivially, which generally leaves the unfulfilled and ruins the game experience.
Now, normally this would be trivial and I’d find an MD5 or a SHA-256 from the a library, but since I’ve not worked out how to use third party libraries in the worker yet, and since this is a personal project where I can try to do some fun things, I decided to write this myself.
The checksum process, in its simplest form, takes a byte of data, adds that byte (or xor to avoid overflow issues) into the checksum, then continues with the next byte. This is a very simple checksum, in that if you add one to a single byte in the source, you add one to the checksum too. To make it a bit more complex, I used more than one byte for my checksum and rotate through, shuffling some data around a bit on each cycle so one byte change early on actually affects several bytes of the checksum.
This is not nearly as good as a proper checksum – critically there are still only small changes for a small change in the source data, but it really doesn’t matter too much as I’m really just trying to stop the casual editing of the saved game. I don’t expect any of this to stop someone who really wants to hack their game (regardless, it would be a lot easier to edit the memory of the game while it’s running, for example).
Once I have the checksum for the save game, I add it to the start of the save game string in hex, and that means when I load the game I have the checksum ready to validate.
Compression
My saved game format was pretty much handed on a plate from the message passing I did earlier. It’s a long string, with a lot of symbols in it, and some words that will definitely be repeated. This looks like a prime target for a bit of compression.
For this (again, I have no third party libraries) I used an LZ-style compression algorithm (defined Wikipedia) which looks for strings of text that have already been sent and says look 40 characters back and take the next 23 characters. Note that I’m using UTF16 here, so each character has 2 bytes of data available. Here I first check there’s no ‘\0’ (character code 0) characters in my string (an improvement will be to encode \0 as \0\0, but I didn’t need that). Then when I find a match in the buffer so far for the current string that can be replaced I add \0 followed by 2 bytes of offset in one character and 2 bytes of characters to take in the next. If I can replace 4 or more charactes, I’ve saved space – otherwise I move on.
This means things like “actor=player&actor_name=Esme” would be compressed to “actor=player&[\0,13,5]_name=Esme” – note that the string in the [] is actually three characters. This is perfectly adequate for my needs – there are a lot of duplicated strings in my saved game, so we’re getting about 50% compression on the very short save games I have at the moment. I think once the game gets a bit more complex, it’ll do better than that.
Encoding
The next problem I had was the save game string now has unprintable characters (codes that are below 32), or possibly even invalid characters in it (ie codes that are not in the UTF16 range). Normally, I’d just base64 encode this, but…once again, I have no libraries. I did attempt to use a javascript standard library version, but this wouldn’t encode strings with invalid characters.
There’s lots of instructions about writing base64 encoders and decoders online, although in the spirit of being obscure I used a slightly different system – I just used the characters starting with 0, and didn’t worry about a terminating character as I don’t need that (I can just discard bits left over than aren’t used in a string). There is another small complication, in that the strings in javascript are UTF16, and I can’t convert to a byte array (no libraries!), so I encode 16 bits at a time rather than 8.
Saved Game Result
Once I’d serialised the data, added a checksum, compressed and then encoded, I add a v1: string to the front so I can change the format later. The end result is a save game that looks like this:
v1:d0@H0<30R1`=0L30b0@I0D60Q1`<0D60T1@>0@60`00I0P30b00=0D60b0`H0H60S10<0H60S1@<0D30g0`=0X30V20M0T60S1`J0<70\20>0P30e00=0D30\2@H0<60d1`K0870c10[0H:0V20M0T70`1@I0`:0@10C0440I1@A085000@50@00Y1`K0h60\2000@1060PA0l40B1@@0L40510[0870U1`L0l60e1PL0<60U10[0h40?1PC0000>0@10D60Q1PL0<60X1000h0060@K0460h10E0T60]1@I0`:0b00<0`:0Q1@K0l60e1PK0@7000P20@00d1@J0d60U10C0D60V10M0`:0a0@=0`:0l10[0<6000`50D00a00[0d60_10I0T60V1@J0D6000`L0@00l10[000020010860e1@J0`60T1@J0h60W1000@8040000`00800E0000h1010P4051PD0840O1`A0440B10A0D40>1000H:06000009070P@0D50910C0@4091PC0L4000PY0h0071@@0@5081@A085000PY0X0000P?0@0000PY0L10a0000D:0800<0h20a0000H:0;0000D:0900<0000U2040<60_1`L0@7061000<8060@<0h20b0@=0`:0R1@H0<70U1`@0l60c10M0`:0V2000H6050@<0030`0000X<0500O0000`1P20H:000030D0000PR0D00c10[0H:0=1@E0<5081PD0l40?1@C0000:0P20d30a0`<0L30h0P=0`7000PY0H0000PA0D00m0@=0D30i0P<0D30l10[0050E1@C0050;1@B0h40\2PY000090`10d30b0P=0`70\2PA0`40?1`E0D40B10[0H:000020H00m0P<0<30b0`<003000PL0D00Which looks ok to me. I don’t know if I care about the fact that it has ? which most programs treat as a word break, or that it has < which is a html special character. Overall I don’t think it matters.
A bug!
Once I’d finally got this all done, and used the very simple Storage object to save the string I found a bug! It failed to load because it appeared to includ a single empty string in the research list.
This was because my array encoding system doesn’t have a way to distinguish between an empty array and an array containing an single empty string, as the empty string has no delimiters.
For this I changed my list encoding to dictate that an empty string at the end of a list is ignored. So [] is an empty list, and [,] is a list containing one empty string, and [x,y,] and [x,y] are both a list containing two strings x and y. The last comma is usually optional, but I add it every time when encoding for simplicity.