Developing multiplayer for an action game is quite a daunting challenge

[BS-er]

I knew I was in for a challenge when the time came to start thinking about multiplayer.  Now that the time has come, I see that I had only had a foggy idea what I would be getting into.

The biggest challenge to grapple with is that as a first-person action game, it must do a good job predicting the future, which is something that a single player game doesn't even need to worry about.

An action-oriented multiplayer game must predict the future because of the delay in getting information on the actions of other players.  That information might be 0.2 seconds old, or 1.2 seconds old, or even older.  It would make for a very choppy, delayed response game if the game waited for all players inputs in order to move forward.  The best it can do is extrapolate or basically guess the positions and actions of the players, using the outdated information.

That doesn't seem too bad, but what really is straining my brain is firing projectiles.  Their lives are short, and they move fast.  Making projectiles believable in multiplayer is going to be one of the greatest challenges.  It makes it worse that projectiles may be created in an alternate timeline that needs to be removed and replaced by a more correct timeline.  Oye!

[Black Manatee]

Hey, Bob--

Not to beat a dead horse (or whatever cliche would apply here), but this may be an area where taking a good look at the Torque system might help.  I'm not talking about trying to incorporate any of the engine/code/whatever; instead, I just mean it could be instructive to see how the Torque game engine handles it. 

I'm guessing you may have already studied Torque's multiplayer system, which -- according to a lot of the comparisons I've read -- may be the strongest aspect of the engine.  Given that the game is set up as natively multiplayer (and you actually have to sort of "disable" some aspects in order to do a single-player game), there are doubtless many aspects which would be totally unworkable in MAD-world. 

I'm guessing that one area of incompatibility would certainly involve the "pause/wait" element of a scripted mission; it's a feature that's totally absent in Torque, since the system relies on a single thread that's followed/shared by all players (and so, a pause would simply halt the entire game).  The Torque system--from my experience--is set up much more as an "object-oriented" engine, with relatively little provision for any game-wide event handling (which in some ways is a core feature of MAD).  That's one reason the multiplayer is so stable/strong in Torque: each iteration of an object behaves independently, and so it's kind of like the objects report their state to the system, rather than the system checking on the state of the objects.

On the other hand, I'm curious as to how much (if any) scripting you're planning to include in the multiplayer versions of MAD.  If multiplayer levels aren't going to rely on much of any scripting, maybe some aspects of the Torque methodology could be worth examining...   

[BS-er]

Right now I'm open to evaluating all possibilities.  The BZ2 approach is one possibility, and the torque approach is another.

I just downloaded OpenTNL (Torque network code) from SourceForge.  I will be looking into what aspects make it a strong choice.

BZ2 and Torque are similar in that there is always one machine that acts as both server and client, while all others act only as a client.

My overall impression of the Torque model is this:

• A server sytem that maintains a game state, runs scripting, sends game state data to clients etc.  It does a lot of heavy lifting.
  
• A very different client system that receives data from the server and uses it to maintain the best possible estimate of the server's gamestate (particularly in the player's proximity).
• State information of all relevant game objects (maybe only within range of the player) needs to be sent continually from server to client
• Uses UDP, possibly so that even out-of-order packets can be utilized immediately for improved prediction

My overall impression of the BZ2 model is this:

• The true server is just a hub that receives control inputs from clients, packages them and sends them to all clients.  Other duties include handling new players, sending game state etc.
• Client is a simulation drive only by player inputs.  The simulation runs in lockstep with all other clients, using only basic player-driven control data.  Updates are not smoothly spaced because of the irregularity of player inputs from clients over the Internet.  The client simulation at the server machine is treated as the master simulation.  Each client runs a copy of the game world as well as scripting.
• Client also runs a smooth predictor simulation of all game objects in range of the player of that client.  Player inputs and AI are extrapolated forward from the actual simulation.  A refresh is done periodically from the actual server.  Put simply, it is a "Donnie Darko" parallel dimension of an area surrounding the player, that moves forward in time ahead of the true simulation.  It is periodically updated/changed such that it will never become too different from the true simulation.
• Uses TCP, necessary to properly compute matching simulations on all machines.

