Hypothetical suggestion for optimizing resync, game joining

Hypothetical suggestion for optimizing resync, game joining

Requests for features in the spring code.

Moderator: Moderators

Post Reply
User avatar
Caydr
Omnidouche
Posts: 7179
Joined: 16 Oct 2004, 19:40

Hypothetical suggestion for optimizing resync, game joining

Post by Caydr »

Ancient, monthly topic rotation, etc, yeah, I came up with an idea that might be useful though.

As I understand it, a big part of the problem with post-launch game joining and other sync-correction events, is the bandwidth required. The host must basically send a full game recording to the person on the other end.

I had an idea that might be able to alleviate this a bit though. I don't know if anyone here is familiar with usenet, but basically you get in a lot of situations like this: you have a big file, divided into chunks. You download all the chunks and then, oh shit, one of them is corrupt. Since it is one monolithic RAR file, the whole thing is scrap right? No, you use some voodoo magic called a PAR file.

When I first learned what a PAR file was, I basically couldn't wrap my head around it because it seemed so completely impossible and yet incredibly simple. The way it works is like this, you take one big file and divide it into smaller chunks. Then you use a program to create PAR files based on those chunks. The PAR files you create can be used to substitute for ANY of the chunks. Example, you get a file that is 80 chunks. Chunk number 44 is corrupt. You download a PAR file for the 80-piece volume, which is the same size as any of the other chunks, and that "generic" PAR file is used to fill in the blank, even though it wasn't made for that specific blank.

Still sounds simple, right? It's a parity file, it knows that the bits should add up to 1010101, but currently they add up to 0000111, so it knows what needs to be done to fill in the blank. Basically it's like a RAID-5 array but made up of a single file. Clever, but not something out of science fiction. Yet.

Go back to the earlier scenario, you have 80 volumes. Lo and behold, 75 of them are corrupt. Download 75 PAR files, based on the complete, intact volume. Use the program to merge them, and you've got the perfect file, all 80 intact volumes of the one large file. This stuff sounds like rocket science to me, maybe not to you, but my mind was blown the first time I actually did this and it worked exactly as advertised.

So my idea of how this could work for Spring is like this. You have an 8-player game, one player drops, you're left with 7 players. Those seven players are still in perfect sync with each other, minus unsynced things that are deemed unimportant for gameplay and therefore don't really matter. The seven players' game pauses when player 8 drops, someone else wants to join in his place. Since all seven players have a perfectly synchronized view of what's going on in the game, their Spring.exe does a quick calculation of what how large each 30-second portion of the game time is, in terms of demo filesize. This is divided out between the players depending on their upload speed. One player might get assigned the whole first 5 minutes because not much happened during that time. Another player might only get assigned 30 seconds because he has a slow connection. Another player might get assigned 10 minutes because he has a very fast upload speed. One player might get assigned to transmit the entire heightmap and how it's changed over the course of the game but nothing else. Each player generates their assigned portion of the synchronized game as a PAR file, and together they transmit it to the new player, who gets the whole thing and merges it, indicates he's ready, and the game resumes.

So... basically I just thought PAR files were totally awesome and they might be valuable for transmitting portions of a complete "image" of the game. I don't think I've ever even seen anyone here use the word PAR so... didn't know if anyone else was aware of how the technology (if I can call it that?) might be able to benefit us. It's all open source AFAIK, look up QuickPAR et al.

If only a snapshot of the game "as it lies" has to be transmitted and not the whole history of it, then you could, for example, divide up the heightmap into 4 sections and have each player transmit part of it, and similarly divide up other things this way.

If this was all useless, sorry, sounded good as I was typing it and I haven't slept in a little bit... :|
User avatar
SpliFF
Posts: 1224
Joined: 28 Jul 2008, 06:51

Re: Hypothetical suggestion for optimizing resync, game joining

Post by SpliFF »

As I was recently reminded this still leaves an issue with firewalls. Not all players can directly contact all others. Also a par file deals with only small corrupt pieces, after a certain point there are too many combinations to create the same parity. RAID 5 parity is basically 1 bit for every byte I think so rather than save bandwidth you're really adding to it. It still needs most of the corrupt data to work properly.

And finally, most important, TCP handles data corruption for us, at least for the network side. Parity is not really compression, it's a error correction tech.
User avatar
Caydr
Omnidouche
Posts: 7179
Joined: 16 Oct 2004, 19:40

Re: Hypothetical suggestion for optimizing resync, game joining

Post by Caydr »

The firewall issue, I don't know what to say about that. Other games must be finding a way around it, I imagine.

Rather than using the PAR technique as compression primarily, I meant for the purpose that... like, say you've got 4 players. One drops. Someone wants to (re)join. The players compress their gamestate as best they can, taking into account where the best compression:time ratio is, PAR the file up, and whatever chunks are able to be transferred from one given client to another, can be transferred.

I'm not an expert on PAR stuff, I just thought it was ossum. Wanted to make sure the developers knew it existed because it seems like the kind of thing that would be very useful. Fault tolerant and it doesn't matter what specific parts that are originally sent become corrupt, you can just include a PAR and it'll patch up whatever's needed. You say TCP handles error correction and I don't know half of dick about that stuff, but isn't packet loss a pretty common thing?
Post Reply

Return to “Feature Requests”