Network, network aaaand network… yeah, I’m working on multi over Internet mod for some months now. But here it is, today I decided to take a rest and write a post about the backstage, for you!
RTS & Lock-stepping
In a multiplayer game, we use the network to synchronize the world’s state on all the computers. Every player has then the same representation of the map than the others. Following the example of all known RTS, WinThatWar! network layer is based on an algorithm called lock-stepping.
The classical approach (in FPS for instance), is to synchronize the internal representation of every items of the game by relaying, via the network, the changes bring to the other players. In a RTS, we can get to hundreds, even thousands of items to synchronize at the same time. So, you would probably understand that’s not possible to send, 5 time a second, the exact location of every unit of the map to every player in the game. However, even the most frenzied korean Starcrafter doesn’t exceed more than 5 commands by second, so that’s 300 APM (actions per minute)… Ok that’s not so bad.
To simplify, the lock-stepping will “cut” the game in 200ms turns. During that turn, we’ll record all the controls of the player: selection, moving orders, attack orders… At the end of the turn, theses controls will be send to all the other players while you’re waiting for their own. After a period of time, all the players finally get the list of all the controls for this turn. This list is delivered to the game-logic (AI, Gfx, etc.) that will execute them (the controls). Then, the next turn begins. If the game-logic is determinist, which means it will always get to the same result for a given list of controls, the World state is exactly the same for every player. It’s called “Synchronous simulations”.
In facts, that’s a bit more complicated: we mask the network latency by simulating a n -1 turn, so we give time to the next turn controls to arrive before the end of the current turn simulation. Are you still following me? Anyway, in the case of games over Internet, we just make sure that these turns length of time vary depending on the players’ computers and network capacities.
This paper, wrote by Age of Empires creators, describe this principle very well.
At the end, the network part is quite simple. The true difficulty resides in the game-logic determinism. For a given list of controls, all the computers have to end in the exact same result.
Procedural generator & GPU
In the case of WTW, we chose to use procedural generation to produce our maps. We’ve actually got a tool that allows us to define varied maps styles, then our generator is able to create an infinity of variants of them. Well, we have to confess that’s still a bit experimental now, but we’re working on it!
For the sake of performance, the maps relief (heightmap) is generated by the graphics card with the help of Pixel Shader, at the very beginning of the match. That’s quick, and efficient.
Problem is there’s still some negligible differences between what results of two graphics cards made by a different constructor or so. Usually, it really is a tiny variation, in the range of 10e -5 or 10e -6 maybe (0,00.001 and 0,000.001 if you prefer). But here it is, that causes troubles in the synchronous simulations. For example, at Player 1’s, a tank could perfectly shoot the target, but at Player 2’s, the tank seems a bit upper on the map, and it can’t shoot. In short, that’s not synchronous anymore. And we do not like it this way.
P2P transfer & ECC
I the way to fix this problem, in LAN mode, the host was sending his own heightmap to all the player. This way, we ensured there was no display difference. But we can’t use this method concerning the multiplayer over Internet mode. Our largest maps heightmaps is around 400Ko heavy. In the case of a 8 players game, the host would have to transfer 7x400Ko of data, knowing our Network technology is P2P based, and if, like me, you didn’t have choice and subscribed to an ADSL which don’t allow you to upload more than 100ko/s… it would take you 28 seconds just to transfer the map. And we all now, here, how these seconds can seem lengthy when you wait a game to be launch.
So, this is roughly how it works at Insane Unity: If 8 players join the game, the map is “cut” in 8 parts, and every player send his own eighth to the 7 others. So one player will upload only 350Ko (7x50Ko), which means 3.5s sending time.
Actually, the map is “cut” to be as efficient as possible for the processor cache, but in any case, it doesn’t change anything of the 8 parts things, since every player will send more or less the same volume of data.
The heightmap in Yellow, the cutting in Red.
But wait for it… that’s not the best!
I think that ECC (Error Correction Codes) are one of the most magical thing of informatics. The principle is to use an abstruse mathematical process: For one data bloc, a “parity” bloc is reckoned. The whole (data + parity) is relayed, then through a second abstruse process, we can firstly check that none of the data are damaged, and then fix the potential errors. Reed-Solomon codes (RS) might be the most used: CD, DVD, Blu-Ray… it even works when it’s scratched. And, if as mine, your ADSL is a 2,5km long interferences antenna, I think you might be happy that your residential gateway or router fix some of the errors.
RS bloc coding, n = total weight, k = playload (useful data), and 2t = parity. Through a 2t parity, you can fix up to t errors.
Well, let’s get back to our map. The heightmaps are almost the same for all the players. So, I’m using the RS to calculate a parity bloc, and that’s what players are exchanging through the Network. Then everyone can apply the error correction, and that’s how all the players will finally can have a perfectly identical map. Oh yeah, I almost forgot, parity bloc is obviously smaller than data bloc but you probably noticed that already. In our case, it’s RS(223,255), being 32 octets parity and 223 octets of data. Let me do the calculation for you: Now, the players just have to upload 50Ko each thanks to this method, which means an half a second transfer. And that’s what we like!
So, that’s my daily life at Insane Unity. Hope you enjoyed this post.