Level Storage and Management Overhaul

Alright, I think I covered everything I was going to say. You can go ahead and read this post in its entirety.

So here's something for you to work on after you finish the main overhaul. After completing this overhaul, the game will be much closer to its first release version. So what is this? We need a new system for the way levels are created, saved, stored, loaded, manipulated, and selected. The way we will accomplish this is using Level UUIDs. A UUID, or Universally Unique Identifier, is a way of assigning a unique string of characters to each "thing" in a system (whatever said thing may be), that will never coincide, or at least isn't supposed to coincide, with any other UUID in the system. In our case, those "things" would be levels, and the system would be every single user running any version of Blockade on any machine. So in other words, we want to assign a unique identifier to every level that anyone creates using our game. By using UUIDs, we can easily track player progress on any given level, regardless of if the name or any other defining attribute of that level (besides the UUID of course) is changed between play sessions. We need them to be unique, or else if a player were to download two levels with the same ID, they would somehow have the same score and progress on two completely different levels.

So the real question is how we're going to actually generate these UUIDs so that they are always unique. We could just store all existing UUIDs in a database, and every time a player creates a level check to see if that UUID is already taken, but then using the level editor would require an Internet connection. Now, there are actually standards for UUIDs in place, and the most common type of UUID is UUID v4, which is basically just a randomly generated string of hexadecimal values. Assuming these strings are perfectly random, yes, it is technically possible for two to coincide, but with such a long string of characters the probability is negligible. But that's assuming they're perfectly random. Of course they aren't, because computers rely on pseudorandom number generators (PRNGs). I don't really understand how PRNGs work entirely, but I can sort of sum it up like this: given a "seed", a PRNG can generate an indefinitely long sequence of values which will seem random, but theoretically, if another PRNG of the same type were given the same seed, it would generate the exact same sequence of values. It's not like I really understand where PRNGs get their seeds, but I assume it's from some weird arbitrary values from some kernel processes happening within the system. In that case, there's a chance that two machines could end up with the same seed given similar circumstances, and unlike the chances of two truly random number generators generating the same value within a large enough domain, this probability is decidedly not negligible. I honestly haven't the slightest clue why UUID v4 is used so commonly with such a glaring flaw, but there you have it.

Anyway, there's an older variant of UUID called UUID v1, which uses a different process to obtain unique identifiers. This one is actually surprisingly similar to an idea I had completely on my own. This variant of UUID takes your system's MAC address and mashes it up against your system's timestamp, to create a unique value that could only reproduced if you took the exact same computer and rewinded the system clock, and timed the creation of another UUID to the exact millisecond that the first one was created. Seems like a great solution, but in another dumb moment from whoever came up with this UUID stuff, it doesn't use a hashing algorithm. That means that given the UUID of a level, someone could basically figure out the MAC address of the level creator's system and the time they made it, without any difficulty at all. A strange decision, and while I don't know if there is any danger in someone else having your MAC address, the whole thing just seems weird.

In case you were wondering, UUID v2 and v3 exist, and so does v5. UUID v2 is almost the same thing as v1, and since it's not used nearly as often as the other four variants I haven't really read up very much on it, but due to the significant problems with UUID v1, I don't think it's something we should be concerned with. UUID v3 and v5 are basically the same thing, with v3 being a deprecated version that became the target of a security exploit, and v5 being the newer version. Both of these work differently from the other three, however; instead of simply creating a UUID from scratch, they take in a piece of data in the form of a string, and basically convert that into a unique UUID. Since we don't have any unique piece of data to feed into such an algorithm, I think we can throw these two variants out the window also.

I think our best bet is to use a "custom" version of UUID which would work the most similarly to v4, in which we combine the system's MAC address, the system timestamp, and a pseudorandomly generated number to create an identifier that is virtually guaranteed to be unique, and then run it through a hashing algorithm so that viewers of the UUID can't derive the level creator's MAC address. Just to make sure you know, hashing algorithms will always provide a unique result given a unique input (although some algorithms aren't proven to give a unique result, the chance that there will be a collision is very negligible). I think this "custom" UUID variant would actually fit the definition of UUID v4 just fine, since even though the outcome is meshed with a MAC address and a timestamp, it is technically pseudorandom (I think, unless the definition of pseudorandom is more narrow than I thought). As far as I know, all pseudorandom means is a number generator that simulates randomness, but isn't truly random, and is predictable to some extent.

One more note: we can always change our UUID generation algorithm later, as long as we keep the output in the same format (which is standardized), since the chance that two UUIDs generated by two separate generation algorithms would collide is the same chance that two truly random UUIDs would collide. So in other words, negligible.

