A method for networking / state synchronization of several player directed psuedo-predictable entities in a game world

WE PRESENT A NOVEL METHOD!!!

No, seriously though, I just had an idea.

LONG BACKSTORY / CULTURAL COMMENTARY:

So um. Over the past few months (In addition to getting a job and kind of going to college) I've been extremely absorbed by competitive Starcraft. "Oh, you mean that cool RTS game Blizzard made back in 1998?" you may ask, and you would be correct. As weird as it seems, many many people still play it. The main reason is that it got adopted as a sport in Korea, and is played professionally on stages in stadiums and malls, with live events broadcast on tv. Another notable thing is ICCup or the International Cyber Cup, which is a free Starcraft server where anyone can play on a modified game client and 3rd party server with great ladder, anti-hack and latency features. Without these things starcraft would be dead for certain, but it has persisted as a competitive e-sport for both pro players in Korea and amateurs everywhere else in the world. I was very impressed with the community that surrounds starcraft and how it is played.

I've always appreciated multiplayer games with insanely skilled players, like Quake, Counter Strike, and such, especially those played professionally. The reason is that when a game becomes a sport, the community around it transforms radically. Gamers are stereotyped as assholes with no lives, and they are all too often to fit that stereotype to the letter. The anonymity of the internet further compounds the negative cultural stereotype to form an absolute pigsty of human interaction. Anyone who has ever played on xbox live with a headset or seen a relatively unestablished gaming forum knows this; it is sometimes scary and almost always disgusting how low the level of discourse is. However, when the focus is on the competitive aspects of a game, and becoming skilled is a legitimate pursuit that is challenging, rewarding and respected by others, gamers are brought up out of the gutter and made into stars, teams, friends, and their discourse rises with them.

Fig. 1. South Park's depiction of a harcore gamer.	Fig. 2. Korean progamer LeeJaeDong after winning the OnGameNet Starleague.

Wait, wasn't I supposed to be talking about network code? My plan was to mention offhandedly that I also had been thinking about the culture of gaming a lot and I'd write a different blog about it, but I guess I wanted to write it NOW!!

Anyways, after thinking long and hard about the gamer culture in Korea and in global communities like ICCup and teamliquid.net, I was really inspired to try to make a competitive game. No, not a competitive game, an ESPORT even! Games have always appealed to me that way, and I've always wanted to make a multiplayer game "someday"... So I've been working on a successor to Megapixel in the form of an RTS in my spare time, and thinking long and hard about how to network an RTS game successfully. Tonight I had an idea and couldn't shut up about it, so here we go.

ACTUAL NETWORKING THINGS:

Networking any game always presents countless challenges. Latency (i.e. the time it takes for a packet to travel from one computer to another) is the first and foremost problem that must be overcome in networking. The problem that latency presents is that it is physically impossible for both players' computers to hold identical representations of the game world at any time, simply because when one player issues input of any kind it will take anywhere from 50 milliseconds to 400 milliseconds for that input or any effects of it to reach the other player(s). In some games, such as first person shooters, synchronization is not very much of an issue. Many FPS games simply move the other player's representations on the client machine around according to the packets as they arrive, possibly with prediction of their current positions based on the velocities they had when the packet was sent, and player at the client computer is challenged to hit opponents with his weapon. When the client claims that he did hit an opponent, the server usually just relays that information to all other concerned clients. Of course, this leaves room for hacks wide open; I can engineer my client to report to the server that I shot everyone in the head at once whenever I click the mouse. Hacks like this can be dealt with either by changing the network model (the server makes all the decisions) or building careful sanity checks into the game code, but that is another story.

The thing about networking RTS games is that they can have hundreds of individual units interacting in a very chaotic fashion, and any difference in involved client computers' representations of the game world will compound quickly as they interact, most likely resulting an an impossible conflict resolution process where both players will see units teleport, come back to life, and take unbelievable amounts of damage without dieing. The main reason for this is that pathfinding algorithms for groups of AI characters are emergent systems, that is, their behavior cannot be determined in any other way than playing out the simulation, and small changes in the input parameters will dramatically effect the outcome.

