Monday, August 27, 2012

Second hand stores

I love going through second hand stores. I find all sorts of neat trinkets and toys from years ago. Most recently, I found a Skannerz toy, from sometime in 2000. Still works, and it even had batteries in it.

I got to playing with this, and I got to thinking... Nothing really similar has been done lately, to my knowledge. With smartphones booming, the majority of them including cameras, there's no reason you couldn't do everything this toy does and more with the hardware that people are already carrying around.

And so an idea was born. I love when this happens.

I know there's barcode reader apps out there for Android, and if I remember correctly, you can take advantage of those apps from other apps. So I don't even need to write the barcode reader side of things. That's a huge portion of the work gone, right there.

So now we need a way to get a monster out of an arbitrary barcode. The first thing that came to mind is just using the numbers in the barcode itself. But then I remembered that those barcode reader apps also do QR codes, and NFC tags are starting to become more common. So we need a way to do it from not just an arbitrary barcode, but an arbitrary string, of arbitrary length and content.

New plan. Hash whatever data we get, so we get a fixed length and a fixed set of characters, and then use that hash to do your monster generation. Easy enough. MD5 has a fixed length, and is hexadecimal, and has been around long enough that there's implementations is pretty much every programming language out there.

Now, we need a way to get a monster out of that hash. MD5 isn't collision proof, but for what we're doing, it might as well be. This means we can't just use the raw MD5 hash to say "hey, this is monster". We need a way to make collisions happen. So we start dividing up the hash.

The easiest way to do this is to just grab specific characters and look at those. But that still leaves us with way too much room to work with in some ways, and not enough in others. My current thinking is that I'll grab a few bytes(MD5 results in 16 bytes. I'm thinking groups of four.), add those bytes together, and modulo 256 that result. This gives us much smaller numbers, and gives us a few "fields".

I'm thinking the first field would be a "type" or "group"(Or "expansion set") thing, so you could have different groups of monsters, items, etc.. Second field would be which actual item/monster that one is. Third field could be a "variation"(Think shiny pokemon). Fourth field could be a seed for a random number generator, for battle stats and things like that. This gives you room for expansion, down the road.

The problem here is that same expandability, though. The way I see it, there's two options here. You either leave a good chunk of hashes useless at the start(If you managed to fill out 64 full groups, you're still only using a quarter of all possible hashes out there. That's a lot of failed scans.), or you start out "wrapping" the hashes, and when you expand it later, some of your previous scans no longer lead to the same thing...

I don't really like either of these options. The first one leads you to a lot of failed scans(That using 64 full groups example? That's 16,384 items/monsters.), and the second one leads to confusion when you release the expansions, 'cus all these barcodes people had found don't necessarily point to the same thing anymore.

One option is to reduce your expandability, so there's less failed scans. This is probably a good idea, 'cus I really don't think you're going to use 65k item/monster slots(Even pokemon hasn't gotten that far yet). But there's still the problem of not maintaining a consistent successful scan rate, or causing confusion when all your barcodes change meaning with new expansions...

This is where I'm at at the moment. I'll need to think on this more.