I am bogged down by this for a while and I can't figure out a proper way to do it.  In a multiplayer game, a player should be able to see other players' visible states on the same screen/ same zone.  For example, my player should see other players' state change when they change size or color or collide with some entities if these players are in my player's viewport. The same applies to other players, so they can see what my player is doing, seamlessly. 

I have designed a architecture that if each player has some collection called "nearbyPlayers", each player can iterate through them one by one and get the state changes and then send them to the current player. But on the server because these players are at the same zone some state changes will be iterated many times. Assume A, B, C and D are on the same viewport, to get the environmental screen state changes for A, I need to iterate through collection = [A, B, C, D]. And for B, C and D I need to iterate through the same collection. I think this way my structure has repeatedly computed some states many times, which wasted a lot of CPU cycles. Maybe there is a term to describe the problem but I don't know.

I have also tried to design a pub-sub pattern, so that if players are on the same screen/same zone, each of them are subscribed to each other and if one player changes state the others should know the change. But still, the player need to tell all the subscribers the change. And in a simple implementation of this pattern I didn't find much performance improved. 

In both ways I find it easy to make mistakes such as detecting collisions with the same entity multiple times. Is there a generic or standard way to solve this problem?

The problem is that you're polling for state changes instead of letting the subscription tell you about them, which is what pub/sub is for.

For example, instead of this:

"to get the environmental screen state changes for A, I need to iterate through collection = [A, B, C, D]. "

What you should be doing is this:

"B changed, and A is subscribed, so queue an update about B for A."

"D changed, and A is subscribed, so queue an update about D for A."

... and a little later (e.g. milliseconds, not seconds or minutes)

"A has queued update messages about B and D - transmit them to A's client."

