Multiplayer: Hacking A Fix Around OOS Errors

All good points. What I am going to do is add a int counter variable for units/cities that tracks the last allocated id, so the next id will be the last id + 1. This will cause ids to be allocated in order, 0 - 2^32 - 1.

When the id reaches the maximum int value, it will wrap. That's fine. I'll also add a check to ensure an id is not being allocated for an existing unit.

The odds of the id allocation wrapping for a game is infinitesimal. If it does wrap, it will be using ids that were allocated in the very beginning, and likely are no longer referenced anywhere (simply due to being so old). So recycling those ids are likely to be safest.

I finished coding the resync for teams, players, cities, and units (and it all works a SP local game).

I added code to chunk the data up (into 10000 tiny packets...) and discovered the game does NOT send packets in the exact order you send them. So I have to wait for them to all arrive, then re-order.

Afforess said:

All good points. What I am going to do is add a int counter variable for units/cities that tracks the last allocated id, so the next id will be the last id + 1. This will cause ids to be allocated in order, 0 - 2^32 - 1.

When the id reaches the maximum int value, it will wrap. That's fine. I'll also add a check to ensure an id is not being allocated for an existing unit.

The odds of the id allocation wrapping for a game is infinitesimal. If it does wrap, it will be using ids that were allocated in the very beginning, and likely are no longer referenced anywhere (simply due to being so old). So recycling those ids are likely to be safest.

Click to expand...

That sounds safe. The big question is probably what the performance impact of the key lookup is on the id deref (which happens many millions of times per turn on a mature game). The use of a hash will have changed that from O(1) to O(ln N)

So my initial discoveries in using this:

1.) Packets are not sent in order
2.) Packets are also sent to yourself
3.) Packets are sent to everyone, even players you don't care about
4.) The max packet size seems to be ~ default MTU, which is ~1500 bytes, but probably a bit less to be safe. I use 1250 and it seems to work ok.
5.) You can't send thousands of packets per turn slice, the clients will drop. (Probably this blocks some internal EXE heartbeat packet not exposed to the DLL)
6.) The resync process takes 10000-50000 packets to send, naively.

So on the 5th point. I added a std::vector queue to the CvGame object and send 25 packets per turnslice. Sending more begins to make the UI visibly lag. This is on a local network game.

The receiving player stores the incoming packets in a stdext::hashmap, so that when they all arrive, they can be consumed in order. The hashmap key is the packet order number. The value is the packet.

On the 6th point, we can lower the number of packets dramatically, I think. First off, compression. That likely will cut the size in half. That's good, but still if we are sending 5000 packets, 25 packets per turn slice, and 1 turn slice per second (ish), that is 3 minutes to wait to resync a game. Not exactly fast.

The biggest component of the data is the map, and more specifically, the CvPlot objects in the map. I think a checksum system for each player, each team, the game, the map (without tiles), and the tiles, would make it possible to skip resending a large majority of the information. Possibly we could further subdivide the tiles into groups and checksum these groups to avoid resending all tile information as well. This should dramatically decrease the data needed to be sent.

To subdivide tiles into groups my initial thought was simply to use the modulus operator over the tile id. Each tile is given an index id, 0 - NumTiles, so if I used % 100 on that id, and examined the remainder, I would subdivide the tiles into 100 groups. My initial concern is that this naive approach places tiles that are far apart in the same group, possibly increasing the number of groups that will have inconsistent checksums, in a case where a game is out of sync in a relatively local area.

Afforess said:

To subdivide tiles into groups my initial thought was simply to use the modulus operator over the tile id. Each tile is given an index id, 0 - NumTiles, so if I used % 100 on that id, and examined the remainder, I would subdivide the tiles into 100 groups. My initial concern is that this naive approach places tiles that are far apart in the same group, possibly increasing the number of groups that will have inconsistent checksums, in a case where a game is out of sync in a relatively local area.

Click to expand...

How about this:

1) Divide the map into N vertical strips. Compute a checksum for each.
2) Divide similarly into M horizonal strips (doesn't matter if M = N or not) and compute a checksum for each.
3) Transmit the 2 arrays of checksums (N+M)
4) On the recipient do likewise and see which strips differ. Only the tiles in the intersection regions of the differing strips need then to be transmitted in detail.

If you assume changes are geographically localized (if not your simple modulo approach is optimal anyway) then almost always only one intersection region will differ, so you have a quadratic reduction in the number of tiles that need to be transmitted, for a linear fixed cost of the slice arrays.

If you really wanted to you could apply this recursively.

Koshling said:

How about this:

1) Divide the map into N vertical strips. Compute a checksum for each.
2) Divide similarly into M horizonal strips (doesn't matter if M = N or not) and compute a checksum for each.
3) Transmit the 2 arrays of checksums (N+M)
4) On the recipient do likewise and see which strips differ. Only the tiles in the intersection regions of the differing strips need then to be transmitted in detail.

If you assume changes are geographically localized (if not your simple modulo approach is optimal anyway) then almost always only one intersection region will differ, so you have a quadratic reduction in the number of tiles that need to be transmitted, for a linear fixed cost of the slice arrays.

If you really wanted to you could apply this recursively.

Click to expand...

This is an excellent analysis. Thanks for the suggestions, your approach is would be more efficient.

Good news. I used the gDLL->Compresss/Uncompress (which interestingly is never used anywhere in the dll) and it works and it compressed ~10,000,000 bytes to ~50,000. The checksum process above may not even be needed, I need to test on older saves.

I did have a new concern. Do selection groups also need to be rewritten to use vector & hash map? There will be at least 1 selection group per unit, and if any thing, players churn through selection groups faster than units.