RTS games go about solving the problem of different game representations in many different ways, and I have not studied them all thoroughly. One think I do know is that in my game, I want instant reaction time on all clients. In some games, such as age of empires 2 and warcraft 3, your units will only begin to move a short time after you click, which helps the two game worlds stay concurrent, as it simulates the time it takes for the packet to reach the other client(s). Although this may be beneficial for fairness in some cases and make networking easier to implement, in my experience it does not yield a very smooth and fun user experience. Likewise, starcraft (By default) will periodically freeze the game for a few milliseconds (or more) to synchronize the network states, and allows the user to adjust how much latency is compensated for by an artificial latency in unit commands and a slowdown of the whole game. The ICCup version of starcraft includes a hack that forces the game to never slow down or introduce an artificial latency with unit commmands, however this can cause the game state to become grossly desynchronized and introduce artifacts like teleporting units in some cases.

A MODEL FOR SYNCHRONIZED PATHFINDING IN LARGE SCALE GAME SITUATIONS:

My proposed solution to the pathfinding problem is to predestine the unit's fates, that is, calculate their paths ONCE such that they move toward their destination while avoiding all other units whose paths are already known, as well as static obstacles in the scene. Here is a step by step example of how this would work in a networked game.

1. When the game starts, the client computers and server agree on where the initial units and structures of each player are, and attempt to match their clocks as well as they can. (I don't know if it is even possible to synchronize clocks within 100 milliseconds of eachother over a possibly varying latency that can be even greater than 100 milliseconds, but it seems like it must be possible somehow. Possibly with a 3rd computer acting as a dedicated timeserver or something.)

2. When I give my units their first command, I send the IDs of the affected units, the time, and the destination. Since the state begins synchronized, both computers can use my hypothetical pathfinding algorithm to generate an identical animation for the unit. I am pretty sure that with the Unity engine, even across platforms and processor architectures, absolutely identical paths can be calculated in this way. Thus, even though all I sent over the network was the Unit IDs, time and destination, all interested clients generate the same temporally marked path and can sample from it arbitrarily. Real synchronization is achieved through the unit's relatively high independence; the motions of the player's hands are not connected to the units 1:1 (at least in "macromanagement" type situations where the players issue a command to their units and then ignore them while they execute the command to give attention to other situations on the map or game board), and so the units predictable behavior can be calculated the same way on all clients and synchronized.

3. When later commands are given to units, the units will stop moving along their current "destiny" path and onto a new one determined by the command. Since all clients store the same path, when they are told to deviate specific units off that path onto a new one at at an exact point in time, they can simply look back on the current path to the time of the command and calculate new paths from there, preserving the state of synchronization.

Of course, this all depends on a quite magical pathfinding function. Could such a thing be made? Could it be optimized to the point where it runs fluently on the majority of hardware? I don't know, but I'd like to try. It is harder than most pathfinding algorithms, because the full paths for all units in the selection must be calculated during the frame where the command is given.

FURTHER MISC THOUGHTS:

The obvious problem with this model is that if you can see another player's units while he issues a command to them, with the most basic sampling methods for the generated paths, his units will appear to jump forward the distance that they traveled since he issued the command. Also, this method of networking gives no benefit, and, in fact, falls apart in "micromanagement" situations where one or both players are giving many commands per second to one unit or group of units, and both are carefully watching the outcome of the fight. In these situations a more FPS-like model would be favorable, and so for a fluid experience the game may require desynchronization and resynchronization of units based on how the players are controlling them.

Since Megapixel has no shame about being a game and never pretends to be anything else, I am not afraid to features glitches most game developers would cringe at the sight of. We know that army men never glitch around and periodically intersect eachother, so most developers of army man games try to avoid it. (They never succeed entirely, however.) But who is to say that digital pixel beasts don't teleport sometimes? Impossible problems and situations in networking can be solved with a pretty animation, and I will have a much easier time implementing things.

Another interesting thing about this method is that it makes replays extremely easy to implement, even rewindable replays. Only the commands need to be stored and the paths can be calculated by the replay viewer, then once the paths over a given time are stored in memory, everything in the game can be scrubbed back and forth smoothly; All that the code is doing is telling each unit to look like it did at time x, where x can be any time along the path.

I was also imagining that replays of networked games would be automatically saved and stored on a server such that anyone can go to your profile page and look at all the matches you played, just like ICCup, except they can view the reply right in the web browser as well through the Unity Web Player.

Lastly however.. With school and work and my unpredictable drive to actually code and create things, it is unlikely that I will implement any of this anytime soon. Oh, whats that? You want to see what I have so far anyway? Well, alright. The latest build can always be accessed (In Unity Webplayer form) at http://yogware.bluegillstudios.com/build/.



Right now, there is no network code, no pathfinding, only hexagonal terrain, pretty water, and shader-based fog of war w/ soft shadows, demonstrated by a lonely torch wandering Digital Lost Temple in a sinecosine circle for all eternity.