You're making the same mistake regarding detecting collisions. You shouldn't have every entity check for collisions against every other entity in isolation. Instead, you should run collision detection once across all entities, comparing each pair only once, and notify any pairs when collisions happen. (In a client/server game, that's probably a multi-step process, because you notify the server that a collision has happened, you resolve the collision, and then tell the clients what has happened as a result of that resolution).

1 hour ago, Kylotan said:

The problem is that you're polling for state changes instead of letting the subscription tell you about them, which is what pub/sub is for.

For example, instead of this:

"to get the environmental screen state changes for A, I need to iterate through collection = [A, B, C, D]. "

What you should be doing is this:

"B changed, and A is subscribed, so queue an update about B for A."

"D changed, and A is subscribed, so queue an update about D for A."

... and a little later (e.g. milliseconds, not seconds or minutes)

"A has queued update messages about B and D - transmit them to A's client."

 

You're making the same mistake regarding detecting collisions. You shouldn't have every entity check for collisions against every other entity in isolation. Instead, you should run collision detection once across all entities, comparing each pair only once, and notify any pairs when collisions happen. (In a client/server game, that's probably a multi-step process, because you notify the server that a collision has happened, you resolve the collision, and then tell the clients what has happened as a result of that resolution).

Thanks I try to understand how this works. But one thing I don't understand is that when B changes, how does B know who subscribes to itself? If B wants to queue an update for someone, it needs to iterate through a subscribers list to find that particular player right? If it works like this I still need to check each player in this list. And if A is subscribed for B and B is also subscribed for A, do I need to queue messages both ways?

Or maybe I totally misunderstood the way how pub/sub works. Is it more like a messaging system? So I will put every update message in a global queue and every player looks up this queue and find the message that he is interested in. I am using javascript so maybe that'll be easy to implement.

It's not really about "B knowing who is subscribed to itself", nor does B "want to queue an update" for anyone specific. It's about your server knowing which clients are subscribed to which entities. When your server changes entity B, it should have a list of clients interested in B, and can send or queue messages for those clients accordingly. Yes, it involves iterating through the list, but only a list of subscribers - i.e. clients you know need an update - not a list of everyone on the server, many of whom will not need this update.

Pub/sub is literally just where the subscriber says, "put me on the list, so when you publish something, I get a copy". In this case, the publisher is B, and it 'publishes' a state change, and all subscribers get sent this change.

@Kylotan Even though this looks easy, I am still confused with monitoring the updates. For example, on the server, at some interval, I iterate though the player list, and in each loop step I get update changes for current player and queue updates for its subscribers, and then I send out the updates to that client / current player. The updates I send to current player which is B in this case may not contain the updates other players that B subscribes to, if I iterate B at the beginning of the player list, because other players are not checked at the time. Then B may get the update info it subscribes to in next loop after some interval. The problem is, I can't keep this update info forever because a few frames later B may be in different position and see different players states on B's screen. So when should I clear the old update info and use the new update info? If I do this before I loop through the player list it may delete the update info that B may need to use in next loop.

Pseudo Code example:

if (currentTime >= nextUpdateTime) {

    // When to clear the update info for subscribers?

    for (const player of playerList) {

        Bstates = getPlayerStates(player);

      	someChanges = EventQueue[player.id].pop();
        
      	// Bstates doesn't contain player info B subscribes to if I iterate B before testing other players
		
      	Bstates.add(someChanges); // someChanges maybe empty?
      
      	sendUpdateTo(player, Bstates);
    }

    nextUpdateTime += interval;

}

I don't understand your code because I don't know what those variables represent. I'll explain the basic model that works for me and hopefully you can make sense of it.

When sending updates to B, what you want to send is any relevant messages that have been accumulated since last time you sent messages to B. Nothing more complicated than that.

If you're worried about messages not being sent quickly enough because entity C gets updated later in the loop than entity B, then just do all the updates in one loop and the sends in another loop. e.g.

for entity in world:
    change_message = entity.update()
    for each client in entity.subscribers:
        client.queue_outgoing_message(change_message) 
        
for client in connected_clients:
    if client.queued_outgoing_messages.length() > 0:
        client.transmit(client.queued_outgoing_messages)
        client.queued_outgoing_messages.empty()

There's no rule saying you have to handle everything in one single loop.

Also, in the general case, it is not correct to talk about entities and players and clients as if they're the same thing. In many games, you can talk this way because each player controls one client and that client controls one entity - but that doesn't hold true when you talk about NPCs (1 entity, no client, no player) or admin/spectator clients (1 player, 1 client, 0 entities), etc.

With this in mind, it makes even more sense to separate out your entity updates from your network sending loop. You could even run them at different rates if you liked. If you find that a client ends up with 2 updates for the same entity, you could drop the oldest one, but that's an optimisation, not an essential part of the logic. As long as the messages are transmitted in the right order then everything will be consistent.

48 minutes ago, Kylotan said:

I don't understand your code because I don't know what those variables represent. I'll explain the basic model that works for me and hopefully you can make sense of it.

When sending updates to B, what you want to send is any relevant messages that have been accumulated since last time you sent messages to B. Nothing more complicated than that.

If you're worried about messages not being sent quickly enough because entity C gets updated later in the loop than entity B, then just do all the updates in one loop and the sends in another loop. e.g.

for entity in world:
    change_message = entity.update()
    for each client in entity.subscribers:
        client.queue_outgoing_message(change_message) 
        
for client in connected_clients:
    if client.queued_outgoing_messages.length() > 0:
        client.transmit(client.queued_outgoing_messages)
        client.queued_outgoing_messages.empty()

There's no rule saying you have to handle everything in one single loop.

Also, in the general case, it is not correct to talk about entities and players and clients as if they're the same thing. In many games, you can talk this way because each player controls one client and that client controls one entity - but that doesn't hold true when you talk about NPCs (1 entity, no client, no player) or admin/spectator clients (1 player, 1 client, 0 entities), etc.

With this in mind, it makes even more sense to separate out your entity updates from your network sending loop. You could even run them at different rates if you liked. If you find that a client ends up with 2 updates for the same entity, you could drop the oldest one, but that's an optimisation, not an essential part of the logic. As long as the messages are transmitted in the right order then everything will be consistent.

Thanks now this finally makes sense for me.

In general, though, "players seeing players" is a n-squared problem. If all players are within view range of each other, then all players need to see all players, which requires N players state updates generated for N players.

In general, you'll want to cache what the actual state is on the server, rather than compute it when anyone wants to observe it. The simulation updates the actual values of each player -- this is just once per player. Then, the network-view iterates through each player, and sends the state for each player that player can see. There's no re-computation at that point, just packing a bunch of states into a packet, and then sending it.

For interest management (which is the formal name for the mechanism of "who can see what") you'll often end up needing a spatial index (quad tree, hash grid, etc) to efficiently figure out who can see what. Otherwise, each time any player moves, that player has to check ALL other players for which players are nearby or not. It's better to scan only a subset of players when you need to.

4 hours ago, hplus0603 said:

In general, though, "players seeing players" is a n-squared problem. If all players are within view range of each other, then all players need to see all players, which requires N players state updates generated for N players.

In general, you'll want to cache what the actual state is on the server, rather than compute it when anyone wants to observe it. The simulation updates the actual values of each player -- this is just once per player. Then, the network-view iterates through each player, and sends the state for each player that player can see. There's no re-computation at that point, just packing a bunch of states into a packet, and then sending it.

For interest management (which is the formal name for the mechanism of "who can see what") you'll often end up needing a spatial index (quad tree, hash grid, etc) to efficiently figure out who can see what. Otherwise, each time any player moves, that player has to check ALL other players for which players are nearby or not. It's better to scan only a subset of players when you need to.

 

Thanks for advice I am doing this already.

As an additional addendum ... It looks like you are doing good. 

12 hours ago, caymanbruce said:

Even though this looks easy, I am still confused with...

Trying to manage this type of relationship is complex, it has difficulty, and it is one of the more computer-sciency topics in game development.

Interest management is a tricky balancing act. There are many different factors that are competing, and each game makes different tradeoffs.  Exactly what to scan, what to process, what to transmit, when to scan, when to process, when to transmit, what to retain, what to prevent, ... balancing all the details make an enormous difference for online games.  

Many games make it look easy, the best games make it completely invisible to the player, but the developers either got extremely lucky or they invested enormous amounts of efforts to make the game work so well.

I think all of us with network game experience have been there and felt the pain. I don't have much more to add other than both commiseration and praise. It is hard work, and it takes effort to do well.  Find a good balance between immediate work, deferred work, and avoidable work, that's often a good starting point to help break down the problems.  Otherwise, high five or fist-bump or whatever kids are doing these days, because any progress in a networking project is good.