next »

Having finished the skill selection system (yay) and this week's homework assignments, I'm now looking towards my next contribution towards the project.  I've decided to tackle the internet component and create the framework necessary to have a multiplayer game.  I've wanted to approach this feature early in development, because games that treat multiplayer as a feature to be tacked on at the last minute really show it, often with poor performance and gameplay considerations.

I've made this thread to discuss how we must organize the game in order to properly support multiplayer.  We must presume there will be an indeterminable amount of delay between players, but that each player must remain "in sync" with the others.  We must therefor have a way to synchronize the inputs to the system, and the outputs of the system such that all instances of the same session are the same.


First of all, for performance reasons we cannot "send" the state of the game dynamically to each player.  Instead, each player will "run" an identical instance of the game to every other player.  We will not send information back and forth based on the status of the game, but rather based on changes to the status of the game.  However, we must ensure that these changes happen at exactly the same time on every system.  Because of this, there are some things we can manage without any sending any information to the server, and some things we cannot.  For instance, the server has no business knowing where a client player's mouse cursor is.  It only needs to know where it was at the moment a click occurred.  Only actions that will change the state of the server need to be communicated.

My proposed solution is to use the server (or "host" if you prefer) as the guy with the stopwatch.  Whenever the user makes an action (for instance, clicking the mouse or pressing a keyboard button) the appropriate information is sent to the server.  The server will then be the one to assign this action a timestamp.  The server will then send information regarding this action and its timestamp to every client (including the one that made the action), thus standardizing when the action will happen.  However, this alone does not solve the problem.  Take, for instance, the case where the server assigns an action a timestamp of T.  Suppose that its message that contains this action only reaches one of hte clients at time T+1.  The time at which this action was supposed to have occurred has already passed!  As we must presume an indeterminable amount of delay, this is an unacceptable solution in its current state.

To complement this solution, I propose a system of locking timeframes.  The game will naturally run with a delay (on the host) of about 50 milliseconds, which is completely undetectable to the human eye.  Before each 50 millisecond duration may begin, the host must "lock" that  timeframe.  All new actions received will be given timestamps that are ahead of that timeframe.  Once the timeframe is locked, the server will send a message to all clients that that the next 50 milliseconds are safe to run.  Until they receive a message from the host that this next time frame is safe to run, they will pause the game and wait for that confirmation.  This will ensure that they don't get ahead of themselves and maintain the sync between all clients and the server.

As an aside, a request for a random value will also be sent to the server, and it will tell each client what that random value was to ensure they all have the same value.  Similarly, the server will run all NPC AI's and send appropriate timestamps of their actions to all clients.


By the way, I'm taking a course called "Computer Networking" this semester.  It used to be called "Computer Networking with focus on the Internet" but apparently the faculty thought that was along the lines of calling water wet.

Makes sense. When desiging these kind of systems, keep cheating in mind. The client can't be trusted concerning any information that might influence victory or loss, since clients can be hacked or even reprogrammed.

Anyway, it'd be good to practice with this kind of thing first, not implement in in the real game straight away. In case you hadn't noticed, I've added a high-level network layer (which I created for a school project) to the Victory engine, in org.openwar.victory.network, you can take a look at that.

Well, there are a couple things I'm concerned about specifically from a security standpoint:

1) spoofing; we don't want one client pretending to be another, or pretending to be the host!  The only way I can think of to stop this from happening is some form of encryption, probably RSA, to ensure that each client and the host is who they claim to be.  By giving the host the private keys and the clients different public keys, we can know who for certain who is sending what message.

2) non-legitimate changes to the model: this is one that I actually think we have covered.  Since we communicate interface events rather than the results of those events, if someone has modified their game then it will not impact anyone else.  They'll go out of sync and from there whatever interface inputs they give will not be relevant to the models of the other players.

3) illegitimate data access: since all computers will contain all the information of the game, it is possible for a player to have illegitimate access to that data.  For instance, his computer knows there is an invisible enemy sneaking up behind him.  If he's hacked his game, he can know about this without any need for communication with the host.  No one would ever know what occurred. 

#1 and #2 I think we can solve quite nicely.  It's #3 that worries me.  After all, it's hacks that take advantage of #3 that make up about 99% of all hacks in mainstream games, and are by far the hardest to crush.  Even Blizzard, a high end company with a vicious anti-hacking policy and a huge amount of resources dedicated to stopping this, still has many such hacks made for their games that are indeed successful.  To make matters harder for us, our code is opensource and therefor anyone who wants to make a cheating modification can literally open up the source code and basically has a text-book on how to do it.   I'm not sure at this time of how we can tackle that issue.

spoofing; we don't want one client pretending to be another, or pretending to be the host!  The only way I can think of to stop this from happening is some form of encryption, probably RSA, to ensure that each client and the host is who they claim to be.  By giving the host the private keys and the clients different public keys, we can know who for certain who is sending what message.

