I think perhaps you should consider how that plays out with how you described your game.

Every player communicates through a tree pattern. Every player can take actions that propagate out to every other player. When any player takes any action, you're going to need to reconcile it with every other game client before any other player can take their actions. If the moves are not reconciled everywhere then the next action will take place on a game board that is out of sync, and future moves will desync the game more and more.

Now, again in contrast with a central star or hub with the server. Every player can take actions which get pushed back to the hub. When any player takes any action, you're going to ned to reconcile it only with the hub's version of the simulator, and any other game client can also take their actions. The server hub is the only location where actions are reconciled, all actions are accepted or rejected there, and the game simulation does not desync.



The tree-style communication can work well for distributing identical information to many people, but suffers difficulties by requiring a large number of connections. In practice due to networking constraints it is generally difficult to build a large fully-connected communications mesh, and difficult to maintain it when connections are being added and removed frequently, as you described. If your main purpose is to transfer identical globs of information across a network, what you describe may work and is similar to other protocols like bittorrent. But few games work in this manner.

If you are building a lockstep game where the communications mesh requires everyone to get all the same step, then distribute a bunch of information and advance to the next step, sure, that pattern works well. Maybe that's a giant game of Civilization or Chess or some other turn-based game. But if you're building something where actions should be taken quickly, that won't work quite so well out in the real world of slow, poorly connected hardware.

Hey frob,

I did consider the whole desync issue. The way I have it set up is so that the commands getting sent are all relative to the map itself and can be sent in any order (e.g. player moves to location x,y as opposed to player moves 10 steps west from their current location). And furthermore because the host can do validation checking, it is impossible to cheat unless the host allows it.

I think the main problem occurs when you are a node placed near the bottom of the tree (as braindigitalis mentioned above). As an example of a worst case scenario, if you are in a game with 64-127 players and are placed at the very bottom of the tree, then 7 nodes would have to be transversed before any information reaches you. Assuming that each node takes approximately 100 milliseconds to relay the information, there would be an average of 700 milliseconds delay. Furthermore, more nodes means a higher likelihood for failure, and so the game would not only be extremely laggy but also very jittery (e.g. players randomly appearing and disappearing out of thin air).

I guess for it to work, I'll either have to change my game into a slower-paced game (e.g. a Turn-Based game as you mentioned, or even just a plain strategy game such as Stronghold Kingdoms), or incorporate it into other things where lag is not as big of an issue (e.g. spectator mode). I'll also have to consider if using a star-shaped topology would be a better option in such cases.

Thanks again,

achew

Also I should point out, the reason why the number of connections is not a problem is because it is O(1); which is the same as a star-topology. In a star topology, each user has one connection for sending and receiving with the host. Whereas in the tree topology each user will always have 1-3 connections; one for receiving from their parent and at most 2 connections for sending to their children. This doesn't matter if the tree contains 10 users or 1 billion users.

And furthermore because the host can do validation checking, it is impossible to cheat unless the host allows it.

Who checks that the host isn't cheating?

Also, I may be misunderstanding your topology, but it seems that while a host may only have 2 open connections, it's still responsible for verifying and sending out packets for absolutely everyone. As such it's a de-facto server, right?

I played around with the idea of a tree-structured network topology a while back, and came to the conclusion that the additional latency from the additional hops is not worth it, compared to just letting everybody connect in a star to the host. Network bandwidth is not generally a main limiting factor.

Hey Kylotan,

Who checks that the host isn't cheating?

This is one downfall which stems in all peer-to-peer networking games. It's either everyone is allowed to cheat or the host decides if people are allowed to cheat. I personally think the latter works best.

Also, I may be misunderstanding your topology, but it seems that while a host may only have 2 open connections, it's still responsible for verifying and sending out packets for absolutely everyone. As such it's a de-facto server, right?

Sorta. Think of how many commands the host has to send out if all "n" players sent out one command at the same time. The host would have to send out 2*n commands; n commands to each of it's 2 children. Whereas in a pure client-client model, it would have to send out a whopping n2 commands; n commands to n players.