Afforess said:

Good news. I used the gDLL->Compresss/Uncompress (which interestingly is never used anywhere in the dll) and it works and it compressed ~10,000,000 bytes to ~50,000. The checksum process above may not even be needed, I need to test on older saves.

I did have a new concern. Do selection groups also need to be rewritten to use vector & hash map? There will be at least 1 selection group per unit, and if any thing, players churn through selection groups faster than units.

Click to expand...

That sounds like an issue but I'm not sure how it really works - if it caps out at all as it is now.

@Koshling: Would this method of passing the plot data be needing updating to multi-maps/viewports coding? Or will it be fine as he's got it?

Thunderbrd said:

That sounds like an issue but I'm not sure how it really works - if it caps out at all as it is now.

@Koshling: Would this method of passing the plot data be needing updating to multi-maps/viewports coding? Or will it be fine as he's got it?

Click to expand...

If it's being done on what amounts to a save-stream it'll be fine - the save stream includes all the maps in the multi-map set. If it's explicit code syncing the maps then it'll just be the current one presumably.

Afforess said:

Yes to both counts. There is no problem (that I am aware of ) preventing previously used ids could not be recycled, and as long as the game has less than 2^32 - 1 units alive, per player, things should be fine.

Click to expand...

Thunderbrd said:

Then with all my heart I hope to see you successful in this endeavor!!! That would be very great advances for us all.

Click to expand...

If you want to have any advantage from it in C2C you have to reduce the CvUnit memory usage. I did a bit of testing and added 10000 Horseman Units using CvPlayer::initUnit the memory usage went from ~750MB to ~2400MB. If you can't even have two Players with more then 8192 Units there is no advantage from having more possible Units.

alberts2 said:

If you want to have any advantage from it in C2C you have to reduce the CvUnit memory usage. I did a bit of testing and added 10000 Horseman Units using CvPlayer::initUnit the memory usage went from ~750MB to ~2400MB. If you can't even have two Players with more then 8192 Units there is no advantage from having more possible Units.

Click to expand...

I presume this means (basically) eliminating unit data as is declared in CvUnit.h? Damn... that'd be a bit of a project. Could be done I think as there are probably some ways to streamline. I was just about to add/subtract a few things soon (more adding than subtracting) but I could take a deep look through it and eliminate what we don't need - I know there's a number of unessential things being tracked needlessly now.

I don't want to be premature, but my local tests with direct ip multiplayer with 2 clients on the same computer shows the resync process to be working. It's not yet ready for pitboss, but should work between regular LAN/IP games.

If your computer explodes, or other strange oddities occur, I apologize in advance. The code is still unpolished and experimental.

I plan on running some MP tests with others so I can confirm it works in more complex games.

alberts2 said:

If you want to have any advantage from it in C2C you have to reduce the CvUnit memory usage. I did a bit of testing and added 10000 Horseman Units using CvPlayer::initUnit the memory usage went from ~750MB to ~2400MB. If you can't even have two Players with more then 8192 Units there is no advantage from having more possible Units.

Click to expand...

This doesn't surprise me. I forget who I was talking to now, but I previously have speculated that CvUnit was the other big memory sink. I think a lot of the fields on units are mostly never used (as they exist for promotions, many units never receive any, or very few) and it would probably be possible to decouple the promotion related arrays to a new promotion struct, to cut down on the memory usage.

Anyway, the id changes are not a wasted effort. It eliminates the major technical blocker to any kind of unit limits.

sweet afforess,
im waiting on the completion, cant wait, wanna port barsoom into rand.

Afforess said:

This doesn't surprise me. I forget who I was talking to now, but I previously have speculated that CvUnit was the other big memory sink. I think a lot of the fields on units are mostly never used (as they exist for promotions, many units never receive any, or very few) and it would probably be possible to decouple the promotion related arrays to a new promotion struct, to cut down on the memory usage.

Click to expand...

Koshling already did that in C2C with the PromotionKeyedInfo struct. The same goes for UnitCombatTypes, PromotionLine, Terrain and Feature related arrays. You can look at it maybe it helps.

The next step would be to cut unused or useless stuff and use smaller datatypes. Alot fields use the int datatype but they never reach high values. E.g. no unit will ever have more then 127 moves so a char could be used to save 3 byte.

Koshling said:

That sounds safe. The big question is probably what the performance impact of the key lookup is on the id deref (which happens many millions of times per turn on a mature game). The use of a hash will have changed that from O(1) to O(ln N)

Click to expand...

With a standard hashmap implementation, aren't key lookups O(1)? There is a time penalty for the hashing function, but that should be trivial.

I haven't measured, but anecdotally I've not noticed a slowdown.

Afforess said:

With a standard hashmap implementation, aren't key lookups O(1)? There is a time penalty for the hashing function, but that should be trivial.

I haven't measured, but anecdotally I've not noticed a slowdown.

Click to expand...

I think it is O(1) in the best case and O(ln N) in the worst case.

alberts2 said:

I think it is O(1) in the best case and O(ln N) in the worst case.

Click to expand...

Worst case for hash map is O(N) but it is highly unlikely with a good hash function and sufficient reserve space, especially for such a uniform id space.

Heya afforess and friends,

So i see the svn version includes the resync now, so is it good yet?

keldath said:

Heya afforess and friends,

So i see the svn version includes the resync now, so is it good yet?

Click to expand...

There are one or two remaining bugs I need to work out and also I want to create a popup that asks the player what to do when an OOS occurs, not just force a resync on them.