i don't quite get you here. once you have a socket, you can generally be sure that each packet you get is from the same machine you first connected to. of course, hackers could hijack a tcp connection, but would they really, for a game?

illegitimate data access: since all computers will contain all the information of the game, it is possible for a player to have illegitimate access to that data.  For instance, his computer knows there is an invisible enemy sneaking up behind him.  If he's hacked his game, he can know about this without any need for communication with the host.  No one would ever know what occurred.

yes, there's a concern. a little step in the right way (but not a full protection) would be letting the client send some kind of hash of it's own executable files, thereby verifying it's an official client. however, you're certainly right it's the most impressive challenge

i don't quite get you here. once you have a socket, you can generally be sure that each packet you get is from the same machine you first connected to. of course, hackers could hijack a tcp connection, but would they really, for a game?

I don't think it's overly difficult if someone had the desire to make it happen.  Besides, all you need is one illegitimate packet to get through and you can have a really successful cheat, giving an enemy player's character orders he never intended.

a little step in the right way (but not a full protection) would be letting the client send some kind of hash of it's own executable files,

That's easily faked.  Once again, our source code is completely open, so it's easy to figure out what should be sent and then change things around to make that happen. 

[do not]

By the way, I'm writing these long articles mostly to collect my own thinking on these subjects.  I'm trying to get my head around the entire scope of the game, and there's no reason not to post it once it's done.

Time is a critical part of the game which must be regulated thoroughly.  The random stops and goes of threads upon a processor cannot be allowed to interfere with a very rigidly enforced notion of when something happens, and what happens to it as time passes.  In order for the multiplayer model to work, each game must always maintain the same timeline (although time shifting and scaling is acceptable, as I will attend to shortly). 

To deal with this issue, I will fall back upon a very simple notion: a "real time" game is just a turn based one that has been sped up to human speeds.  The game will not stop for you if you "skip" your turn, and reflexes become a critical component.  The passing of time will therefor be easy to enforce.  The engine itself will attempt to time itself based on the system timer, but will not attempt to make the guarantee that it will maintain perfect timing.  Instead, it will ensure that regardless of the timing, that the same time-stamped input would always produce the same system states in the future.

In other words, the engine is allowed to speed up or slow down, but it will not change its output.  In a multiplayer setting, we can easily tell a computer that's getting ahead to slow down, or a computer that's falling behind to speed up.  Because the state of the system is not impacted by the actual passing of time, this creates a few milliseconds of delay or speed-up, then normal play resumes without issue.

There is another upside to this system.  Because we keep track of all the time-stamped inputs, we can easily create an action-replay feature.  By storing the state of the system at the start of the replay and all time-stamped events, it can be re-run in the engine in order to produce exactly the same output.  Random values would be dealt with by having the host randomly generate a seed value for every event, which would be stored on the queue with the event itself.  This way, every system would use the same seed for that event, ensuring the same "random" output. 

When an interface event occurs, an event is put into the queue.  We will use an interface map to translate the external event into something of internal meaning.  This would enable the user to customize which buttons map to which internal events, allowing for control settings.  After this conversion, we will have two things: a unique event code describing what the action is, and a timestamp of the system time when this occurred.  It may be that other information must be queried, such as the position of the mouse cursor at the time, to supply the event with all the input information it requires.  From here, we convert the system timestamp to a game timestamp.  Since the game could "pause", but the system cannot, it is important to have game timestamps to maintain the relative difference.

For multiplayer, the host would then send this event information to all clients.  Since clients will use only the host's time stamps (and only relative time is relevant), they can maintain the same event queue as the host.  Clients, on the other hand, will not queue their own events, but instead will send only the event code identifier to the host.  The host, upon receiving this communication, will schedule the event with its own timestamp, then inform every client (including the one that sent this initial communication) of the scheduled event.

Events are thrown onto the queue one by one, and then executed at the appropriate points in time.  However, the real time difference between when they are executed is ignored.  All that matters is the time-stamped difference.  Because of this, we do not need to ensure - and indeed, have no reason to worry - about the actual flow of time.  So long as it is reasonably accurate, the game works properly.  Any object updating that needs to occur will do so not based on the passing of system time, but the passing of game time. 

There are two ways to ensure that players never get too far ahead.  The first is to use "locks".  At regular intervals, a lock is placed on the event queue.  Locks are numbered sequentially, and the total number of locks is always remembered.  Should a client (or host, for that matter) encounter a lock on the event queue, it will check that lock's number.  If it is, indeed, the last lock, then it will not proceed and will wait for another lock to be added to the queue.  This ensures it will never pass into a block of execution with loose ends (akin to reading a page while it's being written).  By ensuring that no action is EVER added preceeding an exist lock, we know that these finished blocks are safe to execute.