I like many aspects of the BZ2 approach.  It will be easier to do elaborate scripting in multiplayer (this is why BZ2 MPI works well).  Strategy games with many AI units may go smoother.

A drawback of the BZ2 approach is that simulations would diverge on different systems, i.e. a Mac system vs. a Linux system vs. a Windows system.  This is because each of these systems introduce minute differences in floating point computations.  Often it is just order-of-operation optimizations, done differently with different compilers etc.  There may even be minute floating point differences on the same hardware and OS, although my testing of my Athlon PC vs. my Pentium M laptop showed that they will run the exact same game with no differences for hours.

[Black Manatee]

Yeah, it does seem like the BZ2 model is much better-suited to MAD's script-heavy approach (and far more democratic :-)  ), compared to the Torque model.  So much of what appeals and is unique about MAD is related to the scripting and the action/strat hybridization, so I guess it would make sense that the BZ2 approach would constitute a better solution!

Regarding the asynchronicity of Win/Mac/Linux hardware/software: I'm sure you've already considered this, but it seems like there are two approaches that present themselves immediately:

1)  Multiplatform support for single-player, but single-platform support for multiplayer.  I know that multiplatform is key for indie titles, when you need every potential market you can get (especially the lower-penetration ones, like Linux), and Ogre's support makes this a given.  But if worst came to worse, it could certainly work as a Win/Mac/Linux title with an asterisk for multiplayer support (interplatform support isn't guaranteed, or some such phrasing).

2)  "Scalable" server updates, where update frequency rises (perhaps sharply) when multiple platform types are detected.

2.5)  I know this is way out there, but I've been hearing a lot about folks handing off more and more code support to the graphics card, due to its relatively higher power (especially math/vectors) relative to the CPU.  Is there any chance of sending some operations -- even a "timing" or "math-check" operation -- over to the GPU, for either verification or primary calculation?  Or is that too bizarre to even deserve an answer?!   

[BS-er]

Yeah GPU offloading is a bit out there, especially for an indie team.  I would only feel comfortable using a 3rd-party library that encapsulates and hides the GPU details.  I believe there are physics libraries that use the GPU.  For MAD, we're better off targeting multi-core for improved performance, and even that is very tricky.  The MAD code was built to run world state computations in separate thread, as an option, with the primary thread for startup and Ogre, but that option has been broken for awhile.  Currently a single thread handles all.

I've been studying TNL today and it looks interesting.  This documentation does a good job explaining it.  Overall it's a great approach.  I plan to give it a lot of thought before dismissing it as an option.  There's nothing about it that would inherently prevent heavy scripting.  There would probably need to be two different scripting interfaces: 1) client scripting (GUI, command interface, visuals), 2) server scripting (interaction with the game state and game objects).  With Lua, the ability to wait wouldn't be a problem.

If I take a BZ2-style approach, the multiplayer match server would have to disallow connections between different platforms.

[Black Manatee]

Very cool!  I hadn't realized that the TNL had been posted as an open-access reference.  Seems like it could be quite helpful, at least in terms of comparisons and reference, anyway.  When they say "OpenTNL," does that mean it's really "Open?"  If so, that's quite a nice contribution to the open-source community!

I've sent you a message with some info about GarageGames's current status, etc; let me know if you'd like me to follow up on that. 

[BS-er]

It's open source, with a GNU license, so MAD would need to be released with the same license in order to use the GNU license.  Otherwise there is a commercial license for a fee.  I'm not sure how much, but I suspect it's reasonable.

