#170763 - LOst? - Sun Oct 18, 2009 10:46 pm
I have done some testing using multiple DSs and Mario Kart DS, to see how the game works and how it synchronizes multiplayer play.
From what I can tell by simple testing, all the connected players play their own version of the game (meaning they don't share CPU players, or even their own car with the other DSs during the actual gameplay).
The game then runs at 60 fps (only guessing, might be 30 fps), and sends only the input from its game to the other DSs.
The synchronization rules seems to be simply to keep all the DSs on the same frame, and that the DSs shared the same game start and randomizer to give the same items and CPU player AI.
Now if one of the DSs gets out of range, 4 seconds is the limit before that player is disconnected. This also means that during those 4 seconds, all DSs are paused waiting for that player, so that no frames needs to be dropped, and the randomizer gets out of sync.
Now, the question I am asking doesn't need to be correctly answered, only guessed. When playing Mario Kart DS over the Nintendo WiFi service, wouldn't it take alot of lag using the rules I stated above?
Then I am not thinking about slow Internet connections, BUT the fact that people around the world play the game at the same time? And this is a kinda stupid fact that might not be true: It takes 4 seconds for light to travel one revolution around Earth; SO how does the game deal with the delay of many seconds sending game input over long distance connections?
This might be related to Mario Kart DS discussion, but I am not interested in that game alone, but rather the technology it uses so that I can understand how to sync my own games in the future, even if it is just a simple Snake game with 3 players running at 60 fps on DSs across the globe.
_________________
Exceptions are fun
#170766 - Miked0801 - Mon Oct 19, 2009 1:14 am
I would be floored if a 4 player game manages 60hz. Even 30Hz is difficult when waiting for 4 systems every gameloop to stay in sync as they all run at the speed of the slowest player.
Anyways, you've just touched on why throughput matters. For a key sharing system like you described and like is used in almost all DS (GBA, GBC, etc.) games, packet loss cannot be tolerated because throughput is nearly nonexistant. As such, a lot of the communication time is just sending handshakes back and forth to make sure everyone is in sync. The good part about this is it takes almost no throughput to keep things working right - as long as the games stay 100% absolutely, positively, you've got to be kidding me careful, in sync. Digimon Racing GBA sent roughly 12 bytes per gameloop to stay in sync with 4 players over serial.
Enter lag and lost internet packets and this system fails. You just cannot run a system like this over the net. Too much chaos. But, you get much, much more throughput.
So, you are forced to code systems where the games can run for a certain number of game loops without confirmed data. Then, when a packet arrives, it contains all pertinent information about what all the other players have done and the game resyncs. As long as the information isn't too late, you don't notice the small differences. As the data arrives later, the game is forced to take more drastic changes to keep things in sync and hence lag effects.
If you are coding for internet, you will almost certainly need to do some really fancy error checking and packet sending.
#170768 - LOst? - Mon Oct 19, 2009 12:03 pm
| Miked0801 wrote: |
Digimon Racing GBA sent roughly 12 bytes per gameloop to stay in sync with 4 players over serial.
|
Thank you for all the awesome explainations! They really helped me :)
| Miked0801 wrote: |
Enter lag and lost internet packets and this system fails. You just cannot run a system like this over the net. Too much chaos. But, you get much, much more throughput.
So, you are forced to code systems where the games can run for a certain number of game loops without confirmed data. Then, when a packet arrives, it contains all pertinent information about what all the other players have done and the game resyncs. As long as the information isn't too late, you don't notice the small differences. As the data arrives later, the game is forced to take more drastic changes to keep things in sync and hence lag effects.
If you are coding for internet, you will almost certainly need to do some really fancy error checking and packet sending. |
Yea, so my guess is (since I haven't played Mario Kart DS over the Nintendo WiFi service) no CPU players can be activated during races. They simply are too much to deal with. It must work differently. Sending extra infromation such as skipping frames, and make the current frame the right one (like renewing the randomizer, car positions, items collected/or active attacks).
Just one question... Is it just the DS who can hardly handle 30 fps for that many player connections? Or is it the Internet speed that comes into mind?
_________________
Exceptions are fun
#170770 - Kayvon - Mon Oct 19, 2009 4:46 pm
| LOst? wrote: |
| And this is a kinda stupid fact that might not be true: It takes 4 seconds for light to travel one revolution around Earth |
Circumference of the earth = 40,075 kilometers (equatorial)
speed of light = 299,792 km/s
40,075 / 299,792 = 0.13 seconds
In four seconds, light could travel closer to 30 revolutions around the earth.
What's more likely happening is the DS is sending the current cart location, direction, and speed (and a timestamp) many times a second, but not necessarily a 30 or 60Hz. When your local DS receives the data for the other racers, it is able to extrapolate the path for those carts until it receives the next update. The updates occur with such frequency that, from a player's point of view, the carts seem to perfectly in sync with what the other players are directing.
#170771 - Miked0801 - Mon Oct 19, 2009 6:22 pm
| Quote: |
Just one question... Is it just the DS who can hardly handle 30 fps for that many player connections? Or is it the Internet speed that comes into mind?
|
Both, though the internet is a much larger portion of the problem as it requires a more intense protocol to work right.
The DS has quite a bit of throughput - don't have the numbers off the top of my head, but it's much much higher than what the GBA could handle. Multiplayer is no longer a guarenteed slowdown to barely 30 hz, although in my current game, multiplayer is a very large CPU hit that I had to account for to keep performance reasonable.
Yes, the DS has enough throughput to send full game state info (carefully!) This is how Wifi games are forced to work.
#170774 - LOst? - Mon Oct 19, 2009 11:13 pm
Thank you Kayvon for the fact about light speed. My old facts about light travel around Earth bugged me alot!
Since Mario Kart DS already has a system for handling multiplayer gameplay (used through Download Play), wouldn't it be kinda stupid (waste of development time) to have two different ways of handling multiplayer ingame (one that extrapolate the path of the cars for online connection)?
If I developed the game, I would choose one technique and go with it. I so need to try Mario Kart DS online to see what happens :P
Miked0801, thanks so much!
Just curious, is your game frame based? Does it do the math for one frame at a time and requires a constant framerate, or is it tame based (calculating everything from delta timing)?
My games are frame based, and I really believe Mario Kart DS is frame based.
_________________
Exceptions are fun
#170780 - sverx - Tue Oct 20, 2009 3:36 pm
7,5 revolutions in a second. If light could travel around a sphere ;)
#170784 - PhoenixRising - Tue Oct 20, 2009 6:15 pm
| LOst? wrote: |
Since Mario Kart DS already has a system for handling multiplayer gameplay (used through Download Play), wouldn't it be kinda stupid (waste of development time) to have two different ways of handling multiplayer ingame (one that extrapolate the path of the cars for online connection)?
If I developed the game, I would choose one technique and go with it. I so need to try Mario Kart DS online to see what happens :P |
I'm not quite so certain.
In my case, I have chosen to use two different methods, because:
1) When you are connected to the internet, lag is going to be more than with a local game. You are connecting back to a server, and I have chosen to make the server the master of the game. Each DS controls their personal location, speed, and direction. They send that data to the server. The server uses that data to run the bulk of the game and broadcast the results back to the clients. The clients become fairly thin, with very simple rules to allow for movement... There are no "AI" players in the WIFI portion of my game... AIs are going to run as separate clients on the server, using the same protocol as the DS client does.
2) When you are doing local (by local, in my case, I am envisioning liblobby, so you can play without an access point using direct DS communication, having a wifi / nifi versions of the game) you need one of the DSes to arbitrate the results... In the WIFI game, if one player shoots another player, the server decides if the shot hits. So one of the DSes has to act as the server. The alternative would be each decides for themselves if the shot hits, and broadcasts the result.
I've not decided as I am currently working on the internet side of the game, but clearly, because there is no server to arbitrate, the DS code will be different in the local "NIFI" game than the internet based wifi game.
Is my assumption still correct that play without an access point still requires a second second executable because all of the logic won't fit into the ARM7? I'm currently enjoying listening to the MODs play while playing on the server... :) The MOD player, plus the WIFI handler plus liblobby all can't fit at the same time?
#170786 - sgeos - Tue Oct 20, 2009 7:01 pm
Re: PhoenixRising
Couldn't you abstract server communication, so that your program always runs through the same API?
Then you could use WIFI, NIFI, or local server event arbitration depending on the circumstances.
#170792 - LOst? - Tue Oct 20, 2009 11:22 pm
| PhoenixRising wrote: |
In my case, I have chosen to use two different methods, because:
1) When you are connected to the internet, lag is going to be more than with a local game. You are connecting back to a server, and I have chosen to make the server the master of the game. Each DS controls their personal location, speed, and direction. They send that data to the server. The server uses that data to run the bulk of the game and broadcast the results back to the clients. The clients become fairly thin, with very simple rules to allow for movement... There are no "AI" players in the WIFI portion of my game... AIs are going to run as separate clients on the server, using the same protocol as the DS client does.
2) When you are doing local (by local, in my case, I am envisioning liblobby, so you can play without an access point using direct DS communication, having a wifi / nifi versions of the game) you need one of the DSes to arbitrate the results... In the WIFI game, if one player shoots another player, the server decides if the shot hits. So one of the DSes has to act as the server. The alternative would be each decides for themselves if the shot hits, and broadcasts the result.
|
That's kinda nice explaination there! I wrote most of that down so it will help me.
Because I am running frame based. I can only make one move each new frame. Kinda like a chess move. So that's how I need to think.
Player 1 might be on frame 30. Player 2 might be at frame 29. That means that I have three choices:
1. Wait with player 1 for one frame.
2. Try to run one extra frame for player 2 to catch up.
3. Convert player 2's frame from 29 into 30.
The 3 option is unfair to player 2, because he/she lost ground position in the "race" and also requires updates for all objects and not just player's positions and speeds to make the frame the same as player 1.
The 2 option is a gamble, where there might be even more frames to get lost because of the extra CPU time used. The player 2 might never catch player 1's frame, and might drop back instead.
Option 1 is unfair to player 1. Player 1 had it running just fine, and player 2 got into trouble. Now player 1 has to pay for it.
I am considering every client including the server to run all the code for every player and objects. And every client's own player will be validated against the server, and adjusted if needed. Or something simular.
Is it better to have the server do all the work for the players? And have the clients use dummies instead that only update positions? Then in case of lag, it wouldn't be that smooth. A lot of jumpy players.
I rather have a FULL player run off a cliff and die during a huge lag, just to be adjusted by the server and show up somewhere else close by. That would be more smoothly.
Feel free to help me out here ;)
_________________
Exceptions are fun
#170795 - Kayvon - Wed Oct 21, 2009 1:29 am
You can do it without a server; Mario Kart does. But you'll need to arbitrate a way to make determinations like frame sync, player placement, player/object collisions. Doing this on the DS end eliminates the need for a server, but greatly facilitates hacks and cheating. In a homebrew game, the market for hacks isn't as great, so maybe you're not worried about that.
It might help to not think of everything in terms of frames. As mentioned earlier, you won't get a data packet from every other player between every frame. Even if you could, you wouldn't want to; what would you do if a packet never arrived? The game must go on; just wait until you do get a packet and do an update then.
This is where that extrapolation comes into play that I mentioned earlier. Each DS keeps track of all the other objects and players until an update is received. Updates are usually frequent enough that players don't notice any corrections taking place, but if you've ever played an online game you've experienced "jumping" when there's lag. Mario Kart is a good example; when excessive, brief lag occurs, other players may seem to "jump" from their original positions do other positions from your viewpoint. This is your DS catching up to the action that has occured while you were briefly blacked out from outside communication.
You need to separate the idea of communications from the idea of frames. You'll need frames to get the engine running and do incremental internal updates. But the frames shouldn't be strictly tied to communication.
#170803 - LOst? - Wed Oct 21, 2009 11:36 am
| Kayvon wrote: |
You can do it without a server; Mario Kart does. But you'll need to arbitrate a way to make determinations like frame sync, player placement, player/object collisions. Doing this on the DS end eliminates the need for a server, but greatly facilitates hacks and cheating. In a homebrew game, the market for hacks isn't as great, so maybe you're not worried about that.
It might help to not think of everything in terms of frames. As mentioned earlier, you won't get a data packet from every other player between every frame. Even if you could, you wouldn't want to; what would you do if a packet never arrived? The game must go on; just wait until you do get a packet and do an update then.
This is where that extrapolation comes into play that I mentioned earlier. Each DS keeps track of all the other objects and players until an update is received. Updates are usually frequent enough that players don't notice any corrections taking place, but if you've ever played an online game you've experienced "jumping" when there's lag. Mario Kart is a good example; when excessive, brief lag occurs, other players may seem to "jump" from their original positions do other positions from your viewpoint. This is your DS catching up to the action that has occured while you were briefly blacked out from outside communication.
You need to separate the idea of communications from the idea of frames. You'll need frames to get the engine running and do incremental internal updates. But the frames shouldn't be strictly tied to communication. |
Thank you! It was exactly what I thought. The communication cannot be strictly tied to the frames.
Another question is animations of objects and global level animations like blinking lights etc... How important is it to synchronize such things?
For example, if you have a game where you are running around windmills, some windmill blades you can grab on to (obviously needs to be synchronized) where others are just background elements. Where do you draw the line between what needs to be synchronized to play exactly the same on every DS and what not?
Mario Cart DS doesn't care about synchronizing music... At least not in the menus between games. That is actually the only noticable thing I can see/hear while playing against another DS close by.
_________________
Exceptions are fun
#170819 - Miked0801 - Wed Oct 21, 2009 4:40 pm
Things that don't affect gameplay (non collision things) don't need to be syncronized (and we use a different random number seed for these that is local to that machine)
Things that are in the grey maybe area for syncing are usually dropped from the design :)
And yes, I seriously doubt Mario Cart is using frame based and locked multiplayer for their internet stuff. That would make that game's framerate unplayable and worse every time someone else joined the game.
And also yes, this is where a dedicated server can really be useful to make all game decisions and broadcast them. Saves game processing on the units and eliminates a large source of cheating.
To answer your earlier question, all the games I've worked on for GBA/DS have used frame locked, frame counted timings with keysharing. It eliminates having to do predictive coding and uses the smallest amount of throughput. The cost is that all players run at the speed of the slowest game and keeping the games synced is hellishly difficult. One array overwrite bug or one extra random number call or, etc and your games are unsynced.
#170824 - LOst? - Wed Oct 21, 2009 10:06 pm
| Miked0801 wrote: |
Things that don't affect gameplay (non collision things) don't need to be syncronized (and we use a different random number seed for these that is local to that machine)
Things that are in the grey maybe area for syncing are usually dropped from the design :)
And yes, I seriously doubt Mario Cart is using frame based and locked multiplayer for their internet stuff. That would make that game's framerate unplayable and worse every time someone else joined the game.
And also yes, this is where a dedicated server can really be useful to make all game decisions and broadcast them. Saves game processing on the units and eliminates a large source of cheating.
To answer your earlier question, all the games I've worked on for GBA/DS have used frame locked, frame counted timings with keysharing. It eliminates having to do predictive coding and uses the smallest amount of throughput. The cost is that all players run at the speed of the slowest game and keeping the games synced is hellishly difficult. One array overwrite bug or one extra random number call or, etc and your games are unsynced. |
Awesome info, thanks!
_________________
Exceptions are fun
#170835 - PhoenixRising - Thu Oct 22, 2009 1:47 am
| sgeos wrote: |
Re: PhoenixRising
Couldn't you abstract server communication, so that your program always runs through the same API?
Then you could use WIFI, NIFI, or local server event arbitration depending on the circumstances. |
To a certain extent, I have. I use an event driven architecture, where inbound messages fire events into the game engine, and the game engine fires events as results. So the listeners implement interface between the game engine and the user as well as the game engine and the network, and the core game engine doesn't know the difference.
So I can have a WIFI event handler, NIFI event hander, and the local game event handler. However, the game engine currently does the collision detection, so I find that I do need a network engine vs. a local engine so that the network engine does less work. But since I'm doing my programming in C++, it means I have an IGameEngine class that implements base level events, and a LocalGameEngine vs. an InternetGameEngine that implements the specifics of each interface.
#170838 - PhoenixRising - Thu Oct 22, 2009 2:08 am
| LOst? wrote: |
Because I am running frame based. I can only make one move each new frame. Kinda like a chess move. So that's how I need to think.
Player 1 might be on frame 30. Player 2 might be at frame 29. That means that I have three choices:
1. Wait with player 1 for one frame.
2. Try to run one extra frame for player 2 to catch up.
3. Convert player 2's frame from 29 into 30.
The 3 option is unfair to player 2, because he/she lost ground position in the "race" and also requires updates for all objects and not just player's positions and speeds to make the frame the same as player 1.
|
I would agree that this is unfair...
| LOst? wrote: |
The 2 option is a gamble, where there might be even more frames to get lost because of the extra CPU time used. The player 2 might never catch player 1's frame, and might drop back instead.
|
This depends on the data that you have I think. In my case, I've segmented things so that one message is just about player location. this message includes the current vector of the player, so I have their x/y location, direction, and speed. So when I am ready to "tick" the next frame, if I don't have an update for a player, I run the next frame with outdated information. The player location update message is only sent when the player presses or releases a button, invalidating the vector. So my frames normally run with old data, only in the middle of a dog fight between cars do I expect to have a lot of messaging going on, and even then, it is limited by how fast people can press buttons... I have no measurements, but I can't imagine people would be hitting buttons faster than 10 times per second, which would be every 6 display frames.
| LOst? wrote: |
Option 1 is unfair to player 1. Player 1 had it running just fine, and player 2 got into trouble. Now player 1 has to pay for it.
|
It depends upon the nature of the game I think. In your chess example, there is no choice, you can't proceed without input from player 2. But if you can guess what player two is going to do, you never let them get behind, you just pretend you got the update on the right schedule, and when you get the next update, you fix whatever you guessed wrong on...
| LOst? wrote: |
I am considering every client including the server to run all the code for every player and objects. And every client's own player will be validated against the server, and adjusted if needed. Or something simular.
|
You can only do this to the extent that you have data for every player. In my game, the player does have the "master" data about their player, so if the server says that they are at x1,y1 but they send an update message saying that they are at x3,y3, the server updates all of the clients with the corrected position. But again, I think the key is going to be that they player can input data only so fast, and you have to take that into account as you are processing a turn. In my case, I don't have a lot of random events going on all of the time, so I don't have any synchronization issues related to randomization. Each client is responsible for themselves.
| LOst? wrote: |
Is it better to have the server do all the work for the players? And have the clients use dummies instead that only update positions? Then in case of lag, it wouldn't be that smooth. A lot of jumpy players.
|
I've abstracted the control interface away from the rest of the game. So for me, I have a "ControlStyle3" class for example, that says that when the player presses up on the key pad, that means they want to go north. I also have a ControlStyle1 class that says when the player presses up on the key pad, that means they want to go faster. For network play, I have a dummy controller that takes the input from the server and updates the location appropriately. This is how my AI players are going to work. Each AI player will have their own controller and act similarly as if they were pressing buttons, though not exactly so.
If your game lends itself to vector descriptions of player positions, then you should be ok, and it shouldn't be too jumpy. You know the person was going at 437 degrees (the DS degrees) and at a speed of 5. As long as they haven't changed direction in the last 1/60 of a second, you do know where they are going ot be next. So the updates coming from the players just need to be new vectors, with new starting x/y locations, and you're back on track. I'm not expecting to be off by more than a few pixels at any given time, even with a lag of 1/4 of a second. If lag gets to be more than that, I would have serious issues.
| LOst? wrote: |
I rather have a FULL player run off a cliff and die during a huge lag, just to be adjusted by the server and show up somewhere else close by. That would be more smoothly.
Feel free to help me out here ;)
|
What do you mean by having a "FULL player" run off a cliff and die? Or do you mean tracking the vector so that you are updating the position every frame and avoiding the jerkiness of just getting position updates? If so, I would agree, an x/y location, a direction and a speed are a good way to interpolate the position of the players without sufficient data.
#170848 - sgeos - Thu Oct 22, 2009 10:12 pm
| PhoenixRising wrote: |
| I have an IGameEngine class that implements base level events, and a LocalGameEngine vs. an InternetGameEngine that implements the specifics of each interface. |
You know this, but you could make some sort of a hybrid engine that holds a copy of the local and internet engines and passes events to one or the other depending on the specific event. Ie, a class that takes a PureLocalGameEngine for collision and a PureInternetGameEngine for everything else. Obviously, the PureInternetGameEngine could handle collisions. (There is probably a design pattern that elegantly describes this behavior...)
#170853 - PhoenixRising - Fri Oct 23, 2009 1:48 pm
| sgeos wrote: |
| PhoenixRising wrote: | | I have an IGameEngine class that implements base level events, and a LocalGameEngine vs. an InternetGameEngine that implements the specifics of each interface. |
You know this, but you could make some sort of a hybrid engine that holds a copy of the local and internet engines and passes events to one or the other depending on the specific event. Ie, a class that takes a PureLocalGameEngine for collision and a PureInternetGameEngine for everything else. Obviously, the PureInternetGameEngine could handle collisions. (There is probably a design pattern that elegantly describes this behavior...) |
I think that normally, to do something like that, you would need an explosion of classes. The delegate pattern would have you create an interface class for each type of behavior, and then you register the appropriate class for each behavior. So you'd have an ICollisionDetector interface class and LocalCollisionDetector or InternetCollisionDetector as the actual engine, probably an IPlayerAttack, IPlayerAttacked, .... But quite frankly, to use this type of pattern, you really really really have to have a good design, which doesn't work unless you write it all down (at least that's what I've found in the past...)
#170867 - keldon - Sat Oct 24, 2009 12:06 pm
My apologies if it's been mentioned but I've had little sleep and reading hurts my brain. Dead reckoning is used intensively for on-line multiplayer racing games - you will see evidence of this in games like Gotham Street Racing where opponent cars appear to jump across the screen. This is because you first saw your computer's prediction of where there car might be.
You will notice that on some occasions when GSR misses a collisions the opponent's car will be able to drive through you. The main thing is for the player to see a result of a collision if it appears on his screen, however if only one screen saw the collision then you have a problem - which appears inevitable to some degree if the update frequency is too low, hence removing collision detection for those moments (or just making the less unstable).