I am writing collision detection for a 2D top down game. But I am stuck on updating environmental information for each player.

Suppose I have 3 or 4 thousand static entities and a few hundreds moving players on the map. At each move of my player, he can only see a small part of the map on his screen.

Using brutal-force to iterate all the entities and moving players is a bad idea. And this is also true for sending all the information on the map from the server to a client. So I want the player to only receive the update of other entities/players that are on his screen, maybe within an area slightly bigger than his screen.

A small example goes like this. At time step N, the player sees 200 entities and a dozen other players, all other entities and players are unknown to him. I suppose not all information is needed to be sent over the network. At time step N + 10, the player may see other stuff including 50 more other entities and some updated information. Now maybe I should send the information of that 50 entities from the server to the player.

However, some entities may be destroyed even before the player sees it and will never show up again. In this situation, does the player need to know/receive status update of the entity at all? In the mean time, some new static entities may appear on the map, and I also don’t think the player should know the status of the entities that are outside of his screen.

I am thinking of using array or map to store this information, just to make it simple. Maybe one array to store the entity information on the screen area, and one array to store the new entity information that is about to show up on the screen area. But even in this way I am still sending duplicated information to the player because some entities or players may not update their status between two updates.

I have also learned about publish-subscribe pattern that can be used in this situation, but I don’t know how to implement it. An example for this would be very helpful. I might need to put a linked list to each player and store information that is needed to send out, delete the information previously sent but is not required to update, so maybe less memory space is required and probably less data to be sent when using this pattern.

Another problem is that I send out all the information of everything to the client at the initial state when the player joins. If I don’t maintain the information of all the static entities things may go wrong on the client side. So I also need some suggestion on how to begin the game when a player joins the game.

Where possible, send static data before play.

Where not possible, static entities and mobile entities can be handled exactly the same way; the only difference is that you don't need to send any state updates for static entities.

A player's area of interest moves around with the player and the server needs to watch which entities enter and leave it.

A very simple algorithm for this is as follows:

Periodic interest update:
    For each player:
        Find nearby entities of interest
        for each of the above entities:
            if it wasn't already in our subscribed list:
                add it to subscribed list
                queue a 'new entity' message for player
        for each entity on our subscribed list:
            if it isn't in the nearby entities list:
                remove it from our subscribed list
                queue a 'deleted entity' message for player

Each time an entity has a significant state change:
    for each player:
        if that player is subscribed to this entity:
            queue a 'updated entity' message for that player
            

Those are the basics. Note that it works fine in the special case of starting the game for the first time, as well as every subsequent update. You get bonus points for:

• Applying hysteresis so that entities right on the interest border don't create constant new/deleted/new/deleted oscillations
• Using an efficient structure so that you can find all players subscribed to an entity without iterating through all players
• Buffering or delaying frequent state changes so that you don't need to send as many messages, especially based on distance. This may include remembering what was last sent, and now recently. (e.g. Position updates)
• Making entities or subscriptions more granular so that you don't send irrelevant changes to clients that don't need them
• Growing the interest range over time so that messages for nearby entities get sent before more remote entities, and not all on frame/update #1

Where possible, send static data before play.

Where not possible, static entities and mobile entities can be handled exactly the same way; the only difference is that you don't need to send any state updates for static entities.

A player's area of interest moves around with the player and the server needs to watch which entities enter and leave it.

A very simple algorithm for this is as follows:

Periodic interest update:
    For each player:
        Find nearby entities of interest
        for each of the above entities:
            if it wasn't already in our subscribed list:
                add it to subscribed list
                queue a 'new entity' message for player
        for each entity on our subscribed list:
            if it isn't in the nearby entities list:
                remove it from our subscribed list
                queue a 'deleted entity' message for player

Each time an entity has a significant state change:
    for each player:
        if that player is subscribed to this entity:
            queue a 'updated entity' message for that player
            

Those are the basics. Note that it works fine in the special case of starting the game for the first time, as well as every subsequent update. You get bonus points for:

• Applying hysteresis so that entities right on the interest border don't create constant new/deleted/new/deleted oscillations
• Using an efficient structure so that you can find all players subscribed to an entity without iterating through all players
• Buffering or delaying frequent state changes so that you don't need to send as many messages, especially based on distance. This may include remembering what was last sent, and now recently. (e.g. Position updates)
• Making entities or subscriptions more granular so that you don't send irrelevant changes to clients that don't need them
• Growing the interest range over time so that messages for nearby entities get sent before more remote entities, and not all on frame/update #1

I have implemented a basic version of this but I don't see a great performance boost. In terms of the data structure of the subscribers, I am using Object Literal in javascript which is very similar to a map. I store the id as the key and the rest as the entity. I am not sure if this is good or bad for network traffic. And I only send state changes of those entities which actually change their state (like appear in the scene or removed). I am not sure how to buffer or delay frequent state changes, as I need state change quick enough for interpolation on client side. If the state change couldn't arrive in time wouldn't the client side become jitter?