I do need to weigh things carefully.  If I take the TNL approach, state information for nearby objects (at least those with changing states) will need to be sent to each client.  The full state of some objects would be a few hundred bytes, accounting for A.I. etc.  That would support better prediction, by extrapolating the full behavior, but could get bandwith-intensive.  extrapolating using only physical aspects would probably yield more erratic prediction, making them look much jerkier.  Projectiles might really clog the bandwitch.

The BZ2 approach will surly require less bandwidth overall.  Cross-platform interaction would be out though.  Ultimately I'd like to make the decision that yields the best quality gameplay, but it's not easy to determine which one would yield that.

Anyway, just sharing some of the aspects that make multiplayer development so mind-bending.  It certainly makes me respect the programmers of BZ2, Tribes etc. for making their multiplayer work as well as they do.

[Dataanti]

NPC i think arnt a big deal cause they move differently on everyone's screen don't they, the only thing you have to deal with is players moving rite?

[OvermindDL1]

Greetings!  Semester is finally over, free time again!

I talked about all this before you know, multiple ways of multiplayer, stating that the engine should have been built around it or you will be encountering difficulties when you do finally put it in. 

An example:
Let's take the Unreal engine or the Source engine or the Quake engine.  Now they are very network friendly, but why?  These engines are built in such a way that there are two different parts.  There is the part that does the calculations, manages the game world, knows everything, but it has no real interface, instead it has an interactable API.  The main interface people will use is the 3d rendering, it calls into the server logging in as a certain user/player.  The server back-end only sends it the data that it needs to render, this is for two reasons, to reduce cheating (cannot know where someone is if their information is not sent to you), and to vastly reduce the network load.  The front-end deals with drawing things based on their positions it handles interpolation to make things smooth, but it has no authority and does no game-affecting calculations on its own.  Realistically AI code and such is ran on the graphic front-ends as well but their state is checked with the server's to make sure they stay in sync (if they are perfectly made, they will always stay in sync), else they get updated data and continuing running based on that data.  You can even have other interfaces other then the 3d renderer, such as a web-based management interface, as some of those above listed engines have, and you could potentially make more.

Now, what I was describing above may sound good for multiplayer, but those games do not just use that style for muliplayer, but singleplayer too.  Singleplayer starts up a server, then the 3d interface logs into that server and that is your interface into the world.  This is generally considered the best way to create multiplayer games, best network usage, best stability, best reliability, best anti-cheat design.  Quite frankly, I do not like the BZ2 style, dealing with it is a pain, the mission code is nasty, the synchronization is difficult because different computers run differently, there will always be something that faults in that design.  That is why I stated that the game needed to be built with multiplayer in mind from the beginning, because if you took the above design then you would really have no synchronization issues as there is only one server controller, the 3d interfaces themselves you would only have to worry about interpolation, that is the extent of synchronization that you would have to deal with, and you would be able to scale it in new ways as new situations arise.


Either way, as stated, semester is over, I have a lot more free time now, need anything done, need help with anything, etc?

You stated that you are using RakNet, I helped program some parts of RakNet, so I know it exceedingly well, so if you need help with it, feel free to ask about that too.

[BS-er]

Glad you survived the semester.  You did seem pretty quiet on the various forums that you visit.  What are your studies, and how are they going?

I'm still glad that I chose the path that I've chosen with the programming so far.  It often just seems to work out for me.  For example, I waited to incorporate game saving, and I'm glad I did.  I acrued a lot of mental notes on game saving as I progressed, and it took about 24 hours of work to incorporate it in the end.

I've been doing some tests for deterministic gameplay and so far things look promising across a number of XP/vista platforms.  I generate a data log using the Endless Mayhem mission, and then run the mission while reading that log in comparision mode for tests (saved missions too).  An hour-long log session has shown complete sync on several platforms: Athlon 1.1GHz, and Pentium M 2GHz.  I had to fix a few bugs to get there, and perfect sync across all target platforms is hardly confirmed yet, but I'm encouraged by what I see.  There may be some old dinosaur x86-based CPUs that would go astray, but may be unlikely to run the game at acceptable speeds to begin with.  However if I come across a more modern x86-based CPU that can't be made to stay in sync, I'll need to rethink it.  I'll have an SVN update in a week or two to allow others to help test that.