Alright. So regardless of how we generate these UUIDs, we need to set straight how the game would actually use them. Levels in the main game would no longer be identified and stored according to their level number (e.g. level12.json), but rather would be stored using their UUIDs, for example 04e7b5b7-b972-40c8-98b6-ac499abbb271.level (note that the extension is now .level, you'll see why in a minute). The name of the level will move to a new home - within the info section of the JSON, along with creators, creator-scores, flags, and all the other properties that define a level. Just to make it clear, levels created via the editor would be stored in this same way, rather than being saved using their name (e.g. jailbreak.json). Once we implement this UUID system, we can finally consistently store user progress across levels, by storing a file called 04e7b5b7-b972-40c8-98b6-ac499abbb271.progress within the save-data/progress folder (this has a different extension than its level file counterpart, so that it is possible to differentiate between the files). As a side note, since we have the .level extension now, we could implement a feature so that .level files automatically open in Blockade (we might want to have a more unique extension such as .blevel for this reason).

This new system also calls for a bit of an overhaul to the level editor. Currently, when editing a level in the editor, the level isn't actually associated with a level file until you press the Save button and tell the game where to save your level, at which point you can either overwrite the existing file or create a new file altogether. With the UUID system, whenever you opened the level editor a UUID would automatically be generated for the level you were working on, and once you pressed the Save button it would ask you for a level name (along with creators), but it would save the level according to the UUID. I'm still debating whether or not editing a level would give it a new UUID (since progress and scores are tied to the UUID), but either way, every time you opened a level in the editor a UUID would be loaded alongside it, and when you saved the level it would be in accordance with that UUID.

There's one last thing, which is how the levels would be displayed within the level select screen. Since level files are no longer stored according to their level number, we would need a new way to order the levels. So I suggest that we replace the unlocked.json (formerly progress.json) file with a new file, which might have a name along the lines of sequence.json. This file would keep track of the order in which the levels would appear in-game, and would be immutable unless edited directly. Now, the easy way out would be to just make an array of levels, in the order that they would appear. For example:

{
    "levels": [
        "97660c6e-0f10-4323-8f8d-e27d6336408d.level",
        "bb7d2e47-e31b-4ad7-8e02-710609951a51.level",
        "6911704a-7684-443f-a9b7-79492516a24c.level",
        "27ea7dcb-b889-477b-bde5-8324db3d9329.level",
        "cfc1d954-ec18-4d09-b6c1-00ad637a8858.level",
        "01d2f79c-5119-4f3c-85f9-53bb4a8e7084.level",
        "1419a4d2-d9f9-4af0-9d28-ee450b763a8d.level",
        "2b487c4a-7aeb-43e8-817b-b78820a21267.level",
        "d11082cc-13c4-406b-b6f2-56340dc53f79.level",
        "6bcbc1da-dee6-45ca-a121-14963641d9d5.level"
    ]
}

However, the way the game's levels are actually organized is (or will be, once we start adding new mechanics) different. For example, hollow blocks, the game's first new mechanic, shouldn't appear until level 17. The next mechanic won't appear until page 33. In other words, each page of the level select screen introduces a new mechanic. If we don't have 16 finished levels to fill the first page up with, but we want to start putting levels on the second page, we will need a different system. We could just do something like this:

{
    "levels": {
        "1": "97660c6e-0f10-4323-8f8d-e27d6336408d.level",
        "2": "bb7d2e47-e31b-4ad7-8e02-710609951a51.level",
        "3": "6911704a-7684-443f-a9b7-79492516a24c.level",
        "4": "27ea7dcb-b889-477b-bde5-8324db3d9329.level",
        "5": "cfc1d954-ec18-4d09-b6c1-00ad637a8858.level",
        "10": "01d2f79c-5119-4f3c-85f9-53bb4a8e7084.level",
        "17": "1419a4d2-d9f9-4af0-9d28-ee450b763a8d.level",
        "18": "2b487c4a-7aeb-43e8-817b-b78820a21267.level",
        "33": "d11082cc-13c4-406b-b6f2-56340dc53f79.level",
        "100": "6bcbc1da-dee6-45ca-a121-14963641d9d5.level"
    }
}

The problem with this is that every time we wish to add a new level to a page, we have to shuffle every other level upward by one. Besides, it would be weird to do something like I did here, by placing level 10 on the first page with no levels 6 through 9 to fill in the gap. So here is my proposed final solution:

{
    "levels": [
        [
            "97660c6e-0f10-4323-8f8d-e27d6336408d.level",
            "bb7d2e47-e31b-4ad7-8e02-710609951a51.level",
            "6911704a-7684-443f-a9b7-79492516a24c.level",
            "27ea7dcb-b889-477b-bde5-8324db3d9329.level"
        ],
        [
            "cfc1d954-ec18-4d09-b6c1-00ad637a8858.level",
            "01d2f79c-5119-4f3c-85f9-53bb4a8e7084.level",
            "1419a4d2-d9f9-4af0-9d28-ee450b763a8d.level",
            "2b487c4a-7aeb-43e8-817b-b78820a21267.level"
        ],
        [
            "d11082cc-13c4-406b-b6f2-56340dc53f79.level",
            "6bcbc1da-dee6-45ca-a121-14963641d9d5.level"
        ]
    ]
}

It's a list of pages, which are each lists of levels. So the levels listed in that JSON would be levels 1, 2, 3, 4, 17, 18, 19, 20, 33, and 34 respectively. This way levels can easily be added to each page (and pages can easily be added to the entire listing), and it's effortless to organize levels by pages so that they are separated according to their game mechanics. Additionally, this goes back to issue #14; instead of capping the level select at 512 like I initially said, just cap it at the highest page that actually has levels in it. As a note: your program should be prepared to handle a situation where there are 17 or more levels in one page, in which case the game should simply not display those levels.

EDIT: You should see what I said under Issue #14 also.

cooperuser / blockade

Level Storage and Management Overhaul #58

Alright, I think I covered everything I was going to say. You can go ahead and read this post in its entirety.