How will I detect de-syncs in an autochess/RTS style game?

Hi thanks for any 2cents on this issue! I am working on a lock-stepped autochess/RTS style game with self-hosted servers, and I need to be sure that the hundreds of different positions of units on the grid/their relevant stats (health, shields etc.) is equivalent on both machines as the game progresses turn by turn, every turn, so that the battle is the same. There is no unit micro in this game, only spawning units. Lockstep is in place to ensure that player input is being deliberately scheduled in advance and all that, but I don't fully get the preferred method of how to actually 'detect' a de-sync, like in Starcraft for instance.

Is this done with hashtables? Or are there some better or various methods? I understand that in Homeworld (that game is P2P) the clients send a hashtable of the 'game state' (not sure what they are really sending) 1x/sec, which they would have to agree on continuously through the game. But I don't understand for my own case, how the entire game state, hundreds of grid positions of units/their stats can be sent to a server 1x/sec, as this amounts definitely to too much bandwidth in my case. How to 'check' for de-syncs? Thx again

 

Why you want to use lockstep in autochess game. Are you going to have hundreds of units at the same time ?

 

Yes hundreds of units per side. The game is an RTS game that uses a grid and has no unit micro. Maybe autochess isn't the best word, but the game plays out automatically without micro. The game uses lockstep turns but the visual layer is lerp'd so it appears as non-turnbased, realtime game. You spawn units and they just go forward. This game is a real time strategy game and needs lockstep the same as any other RTS

 

I'd probably come up with a system where I generated a checksum of all relevant data, then send that checksum. On the other machine you do the same. If the checksums match then you're in sync.

 

This is what I figured, something like this, since you only need to monitor slight changes in the data and don't need all the data...in my case for instance, you are saying I should simply sum all of the grid cell position #s and send that value for comparison, in the case of unit position? And then sum total health of all units and send this also, etc?

 

No RTS don't need a lockstep.
Lockstep is needed when you don't have enough bandwidth for fluent gameplay.
And frankly speaking your game doesn't sound like a candidate for a lockstep.

 

This is interesting you say that and I can't understand really. Do you think there exists another way to schedule the player inputs? If player inputs are not scheduled for specific turns, like placement of buildings or spawning of units, the game will surely risk de-sync yes? The server will just spit player inputs from one player to the other without controlling the order at all, leaving the order up to the net speed and FPS of players even

 

It is just a suggestion off the top of my head. I don't know if it is the "best" way or anything. As far as what to add up, I'd choose anything you'd want to to verify in a sync check.

It might look something like this, again just off the top of my head:

Code (csharp):

1. private static List<byte[]> allThemBytes = new List<byte[]>();
2.  
3. public static void AddToChecksum(byte[] newByteArray)
4. {
5.     allThemBytes.Add(newByteArray);
6. }
7.  
8. //returns a 256 bit checksum of everything added to the list since the last checksum
9. public static byte GenerateChecksum()
10. {
11.     byte returnChecksum;
12.     foreach (byte[] byteArray in allThemBytes)
13.     {
14.         foreach(byte b in byteArray)
15.         {
16.             returnChecksum += b;
17.         }
18.     }
19.  
20.     allThemBytes.Clear();
21.     return returnChecksum;
22. }

Then you might put something like this in all the scripts which have data which need checking:

Code (csharp):

1. public void AddAllMyStuffToChecksum()
2. {
3.     ChecksumScript.AddToChecksum(BitConverter.GetBytes(health);
4.     ChecksumScript.AddToChecksum(BitConverter.GetBytes(gridPosition.x);
5.     ChecksumScript.AddToChecksum(BitConverter.GetBytes(gridPosition.y);
6. }

I have no idea how your grid works or anything. Then after you call AddAllMyStuffToChecksum() on all your objects you want to check (maybe you call them all with an event at the same time or something, or have a manager that goes through a list of all your objects you want in sync, etc), you call GenerateChecksum(). You then send the result to the other party. When the other party receives that message, they should be at the same point in your lockstep as when the first computer sent it, they will then call AddAllMyStuffToChecksum() on everything and generate their own checksum. Then compare.

Just an idea. 256 bit isn't very strong, but if you're running it every second it is probably fine anyways, but you could change it up to a stronger one without much work. By the way, I just wrote the code directly into the forum without checking it, so there's probably a typo or two . I wouldn't be surprised if there's a better way or better idea as well.

 

That all made quite good sense to me what you wrote anyways, at least the general idea of it, and you basically seem to agree with what I had already expect to be the best solution, so thank you...still interested in knowing more about this though. In Homeworld I believe their solution is very similar to what you just proposed, employing checksums of relevant info, though they make use of a hash function somehow at some point in the process.

EDIT: It seems like for sure checksum -> hashtable makes a lot of sense. They probably use a hash function just to reduce the data transmitted, or for other conveniences. You know there are probably multiple ways of compressing the relevant info into a singular hash-table, and checksumming is just one of them. I suppose you could deal with the info in some other way that may end up being more accurate/generally better/more reliable somehow, like hashing entire lists of data points to one table rather than just summing data together and hashing that...