I find myself leaning toward a BZ2 approach so far, given the promising sync tests I've run.  I like that it is able to portray the complete battle picture for each player, for things such as command of remote units.  It will still be no walk in the park, and I'm always considering the alternative approaches.  I always have my eye out for good online articles on successful multiplayer implementations.  These are some of the reasons that I'm glad I held off on multiplayer.

Raknet looks to be a piece of cake to use, which is a testament to its quality.  I've been giving it an overview and I don't think I'll have much trouble figuring it out, but your advice on best usage of it would always be appreciated.

[OvermindDL1]

Yea, had no time to really even visit forums on my phone between classes even, way to busy.  One more semester left for my B.S. and in addition to my Associates in Information Technology I will have a B.S. in Computer Science, emphasis in programming (HAH, this university is a load of crock, the highest level stuff they taught I knew when I was 10) and a minor in Electrical Engineering.

As for game saving, serializing server data to clients and saving uses the same code in all the afore-mentioned engines as well. 

For synchronization  you are doing better then BZ2 did then, only recently has the BZ2 state been somewhat consistent. 

I still have no clue why you chose the DeadMans world style though, seems like a huge hassle, especially with script synchronization (if you truly use a coroutine style as you say you have been, then those are inherently non-deterministic, I got away with it in my Python BZ2 scriptor due to a heavy back-end for it that enforced synchronization, would have been *SO* freakishly easier if BZ2 did networking a more reasonable way.

BZ2 really should have been able to stay in sync since it had a lock-step world (as you do), but it was just not programmed well enough in the data areas, which, thankfully, GSH has fixed.

Although, I still do not like lock-step worlds either, they do not scale, at all.

As for RakNet, the examples tend to show easy ways to set it up, but not best practice in the easier ones, although the more advanced ones are better with that.  I use a self-made dispatcher system (of which a small part of it ended up in RakNet as the template based RPC system, yes I am proud of that, it is the only thing like it that I have seen, a type-safe, efficient, and extensible RPC system for C++, yea, try to figure out any other C++ RPC system that can do all that  ).

EDIT:
Next chance I get I can resync to your SVN and try it out, I have a Server AMD Opteron 2.37ghz dual-core that I can test with if anyone is up for multiplayer.

[BS-er]

The latest SVN doesn't have the right fixes yet.  I want to set up the game to generate a log while at the same time reading the reference log.  That way someone can send me the generated log and I can capture where things went different in the debugger.

So far Lua (with Pluto) has been a champ as far as synchronization and persistence.  The coroutines are completely cooperative, so it stands to reason that they ideally should be deterministic.  I'd still like to tackle Python in a project some day, but not for this project.  MAD is just too intertwined with Lua.  Maybe I should've abstracted it a bit more, but oh well.

The determinism finally appeared solved when I realized that Ogre's scene nodes don't necessarily iterate in a consistent order (hash_map, and auto-generated names and all).  When setting up a Newton convex collision body, The same vertices in different orders can produce subtle differences.  A checksum of the vertices didn't show the glitch, but a CRC nabbed it.  The solution was to devise a scheme to iterate through multiple child scene nodes in a consistent order, when creating the array of vertices.

So it will be a few days before I get the latest build to SVN.

[OvermindDL1]

Ah, nice catch with the point ordering in newton, I heard of that before for determinism, but would not have remembered. 

And yea, coroutines should be deterministic without using a scheduler as you do.  Python uses a scheduler, which by default is deterministic (if your code is), but it was easy to override it and supply your own, which is what I did, so even if someone wrote non-deterministic code in their mission scripts, I still forced it to sync otherwise.

Although that may be the case in LUA as well, people may just need to be careful that their mission code is deterministic as well.  That is why I like normal server setups, the code does not need to be deterministic, at all.