In the tree model, how it works is half of the total number of players (n/2) each send out 2*n commands (since half of the nodes in the tree each have 2 children and the other half consists of the "leaves" which don't have any children). Therefore the total number of commands still equals to n2 since (n/2 * 2*n = n2).

So the answer to your question is yes. The host is responsible for verifying and sending out packets, but it has the advantage that the work for sending out packets is divided amongst half of the total number of users (unlike a client-server model where the server does everything).

I hope this clarifies things,

achew

I played around with the idea of a tree-structured network topology a while back, and came to the conclusion that the additional latency from the additional hops is not worth it, compared to just letting everybody connect in a star to the host. Network bandwidth is not generally a main limiting factor.

I totally agree with you about the additional hops not being worth it. In my game however, network bandwidth is the main limiting factor. Although lag is equally important as well.

I've been thinking about this and came up with yet another proof of concept; it's a slight modification of my original concept (and surprise surprise, it involves a tree!).

There are basically 2 changes:

• Instead of using a BST, it uses an octree (8 children per node)
• The tree has a maximum depth of 2 (see below)

01 users in depth 0 (primary-host)
08 users in depth 1 (secondary-hosts)
64 users in depth 2 (regular-users)

Advantages:

• Maximum delay caused by the additional hops is 3*relay-delay for regular-users, 2*relay-delay for secondary-hosts, or 1*relay-delay for primary host.
  • relay-delay is typically between 10 and 100 milliseconds so it won't be a big concern
  • a normal client-server architecture always has 2*relay-delay
  • see diagrams at the end of this post for a visual of what I mean by relay-delay
• The shorter relay-delay for secondary-hosts also gives people an incentive to become a secondary-host
• Freeloading still doesn't work due to "complain" (see original post about "complain")
• Don't have to worry about what happens when multiple nodes "complain" since there's only one culprit
  • in the original concept, the culprit could be someone else higher up in the tree however in this case, anyone higher than the secondary-host is the primary-host, and thus can't be the culprit
• Cheating can still be prevented using the primary-host

Disadvantages:

• Maximum players of 73 (1 + 8 + 64)
• Sybil Attack
  • a secondary-host could create fake regular-users for themselves to host; thereby not having to worry about then "complaining"
  • only practical way to combat this is to have the primary host monitor all the users from time to time
• Load balancing is not as good
  • 9/73 of the total players are doing all the work in an octree as opposed to half in the BST method

Client-Server relay-delay visual:


Octree relay-delay visual:


Comparison of Upload Bandwidth per host: Octree vs. Client-Server

Hey Kylotan,

Who checks that the host isn't cheating?

This is one downfall which stems in all peer-to-peer networking games.

No, it's not. A peer to peer game where everyone runs the same simulation does not suffer from this. What you have is a client-server game, where one of the players controls the server.

Sorta. Think of how many commands the host has to send out if all "n" players sent out one command at the same time. The host would have to send out 2*n commands; n commands to each of it's 2 children. Whereas in a pure client-client model, it would have to send out a whopping n2 commands; n commands to n players.

Right. You're assuming the cost of sending commands is the expensive thing, and you're reducing that. But in my experience, at this scale, commands and bandwidth are not the issue. The expensive part is the logic of the simulation.

I'm not an expert on this in any way so consider my reply just as feedback.

What I don't like about peer to peer setups is that when the host decides to suddenly exit for whatever real life reason, the game just poofs for every other player in the middle of what they are doing at that moment. If I as a gamer look for a multiplayer game to buy and realize the only option it offers is a peer to peer setup then I would not choose this game. Cheating would be a concern too because I know how inventive people can be to exploit certain weaknesses if it gives them an advantage.

I know you mentioned your reason why you choose peer to peer. I'm just thinking that in the end if you want to sell your game it's good to think that there are so many games out there using a client - server model that players can choose from.

Some games support host migration, which mitigates the "game poofing" problem.