A second way to ensure that no one gets ahead is far simpler; simply stipulate that all events must be placed at the end of the queue.  Therefor, no event already on the queue could have another event that was actually supposed to preceed it.  This design is certainly the simpler of the two, but precludes any event scheduling tricks.  Once an event is scheduled, we can never schedule anything ahead of it.  For instance, take the example of a spell that causes an explosion at the targetted location once per second every five seconds.  The event could simply reschedule itself with a timestamp of one second later and decrement a private variable for the number of explosions remaining.  If we use the second of the two scheduling systems, this would preclude any other events from being scheduled in the next second, which is unacceptable.

Another item for note is the above case: events that schedule other events.  In this case, is the host really necessary?  After all, we would expect that every system running the game would generate the same timing for the event.  Not true; suppose the case where a host issues a "lock" event to every client.  While this lock event is en-route over the internet, the host (and every client!) processes an event which schedules another event.  The event happens to be a poorly made custom-script by a modder and tries to schedule another event too soon, and the time frame is already locked.  The host knows this time frame is locked, and "bumps" the event up to compensate.  The lock is not yet known to all clients, however, so they do not bump the the event time, and happily receive the lock a moment later, not knowing they've made a grievous mistake and desynchronized themselves.

There are two solutions to the above; the first is to allow an event to schedule another event inside a locked time-frame.  Since this re-scheduled event was predetermined anyways, all systems will do it so there won't be a problem.  This is the preferred solution.  If it doesn't work, the only alternative I see is to force all clients to ignore the request for rescheduling, and have the host explicitly alert them to this event.  This needlessly inflates internet traffic, however, and because of that would preclude using rescheduling events in large masses to produce persistent effects.


Upon reflection of what I've talked about here, I feel the game should have three threads of execution.  The first thread should be the controller; this deals with all user input and also with any client/server relations.  The controller collects and stores data independently.  It will then leave it up to the host to schedule the events for the second thread, the model, to deal with.  The model is what runs the game, essentially following the queue of events and executing them at appropriate times with appropriate delays in between.  The final thread would be the viewer, which manages the output (not of the internet variety; this would be left to the controller) of sound and image.  It would query the state of the game from the model, and acquire some data (cursor position, etc) from the controller.  The view and controller would talk directly when the player accesses any menus (anything that doesn't impact the model, basically).

Yes, this is MVC, and only now can I see it in an implemented state.  There is one huge advantage I can see in this approach: we can gut and re-implement the entire viewer module.  In other words, we can make this 2D sprite-based now, but later on we could change it a 3D engine.

I think it's important to just seperate client and server parts first. That way we can switch to 3d or something else without changing the server. The next step would be to decide on possible architectural layers in either, but independent from eachother (eachother being client - server).

The singleplayer game would work the same way, by launching and connecting to an internal server (as is the way it's done for nearly all multiplayer games, I believe).

The system I have described already separates the graphical component of the game such that it can be swapped out at a later date.  The actual "events" that are processed in game are independent of the actual graphical output, and any communications between the interface and the game are also such.  The only case of overlap between the graphical output and the interface is the cursor and menus.

I've implemented an EventList and Event class.  It's basically a linked list that will run events sequentially and insert new events into their appropriate position in the list.  It also implements the locking mechanism described in this topic.  Every time a "LOCK" event is added to its list, it increments its lock counter, and every time it encounters one in the process of execution, it decrements its counter.  It will not proceed with executing events unless its lock counter is greater than 0.  In the case of events with equal timestamps, the order in which they are added to the list is used to determine their precedence.

It's occurred to me that we may have trouble with the cursor position.  Since the cursor's position is used (in real time) to generate the directionality of your character's movement, the position of the cursor must be known by every computer, and must have a game-time model.  As such, I believe the cursor's position should be sampled regularly (every 10 milliseconds or so) and the change in its position be registered as an event.  This is the most straightforward approach I can think of to do it.

Not so much. Only the player's position needs to be sent over the net. Whether this comes from a mouse, a joystick, or a motion-sensor helmet, who knows, it shouldn't matter.

The cursor is also used for the directionality of attacks, and some continuous spell abilities which use the cursor's instantaneous position rather than the position it had when the ability was activated.

Sending the character's position is dubious.  For one thing, we'd have to check the validity value anyways to ensure that someone isn't trying to use a teleportation hack.  By communicating the interface events themselves, we ensure that only valid changes to the model occur.  There's another issue here: we don't actually know what a character's position will be at time T until we've actually reached time T.  By that point, it's too late to communicate this information.  We cannot necessarily extrapolate these values, either, since we cannot predict how an unexecuted event (say, an explosion) will affect an object's position.  By instead only communicating interface events, every system can independently resolve the results of such events without having to wait on other systems. 

What I've built in the EventList is a linked list of events that describes everything that happens in the game.  There is a certain sequential order of events, and as these events resolve they change the state of the model.  Interface events will in turn add new events to the list, which will be executed at a later point in time.  Since every computer connected to the same session will execute exactly the same events in exactly the same order, they will maintain their integrity and be running exactly the same game.  Some of these events, however, may require continuous input on the location of the cursor.